Meta Heuristic Optimization of TSP using Genetic Algorithm

Richa Singh; Suraiya Parveen; Aparna

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

Submit Manuscript Login / Register Subscribe

Home Page

Editorial Advisory Board

Mission, Aims & Scope

Current Issue

Meta Heuristic Optimization of TSP using Genetic Algorithm

Richa Singh, Suraiya Parveen, Aparna

Vol 2 , Issue 1 , January - March 2014 | Pages: 42-45 | Research Paper

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

Received: February 02, 2014 | Revised: January 29, 2014 | Accepted: February 20, 2014 | Published Online: March 15, 2014

Author Details ( * ) denotes Corresponding author

1. * Richa Singh, Department Of Computer Science and Engineering, Jamia Hamdard, Faridabad, Uttar Pradesh, India (itrichasingh@gmail.com)

2. Suraiya Parveen, Department Of Computer Science and Engineering, Jamia Hamdard, Faridabad, Uttar Pradesh, India

3. Aparna Department Of Computer Science and Engineering, Jamia Hamdard, Faridabad, Uttar Pradesh, India

Initiation of this paper demarcates the limits of artificial intelligence, as it calls artificial intelligence a science for its extensibility and genetic algorithm to provide an affable decision to solve a popular routing problem named as Travelling Salesman Problem. This study will help more in moving to a world where a computer will be able to program based on natural selection and evolution. The travelling salesperson (or, salesman) problem (TSP) is an important combinatorial optimization problem. A combinatorial optimization problem helps to find an optimal object from a finite set of objects which does not follows an exhaustive search but the set of feasible solution is discrete. TSP aims to find the shortest path that travels through every city in a provided set of cities exactly once and travels back to the initial city using genetic algorithm. TSP is complex as it is a NP-complete problem. This literature proposes a heuristic approach for solving TSP: To find shortest path that travels through every city in a provided set of cities exactly once and travels back to the initial city. Proposed solution will provide a faster solution but not necessarily an optimal solution.

Keywords

Heuristic; Combinatorial problem; Genetic Algorithm; Travelling Salesman Problem

R. A. Brooks, Intelligence without representation, Artif. Intell, 47 (19’31) 139-159.

D. A. Pomerleau, J. Gowdy C. E. Thorpe, Combining artificial networks and symbolic processing for autonomous robot guidance, J. Eng. Appl. Artif. Intell. 4 (1991) 961-967

D. Waterman, Generalization learning techniques for automating the learning of heuristics, Artif.Intell. 1 (1970) 120-170.

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

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

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

M. Gendreau, A. Hertz, G. Laporte, “A tabu search heuristic for the vehicle routing problem”, Management Science 40(1984) 1276–1290

Kuk-Hyun Han Genetic quantum algorithm and its application to combinatorial optimization problem 0-7803-637 5-2 [9] S. R. Shubhra, B. Sanghamitra, K. Pal. Sankar, “New Operators of Genetic Algorithms for Traveling Salesman Problem”, IEEE, 0-7695-2128-2/04, 2004

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

Buthainah Fahran Al-Dulaimi, Hamza A. Ali, “Enhanced Traveling Salesman Problem Solving by Genetic Algorithm Technique (TSPGA)”, World Academy of Science, Engineering and Technology 38 2008