A Novel Genetic Algorithm for Traveling Salesman Problem
解旅行商问题的一个新的遗传算法

A novel genetic algorithm is proposed in this paper for solving traveling salesman problem(short for TSP).First,a new encoding schema and decoding schema are designed for TSP.Second,an efficient crossover and a mutation operator are designed according to the character of the encoding scheme.In order to enhance its ability of exploration,a novel local search scheme is integrated into the crossover operator.Based on these,a novel and effective evolutionary algorithm for TSP is presented and its convergence to global optimal solution with probability one is proved.The proposed algorithm was evaluated on 10 standard test problems in which the numbers of cities range from 14 to 1000.Experimental results indicate that the proposed algorithm performs well and is very competitive with other algorithms.