Schema Analysis of the Traveling Salesman Problem Using Genetic Algorithms
Abdollah Homaifar
Department of Electrical Engineering,
North Carolina A&T State University, Greensboro, NC, 27411, USA
Shanguchuan Guan
Department of Electrical Engineering,
North Carolina A&T State University, Greensboro, NC, 27411, USA
Gunar E. Liepins
Oak Ridge National Laboratory,
P.O. Box 2008, Oak Ridge, TN, 37831, USA
Abstract
This paper provides a substantial proof that genetic algorithms (GAs) work for the traveling salesman problem (TSP). The method introduced is based on an adjacency matrix representation of the TSP that allows the GA to manipulate edges while using conventional crossover. This combination, interleaved with inversion (2-opt), allows the GA to rapidly discover the best known solutions to seven of the eight TSP test problems frequently studied in the literature. (The GA solution is within 2% of the best known solution for the eighth problem.) These results stand in contrast to earlier tentative conclusions that GAs are ill-suited to solving TSP problems, and suggest that the performance of probabilistic search algorithms (such as GAs) is highly dependent on representation and the choice of neighborhood operators.
