An Improved Adaptive Multi-Start Approach to Finding Near-Optimal Solutions to the Euclidean TSP

Genetic and Evolutionary Computation Conference, GECCO-2000

Dan Bonachea
Eugene Ingerman
Joshua Levy
Scott McPeak

Abstract:

We present an "adaptive multi-start" genetic algorithm for the Euclidean traveling salesman problem that uses a population of tours locally optimized by the Lin-Kernighan algorithm.An all-parent cross-breeding technique, chosen to exploit the structure of the search space, generates better locally optimized tours. Our work generalizes and improves upon the approach of Boese et al.

Experiments show the algorithm is a vast improvement over simple "multi-start", i.e., repeatedly applying Lin-Kernighan to many random initial tours. Both for random and several standard TSPLIB instances, it is able to find nearly optimal (or optimal) tours for problems of several thousand cities  in a few minutes on a Pentium Pro workstation. We find these results are competitive both in time and tour length with one of the most successful  TSP algorithms, Iterated Lin-Kernighan.

Paper:

Bonachea, D., Ingerman, E., Levy, J., and McPeak, S., "An Improved Adaptive Multi-Start Approach to Finding Near-Optimal Solutions to the Euclidean TSP," Genetic and Evolutionary Computation Conference (GECCO-2000), July 2000. (Acrobat pdf) (PostScript  ps)

GECCO-2000 Presentation

Cool pictures of some TSP instances solved by AMS (click to enlarge):

2392-node graph from TSPLIB (pr2392)	1000-node uniform random graph	1615-node graph of our names  :-)

Source Code for AMS:

Version 1.8 - The version studied in the paper above
Version 2.8 - A new version with parallel capabilities and more diagnostic output options

Authors:

Related Links:

Concorde - a code for solving Traveling Salesman Problems
TSPBIB Home Page
TSPLIB
Our Original CS 270 Class Project
Genetic and Evolutionary Computation Conference, GECCO-2000