METHODS OF SOLVING THE TRAVELING SALESMAN PROBLEM BASED ON COMPUTATIONAL INTELLIGENCE
DOI:
https://doi.org/10.26906/SUNZ.2024.2.099Keywords:
traveling salesman problem, route, graph, genetic algorithm, crossover, mutation, selection, ant algorithm, artificial neural networks, Kohonen’s self-organizing mapAbstract
Topicality. Today, the traveling salesman's problem remains actual, as the need to find the shortest routes is currently found in many areas of human activity. With the development of technologies and the increase in the complexity of production processes and logistics, the requirements for accuracy and speed of search are increasing, which makes it necessary to choose appropriate methods for solving this problem. The goal of this work is to study the effectiveness of algorithms for solving the traveling salesman problem based on computational intelligence methods. The object of research is the process of finding the shortest route in large-dimensional TSP. The subject of research is route search algorithms for the traveling salesman problem using methods of computational intelligence, in particular, the analysis of the convergence of genetic algorithms when using different types of genetic operators. Results. This paper examines the features of the application of computational intelligence methods for solving the salesman's problem, which involves the use of variations of genetic algorithms, ant algorithms and artificial neural networks, in particular, Kohonen's self-organizing map. The obtained results of the performed experimental studies allow to draw conclusions about the advantages and disadvantages of individual algorithms. Conclusions. The proposed algorithm based on an artificial neural network has the highest speed, as well as the highest accuracy when problem graph contains approximately 1000 vertices. For problems with a smaller number of vertices, the genetic algorithm provides more accurate results.Downloads
References
Davendra D. (2010), “Travelling Salesman Problem, Theory and Applications”, InTech, P. 338, ISBN 978-953-307-426-9
Dahiya C., Sangwan S. (2018), “Literature Review on Travelling Salesman Problem”, International Journal of Research, Vol. 5(16), pp. 1152-1155, e-ISSN: 2348-6848, p-ISSN: 2348-795X
Toaza B, Esztergár-Kiss D. (2023), “A review of metaheuristic algorithms for solving TSP-based scheduling optimization problems”, Applied Soft Computing, Vol. 148, pp. 1-24, doi: https://doi.org/10.1016/j.asoc.2023.110908
Crişan G. C., Iantovics L. B., Nechita E. (2019), “Computational Intelligence for Solving Difficult Transportation Problems”, Procedia Computer Science, Vol. 159, pp. 172-181, doi: https://doi.org/10.1016/j.procs.2019.09.172
Eskandari S., Rafsanjani M. K. (2023), “Two new selection methods and their effects on the performance of genetic algorithm in solving supply chain and travelling salesman problems”, International Journal of Bio-Inspired Computation (IJBIC), Vol. 22(3), pp. 176-184, doi: https://doi.org/10.1504/IJBIC.2023.135464
Іващенко Г. С., Скляров А. С., Барковська О. Ю. (2023), “Гібридний метод рішення задачі маршрутизації транспорту з урахуванням додаткових обмежень”, Системи управління, навігації та зв’язку, №1, с. 75-79, doi: https://doi.org/10.26906/SUNZ.2023.1.075
Wang, Y., Han. Z. (2021), “Ant colony optimization for traveling salesman problem based on parameters optimization”, Applied Soft Computing, Vol. 107, pp. 1-11, doi: https://doi.org/10.1016/j.asoc.2021.107439
Zhang J., Feng X., Zhou B., Ren D. (2012), “An overall-regional competitive self-organizing map neural network for the Euclidean traveling salesman problem”, Neurocomputing, Vol. 89, pp. 1-11, doi: https://doi.org/10.1016/j.neucom.2011.11.024
Shafie M. F., Ahmad F., Osman M. K, Ismail A.P., Ahmad K. A., Yahaya S. Z. (2023), “Optimization of Saleman Travelling Problem Using Genetic Algorithm with Combination of Order and Random Crossover”, 2023 IEEE 13th International Conference on Control System, Computing and Engineering (ICCSCE), pp. 255-258, doi: https://doi.org/10.1109/ICCSCE58721.2023.10237137
Deep K., Mebrahtu H. (2012), “Variant of partially mapped crossover for the Travelling Salesman problems”, International Journal of Combinatorial Optimization Problems and Informatics, Vol. 3(1), pp. 47-69, ISSN: 2007-1558
OuYang Q., Xu H. (2015), “The study of comparisons of three crossover operators in genetic algorithm for solving single machine scheduling problem”, International Conference on Manufacturing Science and Engineering (ICMSE 2015), Atlantis Press, pp. 293-297, doi: https://doi.org/10.2991/icmse-15.2015.55
Kumar R., Memoria M., Thapliyal M., Kirola M., Ahmad I., Gupta A., Tyagi S., Ansari N. (2022), “Analyzing The Performance Of Crossover Operators (OX, OBX, PBX, MPX) To Solve Combinatorial Problems”, 2022 International Conference on Machine Learning, Big Data, Cloud and Parallel Computing (COM-IT-CON), pp. 817-821, doi: https://doi.org/10.1109/COM-IT-CON54601.2022.9850689
Singh D. R., Singh M. K., Singh T. (2016), “A Hybrid Algorithm with Modified Inver-Over Operator and Genetic Algorithm Search for Traveling Salesman Problem”, Advanced Computing and Communication Technologies, pp. 141-150, doi: https://doi.org/10.1007/978-981-10-1023-1_14
Chopard B., Tomassini M. (2018), “The Ant Colony Method”, An Introduction to Metaheuristics for Optimisation, pp. 81-96, doi: https://doi.org/10.1007/978-3-319-93073-2_5
Colorni A., Dorigo M., Maniezzo V. (1991), “Distributed Optimization by Ant Colonies”, Proceedings of ECAL91 – European Conference on Artificial Life, Elsevier Publishing, pp. 134-142
Dorigo M., Maniezzo V., Colorni A. (1996), “The Ant System: Optimization by a colony of cooperating agents”, IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), Vol. 26(1), pp. 29-41, doi: https://doi.org/10.1109/3477.484436
Yaloveha, V., Hlavcheva, D., Podorozhniak, A. and Kuchuk, H. (2019), “Fire hazard research of forest areas based on the use of convolutional and capsule neural networks”, 2019 IEEE 2nd Ukraine Conference on Electrical and Computer Engineering, UKRCON 2019 – Proceedings, DOI: http://dx.doi.org/10.1109/UKRCON.2019.8879867
Yaloveha, V., Hlavcheva, D. and Podorozhniak, A. (2019), “Usage of convolutional neural network for multispectral image processing applied to the problem of detecting fire hazardous forest areas”, Сучасні інформаційні системи, Vol. 3, No 1, pp. 116–120, DOI: https://doi.org/10.20998/2522-9052.2019.1.19
Datsenko, S., and Kuchuk, H. (2023), “Biometric authentication utilizing convolutional neural networks”, Advanced Information Systems, vol. 7, no. 2, pp. 67–73. Doi: https://doi.org/10.20998/2522-9052.2023.3.10
Yaloveha, V., Podorozhniak, A., Kuchuk, H. (2022), “Convolutional neural network hyperparameter optimization applied to land cover classification”, Radioelectronic and Computer Systems, No. 1(2022), pp. 115–128, DOI: https://doi.org/10.32620/reks.2022.1.09
Sarikyriakidis S., Goulianas K., Margaris A. I. (2023), “Using Self-organizing Maps to Solve the Travelling Salesman Problem: A Review”, WSEAS transactions on systems, Vol. 22, pp. 131-159, doi: https://doi.org/10.37394/23202.2023.22.14
Faigl J., Hollinger, G. A. (2018), “Autonomous Data Collection Using a Self-Organizing Map”, IEEE Transactions on Neural Networks and Learning Systems, Vol. 29(5), pp. 1703-1715, doi: https://doi.org/10.1109/TNNLS.2017.2678482
