Lawrence Berkeley National Laboratory

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. [2]. 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 [5] 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.