A New Hybrid Genetic Algorithm Proposal with Sequential Local Search for Traveling Salesman Problem

Abstract

The Traveling Salesman Problem, which forms the basis of many routing problems, has a classical mathematical model in the field of optimization. The problem is often solved with the help of heuristic algorithms due to the difficulty of finding the best solution with classical methods. Genetic Algorithm, which is the most widely used heuristic algorithms, can produce effective solutions to the problem. Within the scope of the study, the problem is addressed with Genetic Algorithm hybridized with different types of local search approaches. In the Genetic Algorithm with the sequential local search approach proposed in the study, 3-opt local search approach was used after applying combination of swapping, inversion and insertion, which are neighborhood generating functions in local search. Considering the solution values obtained from the algorithms, it is seen that the proposed approach with sequential local search has a higher success than the others.

Keywords

• Traveling Salesman Problem
• Genetic Algorithm
• Local Search

GEZGİN SATICI PROBLEMİ İÇİN ARDIŞIK YEREL ARAMA İLE YENİ BİR HİBRİT GENETİK ALGORİTMA ÖNERİSİ

Abstract

Birçok rotalama probleminin temelini oluşturan Gezgin Satıcı Problemi, optimizasyon alanında klasikleşmiş bir matematiksel modele sahiptir. Problem klasik yöntemlerle en iyi çözümün bulunmasının zorluğu sebebiyle sıklıkla sezgisel algoritmalar yardımıyla çözülmektedir. Sezgisel algoritmalardan en yaygın kullanıma sahip Genetik Algoritma ile problemde etkili çözümler üretilebilmektedir. Çalışma kapsamında, farklı tipte yerel arama yaklaşımlarıyla hibritleştirilmiş Genetik Algoritma ile problem ele alınmıştır. Çalışmada önerilen, ardışık yerel arama yaklaşımına sahip Genetik Algoritma’da, yerel aramada komşuluk üreten fonksiyonlar olan, yer değiştirme, tersine döndürme ve araya sokmanın birlikte kullanımından sonra 3-opt yerel arama yaklaşımı kullanılmıştır. Algoritmalardan elde edilen çözüm değerlerine bakıldığında önerilen ardışık yerel aramaya sahip yaklaşımın diğerlerine göre daha yüksek başarıma sahip olduğu görülmüştür.

Keywords

• Gezgin Satıcı Problemi
• Genetik Algoritma
• Yerel Arama

References

1. Ali, I. M., Essam, D., & Kasmarik, K. (2020). A novel design of differential evolution for solving discrete traveling salesman problems. Swarm and Evolutionary Computation, 52, 100607.
2. Basu, S., & Ghosh, D. (2008). A review of the tabu search literature on traveling salesman problems. IIMA Working Papers 2008. Indian Institute of Management Ahmedabad, 2008, 1-16.
3. Bouzidi, A., & Riffi, M. E. (2013). Discrete cat swarm optimization to resolve the traveling salesman problem. International Journal of Advanced Research in Computer Science and Software Engineering 3(9): 13-18.
4. Bouzidi, M., & Riffi, M. E. (2014). Adaptation Of The Harmony Search Algorithm To Solve The Travelling Salesman Problem. Journal of Theoretical & Applied Information Technology, 62(1): 157-160.
5. Brady, R.M. (1985). Optimization Strategies Gleaned from Biological Evolution. Nature 317: 804–806
6. Chang, P. C., Huang, W. H., & Ting, C. J. (2010). Dynamic diversity control in genetic algorithm for mining unsearched solution space in TSP problems. Expert systems with applications, 37(3), 1863-1878.
7. Chen, Y., Jia, Z., Ai, X., Yang, D., & Yu, J. (2017). A modified two-part wolf pack search algorithm for the multiple traveling salesmen problem. Applied Soft Computing, 61, 714-725.
8. Dantzig, G., Fulkerson, R., & Johnson, S. (1954). Solution of a large-scale traveling-salesman problem. Journal of the operations research society of America, 2(4), 393-410.

