Enhanced Self-Organizing Map Solution for the Traveling Salesman Problem

• Joao P. A. Dantas FAB
• Andre N. Costa FAB
• Marcos R. O. A. Maximo ITA
• Takashi Yoneyama ITA

DOI: https://doi.org/10.5753/eniac.2021.18428

Abstract

Using an enhanced Self-Organizing Map method, we provided suboptimal solutions to the Traveling Salesman Problem. Besides, we employed hyperparameter tuning to identify the most critical features in the algorithm. All improvements in the benchmark work brought consistent results and may inspire future efforts to improve this algorithm and apply it to different problems.

Keywords: Self-organizing maps, TSP problem, Machine Learning

References

Brocki, Ł. and Korzinek, D. (2007). Kohonen self-organizing map for the traveling salesperson problem. In Recent Advances in Mechatronics, pages 116–119. Springer.

Budinich, M. (1996). A self-organizing neural network for the traveling salesman problem that is competitive with simulated annealing. Neural Computation, 8(2):416–424.

Calado, F. M. and Ladeira, A. P. (2011). Problema do caixeiro viajante: Um estudo comparativo de técnicas de inteligência artificial. e-xacta, 4(1).

Favata, F. and Walker, R. (1991). A study of the application of kohonen-type neural networks to the travelling salesman problem. Biological Cybernetics, 64(6):463–468.

Hopfield, J. and Tank, D. (1985). Neural computation solutions for tsp applications. Biological Cybernetics, 52:141–152.

Huang, L., Wang, G.-c., Bai, T., and Wang, Z. (2017). An improved fruit fly optimization algorithm for solving traveling salesman problem. Frontiers of Information Technology & Electronic Engineering, 18(10):1525–1533.

Kohonen, T. (1998). The self-organizing map. Neurocomputing, 21(1-3):1–6.

Laporte, G. (1992). The traveling salesman problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(2):231–247.

Markovic, D., Madic, M., Tomic, V., and Stojkovic, S. (2012). Solving travelling salesman problem by use of kohonen self-organizing maps. Acta Technica Corviniensis- Bulletin of Engineering, 5(4):21.

Martin, D. (2018). Solving the traveling salesman problem using self-organizing maps. https://github.com/DiegoVicen/som-tsp.

Mele, U. J., Gambardella, L. M., and Montemanni, R. (2021). A new constructive heuristic driven by machine learning for the traveling salesman problem. Algorithms, 14(9):267.

Peterson, C. (1990). Parallel distributed approaches to combinatorial optimization: benchmark studies on traveling salesman problem. Neural computation, 2(3):261–269.

Xu, X., Jia, Z., Ma, J., and Wang, J. (2008). A self-organizing map algorithm for the traveling salesman problem. In 2008 Fourth International Conference on Natural Computation, volume 3, pages 431–435. IEEE.

Zhang, D., Wang, J., and Zhao, X. (2015). Estimating the uncertainty of average f1 scores. In Proceedings of the 2015 International Conference on The Theory of Information Retrieval, pages 317–320.