Research Article Open Access

Solving the Traveling Salesman Problem Using New Operators in Genetic Algorithms

Naef Taher Al Rahedi1 and Jalal Atoum2
  • 1 , Afganistan
  • 2 ,
American Journal of Applied Sciences
Volume 6 No. 8, 2009, 1586-1590

DOI: https://doi.org/10.3844/ajassp.2009.1586.1590

Submitted On: 10 June 2009 Published On: 31 August 2009

How to Cite: Al Rahedi, N. T. & Atoum, J. (2009). Solving the Traveling Salesman Problem Using New Operators in Genetic Algorithms. American Journal of Applied Sciences, 6(8), 1586-1590. https://doi.org/10.3844/ajassp.2009.1586.1590

Abstract

Problem statement: Genetic Algorithms (GAs) have been used as search algorithms to find near-optimal solutions for many NP problems. GAs require effective chromosome representations as well as carefully designed crossover and mutation operators to achieve an efficient search. The Traveling Salesman Problem (TSP), as an NP search problem, involves finding the shortest Hamiltonian Path or Cycle in a graph of N cities. The main objective of this study was to propose a new representation method of chromosomes using upper triangle binary matrices and a new crossover operator to be used as a heuristic method to find near-optimum solutions for the TSP. Approach: A proposed genetic algorithm, that employed these new methods of representation and crossover operator, had been implemented using DELPHI programming language on a personal computer. Also, for the purpose of comparisons, the genetic algorithm of Sneiw had been implemented using the same programming language on the same computer. Results: The outcomes obtained from running the proposed genetic algorithm on several TSP instances taken from the TSPLIB had showed that proposed methods found optimum solution of many TSP benchmark problems and near optimum of the others. Conclusion: Proposed chromosome representation minimized the memory space requirements and proposed genetic crossover operator improved the quality of the solutions in significantly less time in comparison with Sneiw's genetic algorithm.

  • 1,545 Views
  • 1,885 Downloads
  • 4 Citations

Download

Keywords

  • Chromosomes representation
  • crossover operator
  • mutation operator
  • upper triangle binary matrix