An overall-regional competitive self-organizing map neural network for the Euclidean traveling salesman problem

摘要

The paper proposes a novel overall-regional competitive SOM (ORC-SOM) algorithm for solving symmetric Euclidean traveling salesman problems (TSPs). Two novel rules, overall and regional competition rules respectively, are introduced in the ORC-SOM. Overall competition is designed to make winning neuron and its neighborhood neurons less competitive for outlining the tour, and regional competition is.designed to make them more competitive for refining the tour, both compared with the standard SOM. An increasing radius with respect to iteration is designed for a smooth transition from more focus on outlining to more focus on refining the tour. Besides topology preservation property and convex-hull property, an additional significant property of an optimal tour for a complex TSP, referred to as infiltration property, is introduced, and the feasibility of the ORC-SOM algorithm on these properties are studied. Computational comparisons with typical SOM-based counterparts on two sets of benchmark TSP instances from TSPLIB demonstrate the superiority of the ORC-SOM in solution quality.