Effects of crossover operator combined with mutation operator in genetic algorithms for the generalized travelling salesman problem

Ahmed, Z.; Choudhary, M.; Al-Dayel, I.

Growing Science » International Journal of Industrial Engineering Computations » Effects of crossover operator combined with mutation operator in genetic algorithms for the generalized travelling salesman problem

Journals

IJIEC Volumes

Volume 1 (17)
- Issue 1 (9)
- Issue 2 (8)

Volume 2 (68)
- Issue 1 (12)
- Issue 2 (20)
- Issue 3 (20)
- Issue 4 (16)

Volume 3 (76)
- Issue 1 (9)
- Issue 2 (15)
- Issue 3 (20)
- Issue 4 (12)
- Issue 5 (20)

Volume 4 (50)
- Issue 1 (14)
- Issue 2 (10)
- Issue 3 (12)
- Issue 4 (14)

Volume 5 (47)
- Issue 1 (13)
- Issue 2 (12)
- Issue 3 (12)
- Issue 4 (10)

Volume 6 (39)
- Issue 1 (7)
- Issue 2 (12)
- Issue 3 (10)
- Issue 4 (10)

Volume 7 (47)
- Issue 1 (10)
- Issue 2 (14)
- Issue 3 (10)
- Issue 4 (13)

Volume 8 (30)
- Issue 1 (9)
- Issue 2 (7)
- Issue 3 (8)
- Issue 4 (6)

Volume 9 (32)
- Issue 1 (9)
- Issue 2 (6)
- Issue 3 (7)
- Issue 4 (10)

Volume 10 (34)
- Issue 1 (8)
- Issue 2 (10)
- Issue 3 (8)
- Issue 4 (8)

Volume 11 (36)
- Issue 1 (9)
- Issue 2 (8)
- Issue 3 (9)
- Issue 4 (10)

Volume 12 (29)
- Issue 1 (9)
- Issue 2 (6)
- Issue 3 (8)
- Issue 4 (6)

Volume 13 (41)
- Issue 1 (10)
- Issue 2 (8)
- Issue 3 (10)
- Issue 4 (13)

Volume 14 (50)
- Issue 1 (11)
- Issue 2 (15)
- Issue 3 (9)
- Issue 4 (15)

Volume 15 (55)
- Issue 1 (19)
- Issue 2 (15)
- Issue 3 (12)
- Issue 4 (9)

Countries

International Journal of Industrial Engineering Computations

ISSN 1923-2934 (Online) - ISSN 1923-2926 (Print) Quarterly Publication Volume 15 Issue 3 pp. 627-644 , 2024

Effects of crossover operator combined with mutation operator in genetic algorithms for the generalized travelling salesman problem Pages 627-644 Download PDF

Authors: Zakir Hussain Ahmed, Md. Taizuddin Choudhary, Ibrahim Al-Dayel

DOI: 10.5267/j.ijiec.2024.5.004

Keywords: Generalized travelling salesman problem, Genetic algorithms, Crossover operator, Mutation operator, Sequential constructive crossover, Insertion mutation

Abstract: Here, we consider the generalized travelling salesman problem (GTSP), which is a generalization of the travelling salesman problem (TSP). This problem has several real-life applications. Since the problem is complex and NP-hard, solving this problem by exact methods is very difficult. Therefore, researchers have applied several heuristic algorithms to solve this problem. We propose the application of genetic algorithms (GAs) to obtain a solution. In the GA, three operators—selection, crossover, and mutation—are successively applied to a group of chromosomes to obtain a solution to an optimization problem. The crossover operator is applied to create better offspring and thus to converge the population, and the mutation operator is applied to explore the areas that cannot be explored by the crossover operator and thus to diversify the search space. All the crossover and mutation operators developed for the TSP can be used for the GTSP with some modifications. A better combination of these two operators can create a very good GA to obtain optimal solutions to the GTSP instances. Therefore, four crossover and three mutation operators are used here to develop GAs for solving the GTSP. Then, GAs is compared on several benchmark GTSPLIB instances. Our experiment shows the effectiveness of the sequential constructive crossover operator combined with the insertion mutation operator for this problem.

How to cite this paper

 Ahmed, Z., Choudhary, M & Al-Dayel, I. (2024). Effects of crossover operator combined with mutation operator in genetic algorithms for the generalized travelling salesman problem.International Journal of Industrial Engineering Computations , 15(3), 627-644.

Refrences

