The incorporation of an efficient initialization method and parameter adaptation using self-organizing maps to solve the TSP

摘要

This paper presents an approach to the well-known traveling salesman problem (TSP) using Kohonen self-organizing maps (SOM). We investigate these questions, ‘Does it converge to a feasible solution?’ ‘Is there a best adaptation law of parameters for the algorithm?’ ‘What is the effect of different sequencing of the nodes along the initial path?’ ‘How do we organize the index of winner neurons and the initial order of the cities?’ Despite many different types of SOM algorithm having already been approached to solve the TSP in the literature, the purpose of this paper is to look for the incorporation of an efficient initialization method and the definition of a parameter adaptation law to achieve better quality results and a faster convergence. Complexity of the modified SOM algorithm is analyzed. The results show an average deviation of 2.4372% from the optimal tour length for a set of 12 TSP instances. This result is better than an average deviation of 3.69% by using the same 12 TSP instances in the literature [C.V. Frederico, D.D.N. Adiao, A.F. Jose, An efficient approach to the traveling salesman problem using self-organizing maps, International Journal of Neural Systems 13(2) (2003) 59–66].