An Improved Genetic Algorithm to Solve the Traveling Salesman Problem

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.

• Omar M. Sallabi
• Younis El-Haddad

• AI
• Genetic algorithms
• TSP.

[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.