Ahmed, Z. H. (2010). Genetic Algorithm for the Traveling Salesman Problem using Sequential Constructive Crossover Operator. International Journal of Biometrics & Bioinformatics. 3(6), 96–105.
Ahmed, Z. H. (2011). A data-guided lexisearch algorithm for the asymmetric traveling salesman problem. Mathematical Problems in Engineering, 2011, 750968.
Ahmed, Z. H. (2013a). An exact algorithm for the clustered travelling salesman problem. Opsearch, 50(2), 215-228.
Ahmed, Z. H. (2013b). A hybrid genetic algorithm for the bottleneck traveling salesman problem. ACM Transactions on Embedded Computing Systems (TECS), 12(1), 1–10.
Ahmed, Z. H. (2013c). An experimental study of a hybrid genetic algorithm for the maximum traveling salesman problem. Mathematical Sciences, 7(6), 1–7.
Ahmed, Z. H. (2014). The ordered clustered travelling salesman problem: A hybrid genetic algorithm. The Scientific World Journal, 2014, 258207.
Ahmed, Z. H. (2020). A comparative study of eight crossover operators for the maximum scatter travelling salesman problem. International Journal of Advanced Computer Science and Applications(IJACSA), 11(6), 317-329.
Banzhaf, W. (1990). The molecular traveling salesman. Biological Cybernetics, 64, 7–14.
Ben-Arieh, D., Gutin, G., Penn, M., Yeo, A., & Zverovitch, A. (2003). Transformations of generalized ATSP into ATSP. Operations Research Letters, 31(5), 357-365.
Bontoux, B., Artigues, C., & Feillet, D. (2010). A memetic algorithm with a large neighborhood crossover operator for the generalized traveling salesman problem. Computers & Operations Research, 37(11), 1844–1852.
Davis, L. (1985). Job-shop scheduling with genetic algorithms. In Proc. ICGA, Pittsburgh, PA, USA, 136-140.
Dimitrijevic, V., Milosavljevic, M., & Markovic, M. (1996). A branch and bound algorithm for solving a generalized traveling salesman problem. Publikacije Elektrotehnic ̎kog fakulteta, Serija Matematika, 7, 31–35.
Fischetti, M., Salazar-Gonzales, J. J., & Toth, P. (1997). A branch-and-cut algorithm for the symmetric generalized traveling salesman problem. Operations Research, 45(3), 378–394. [https://www.cs.rhul.ac.uk/home/zvero/GTSPLIB/] [last accessed on 25th February 2024].
Fogel, D. B. (1988). An evolutionary approach to the travelling salesman problem. Biological Cybernetics, 60(2), 139-144.
Fogel, D. B. (1990). A parallel processing approach to a multiple travelling salesman problem using evolutionary programming. In Proc. Fourth annual Symposium on Parallel Processing, Fullerton, California, 318–326.
Goldberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning. Addison-Wesley Longman Publishing Co., New York.
Goldberg, D. E., & Lingle, R. (1985). Alleles, loci and the travelling salesman problem. In Proc. ICGA, Pittsburgh, PA, USA, 154–159.
Grefenstette, J. J. (1987). Incorporating problem specific knowledge into genetic algorithms. Genetic algorithms and simulated annealing, 4, 42–60.
Helsgaun, K. (2015). Solving the equality generalized traveling salesman problem using the Lin-Kernighan-Helsgaun algorithm. Mathematical Programming Computation, 7(3), 269–287.
Henry-Labordere, A. L. (1969). The record balancing problem: A dynamic programming solution of a generalized salesman problem. RIRO, B-2, 43–49.
Hu, B., & Raidl, G. R. (2008). Effective neighborhood structures for the generalized traveling salesman problem. Lecture Notes in Computer Science, 4972, 36–47.
Huang, H., Yang, X., Hao, Z., Wu, C., Liang, Y., & Zhao, X. (2005). Hybrid chromosome genetic algorithm for generalized traveling salesman problems. Lecture Notes in Computer Science, 3612, 137–140.
Laporte, G., & Norbert, Y. (1983). Generalized travelling salesman problem through n sets of nodes: An integer programming approach. INFOR, 2(1), 61–75.
Laporte, G., Asef-Vaziri, A., & Sriskandarajah, C. (1996). Some applications of the generalized travelling salesman problem. Journal of the Operational Research Society, 47(12), 1461–1467.
Noon, C. E., & Bean, J. C. (1993). An efficient transformation of the generalized traveling salesman problem. INFOR, 31(1), 39–44.
Oliver, I. M., Smith, D. J., & Holland, J. R. C. (1987). A Study of Permutation Crossover Operators on the Travelling Salesman Problem. In Grefenstette, J. J. (ed.) Genetic Algorithms and Their Applications, Proceedings of the 2nd International Conference on Genetic Algorithms, Lawrence Erlbaum Associates, Hilladale, NJ, 224-230.
Potvin, J.-Y. (1996). Genetic Algorithms. Annals of Operations Research, 63, 339–370.
Reinelt, G. (1991). TSPLIB—A traveling salesman problem library. ORSA Journal on Computing, 3(4), 376-384.
Renaud, J., & Boctor, F. F. (1998). An efficient composite heuristic for the symmetric generalized traveling salesman problem. European Journal of Operational Research, 108(3), 571–584.
Renaud, J., Boctor, F. F., & Laporte, G. (1996). A fast composite heuristic for the symmetric traveling salesman problem. INFORMS Journal on Computing, 8, 134–143.
Schmidt, J., & Irnich, S. (2022). New neighborhoods and an iterated local search algorithm for the generalized traveling salesman problem. EURO Journal on Computational Optimization, 10, 100029.
Silberholz, J., & Golden, B. (2007). The generalized traveling salesman problem: A new genetic algorithm approach. In E. K. Baker, A . Joseph, A . Mehrotra, & M. A. Trick (Eds.), Extending the horizons: Advances in computing, optimization, and decision technologies. In Operations Research/Computer Science Interfaces Series, 37, 165–181.
Smith, S. L., & Imeson, F. (2017). GLNS: An effective large neighborhood search heuristic for the generalized traveling salesman problem. Computers & Operations Research, 87, 1–19.
Snyder, L. V., & Daskin, M. S. (2006). A random-key genetic algorithm for the generalized traveling salesman problem. European Journal of Operational Research, 74, 38–53.
Tasgetiren, M. F., Suganthan, P. N., & Pan, Q. K. (2007). A discrete particle swarm optimization algorithm for the generalized traveling salesman problem. in Proc. GECCO 2007, 158–167.
Yang, J., Shi, X., Marchese, M., & Liang, Y. (2008). An ant colony optimization method for generalized TSP problem. Progress in Natural Science, 18, 1417–1422.