Genetic algorithms (GAs) are randomized parallel search algorithms that search from a population of points [6]. We typically randomly initialize the starting population so that a genetic algorithm can proceed from an unbiased sample of the search space. However in many application areas we confront sets of similar problems. It makes little sense to start a problem solving search attempt from scratch with a random initial population when previous search attempts may have yielded useful information about the search space. Instead, seeding a genetic algorithm's initial population with solutions to similar previously solved problems can provide information (a search bias) that, hopefully, increases the efficiency of the search.
Genetic algorithms have been used to solve large TSPs and can get good solutions quickly [3, 6, 7]. The first efforts to find near optimal solutions to TSPs by using GAs were those of Goldberg using Partial Mapped Crossover [4] and Grefenstette using Greedy Crossover [5]. Davis, Smith, Suh and Van Gucht also tried to solve TSPs with various crossover operators [1, 10, 11]. In this paper, we present evidence to show that augmenting genetic algorithms with a memory of solutions to previously solved similar traveling salesman problems results in better performance than running a genetic algorithm with random initialization. Ramsey and Grefenstette come closest to our approach and use case-based initialization to increase a genetic algorithm's performance in an environment that changes with time [8]. Although they report encouraging results on non-stationary functions, their work does not address the effect of similarity on performance that is addressed in this paper. In the next few sections we describe the genetic operators, our methodology, and results.