Analysis of TSP Optimization Problems using Genetic Algorithm

Aparna; Waseem Ahmad

doi:https://doi.org/10.51976/ijari.221404

Submit Manuscript Login / Register Subscribe

Home Page

Editorial Advisory Board

Mission, Aims & Scope

Current Issue

Analysis of TSP Optimization Problems using Genetic Algorithm

Aparna , Waseem Ahmad

Vol 2 , Issue 2 , April - June 2014 | Pages: 21-28 | Research Paper

https://doi.org/10.51976/ijari.221404

Received: January 05, 2014 | Revised: February 20, 2014 | Accepted: February 28, 2014 | Published Online: June 15, 2014

Author Details ( * ) denotes Corresponding author

1. * Aparna Department of Computer Science & Engineering, AFSET, Faridabad, Haryana, India (tomaraparna030@gmail.com)

2. Waseem Ahmad, Department of Computer Science & Engineering, AFSET, Faridabad, Haryana, India

Initiation of this paper demarcates Genetic Algorithm, as it paradigm shift in soft computing to solve optimization problems. This paper perposed the application of GAs to TSP by examining combinations on different algorithms for the binary and unary operators used to generate better solutions and minimize the search space calls. Operational view of genetic Algorithm to solve TSP. This paper describes the number of crossover operators and mutation operators that can be applied with path representation in order to solve TSP. The TSP is, given a collection of cities, the problem is to determine the shortest route which visits each city precisely once and then returns to its starting point.TSP is complex as it is a NP-complete problem. This literature proposes a heuristic approach for solving TSP with Genetic Algorithm as TSPGA. Genetic algorithm (GA’s) has been used as search techniques on many NP (Non-Deterministic Polynomial Time) problems. Three binary and two unary operators were tested: To find shortest path that travels through every city in a provided set of cities exactly once and travels back to the initial city. It is a faster solution but not necessarily an optimal solution.

Keywords

Genetic Algorithms (GA); Mutation Operator; Crossover Operator TSPGA

D. L. Applegate, R. E. Bixby, V. Chvátal, W. J. Cook, The Traveling Salesman Problem A Computational Study. Princeton University Press, 2006

Schrijver, Alexander, On the history of combinatorial optimization, Handbook of Discrete Optimization (K. Aardal, G. L. Nemhauser, R. Weismantel, eds.), Elsevier, Amsterdam, 2009, 1-68

E. L. Lawler, J. K. Lenstra, A. H. G Rinnooy Kan, D. B. Shmoys, The Traveling Salesman Problem A Guided Tour of Combinatorial Optimization, Wiley address Interscience, Chichester, 1985

P. Moscato, 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, 187 –194.

M. Lalena, Traveling Salesman Problem Using Genetic Algorithms. http //www.lalena.com/ai/tsp/, 2011

D. Whitley, 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, 219 – 228.

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, 399 – 404

D. E. Goldberg, Genetic Algorithm in Search, Optimization and Machine Learning, Machine Learning. Addison-Wesley, New York, 1989

P. Larranaga, C. M. H. Kuijpers, R. H. Murga, I. Inza, S. Dizdarevic, Genetic Algorithms for the Travelling Salesman Problem A Review of Representations and Operators, Artificial Intelligence Review. 13, 1999, 129-170.

S. R. Shubhra, B. Sanghamitra, K. Pal. Sankar, New Operators of Genetic Algorithms for Traveling Salesman Problem, IEEE, 0-7695-2128-2/04, 2004.

Ji. Ping, Ho. William, The Traveling Salesman and the Quadratic Assignment Problem Integration, Modeling and Genetic Algorithm, Int. Symposium on OR and its Applications, 2005, 198-205

C. Ding, Ye. Cheng, M. He, Two-Level Genetic Algorithm for Clustered Traveling Salesman Problem with Application in Large-Scale TSPs”, Tsinghua Science and Technology, 12(4), 2007, 59-465

P. Borovska, T. Ivanova, H. Salem, Efficient Parallel Computation of the Traveling Salesman Problem on Multicomputer Platform, Proceedings of the International Scientific Conference ‘Computer Science’ 2004, Sofia, Bulgaria, 2004, 74-79

R. Gremlich, A. Hamfelt, H. de Pereda, V. Valkovsky, Genetic Algorithms with Oracle for the Traveling Salesman Problem”, proceedings of world academy of science, Engineering and Technology, 2005, 1307-6884

Q. Jiang, R. Sarker, H. Abbass, Tracking moving targets in the nonstationary travelling salesman problem,” Complexity International, 11, 2005, 171-179

V. Lawrence, A. Snyder, M. S. Daskin, A random-key genetic algorithm for the generalized traveling salesman problem, Available online since, 2005

M. Bakhouya, J. Gaber, An Immune Inspired-based Optimization Algorithm Application to the Traveling Salesman Problem, AMO, Advanced Modeling and Optimization, 9(1), 2007

B. P. Buckles, P. E. Petry, R. I. Kuester, Schema Survival Rates and Heuristic Search in Genetic Algorithms, IEEE, 1990, 86-91

D. T. Phillips, A. Rarindran, J. J. Solberg, Operations Research Principles and Practice”, John Wiely and Sons Inc, 1976

D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Addison Wesley Publishing Company Inc. 1989.

Naef Taher Al Rahedi, Jalal Atoum, Solving the Traveling Salesman Problem Using New Operators in Genetic Algorithms, American Journal of Applied Sciences 6 (8) 1586-1590, 2009