Population-Based Algorithm for Solving the Traveling Salesman Problem
Abstract
This article covers the population-based hybrid algorithm for solving the traveling salesman problem. The algorithm is built on two algorithms: the genetic algorithm and the particle swarm algorithm. Hybridization was performed using high level hybridization. This article presents a detailed problem statement of the traveling salesman problem. The traveling salesman problem belongs to the class of NP-complete combinatorial optimization problems. There are arguments in favor of heuristic algorithms for this problem – the traveling salesman problem is considered to be NP-hard, and existence of an algorithm that could solve it in polynomial time is not proven, even more it is not known whether there is a heuristic algorithm that will guarantee accuracy of its solution (this question is still open). In addition, the traveling salesman problem is classified as a transcomputational problem – if the number of cities is more than 66, it is necessary to process more than 1093 bits of information in order to find the exact solution using the exhaustive search. Therefore, effective approximate methods of solving this problem are very important. Further in the article, population-based hybrid algorithm is formulated in a form of a step-by-step structure with detailing the steps of the algorithm. Then a block diagram of the formulated algorithm is presented. In addition, the article presents the results of the program, the developed user interface with the ability to adjust various parameters of the algorithm, which allows us to change the performance of the algorithm. The last part of the article devoted to: comparative efficiency analysis of the formulated algorithm, comparison of the developed population-based hybrid algorithm with the nearest neighbor algorithm and the ant colony algorithm.
References
2. Karpenko A.P. Sovremennye algoritmy poiskovoj optimizacii. Algoritmy, vdohnovlennye prirodoj [Modern search optimization algorithms. Nature-inspired algorithms]. BMSTU, Moscow; 2014. 448 p. (In Russ.)
3. Gladkov L.A., Kureychik V.V., Kureychik V.M. Geneticheskie algoritmy [Genetic Algorithms]. PhysMathLit, Moscow; 2010. 317 p. (In Russ.)
4. Mudrov V.I. Zadacha o kommivojazhere [The traveling salesman problem]. Znanie, Moscow; 1969. 62 p. (In Russ.)
5. Antukh A.E., Karpenko A.P. Global optimization based on methods of particle swarm, mind evolution and clonal selection. Science and Education of Bauman MSTU. 2012; (8):379-416. (In Russ., abstract in Eng.) DOI: https://doi.org/10.7463/0812.0431723
6. del Valle Y., Venayagamoorthy G.K., Mohagheghi S., Hernandez J. -C., Harley R.G. Particle Swarm Optimization: Basic Concepts, Variants and Applications in Power Systems. IEEE Transactions on Evolutionary Computation. 2008; 12(2):171-195. (In Eng.) DOI: https://doi.org/10.1109/TEVC.2007.896686
7. Domínguez J.S.H., Pulido G.T. A comparison on the search of particle swarm optimization and differential evolution on multi-objective optimization. 2011 IEEE Congress of Evolutionary Computation (CEC). IEEE Pres, New Orleans, LA, USA; 2011. p. 1978-1985. (In Eng.) DOI: https://doi.org/10.1109/CEC.2011.5949858
8. Niknam T., Amiri B. An efficient hybrid approach based on PSO, ACO and k-means for cluster analysis. Applied Soft Computing. 2010; 10(1):183-197. (In Eng.) DOI: https://doi.org/10.1016/j.asoc.2009.07.001
9. Ritscher T., Helwig S., Wanka R. Design and experimental evaluation of multiple adaptation layers in self-optimizing particle swarm optimization. IEEE Congress on Evolutionary Computation. IEEE Press, Barcelona, Spain; 2010. p. 1-8. (In Eng.) DOI: https://doi.org/10.1109/CEC.2010.5586255
10. Shi Y., Eberhart R. A modified particle swarm optimizer. 1998 IEEE International Conference on Evolutionary Computation Proceedings. IEEE World Congress on Computational Intelligence (Cat. No.98TH8360). IEEE Press, Anchorage, AK, USA; 1998. p. 69-73. (In Eng.) DOI: https://doi.org/10.1109/ICEC.1998.699146
11. Simon D. Evolutionary Optimization Algorithms. John Wiley & Sons, Inc.; 2013. 784 p. (In Eng.)
12. Kureychik V.V., Bova V.V., Kureychik V.V. Bioinspired algorithm for design and optimization problems. In: Ed. by E. L. Gloriozov. Proceedings of the International Conference on Information technologies in science, education and management. Gurzuf; 2015. p. 427-432. Available at: https://www.elibrary.ru/item.asp?id=23519161 (accessed 13.04.2021). (In Russ., abstract in Eng.)
13. Kureychik V.V., Kureychik L.V. Summary of some hybrid approach to solving combinatorically logical tasks on graphs. Proceedings of the International Scientific and Technical Congress on Intelligent Systems and Information Technologies ‒ 2020 (IS&IT-2020). Publ. house of Stupin S.A., Divnomorskoye; 2020. p. 102-108. Available at: https://www.elibrary.ru/item.asp?id=45435484 (accessed 11.04.2021). (In Russ., abstract in Eng.)
14. Kureychik V.V., Kursitys I.O., Kuliev E.V., Gerasimenko E.M. Application of bioinspired algorithms for solving transcomputational tasks. Journal of Physics: Conference Series. 2020; 1703:012021. (In Eng.) DOI: https://doi.org/10.1088/1742-6596/1703/1/012021
15. Kureychik V., Zaruba D., Kureychik V. Hybrid Approach for Graph Partitioning. In: Ed. by R. Silhavy et al. Artificial Intelligence Trends in Intelligent Systems. CSOC 2017. Advances in Intelligent Systems and Computing. 2017; 573:64-73. Springer, Cham. (In Eng.) DOI: https://doi.org/10.1007/978-3-319-57261-1_7
16. Su F., Kong L., Wang H., Wen Z. Modeling and application for rolling scheduling problem based on TSP. Applied Mathematics and Computation. 2021; 407:126333. (In Eng.) DOI: https://doi.org/10.1016/j.amc.2021.126333
17. Zhang J., Hong L., Liu Q. An Improved Whale Optimization Algorithm for the Traveling Salesman Problem. Symmetry. 2021; 13(1):48. (In Eng.) DOI: https://doi.org/10.3390/sym13010048
18. Krishna M.M., Panda N., Majhi S.K. Solving traveling salesman problem using hybridization of rider optimization and spotted hyena optimization algorithm. Expert Systems with Applications. 2021; 183:115353. (In Eng.) DOI: https://doi.org/10.1016/j.eswa.2021.115353
19. Garn W. Balanced dynamic multiple travelling salesmen: Algorithms and continuous approximations. Computers & Operations Research. 2021; 136:105509. (In Eng.) DOI: https://doi.org/10.1016/j.cor.2021.105509
20. Oliveira S.M., Hussin M.S., Stuetzle T., Roli A., Dorigo M. A detailed analysis of the population-based ant colony optimization algorithm for the TSP and the QAP. Proceedings of the 13th annual conference companion on Genetic and evolutionary computation (GECCO'11). Association for Computing Machinery, New York, NY, USA; 2011. p. 13-14. (In Eng.) DOI: https://doi.org/10.1145/2001858.2001866
21. Nagata Y. High-Order Entropy-Based Population Diversity Measures in the Traveling Salesman Problem. Evolutionary Computation. 2020; 28(4):595-619. (In Eng.) DOI: https://doi.org/10.1162/evco_a_00268
22. Pop P., Matei O., Pintea C. A two-level diploid genetic based algorithm for solving the family traveling salesman problem. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'18). Association for Computing Machinery, New York, NY, USA; 2018. p. 340-346. (In Eng.) DOI: https://doi.org/10.1145/3205455.3205545
23. Bernardino R., Paias A. Solving the family traveling salesman problem. European Journal of Operational Research. 2018; 267(2):453-466. (In Eng.) DOI: https://doi.org/10.1016/j.ejor.2017.11.063
24. Cacchiani V., Muritiba A.E.F., Negreiros M., Toth P. A multistart heuristic for the equality generalized traveling salesman problem. Networks. 2011; 57(3):231-239. (In Eng.) DOI: https://doi.org/10.1002/net.20421
25. Morán-Mirabal L.F., González-Velarde J.L., Resende M.G.C. Randomized heuristics for the family traveling salesperson problem. International Transactions in Operational Research. 2014; 21(1):41-57. (In Eng.) DOI: https://doi.org/10.1111/itor.12026
This work is licensed under a Creative Commons Attribution 4.0 International License.
Publication policy of the journal is based on traditional ethical principles of the Russian scientific periodicals and is built in terms of ethical norms of editors and publishers work stated in Code of Conduct and Best Practice Guidelines for Journal Editors and Code of Conduct for Journal Publishers, developed by the Committee on Publication Ethics (COPE). In the course of publishing editorial board of the journal is led by international rules for copyright protection, statutory regulations of the Russian Federation as well as international standards of publishing.
Authors publishing articles in this journal agree to the following: They retain copyright and grant the journal right of first publication of the work, which is automatically licensed under the Creative Commons Attribution License (CC BY license). Users can use, reuse and build upon the material published in this journal provided that such uses are fully attributed.
