A new encoding based genetic algorithm for the traveling salesman problem

The combination of genetic algorithm and local search has been shown to be an effective approach to solve the traveling salesman problem. In this article, a genetic algorithm based on a novel encoding scheme which converges to a global optimal solution with probability 1 is proposed, in which a new local search scheme is combined into the proposed genetic algorithm. In the proposed algorithm, a new chromosomal encoding scheme and a new crossover operator are described and a new local search scheme is used to improve the quality of the offspring generated by the crossover. The new local search scheme is not an exact local optimization algorithm, but a scheme that can generate good enough solutions using much less computation than general local optimization search algorithms. Moreover, both the crossover operator and the local search scheme are very easy to execute, and the offspring generated by them always represent valid tours. Furthermore, the convergence of the proposed algorithm to a globally optimal solution with probability 1 is proved. Finally, the experimental results on nine standard benchmark problems show the efficiency of the proposed algorithm.