Using Genetic Algorithms with memory to solve Traveling Salesman Problems

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

Abstract:

This paper uses modified genetic algorithms to attack the traveling salesman problem. Instead of starting from scratch, we inject the solutions of previously solved similar problems into the initial population of the genetic algorithm. We evaluate the performance of the genetic algorithm with a memory of previously solved similar problems on a number of traveling salesman problems. Preliminary results indicate that we can always get better performance with injection of previous solutions to similar problems.

• Introduction and Background
• Genetic Algorithms
• Modified GAs for TSPs
  • Encoding
  • Crossover
  • Mutation
  • Selection
• Methodology
• Results and Analysis
  • Results
  • Analysis
• Conclusion and Future Work
• Acknowledgments
• References
• Appendix A
  • Same problem
  • Change one city problem
  • Change two cities problem
  • Add one city problem
  • Delete one city problem
  • Performance comparison tables
• About this document ...