×

Memetic algorithms for the traveling salesman problem. (English) Zbl 1167.90693

Summary: 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.

MSC:

90C59 Approximation methods and heuristics in mathematical programming
68Q25 Analysis of algorithms and problem complexity
68T05 Learning and adaptive systems in artificial intelligence

Software:

Genocop; TSPLIB
PDFBibTeX XMLCite