Extended changing crossover operators to solve the traveling salesman problem.

In order to efficiently obtain an approximate solution of the traveling salesman problem (TSP), the use of extended changing crossover operators (ECXO) which can substitute for any crossover operator of genetic algorithms (GAs) and ant colony optimization (ACO) for another crossover operator at any time is proposed. In this investigation, ECXO uses both ACO or edge recombination crossover (EX) and edge exchange crossover (EXX) in the early generations in order to create local optimum subpaths, and it uses edge assembly crossover (EAX) to create a global optimum solution after a certain number of generations. In EX or ACO any individual or any ant determines the next city it visits from the lengths of the edges or the amounts of pheromone deposited on the edges, where the pheromone indicates the lengths of tours that other ants have completed, thus generating local optimum paths. In EXX, the generated paths converge to a provisional optimal path. In EAX, a parent exchanges edges with another parent to create subcyclic paths, before restructuring the total cyclic path by combining the subcyclic paths so as to minimize the distances between them. In this paper the validity of ECXO is experimentally verified by using medium-sized problems from TSPLIB, and it is shown that ECXO can find the best solution earlier than EAX. © 2010 Wiley Periodicals, Inc. Electron Comm Jpn, 93(7): 1–16, 2010; Published online in Wiley InterScience (<URL>www.interscience.wiley.com</URL>). DOI 10.1002/ecj.10313 [ABSTRACT FROM AUTHOR]