A Comparative Study on Crossover Operators of Genetic Algorithm for Traveling Salesman Problem
Xin-Ai Dou, Qiang Yang, Xudong Gao, Zhenyu Lu, Jun Zhang
Abstract
Genetic algorithm (GA) has been successfully employed to solve the traveling salesman problem (TSP). In GA, the crossover operator makes crucial influence on its optimization effectiveness and efficiency in solving TSP. Therefore, many kinds of crossover operators have been proposed successively in the literature, but a systematic investigation of these operators has not ever been conducted. To fill this gap, this paper systematically compares 10 widely used crossover operators. By conducting extensive experiments on different TSP instances of different sizes, we investigate the optimization effectiveness of the 10 crossover operators in helping GA solve TSP. Experimental results demonstrate that the sequential constructive crossover (SCX) and the zoning crossover (ZX) are the two best crossover operators for GA to solve TSP. Hopefully, this comparative study could provide a guideline for readers and facilitate them to choose a suitable crossover operator for GA to solve TSP effectively.