Modified genetic algorithm with novel crossover and mutation operator for travelling salesman problem

Year 2024, Volume: 42 Issue: 6, 1876 - 1883, 09.12.2024

M.k. Sharma Sadhna Chaudhary Laxmi Rathour , Vishnu Narayan Mishra

Abstract

In this study, Genetic Algorithm (GA), a sort of randomized direct, iterative search methodology built around natural selection, is employ in computers to discover approximations of solutions to optimisation and search issues. GA employs operators including selection, crossover, and mutation to tackle. In case of NP-hard issues, particularly for travelling salesman problem (TSP), the GAs is beneficial. To reduce the overall distance, we propose a novel crossover operator with its python code for the TSP. Along with the Python pseudo coding, we additionally introduced a mutation operator to enhance the consummation of GA in determining the shortest distance in the TSP. To emphasize the proposed crossover and mutation operator, we also illustrate different steps using examples. We integrated path representation with our developed crossover and mutation operator as it is apparent method to represent a tour.

Keywords

Crossover Operator, Genetic Algorithm, Muation Operator, Python Coding, Travelling Salesman Problem

References

• REFERENCES [1] Holland J. Adaption in Natural and Artificial Systems. Ann Arbor: University of Michigen Press; 1975.
• [2] Lidd ML. The travelling Salesman Problem Domain Application of a Fundamentally New Approach to Utilizing Genetic Algorithms. Technical Report, MITRE Corporation, 1991.
• [3] Goldberg DE, Lingle Jr. R. Alleles, Loci and the TSP. In Grefenstette, J. J. (Ed.). Proceedings of the First International Conference on Genetic Algorithms and Their Applications,Hillsdale, New Jersey: Lawrence Erlbaum; 1985. p. 154–159.
• [4] Davis L. Applying Adaptive Algorithms to Epistatic Domains. Proceedings of the International Joint Conference on Artificial Intelligence. New York, USA: ACM Digital Library; 1985. p. 162–164.
• [5] Brady RM. Optimization strategies gleaned from biological evolution. Nature 1985;317:804–806. [CrossRef]
• [6] Grefenstette JJ. Incorporating Problem Specific Knowledge into Genetic Algorithms. In Davis, L. (ed.) Genetic Algorithms and Simulated AnnealingLos Altos, CA: Morgan Kaufmann; 1987. p. 42–60.
• [7] Muhlenbein H, Gorges-Schleuter M, Kramer O. Evolution algorithms in combinatorial optimization. Paral Comput 1988;7:65–85. [CrossRef]
• [8] Muhlenbein H. Parallel Genetic Algorithms, Population Genetics and Combinatorial ¨ Optimization. In Schaffer, J. (ed.) Proceedings on the Third International Conference on Genetic Algorithms, Los Altos, CA: Morgan Kaufmann Publishers; 1988. p. 416–421.
• [9] Syswerda G. Schedule optimization using genetic algorithms. In L. Davis (Ed.), Handbook of genetic algorithms. USA: Van Nostrand Reinhold; 1991. p. 332–349.
• [10] Grefenstette JJ. Incorporating Problem Specific Knowledge into Genetic Algorithms. In Davis, L. (ed.) Genetic Algorithms and Simulated Annealing, Los Altos, CA: Morgan Kaufmann; 1987. p. 42–60.
• [11] Larranaga P, Inza I, Kuijpers CMH, Grana M, Lozano JA. Algoritmos Geneticos en el Problema del Viajante de Comercio. ' Informatica y Automatica (submitted). 1966.
• [12] Grefenstette J, Gopal R, Rosmaita B, Van Gucht D. Genetic Algorithms for the TSP. In Grefenstette, J. J. (ed.) Proceedings of the First International Conference on Genetic Algorithms and Their
• Applications, Hillsdale, New Jersey: Lawrence Erlbaum; 1986. p. 160–165.
• [13] Abu Arqub O, Abo-Hammour Z, Momani S, Shawagfeh N. Solving singular two-point boundary value problems using continuous genetic algorithm. Abstr Appl Anal 2012;2012:205391. [CrossRef]
• https://doi.org/10.1155/2012/205391
• [14] Arqub OA, Abo-Hammour Z. Numerical solution of systems of second-order boundary value problems using continuous genetic algorithm. Inf Sci 2014;279:396–415. [CrossRef]
• [15] Abo-Hammour ZE, Alsmadi O, Momani S, Abu Arqub O. A genetic algorithm approach for prediction of linear dynamical systems. Math Probl Eng 2013;2013:1–12. [CrossRef]
• [16] Abo-Hammour Z, Abu Arqub O, Momani S, Shawagfeh N. Optimization solution of Troesch's and Bratu's problems of ordinary type using novel continuous genetic algorithm. Discrete Dyn Nat Soc 2014;2014:401696. [CrossRef]
• [17] Raiz M, Kumar A, Mishra VN, Rao N. Dunkl analogue of Sz $\acute {a} $ sz-Schurer-Beta operators and their approximation behaviour. Math Found Comput 2022;5:315–330. [CrossRef]
• [18] Mishra VN, Raiz M, Rao N. Dunkl analouge of Sz $\acute {a} $ sz Schurer Beta bivariate operators. Math Found Comput 2023;6:651–669. [CrossRef]
• [19] Dantzig G, Fulkerson R, Johnson S. Solution of a large-scale traveling-salesman problem. J Oper Res Soc Am 1954;2:393–410. [CrossRef]
• [20] Petberg MW, Homg S. On the symmetric traveling salesman problems: a computational study. Math Prog Stud 1980;12:61–77. [CrossRef]
• [21] Fleischmann B. A cutting plane procedure for the travelling salesman problem on road networks. Eur J Oper Res 1985;21:307–317. [CrossRef]
• [22] Padberg M, Rinaldi G. Optimization of a 532-city symmetric traveling salesman problem by branch and cut. Oper Res Lett 1987;6:1–7. [CrossRef]
• [23] Bhide S, John N, Kabuka MR. A Boolean neural network approach for the traveling salesman problem. IEEE Trans Comput 1993;42:1271–1278. [CrossRef]
• [24] Dorigo M, Gambardella LM. Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Trans Evol Comput 1997;1:53–66. [CrossRef]
• [25] Knox JE. The application of tabu search to the symmetric traveling salesman problem. Colarado: University of Colorado at Boulder; 1989.
• [26] Chiang WC, Russell RA. Simulated annealing metaheuristics for the vehicle routing problem with time windows. Ann Oper Res 1996;63:3–27. [CrossRef] [27] Focacci F, Lodi A, Milano M. A hybrid exact algorithm for the TSPTW. Informs J Comput 2013;14:403–417. [CrossRef]
• [28] Ibaraki T, Imahori S, Kubo M, Masuda T, Uno T, Yagiura M. Effective local search algorithms for routing and scheduling problems with general time-window constraints. Transp Sci 2007;39:206– 232. [CrossRef]
• [29] Nguyen HD, Yoshihara I, Yamamori K, Yasunaga M. Implementation of an effective hybrid GA for large-scale traveling salesman problems. IEEE Trans Syst Man Cybern Part B (Cybernetics) 2007;37:92–99. [CrossRef]
• [30] Ghadle KP, Muley YM. Travelling salesman problem with MATLAB programming. Int J Adv Appl Math Mech 2015;2:258–266.
• [31] Kumar A, Gupta A. Assignment and travelling salesman problems with coefficients as LR fuzzy parameters. Int J Appl Sci 2015;10:155–170.
• [32] Majumdar J, Bhunia AK. Genetic algorithm for asymmetric traveling salesman problem with imprecise travel times. J Comput Appl Math 2011;235:3063–3078. [CrossRef]
• [33] Changdar C, Mahapatra GS, Pal RK. An efficient genetic algorithm for multi-objective solid travelling salesman problem under fuzziness. Swarm Evol Comput 2014;15:27–37. [CrossRef]
• [34] Maity S, Roy A, Maiti M. A modified genetic algorithm for solving uncertain constrained solid travelling salesman problems. Comput Ind Eng 2012;83:273–296. [CrossRef]
• [35] Dantzig GB. Linear programming and extensions. Princeton, NJ: Princeton University Press; 1993.
• [36] Velednitsky M. Short combinatorial proof that the DFJ polytope is contained in the MTZ polytope for the Asymmetric Traveling Salesman Problem. arXiv preprint arXiv 2018:1805.06997.
• [37] Oliver IM, Smith D, Holland JR. A study of permutation crossover operators on the traveling salesman problem. In Oliver IM, Smith DJ, Holland JRC (Ed.). Genetic Algorithms and their Applications. Sussex, London: Psychology Press; 2013. p. 224–230.
• [38] Hussain A, Muhammad YS, Nauman Sajid M, Hussain I, Mohamd Shoukry A, Gani S. Genetic algorithm for traveling salesman problem with modified cycle crossover operator. Comput Intell Neurosci 2017;2017:430125. [CrossRef]
• [39] Fogel DB. An evolutionary approach to the traveling salesman problems. Biol Cybrn 1988;60:139–144. [CrossRef]
• [40] Banzhaf W. The 'molecular' traveling salesman. Biol Cybrn 1990;64;7–14. [CrossRef]
• [41] Michalewicz Z. Genetic Algorithms + Data Structures = Evolution Programs. Berlin Heidelberg: Springer Verlag; 1992. [CrossRef]
• [42] Fogel DB. Empirical estimation of the computation required to discovery approximate solutions to the traveling salesman problem using evolutionary programming. Proceedings of 2nd Annual Conference on Evolutionary Programming. 1993. p. 56–61.