An efficient self-organizing map designed by genetic algorithms for the traveling salesman problem

Huidong JIN, Kwong Sak LEUNG, Man Leung WONG, Zong Ben XU

Research output: Journal PublicationsJournal Article (refereed)Researchpeer-review

53 Citations (Scopus)

Abstract

As a typical combinatorial optimization problem, the traveling salesman problem (TSP) has attracted extensive research interest. In this paper, we develop a self-organizing map (SOM) with a novel learning rule. It is called the integrated SOM (ISOM) since its learning rule integrates the three learning mechanisms in the SOM literature. Within a single learning step, the excited neuron is first dragged toward the input city, then pushed to the convex hull of the TSP, and finally drawn toward the middle point of its two neighboring neurons. A genetic algorithm is successfully specified to determine the elaborate coordination among the three learning mechanisms as well as the suitable parameter setting. The evolved ISOM (eISOM) is examined on three sets of TSPs to demonstrate its power and efficiency. The computation complexity of the eISOM is quadratic, which is comparable to other SOM-like neural networks. Moreover, the eISOM can generate more accurate solutions than several typical approaches for TSPs including the SOM developed by Budinich, the expanding SOM, the convex elastic net, and the FLEXMAP algorithm. Though its solution accuracy is not yet comparable to some sophisticated heuristics, the eISOM is one of the most accurate neural networks for the TSP.
Original languageEnglish
Pages (from-to)877-888
Number of pages12
JournalIEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics
Volume33
Issue number6
DOIs
Publication statusPublished - 1 Dec 2003

Fingerprint

Traveling salesman problem
Self organizing maps
Genetic algorithms
Neurons
Neural networks
Combinatorial optimization

Keywords

  • Convex hull
  • Genetic algorithms
  • Neural networks
  • Neural-evolutionary system
  • Self-organizing map
  • Traveling salesman problem

Cite this

@article{1d30b16ace2d4b2e97d7193c219a089b,
title = "An efficient self-organizing map designed by genetic algorithms for the traveling salesman problem",
abstract = "As a typical combinatorial optimization problem, the traveling salesman problem (TSP) has attracted extensive research interest. In this paper, we develop a self-organizing map (SOM) with a novel learning rule. It is called the integrated SOM (ISOM) since its learning rule integrates the three learning mechanisms in the SOM literature. Within a single learning step, the excited neuron is first dragged toward the input city, then pushed to the convex hull of the TSP, and finally drawn toward the middle point of its two neighboring neurons. A genetic algorithm is successfully specified to determine the elaborate coordination among the three learning mechanisms as well as the suitable parameter setting. The evolved ISOM (eISOM) is examined on three sets of TSPs to demonstrate its power and efficiency. The computation complexity of the eISOM is quadratic, which is comparable to other SOM-like neural networks. Moreover, the eISOM can generate more accurate solutions than several typical approaches for TSPs including the SOM developed by Budinich, the expanding SOM, the convex elastic net, and the FLEXMAP algorithm. Though its solution accuracy is not yet comparable to some sophisticated heuristics, the eISOM is one of the most accurate neural networks for the TSP.",
keywords = "Convex hull, Genetic algorithms, Neural networks, Neural-evolutionary system, Self-organizing map, Traveling salesman problem",
author = "Huidong JIN and LEUNG, {Kwong Sak} and WONG, {Man Leung} and XU, {Zong Ben}",
year = "2003",
month = "12",
day = "1",
doi = "10.1109/TSMCB.2002.804367",
language = "English",
volume = "33",
pages = "877--888",
journal = "IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics",
issn = "1083-4419",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "6",

}

An efficient self-organizing map designed by genetic algorithms for the traveling salesman problem. / JIN, Huidong; LEUNG, Kwong Sak; WONG, Man Leung; XU, Zong Ben.

In: IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, Vol. 33, No. 6, 01.12.2003, p. 877-888.

Research output: Journal PublicationsJournal Article (refereed)Researchpeer-review

TY - JOUR

T1 - An efficient self-organizing map designed by genetic algorithms for the traveling salesman problem

AU - JIN, Huidong

AU - LEUNG, Kwong Sak

AU - WONG, Man Leung

AU - XU, Zong Ben

PY - 2003/12/1

Y1 - 2003/12/1

N2 - As a typical combinatorial optimization problem, the traveling salesman problem (TSP) has attracted extensive research interest. In this paper, we develop a self-organizing map (SOM) with a novel learning rule. It is called the integrated SOM (ISOM) since its learning rule integrates the three learning mechanisms in the SOM literature. Within a single learning step, the excited neuron is first dragged toward the input city, then pushed to the convex hull of the TSP, and finally drawn toward the middle point of its two neighboring neurons. A genetic algorithm is successfully specified to determine the elaborate coordination among the three learning mechanisms as well as the suitable parameter setting. The evolved ISOM (eISOM) is examined on three sets of TSPs to demonstrate its power and efficiency. The computation complexity of the eISOM is quadratic, which is comparable to other SOM-like neural networks. Moreover, the eISOM can generate more accurate solutions than several typical approaches for TSPs including the SOM developed by Budinich, the expanding SOM, the convex elastic net, and the FLEXMAP algorithm. Though its solution accuracy is not yet comparable to some sophisticated heuristics, the eISOM is one of the most accurate neural networks for the TSP.

AB - As a typical combinatorial optimization problem, the traveling salesman problem (TSP) has attracted extensive research interest. In this paper, we develop a self-organizing map (SOM) with a novel learning rule. It is called the integrated SOM (ISOM) since its learning rule integrates the three learning mechanisms in the SOM literature. Within a single learning step, the excited neuron is first dragged toward the input city, then pushed to the convex hull of the TSP, and finally drawn toward the middle point of its two neighboring neurons. A genetic algorithm is successfully specified to determine the elaborate coordination among the three learning mechanisms as well as the suitable parameter setting. The evolved ISOM (eISOM) is examined on three sets of TSPs to demonstrate its power and efficiency. The computation complexity of the eISOM is quadratic, which is comparable to other SOM-like neural networks. Moreover, the eISOM can generate more accurate solutions than several typical approaches for TSPs including the SOM developed by Budinich, the expanding SOM, the convex elastic net, and the FLEXMAP algorithm. Though its solution accuracy is not yet comparable to some sophisticated heuristics, the eISOM is one of the most accurate neural networks for the TSP.

KW - Convex hull

KW - Genetic algorithms

KW - Neural networks

KW - Neural-evolutionary system

KW - Self-organizing map

KW - Traveling salesman problem

UR - http://commons.ln.edu.hk/sw_master/2447

U2 - 10.1109/TSMCB.2002.804367

DO - 10.1109/TSMCB.2002.804367

M3 - Journal Article (refereed)

VL - 33

SP - 877

EP - 888

JO - IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics

JF - IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics

SN - 1083-4419

IS - 6

ER -