An Improved Genetic Algorithm to Solve the Traveling Salesman Problem

Authors: Omar M. Sallabi, Younis El-Haddad

Abstract:

The Genetic Algorithm (GA) is one of the most important methods used to solve many combinatorial optimization problems. Therefore, many researchers have tried to improve the GA by using different methods and operations in order to find the optimal solution within reasonable time. This paper proposes an improved GA (IGA), where the new crossover operation, population reformulates operation, multi mutation operation, partial local optimal mutation operation, and rearrangement operation are used to solve the Traveling Salesman Problem. The proposed IGA was then compared with three GAs, which use different crossover operations and mutations. The results of this comparison show that the IGA can achieve better results for the solutions in a faster time.

Keywords: AI, Genetic algorithms, TSP.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1085736

References:

[1] E. Lawle, , "Combinatorial Optimization: Networks and Matroids"., Holt, Rinehart, and Winston, New York1. 1976.
[2] P. Larranaga,C.M.H. Kuijpers, R.H. Murga, I. Innza and S. Dizdarevic ,"Genetic Algorithms for the Travelling Salesman Problem: A Review of Representations and Operators". P.. 13(2), s.l. : Artif. Intell, 1999. 129-170.
[3] D. Beasley, D. Bull, and R. Martin. "An Overview of Genetic Algorithms: Part 1. Fundamentals", University Computing, 1993, Vol. 15(2), pp. 58--69.
[4] TSBLIB, http://www.iwr.uni-eidelberg.de/iwr/ comopt/ soft/ TSPLIB95/TSPLIB.html. (Online) (Cited: 12 22, 2008.)
[5] Holland, J.,"Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence." The University of Michigan Press, 1975.
[6] S. Ray, S. Bandyopadhyay and S. Pal, "New operators of genetic algorithms for traveling salesman problem" Cambridge : s.n., 2004, Vol. 2.
[7] M. Bakhouya and J, Gaber " An Immune Inspiredbased Optimization Algorithm: Application to the Traveling Salesman Problem",. : Advanced Modeling and Optimization , 2007 , Vol. 9.
[8] S. Ray, S. Bandyopadhyay and S. Pal, " New Genetic operators for solving TSP: Application to microarray gene ordering", Berlin : Springer, 2005.