Edge Assembly Crossover with Tabu for Traveling Salesman Problem

This paper proposes a new tabu technique to enhance the search performance of edge assembly crossover (EAX). EAX is known as the most promising recombination operator for the traveling salesman problem (TSP) among population-based evolutional approaches such as genetic algorithm (GA). It succeeds in generating a sophisticated combination of parents' traits and makes GA comparable to state-of-the-art heuristics for the TSP. EAX can find the optimal in very large instances, however, it sometimes does not work well on instances involving a lattice pattern. This is because, in the instance including cities that are arranged in a lattice pattern, it is difficult to find the best tour due to the existence of many alternative candidate tours. In instances that include such patterns, the diversity of edges in the population is decreased because the EAX concentrates and repeats exchanging edges in this local pattern, and pays less attention to combinations of edge globally. In this paper, we improve EAX itself by introducing a tabu scheme to inhibit repeating the exchange of the same edges in order to reduce the bias of edge to be exchanged between parents and enhance the diversity in offspring. Numerical experiments show the search performance of our new method in the instances selected from TSPLIB and VLSI TSP.