Abstract: Genetic Algorithm is an important method for solving Traveling Salesman Problem. In order to improve the algorithm’s rate, some special crossover operators are needed, such as partially matched crossover, cycle crossover and ordered crossover. In this paper, an improved GA is proposed for natural number encoding scheme. It will guarantee the rapid convergence of GA to use an improved ordered crossover_ dissimilar ordered crossover, which makes the offspring inherits the best arrange of its parents. Otherwise, steady state reproduction without duplicates is used to avoid precocity. The results show that the proposed algorithm is effective for both TSP and DHC.

Key words: Traveling Salesman Problem, Genetic Algorithm, Crossover Operators, Ordered Crossover

摘要： 利用遗传算法求解TSP问题，通常需要使用PCX，CX和OX等特殊的交叉算子以提高算法的运行效率。本文针对自然数编码的方式，提出一种改进的遗传算法，即改进传统的顺序交叉算子，进行不相同子排列顺序交叉，使子代继承父代中优秀的子排列，加快算法的收敛速度。另外，采用没有重复的稳态繁殖避免早熟。实验结果表明，此改进算法对于TSP和DHC问题均具有较好的性能。

关键词: 旅行商问题, 遗传算法, 交叉算子, 顺序交叉