Comparison of Genetic Crossover Operators for Traveling Salesman Problem

Year 2025, Early View, 1 - 1

Şahin Burak Dalkılıç , Atilla Özgür , Hamit Erdem

https://doi.org/10.35378/gujs.1582521

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] 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] 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] 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] 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] 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] 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] 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] Ö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] 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] 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] 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] Ö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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] Üç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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] Demšar, J., “Statistical comparisons of classifiers over multiple data sets”, The Journal of Machine Learning Research, 7: 1–30, (2006).
• [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] 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] 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