9. Daoqing, Z., & Mingyan, J. (2020). Parallel discrete lion swarm optimization algorithm for solving traveling salesman problem. Journal of Systems Engineering and Electronics, 31(4), 751-760.
10. Davis, L. (1985). Applying Adaptive Algorithms to Epistatic Domains. Proceedings of the International Joint Conference on Artificial Intelligence, 162–164.
11. Demirtaş, Y. E., & Keskintürk, T. (2011). Kanguru Algoritması Ve Gezgin Satıcı Problemine Uygulanması. İstanbul Ticaret Üniversitesi Fen Bilimleri Dergisi, 10(19), 51-63.
12. Deng, Y., Liu, Y., & Zhou, D. (2015). An improved genetic algorithm with initial population strategy for symmetric TSP. Mathematical Problems in Engineering, 2015: 1-6.
13. Dorigo, M. (1992). Optimization, learning and natural algorithms. PhD. Thesis, Politecnico di Milano, Italy.
14. Fiechter, C. N. (1994). A parallel tabu search algorithm for large traveling salesman problems. Discrete Applied Mathematics, 51(3), 243-267.
15. Freisleben, B., & Merz, P. (1996). A genetic local search algorithm for solving symmetric and asymmetric traveling salesman problems. In Proceedings of IEEE international conference on evolutionary computation (pp. 616-621). IEEE.
16. Gazda, M., TSP algorithms: 2-opt, 3-opt in python. http://matejgazda.com/ (Erişim: 15 Kasım 2020).
17. Gupta, R., Shrivastava, N., Jain, M., Singh, V., & Rani, A. (2018). Greedy WOA for Travelling Salesman Problem. In International Conference on Advances in Computing and Data Sciences (pp. 321-330). Springer, Singapore.
18. Gülcü, Ş., Mahi, M., Baykan, Ö. K., & Kodaz, H. (2018). A parallel cooperative hybrid method based on ant colony optimization and 3-Opt algorithm for solving traveling salesman problem. Soft Computing, 22(5), 1669-1685.
19. Holland, J. H. (1975). Adaptation in natural and artificial systems. Ann Arbor: University of Michigan Press.
20. Jahed, A., & Rahbari, M. (2017). Comparison of Three Neighbor Generation Structures by Simulated Annealing Method to Solve Quadratic Assignment Problem. 10th International Conference of Iranian Operations Research Society (ICIORS 2017), University of Mazandaran, May 2017, Babolsar, Iran. ffhal-01962309f
21. Jati, G. K. (2011). Evolutionary discrete firefly algorithm for travelling salesman problem. In International Conference on Adaptive and Intelligent Systems (pp. 393-403). Springer, Berlin, Heidelberg.
22. Johnson DS, & McGeoch LA. (1997) The traveling salesman problem: a case study in local optimization. Local Search in Combinatorial Optimization. 1: 215–310
23. Juneja, S. S., Saraswat, P., Singh, K., Sharma, J., Majumdar, R., & Chowdhary, S. (2019). Travelling Salesman Problem Optimization Using Genetic Algorithm. In 2019 Amity International Conference on Artificial Intelligence (AICAI) (pp. 264-268). IEEE.
24. Jun-man K, & Yi Z (2012) Application of an improved ant colony optimization on generalized traveling salesman problem. Energy Proc 17:319–325
25. Karaboga, D., & Gorkemli, B. (2011). A combinatorial artificial bee colony algorithm for traveling salesman problem. In 2011 International Symposium on Innovations in Intelligent Systems and Applications (pp. 50-53). IEEE.
26. Karagül, K. (2019). Prüfer-Karagül Algoritması: Gezgin Satıcı Problemi İçin Yeni Bir Yaklaşım. Mehmet Akif Ersoy Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi, 6(2), 452-470.
27. Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598), 671-680.
28. Larranaga, P., Kuijpers, C. M. H., Murga, R. H., Inza, I., & Dizdarevic, S. (1999). Genetic algorithms for the travelling salesman problem: A review of representations and operators. Artificial Intelligence Review, 13(2), 129-170.
29. Lin, B. L., Sun, X., & Salous, S. (2016). Solving travelling salesman problem with an improved hybrid genetic algorithm. Journal of computer and communications., 4(15), 98-106.
30. Lo, K. M., Yi, W. Y., Wong, P. K., Leung, K. S., Leung, Y., & Mak, S. T. (2018). A genetic algorithm with new local operators for multiple traveling salesman problems. International Journal of Computational Intelligence Systems, 11(1), 692-705.
31. Mahi, M., Baykan, Ö. K., & Kodaz, H. (2015). A new hybrid method based on particle swarm optimization, ant colony optimization and 3-opt algorithms for traveling salesman problem. Applied Soft Computing, 30, 484-490.
32. Marinakis, Y., Marinaki, M., & Dounias, G. (2011). Honey bees mating optimization algorithm for the Euclidean traveling salesman problem. Information Sciences, 181(20), 4684-4698.
33. Mzili, I., & Riffi, M. E. (2015). Discrete penguins search optimization algorithm to solve the traveling salesman problem. Journal of Theoretical & Applied Information Technology, 72(3): 331–336.
34. Osaba, E., Yang, X. S., Diaz, F., Lopez-Garcia, P., & Carballedo, R. (2016). An improved discrete bat algorithm for symmetric and asymmetric traveling salesman problems. Engineering Applications of Artificial Intelligence, 48, 59-71.
35. Othman, Z. A., Srour, A. I., Hamdan, A. R., & Ling, P. Y. (2013). Performance water flow-like algorithm for TSP by improving its local search. International Journal of Advancements in Computing Technology, 5(14), 126-137.
36. Ouaarab, A., Ahiod, B., & Yang, X. S. (2014). Discrete cuckoo search algorithm for the travelling salesman problem. Neural Computing and Applications, 24(7-8), 1659-1669.
37. Potvin, J. Y. (1996). Genetic algorithms for the tra&ling salesman problem. Annals of Operations Research, 63(3), 337-370.
38. Pulat, M., & Kocakoç, İ. D. (2017). Gezgin Satıcı Probleminin Çözümünde Kullanılan Genetik Algoritmanın Parametrelerinin İncelenmesi. Uluslararası İktisadi ve İdari İncelemeler Dergisi, 21-36. Özel Sayı.
39. Raman, V., & Gill, N. S. (2017). Review of different heuristic algorithms for solving Travelling Salesman Problem. International Journal of Advanced Research in Computer Science, 8(5).423-425.
40. Rao, A., & Hegde, S. K. (2015). Literature survey on travelling salesman problem using genetic algorithms. International Journal of Advanced Research in Eduation Technology (IJARET), 2(1), 42-45.
41. Razali, N. M., & Geraghty, J. (2011). Genetic algorithm performance with different selection strategies in solving TSP. In Proceedings of the world congress on engineering (Vol. 2, No. 1, pp. 1-6). Hong Kong: International Association of Engineers.
42. Reinelt, G. (1991). TSPLIB—A traveling salesman problem library. ORSA journal on computing, 3(4), 376-384.
43. Ruiz-Vanoye, J. A., Díaz-Parra, O., Cocón, F., Soto, A., Arias, M. D. L. Á. B., Verduzco-Reyes, G., & Alberto-Lira, R. (2012). Meta-heuristics algorithms based on the grouping of animals by social behavior for the traveling salesman problem. International Journal of Combinatorial Optimization Problems and Informatics, 3(3), 104-123.
44. Tinós, R., Whitley, D., & Ochoa, G. (2020). A new generalized partition crossover for the traveling salesman problem: tunneling between local optima. Evolutionary Computation, 28(2), 255-288.
45. Tongur, V., & Ülker, E. (2016). The analysis of migrating birds optimization algorithm with neighborhood operator on traveling salesman problem. In Intelligent and Evolutionary Systems (pp. 227-237). Springer, Cham.
46. Tsai, C. F., Tsai, C. W., & Tseng, C. C. (2004). A new hybrid heuristic approach for solving large traveling salesman problem. Information Sciences, 166(1-4), 67-81.
47. Ulder, N. L., Aarts, E. H., Bandelt, H. J., Van Laarhoven & P. J., Pesch, E. (1990). Genetic local search algorithms for the traveling salesman problem. In International Conference on Parallel Problem Solving from Nature (pp. 109-116). Springer, Berlin, Heidelberg.
48. Wang, G. G., Hao, G. S., Cheng, S., & Qin, Q. (2016). A discrete monarch butterfly optimization for Chinese TSP problem. In International Conference on Swarm Intelligence (pp. 165-173). Springer, Cham.
49. Wang, K. P., Huang, L., Zhou, C. G., & Pang, W. (2003). Particle swarm optimization for traveling salesman problem. In Proceedings of the 2003 international conference on machine learning and cybernetics (IEEE cat. no. 03ex693) (Vol. 3, pp. 1583-1585). IEEE.
50. Wang, Y. (2014). The hybrid genetic algorithm with two local optimization strategies for traveling salesman problem. Computers & Industrial Engineering, 70, 124-133.
51. Wong, L. P., Low, M. Y. H., & Chong, C. S. (2008, May). A bee colony optimization algorithm for traveling salesman problem. In 2008 Second Asia International Conference on Modelling & Simulation (AMS) (pp. 818-823). IEEE.
52. Wu, X. B., Liao, J., & Wang, Z. C. (2015). Water wave optimization for the traveling salesman problem. In International Conference on Intelligent Computing (pp. 137-146). Springer, Cham.
53. Zhou, Y., Luo, Q., Chen, H., He, A., & Wu, J. (2015). A discrete invasive weed optimization algorithm for solving traveling salesman problem. Neurocomputing, 151, 1227-1236.