Enhanced Traveling Salesman Problem Solving by Genetic Algorithm Technique (TSPGA)

Authors: Buthainah Fahran Al-Dulaimi, Hamza A. Ali

Abstract:

The well known NP-complete problem of the Traveling Salesman Problem (TSP) is coded in genetic form. A software system is proposed to determine the optimum route for a Traveling Salesman Problem using Genetic Algorithm technique. The system starts from a matrix of the calculated Euclidean distances between the cities to be visited by the traveling salesman and a randomly chosen city order as the initial population. Then new generations are then created repeatedly until the proper path is reached upon reaching a stopping criterion. This search is guided by a solution evaluation function.

Keywords: Genetic algorithms, traveling salesman problem solving, optimization.

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

References:

[1] J. H. Holland et. Al., "Induction: Processes of Inference, Learning, and Discovery", MIT Press, 1989.
[2] M. Melanie, "An Introduction to Genetic Algorithms", MIT Press, 1996.
[3] S. Sur-Kolay, S. Banerjee, and C. A. Murthy, "Flavours of Traveling Salesman Problem in VLSI Design", 1st Indian International Conference on Artificial Intelligence, 2003.
[4] E.L. Lawler, J.K. Lenstra, A.H.G Rinnooy Kan, and D. B. Shmoys, "The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization", Wiley address Interscience, Chichester, 1985.
[5] Moscato, P. and M.G. Norman, "A `Memetic', Approach for the Traveling Salesman Problem. Implementation of a Computational Ecology for Combinatorial Optimization on Message-Passing a Systems, Parallel Computing and ransputer Applications", edited by M. Valero, E. Onate, M. Jane, J.L. Larriba and B. Suarez, Ed. IOS Press, Amsterdam, 1992. pp: 187 -194.
[6] M. Lalena, "Traveling Salesman Problem Using Genetic Algorithms. http://www.lalena.com/ai/tsp/, 2003.
[7] D. Whitley and K. Mathias, "Genetic Operators, the Fitness Landscape and the Traveling Salesman Problem", Parallel Problem Solving from Nature-PPSN 2. R. Manner and B. Mandrake North Holland-Elsevier, eds., 1992, pp: 219 - 228.
[8] S. Kedar, Naphade & Dilek Tuzun, "Initializing the Hopfield-Tank Network for the TSP using a convex hull: A Computational Study. Proceedings of the Artificial Neural Networks in Engineering (ANNIE'95) Conference, 1995, PP399 - 404.
[9] D. E. Goldberg, "Genetic Algorithm in Search, Optimization and Machine Learning", Machine Learning. Addison-Wesley, New York, 1989.
[10] P. Larranaga, C. M. H. Kuijpers, R. H. Murga, I. Inza and S. Dizdarevic, "Genetic Algorithms for the Travelling Salesman Problem: A Review of Representations and Operators", Artificial Intelligence Review. 13, 1999, PP129-170.
[11] S. R. Shubhra, B. Sanghamitra and K. Pal. Sankar, "New Operators of Genetic Algorithms for Traveling Salesman Problem", IEEE, 0-7695- 2128-2/04, 2004.
[12] Ji. Ping and Ho. William, "The Traveling Salesman and the Quadratic Assignment Proble: Integration, Modeling and Genetic Algorithm", Int. Symposium on OR and its Applications, 2005, PP198-205.
[13] C. Ding, Ye. Cheng and M. He, "Two-Level Genetic Algorithm for Clustered Traveling Salesman Problem with Application in Large-Scale TSPs", Tsinghua Science and Technology, Vol.12, No.4, 2007, PP459- 465.
[14] P. Borovska, T. Ivanova and H. Salem, "Efficient Parallel Computation of the Traveling Salesman Problem on Multicomputer Platform", Proceedings of the International Scientific Conference ÔÇÿComputer Science- 2004, Sofia, Bulgaria, Dec. 2004, PP74-79.
[15] R. Gremlich, A. Hamfelt, H. de Pereda and V. Valkovsky, "Genetic Algorithms with Oracle for the Traveling Salesman Problem", proceedings of world academy of science, Engineering and Technology, Vol. , Aug 2005, PP1307-6884.
[16] Q. Jiang, R. Sarker and H. Abbass, "Tracking moving targets in the nonstationary travelling salesman problem," Complexity International, Vol.11, 2005, PP171-179.
[17] V. Lawrence, A. Snyder and M. S. Daskin, "A random-key genetic algorithm for the generalized traveling salesman problem", Available online since 17 May 2005, www.sciencedirect.com
[18] M. Bakhouya and J. Gaber, "An Immune Inspired-based Optimization Algorithm: Application to the Traveling Salesman Problem, AMO", Advanced Modeling and Optimization, Vol. 9, No. 1, 2007.
[19] B. P. Buckles, P. E. Petry and R. I. Kuester, "Schema Survival Rates and Heuristic Search in Genetic Algorithms", IEEE, 1990, PP 86-91.
[20] D. T. Phillips, A. Rarindran and J. J. Solberg, "Operations Research: Principles and Practice", John Wiely and Sons Inc, 1976.
[21] D. E. Goldberg, "Genetic Algorithms in Search, Optimization, and Machine Learning", Addison Wesley Publishing Company Inc. 1989.