An Improved Genetic Algorithm Crossover Operator for Traveling Salesman Problem

Abstract

The genetic algorithm is one of the best algorithms in order to solve many combinatorial optimizationproblems, especially traveling salesman problem. The application of genetic algorithms to problems which are notamenable to bit string representation and traditional crossover has been a growing area of interest. One approachhas been to represent solutions by permutations of a list, and permutation crossover operators have been introducedto preserve the legality of offspring. There are many existing schemes for permutation representation like PMX,OX, and CX etc. In this paper, we extend the CX scheme which produces healthy offspring based on survival of thefittest theory. Comparison of the proposed operator with other ones for ten benchmarks TSPLIB instances vividlyshow its pros at the same accuracy level. Also, it requires less time for tuning of genetic parameters and providesnarrower confidence intervals on the results than other operators.