Criteria for designing crossovers for TSP
Yuichi Nagata · 2005
This work proposes criteria for designing crossovers for genetic algorithms (GAs) used to solve traveling salesman problems (TSPs). These criteria are [1] that the ratio at which new edges are introduced into offspring by crossovers should be adjusted appropriately and [2] that the quality of the new edges should be high. The validity of these criteria is demonstrated by comparing several crossovers that were designed for TSP with regard to these criteria. Experimental results indicate that the performances of GAs using some previously proposed crossovers can be explained by considering these criteria. Furthermore, experiments with a new crossover designed by modifying a very simple crossover called edge recombination (EX) in accordance with these criteria demonstrate that the performance of the GA using this modified crossover is improved dramatically.