Augmenting Genetic Algorithms with Memory to Solve Traveling Salesman Problems

Sushil J. Louis - Gong Li
- Dept. of Computer Science
University of Nevada,
Reno, NV 89557
sushil@cs.unr.edu
li_g@cs.unr.edu

Abstract:

This paper explores the feasibility of augmenting genetic algorithms with a long term memory. During a genetic algorithm run, we periodically store individuals in a database. When confronted with a new problem, instead of starting from scratch, we inject the solutions to previously solved similar problems (from the database) into the initial population of the genetic algorithm. We evaluate the performance of the genetic algorithm with such a long term memory on a set of benchmark traveling salesman problems. In addition, we compare the performance of these augmented genetic algorithms when trained on traveling salesman problems of varying similarity. Preliminary results indicate that we can always get better performance with injection of previous solutions to similar problems.

• Introduction
• The Traveling Salesman Problem
• Methodology
• Results and Analysis
• Conclusions
• Acknowledgments
• References
• About this document ...