解旅行商问题的一个新的遗传算法

A Novel Genetic Algorithm for Traveling Salesman Problem

对旅行商(TSP)问题设计了一个新的遗传算法.首先,对n个城市的旅行商问题设计了一个新的编码方法,并且对这种编码方法,给出了简便的解码方法.其次,针对编码的特点,设计了一种新的、有效的杂交算子和变异算子,这些算子均能直接产生可行的后代.为提高杂交算子的搜索能力,结合了一个局部搜索技术来改进杂交算子.在此基础上,提出了求解TSP的一个新的遗传算法,并证明了其全局收敛性.为了验证算法的有效性,对10个国际标准算例(城市规模从14到1000)进行了计算机仿真,结果表明算法是有效的.

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.