Comparison of Genetic Crossover Operators for Traveling Salesman Problem

Abstract

The traveling salesman problem (TSP) is an NP-hard problem that has been the subject of intensive study by researchers and academics in the field of optimization for many years. Genetic algorithms (GA) are one of the most effective methods for solving various NP-hard problems, including TSP. Recently, many crossover operators have been proposed to solve the TSP problem using GA. However, it remains unclear which crossover operator performs better for the particular problem. In this study, ten crossover operators, namely; Partially-Mapped Crossover (PMX), Cycle Crossover (CX), Order Crossover (OX1), Order Based Crossover (OX2), Position Based Crossover (POS), Edge Recombination Crossover (ERX), Maximal Preservative Crossover (MPX), Extended Partially-Mapped Crossover (EPMX), Improved Greedy Crossover (IGX), and Sequential Constructive Crossover (SCX) have been empirically evaluated. 30 TSP data sets have been used to comprehensively evaluate the selected crossover operators, and the experiments have been repeated 30 times to make our results statistically sound. Likewise, how successful the operators are, has been found through critical diagrams and statistical tests. Among tested operators, the IGX and SCX methods were the best operators in terms of convergence rate. On the other hand, PMX outperformed other operators in terms of computational cost.

Keywords

• Travelling Salesman Problem
• Genetic Algorithms
• Crossover Operators
• Critical Difference Diagram

References

1. [1] Klanšek, U., “Using the TSP solution for optimal route scheduling in construction management”, Organization, Technology & Management in Construction: An International Journal, 3(1): 243-249, (2011).
2. [2] Matai, R., Singh, S.P. and Mittal, M.L., “Traveling salesman problem: an overview of applications, formulations, and solution approaches”, Traveling Salesman Problem, Theory and Applications, India, (2010). DOI: https://doi.org/10.5772/12909
3. [3] Kavlak, H., İşleyen, S.K. and Toklu, B., “Capacitated multi drone assisted vehicle routing problem”, Gazi University Journal of Science, 37(3): 1386-1415, (2024). DOI: https://doi.org/10.35378/gujs.1340189
4. [4] Liu, H., Zhang, H. and Xu, Y., “The m-Steiner traveling salesman problem with online edge blockages”, Journal of Combinatorial Optimization, 41: 844-860, (2021). DOI: https://doi.org/10.1007/s10878-021-00720-6
5. [5] Lai, X., Zhang, K., Li, Z., Mao, N., Chen, Q. and Zhang, S., “Scheduling air conditioner testing tasks under time-of-use electricity tariff: A predict in and for optimization approach”, Computers & Industrial Engineering, 175: 108850, (2023). DOI: https://doi.org/10.1016/j.cie.2022.108850
6. [6] Groba, C., Sartal, A. and Vázquez, X.H., “Solving the dynamic traveling salesman problem using a genetic algorithm with trajectory prediction: An application to fish aggregating devices”, Computers & Operations Research, 56: 22-32, (2015). DOI: https://doi.org/10.1016/j.cor.2014.10.012
7. [7] Liu, L.L., Wan, X., Gao, Z., Li, X. and Feng, B., “Research on modelling and optimization of hot rolling scheduling”, Journal of ambient intelligence and humanized computing, 10: 1201-1216, (2019). DOI: https://doi.org/10.1007/s12652-018-0944-7
8. [8] Özgür, A., Uygun, Y. and Hütt, M.T., “A review of planning and scheduling methods for hot rolling mills in steel production”, Computers & Industrial Engineering, 151: 106606, (2021). DOI: https://doi.org/10.1016/j.cie.2020.106606

