An expanding self-organizing neural network for the traveling salesman problem

Abstract

The self-organizing map (SOM) has been successfully employed to handle the Euclidean traveling salesman problem (TSP). By incorporating its neighborhood preserving property and the convex-hull property of the TSP, we introduce a new SOM-like neural network, called the expanding SOM (ESOM). In each learning iteration, the ESOM draws the excited neurons close to the input city, and in the meantime pushes them towards the convex-hull of cities cooperatively. The ESOM may acquire the neighborhood preserving property and the convex-hull property of the TSP, and hence it can yield near-optimal solutions. Its feasibility is analyzed theoretically and empirically. A series of experiments are conducted on both synthetic and benchmark TSPs, whose sizes range from 50 to 2400 cities. Experimental results demonstrate the superiority of the ESOM over several typical SOMs such as the SOM developed by Budinich, the convex elastic net, and the KNIES algorithms. Though its solution accuracy is not yet comparable to some other sophisticated heuristics, the ESOM is one of the most accurate neural networks for the TSP in the literature. © 2003 Elsevier B.V. All rights reserved.