Memetic Algorithms for the Traveling Salesman Problem
Peter Merz
Electronic mail address: peter.merz@ieee.org.
Department of Computer Science,
University of Tübingen,
Sand 1, D--72076 Tübingen, Germany
Bernd Freisleben
Electronic mail address: freisleb@informatik.uni-marburg.de.
Department of Mathematics and Computer Science,
University of Marburg,
Hans-Meerwein-Straße,
D-35032 Marburg, Germany
Abstract
Memetic algorithms (MAs) have been shown to be very effective in finding near-optimum solutions to hard combinatorial optimization problems. In this paper, the fitness landscapes of several instances of the traveling salesman problem (TSP) are investigated to illustrate why MAs are well-suited for finding near-optimum tours for the TSP. It is shown that recombination-based MAs can exploit the correlation structure of the landscape. A comparison of several recombination operators--including a new generic recombination operator--reveals that when using the sophisticated Lin-Kernighan local search, the performance difference of the MAs is small. However, the most important property of effective recombination operators is shown to be respectfulness.
In experiments it is shown that our MAs with generic recombination are among the best evolutionary algorithms for the TSP. In particular, optimum solutions could be found up to a problem size of 3795, and for larger instances up to 85,900 cities, near-optimum solutions could be found in a reasonable amount of time.
