Complex Systems

Schema Analysis of the Traveling Salesman Problem Using Genetic Algorithms Download PDF

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.