Chinese Journal of Computers   Full Text
Title	Self Organizing Map with Generalized and Localized Parallel Competitions for the TSP
Authors	ZHANG Jun-Ying ZHOU Bin
Address	(School of Computer Science and Engineering, Xidian University, Xi’an 710071)
Year	2008
Issue	No.2(220—227)
Abstract &   Background	Abstract As one of the most typical NP-complete combinational optimization problems, TSP (Traveling Salesman Problem), which has a diversity of applications in real world, has attracted extensive research interest. Recently, Self-Organizing Map(SOM) based approaches to this problem has been paid great attention for its simplicity and novelty. By analyzing drawbacks of standard SOM algorithm for solving TSP problem, it was found that the standard SOM has a great potential for finding overall optimal solution rather than globally optimal solution for a TSP problem. Based on this, the paper proposes a new SOM algorithm for solving TSP problem, the infiltrative SOM(ISOM), by introducing two new learning schemes, competition generalization and local infiltration. By the collaboration of the two learning schemes in that both the schemes work together in the whole learning process and initial learning focuses more on overall optimization, which is conducted by the competition generalization, while the afterward learning focuses more on local optimization, which is conducted by the local infiltration, the near-optimal solution is much more easy to be found. Experiments on public TSPLIB data show that not only the quality of the solutions is higher, but also the solutions are more robust, by the proposed method compared with those by several typical SOM-based methods such as the KNIES algorithms, the SETSP, the SOM developed by Budinich, and the ESOM. keywords traveling salesman problem; combinational optimization; self-organizing map; global optimization; overall optimization; local optimization background Traveling salesman problem (TSP) is one of the most typical NP-hard combinatorial optimization problems, which has various applications in diversity of fields. Developing algorithms for solving such TSPs, especially large scale TSPs, is of a great significance in both theory and applications. From the notice that solving this problem is of great difficulty, brings great challenges, and possesses much potential in theory, methods and algorithms, it is seen that (a) it is extremely difficult and even impossible for developing an algorithm for finding the globally optimal solution of a large scale TSP problem in an acceptable time and space; (b) the overall optimal solution rather than the globally optimal solution of a TSP can be found with standard self-organizing map (SOM) neural network. Hence, based on the fact of standard SOM for searching for overall optimal solution of a TSP, in this paper, two learning schemes are introduced and embedded into the SOM algorithm, competition generalization and local infiltration. By the collaboration of the two learning schemes in that both the schemes work together in the whole learning process and initial learning focuses more on overall optimization, which is conducted by the competition generalization, while the afterward learning focuses more on local optimization, which is conducted by the local infiltration, the near-optimal solution is much more easy to be found compared with many other SOM-based methods. Experiments on public TSPLIB data show that not only the quality of the solutions is higher, but also the solutions are more robust, by the proposed method compared with those by several typical SOM-based methods such as the KNIES algorithms, the SETSP, the SOM developed by Budinich, and the ESOM. The research group has been working on combinatorial optimization problems for many years. They have published more than 50 papers in recent three years, in Science in China, Progress in Natural Science, Chinese Journal of Computers, Acta Physica Sinica, System Engineering and Electronics, Digital Signal Processing, Chinese Journal of Electronics, etc. and we get the second order Scientific Research Award of Shaanxi Province Goverment. Their work was and is being supported by the Chinese National Science Foundation under grant Nos.60574039, 97946223, 69971018, 60071026 and by the Sino-Italy Joint Foundation under grand No.200625617.