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. Exact methods, like cutting planes, branch and bound [Padberg 87], can only optimally 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.
A genetic algorithm can also be used to 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 a genetic algorithm injected with solutions to 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, our methodology, results, and conclusions.