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

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

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

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

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.

Details

Primary Language

English

Subjects

Clinical Chemistry

Journal Section

Research Article

Authors

M.k. Sharma This is me
0000-0003-3071-5931
India

Sadhna Chaudhary This is me
0000-0003-1255-0395
India

Laxmi Rathour
0000-0002-2659-7568
India

Vishnu Narayan Mishra ^*
0000-0002-2159-7710
India

Publication Date

December 9, 2024

Submission Date

July 11, 2023

Acceptance Date

November 11, 2023

Published in Issue

Year 2024 Volume: 42 Number: 6

IZ

https://izlik.org/JA48DD39BD

Cite

RIS / Bibtex

APA

Sharma, M., Chaudhary, S., Rathour, L., & Mishra, V. N. (2024). Modified genetic algorithm with novel crossover and mutation operator for travelling salesman problem. Sigma Journal of Engineering and Natural Sciences, 42(6), 1876-1883. https://izlik.org/JA48DD39BD

AMA

1.Sharma M, Chaudhary S, Rathour L, Mishra VN. Modified genetic algorithm with novel crossover and mutation operator for travelling salesman problem. SIGMA. 2024;42(6):1876-1883. https://izlik.org/JA48DD39BD

Chicago

Sharma, M.k., Sadhna Chaudhary, Laxmi Rathour, and Vishnu Narayan Mishra. 2024. “Modified Genetic Algorithm With Novel Crossover and Mutation Operator for Travelling Salesman Problem”. Sigma Journal of Engineering and Natural Sciences 42 (6): 1876-83. https://izlik.org/JA48DD39BD.

EndNote

Sharma M, Chaudhary S, Rathour L, Mishra VN (December 1, 2024) Modified genetic algorithm with novel crossover and mutation operator for travelling salesman problem. Sigma Journal of Engineering and Natural Sciences 42 6 1876–1883.

IEEE

[1]M. Sharma, S. Chaudhary, L. Rathour, and V. N. Mishra, “Modified genetic algorithm with novel crossover and mutation operator for travelling salesman problem”, SIGMA, vol. 42, no. 6, pp. 1876–1883, Dec. 2024, [Online]. Available: https://izlik.org/JA48DD39BD

ISNAD

Sharma, M.k. - Chaudhary, Sadhna - Rathour, Laxmi - Mishra, Vishnu Narayan. “Modified Genetic Algorithm With Novel Crossover and Mutation Operator for Travelling Salesman Problem”. Sigma Journal of Engineering and Natural Sciences 42/6 (December 1, 2024): 1876-1883. https://izlik.org/JA48DD39BD.

JAMA

1.Sharma M, Chaudhary S, Rathour L, Mishra VN. Modified genetic algorithm with novel crossover and mutation operator for travelling salesman problem. SIGMA. 2024;42:1876–1883.

MLA

Sharma, M.k., et al. “Modified Genetic Algorithm With Novel Crossover and Mutation Operator for Travelling Salesman Problem”. Sigma Journal of Engineering and Natural Sciences, vol. 42, no. 6, Dec. 2024, pp. 1876-83, https://izlik.org/JA48DD39BD.

Vancouver

1.M.k. Sharma, Sadhna Chaudhary, Laxmi Rathour, Vishnu Narayan Mishra. Modified genetic algorithm with novel crossover and mutation operator for travelling salesman problem. SIGMA [Internet]. 2024 Dec. 1;42(6):1876-83. Available from: https://izlik.org/JA48DD39BD