Skip to main content
Article
An efficient self-organizing map designed by genetic algorithms for the traveling salesman problem
IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics
  • Huidong JIN, Chinese University of Hong Kong
  • Kwong Sak LEUNG, Chinese University of Hong Kong
  • Man Leung WONG, Lingnan University, Hong Kong
  • Zong Ben XU, Xi'an Jiaotong University, China
Document Type
Journal article
Publication Date
12-1-2003
Keywords
  • Convex hull,
  • Genetic algorithms,
  • Neural networks,
  • Neural-evolutionary system,
  • Self-organizing map,
  • Traveling salesman problem
Disciplines
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.
DOI
10.1109/TSMCB.2002.804367
E-ISSN
21682275
Publisher Statement

Copyright © 2003 Institute of Electrical and Electronics Engineers

Access to external full text or publisher's version may require subscription.

Full-text Version
Publisher’s Version
Citation Information
Jin, H.-D., Leung, K.-S., Wong, M.-L., & Xu, Z.-B. (2003). An efficient self-organizing map designed by genetic algorithms for the traveling salesman problem. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 33(6), 877-888. doi: 10.1109/TSMCB.2002.804367