Enhanced Traveling Salesman Problem Solving by Genetic Algorithm Technique (TSPGA)
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.
[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.
[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.
@article{"International Journal of Engineering, Mathematical and Physical Sciences:55641", author = "Buthainah Fahran Al-Dulaimi and Hamza A. Ali", title = "Enhanced Traveling Salesman Problem Solving by Genetic Algorithm Technique (TSPGA)", 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.", volume = "2", number = "2", pages = "102-7", }
