New Crossover Operator of Genetic Algorithms for the TSP

This paper describes a novel crossover operator, Cut-blend crossover, for a genetic algorithm for the TSP. Cut-blend crossover may be the best in such kind crossovers that improve a tour using a sub-tour extracted from other tour or tours (PMX, OX et al.). The proposed operators are embedded in a new genetic algorithm, which extracts sub-tours from a pool consisting of former best tours and current population, to compare with other crossovers. The operator is evaluated on a number of well-known benchmarks, e.g. oliver30, eil76, ch130 and pcb442 in the TSPLIB. Experimental results show that the new crossover is superior to the conventional crossovers such as OX, ER, especially in problems of larger scale.