An Improved Adaptive Multi-Start Approach to Finding Near-Optimal Solutions to the Euclidean TSP
Dan Bonachea · eScholarship (California Digital Library) · 2000
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. [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. 1 BACKGROUND 1.1 THE TSP In the traveling salesman problem (TSP) we are given n points (or "cities") c1; : : : ; cn and a positive distance d(ci; cj) for each distinct pair of cities. Our goal is to find an ordering ss, or tour, of the cities that minimizes the length of the tour, d(css(n); css(1)) + Pn\\Gamma 1 i=1 d(css(i); css(i+1)). We will restrict our attention to the two-dimensional Euclidean TSP, which is the special case where the cities are points in the plane and d(ci; cj) is the Euclidean distance from ci to cj. This optimization problem is NP-hard.