Enhanced Self-Organizing Map Solution for the Traveling Salesman Problem
Resumo
Usando um método aprimorado de Mapa Auto-Organizável, fornecemos soluções abaixo do ideal para o Problema do Caixeiro Viajante. Além disso, empregamos o ajuste de hiperparâmetros para identificar os recursos mais críticos do algoritmo. Todas as melhorias no trabalho de benchmark trouxeram resultados consistentes e podem inspirar esforços futuros para melhorar este algoritmo e aplicá-lo a diferentes problemas.
Palavras-chave:
Self-organizing maps, TSP problem, Machine Learning
Referências
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.
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.
Publicado
29/11/2021
Como Citar
DANTAS, Joao P. A.; COSTA, Andre N.; MAXIMO, Marcos R. O. A.; YONEYAMA, Takashi.
Enhanced Self-Organizing Map Solution for the Traveling Salesman Problem. In: ENCONTRO NACIONAL DE INTELIGÊNCIA ARTIFICIAL E COMPUTACIONAL (ENIAC), 18. , 2021, Evento Online.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2021
.
p. 799-802.
ISSN 2763-9061.
DOI: https://doi.org/10.5753/eniac.2021.18428.