9. [9] Hussain, A., Muhammad, Y.S. and Sajid, M.N., “A simulated study of genetic algorithm with a new crossover operator using traveling salesman problem”, Punjab University Journal of Mathematics, 51(5): 61-77, (2020).
10. [10] Cariou, C., Moiroux-Arvis, L., Pinet, F. and Chanet, J.P., “Evolutionary algorithm with geometrical heuristics for solving the close enough traveling salesman problem: Application to the trajectory planning of an unmanned aerial vehicle”, Algorithms, 16(1): 44, (2023). DOI: https://doi.org/10.3390/a16010044
11. [11] Ozturk, N., & Celik, E., “Application of genetic algorithms to core loss coefficient extraction”, Progress In Electromagnetics Research M, 19: 133-146, (2011). DOI: https://doi.org/10.2528/PIERM11051310
12. [12] Öztürk, N., and Çelik, E., “An educational tool for the genetic algorithm-based fuzzy logic controller of a permanent magnet synchronous motor drive”, International Journal of Electrical Engineering Education, 51(3): 218-231, (2014). DOI: https://doi.org/10.7227/IJEEE.51.3.4
13. [13] Celik, E., and Öztürk, N., “Attenuating saturated-regulator operation effect of brushless DC motors through genetic-based fuzzy logic estimator”, Turkish Journal of Electrical Engineering and Computer Sciences, 26(6): 3207-3223, (2018). DOI: https://doi.org/10.3906/elk-1711-113
14. [14] Reinelt, G., “TSPLIB-A traveling salesman problem library”, ORSA Journal on Computing, 3(4): 376-384, (1991). DOI: https://doi.org/10.1287/ijoc.3.4.376
15. [15] Abdoun, O. and Abouchabaka, J., “A comparative study of adaptive crossover operators for genetic algorithms to resolve the traveling salesman problem”, International Journal of Computer Applications, 31(11): 49-57, (2011). DOI: https://doi.org/10.48550/arXiv.1203.3097
16. [16] Hussain, A., Muhammad, Y.S., Sajid, M.N., Hussain, I., Shoukry, A.M. and Gani, S., “Genetic algorithm for traveling salesman problem with modified cycle crossover operator”, Computational intelligence and neuroscience, 2017(1): (2017). DOI: https://doi.org/10.1155/2017/7430125
17. [17] Hussain, A., Muhammad, Y.S. and Saji̇d, M.N., “An improved genetic algorithm crossover operator for traveling salesman problem”, Turkish Journal of Mathematics and Computer Science, 9: 1–13, (2018).
18. [18] Haq, E., Hussain, A. and Ahmad, I., “Development a new crossover scheme for traveling salesman problem by aid of genetic algorithm”, Int. J. Intell. Syst. Appl, 11(12): 46-52, (2019). DOI: https://doi.org/10.5815/ijisa.2019.12.05
19. [19] Akter, S., Nahar, N., ShahadatHossain, M. and Andersson, K., “A new crossover technique to improve genetic algorithm and its application to TSP”, International Conference on Electrical, Computer and Communication Engineering (ECCE), Bangladesh, 1-6, (2019). DOI: https://doi.org/10.1109/ECACE.2019.8679367
20. [20] Al-Omeer, M.A. and Ahmed, Z.H., “Comparative study of crossover operators for the MTSP”, International Conference on Computer and Information Sciences (ICCIS), Saudi Arabia, 1-6, (2019). DOI: https://doi.org/10.1109/ICCISci.2019.8716483
21. [21] Kuroda, M., Yamamori, K., Munetomo, M., Yasunaga, M. and Yoshihara, I., “Development of a novel crossover of hybrid genetic algorithms for large-scale traveling salesman problems”, Artificial Life and Robotics, 15: 547-550, (2010). DOI: https://doi.org/10.1007/s10015-010-0866-8
22. [22] Ahmed, Z.H., “Adaptive sequential constructive crossover operator in a genetic algorithm for solving the traveling salesman problem”, International Journal of Advanced Computer Science and Applications, 11(2): 593-605, (2020). DOI: https://doi.org/10.14569/ijacsa.2020.0110275
23. [23] Ahmed, Z.H., “Genetic algorithm with comprehensive sequential constructive crossover for the travelling salesman problem”, International Journal of Advanced Computer Science and Applications, 11(5): 245-254, (2020). DOI: https://doi.org/10.14569/IJACSA.2020.0110533
24. [24] Bye, R.T., Gribbestad, M., Chandra, R. and Osen, O.L., “A comparison of ga crossover and mutation methods for the traveling salesman problem”, Innovations in Computational Intelligence and Computer Vision: Proceedings of ICICV, Singapore, 529-542, (2020). DOI: https://doi.org/10.1007/978-981-15-6067-5_60
25. [25] Dou, X.A., Yang, Q., Gao, X.D., Lu, Z.Y. and Zhang, J., “A Comparative study on crossover operators of genetic algorithm for traveling salesman problem”, 15th International Conference on Advanced Computational Intelligence (ICACI), Korea, 1-8, (2023). DOI: https://doi.org/10.1109/ICACI58115.2023.10146181
26. [26] Bennaceur, H. and Alanzi, E., “Genetic algorithm for the travelling salesman problem using enhanced sequential constructive crossover operator”, International Journal of Computer Science and Security (IJCSS), 11(3): 42-52, (2017).
27. [27] Tao, G. and Michalewicz, Z., “Inver-over operator for the TSP”, International Conference on Parallel Problem Solving from Nature, Heidelberg, 803-812, (1998). DOI: https://doi.org/10.1007/BFb0056922
28. [28] Üçoluk, G., “Genetic algorithm solution of the TSP avoiding special crossover and mutation”, Intelligent Automation & Soft Computing, 8(3): 265-272, (2002). DOI: https://doi.org/10.1080/10798587.2000.10642829
29. [29] Wang, L.Y., Zhang, J. and Li, H., “An improved genetic algorithm for tsp”, International Conference on Machine Learning and Cybernetics, China, 925–928, (2007). DOI: https://doi.org/10.1109/ICMLC.2007.4370274
30. [30] Ahmed, Z.H., “Genetic algorithm for the traveling salesman problem using sequential constructive crossover operator”, International Journal of Biometrics & Bioinformatics (IJBB), 3(6): 96-105, (2010).
31. [31] Dalkilic, S.B., Özgür, A. and Erdem, H., “A comparison of crossover operators in genetic algorithms for steel domain”, Steel 4.0: Digitalization in Steel Industry, Switzerland, 103–123, (2024). DOI: https://doi.org/10.1007/978-3-031-57468-9_6
32. [32] Su, F., Zhu, F., Yin, Z., Yao, H., Wang, Q. and Dong, W., “New crossover operator of genetic algorithms for the TSP”, International Joint Conference on Computational Sciences and Optimization, China, 666–669, (2009). DOI: https://doi.org/10.1109/CSO.2009.422
33. [33] Satyananda, D., “Modification of Crossover Operator on GA Application for TSP”, Proceeding of International Conference On Research, Implementation And Education Of Mathematics And Sciences, Indonesia, M1-M10, (2015).
34. [34] Zhang, P., Wang, J., Tian, Z., Sun, S., Li, J. and Yang, J., “A genetic algorithm with jumping gene and heuristic operators for traveling salesman problem”, Applied Soft Computing, 127: 109339, (2022). DOI: https://doi.org/10.1016/j.asoc.2022.109339
35. [35] Thanh, P. D., Binh, H.T.T. and Lam, B.T., “New mechanism of combination crossover operators in genetic algorithm for solving the traveling salesman problem”, Advances in Intelligent Systems and Computing, 326: 367-379, (2015). DOI: https://doi.org/10.1007/978-3-319-11680-8_29
36. [36] Hassanat, A.B. and Alkafaween, E.A., “On enhancing genetic algorithms using new crossovers”, International Journal of Computer Applications in Technology, 55(3): 202-212, (2017). DOI: https://doi.org/10.1504/IJCAT.2017.084774
37. [37] Koohestani, B., “A crossover operator for improving the efficiency of permutation-based genetic algorithms”, Expert Systems with Applications, 151, 113381, (2020). DOI: https://doi.org/10.1016/j.eswa.2020.113381
38. [38] Ismkhan H. and Zamanifar, K., “Study of some recent crossovers effects on speed and accuracy of genetic algorithm, using symmetric travelling salesman problem”, International Journal of Computer Applications, 80(6): 1-6, (2013). DOI: https://doi.org/10.5120/13862-1716
39. [39] Ismkhan H. and Zamanifar, K., “Developing improved greedy crossover to solve symmetric traveling salesman problem”, International Journal of Computer Science Issues, 9(4): 121-126, (2012). DOI: https://doi.org/10.48550/arXiv.1209.5339
40. [40] Khan, I.H., “Assessing different crossover operators for travelling salesman problem”, International Journal of Intelligent Systems and Applications, 7(11): 19–25, (2015). DOI: https://doi.org/10.5815/ijisa.2015.11.03
41. [41] Uray, M., Wintersteller, S. and Huber, S., “CSRX: A novel Crossover Operator for a Genetic Algorithm applied to the Traveling Salesperson Problem”, In International Data Science Conference, Switzerland, 21-27, (2023). DOI: https://doi.org/10.1007/978-3-031-42171-6_3
42. [42] Muazu, A.A., Hashim, A.S. and Sarlan, A., “Review of Nature Inspired Metaheuristic Algorithm Selection for Combinatorial t-way Testing”, IEEE Access, 10: 27404-27431, (2022). DOI: https://doi.org/10.1109/ACCESS.2022.3157400
43. [43] Stork, J., Eiben, A.E. and Bartz-Beielstein, T., “A new taxonomy of global optimization algorithms”, Natural Computing, 21: 219-242, (2020). DOI: https://doi.org/10.1007/s11047-020-09820-4
44. [44] Pulat M. and Deveci Kocakoç, I. “Investigation of crossover operators using genetic algorithms in the solution of the traveling salesman problem based on case studies”, Izmir Journal of Economics, 34(2): 225–243, (2019). DOI: https://doi.org/10.24988/ije.2019342825
45. [45] Hussain A. and Muhammad, Y.S., “Trade-off between exploration and exploitation with genetic algorithm using a novel selection operator”, Complex & intelligent systems, 6: 1-14, (2020). DOI: https://doi.org/10.1007/s40747-019-0102-7
46. [46] Albayrak M. and Allahverdi, N., “Development a new mutation operator to solve the traveling salesman problem by aid of genetic algorithms”, Expert Systems with Applications, 38(3): 1313-1320, (2011). DOI: https://doi.org/10.1016/j.eswa.2010.07.006
47. [47] Whitley, L.D., Starkweather, T. and Fuquay, D., “Scheduling problems and traveling salesmen: The genetic edge recombination operator”, Proceedings of the 3rd international conference on genetic algorithms, 133-140, (1989).
48. [48] Larrañaga, P., Kuijpers, C.M.H., Murga, R.H., Inza, I. and Dizdarevic, S., “Genetic algorithms for the travelling salesman problem: A review of representations and operators”, Artificial intelligence review, 13: 129-170, (1999). DOI: https://doi.org/10.1023/A:1006529012972
49. [49] Samanta, S., De, A. and Singha, S., “Solution of traveling salesman problem on scx based selection with performance analysis using genetic algorithm”, International Journal of Engineering Science and Technology, 3(8): 6622-6629, (2011).
50. [50] Demšar, J., “Statistical comparisons of classifiers over multiple data sets”, The Journal of Machine Learning Research, 7: 1–30, (2006).
51. [51] Friedman, M., “A comparison of alternative tests of significance for the problem of m rankings”, The annals of mathematical statistics, 11(1): 86-92, (1940).
52. [52] Benavoli, A., Corani, G. and Mangili, F., “Should we really use post-hoc tests based on mean-ranks?”, The Journal of Machine Learning Research, 17(1): 152-161, (2016). DOI: https://doi.org/10.48550/arXiv.1505.02288
53. [53] Derrac, J., García, S., Molina, D. and Herrera, F., “A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms”, Swarm and Evolutionary Computation, 1(1): 3-18, (2011). DOI: https://doi.org/10.1016/j.swevo.2011.02.002