APPLICATION OF EVOLUTIONARY ALGORITHM IN TSP
Vikas Gupta
Abstract
The Traveling Salesman Problem (TSP) is a well-known NP-hard problem, meaning that there is no accurate solution for solving it in polynomial time. To solve the TSP, this work provides a novel variation application genetic algorithm methodology with a local search strategy. This article gives an overview of the literature on the Traveling Salesman Problem (TSP). The Genetic Algorithm is one of the most effective ways for solving NP-hard problems like TSP. To address challenges, genetic algorithms always leverage the natural evolution process. This study gives a critical assessment of genetic algorithm approaches presented by researchers for solving the TSP issue.
References
[1] Akshya, J., & Priyadarsini, P. L. K. (2021). Area Partitioning by Intelligent UAVs for effective path planning using Evolutionary algorithms. 2021 International Conference on Computer Communication and Informatics, ICCCI 2021. https://doi.org/10.1109/ICCCI50826.2021.9402352 [2] Al-Khatib, R. M., Al-Betar, M. A., Awadallah, M. A., Nahar, K. M. O., Abu Shquier, M. M., Manasrah, A. M., & Doumi, A. B. (2019). MGA-TSP: Modernised genetic algorithm for the travelling salesman problem. International Journal of Reasoning-Based Intelligent Systems, 11(3), 215–226. https://doi.org/10.1504/IJRIS.2019.102541 [3] Alharbi, S. T. (2018). A hybrid genetic algorithm with tabu search for optimization of the traveling thief problem. International Journal of Advanced Computer Science and Applications, 9(11), 276–287. https://doi.org/10.14569/ijacsa.2018.091138 [4] Allaoua, H. (2017). Combination of Genetic Algorithm with Dynamic Programming for solving TSP. International Journal of Advances in Soft Computing and Its Applications, 9(2), 31–44. https://www-scopus-com- uttaranchaluniversity.knimbus.com/inward/record.uri?eid=2-s2.0- 85025135763&partnerID=40&md5=d44dbb0c0bd4378b49d4ea4c7dee32de [5] Bo, R., Huang, H., & Wu, W. (2005). Application of ant algorithm to scheme solving for conceptual design. Hsi-An Chiao Tung Ta Hsueh/Journal of Xi’an Jiaotong University, 39(11), 1236–1240. https://www-scopus-com- uttaranchaluniversity.knimbus.com/inward/record.uri?eid=2-s2.0- 29144487378&partnerID=40&md5=1024753be28f7c250c65e70c76fd6d50 [6] Cai, Z., Peng, J., Gao, W., Wei, W., & Kang, L. (2004). A novel Evolutionary Algorithm and its application for the traveling salesman problem. Proceedings of the World Congress on Intelligent Control and Automation (WCICA), 3, 2253–2257. https://www-scopus-com-uttaranchaluniversity.knimbus.com/inward/record.uri?eid=2-s2.0- 4444258929&partnerID=40&md5=cdaeae872f41de28b0d7898ba08cf874 [7] De França, F. O., Gomes, L. C. T., De Castro, L. N., & Von...