Solving the Traveling Salesman Problem Using New Operators in Genetic Algorithms

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.