The definition of a traveling salesman problem(TSP) is: given N cities, if a salesman starting from his home city is to visit each city exactly once and then return home, find the order of a tour such that the total distance traveled is minimum. The TSP is a classical NP-complete problem which has extremely large search spaces and is very difficult to solve. People have tried to use both exact and heuristic or probabilistic methods to solve the TSP. The exact methods, like cutting planes, branch and bound [Padberg 87], can only solve small sized problems while the heuristic or probabilistic methods, like 2-opt [Lin 73], Markov chain [Martin 91] and simulated annealing [Kirkpatrick 85] are good for large sized problems. But until now, there has been no one algorithm that can get an optimal solution for every TSP, and for most TSPs we do not know the optimal solution.
The genetic algorithm is also a heuristic method which can solve large TSPs and can get good solutions quickly. The first efforts to find near optimal solutions to TSPs by using GAs are those of Goldberg using Partial Mapped Crossover [Goldberg 85] and Grefenstette using Greedy Crossover [Grefenstette 85]. Davis, Smith, Suh and Van Gucht also tried to solve TSPs with various crossover operators [Davis 85] [Smith 85] [Suh 85]. In this paper, we present evidence to show that the performance of running a genetic algorithm with solutions of previously solved similar traveling salesman problems is better than that of running a genetic algorithm with randomly initialized individuals. In the next few sections, we describe genetic algorithms, how we modify a genetic algorithm to solve TSPs, the methodology of running GAs with solutions of previous similar problems, results, and conclusions.