Memetic Algorithms for the Traveling Salesman Problem
Peter Merz, Bernd Freisleben · 2001
this paper, the tness landscapes of several instances of the traveling salesman problem (TSP) are investigated to illustrate why MAs are well-suited for nding 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 dierence of the MAs is small. However, the most important property of eective 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 large instances up to 85,900 cities, near-optimum solutions could be found in a reasonable amount of time