Abstract: In order to solve the problem of low rate of success and small scale, by amending the original mapping operator and Inver-over operator and introducing differing operator, a new Evolutionary Algorithm(EA) to Traveling Salesman Problem(TSP) is got. According to the experimental results, the algorithm can find all instances’ optimal solution of experiments and the probability of getting the optimal solution is higher, while the IGT algorithm can only get that of partial instances. Comparison of variances shows the new algorithms is more stable and the T-test also shows the full advantages of the new algorithm.

Key words: Traveling Salesman Problem(TSP), Evolutionary Algorithm(EA), distance neighbor tabulation, differing operator

摘要： 针对IGT算法在求解旅行商问题(TSP)中存在的求解规模较小、求解成功概率较低等问题，通过改进原有映射算子及Inver-over算子并引入求异算子，提出一种新的求解TSP问题的演化算法。方差对比及T-test结果表明，与IGT算法相比，该算法可以求得概率较高的最优解，且稳定性也更好。

关键词: TSP问题, 演化算法, 距离近邻表, 求异算子

CLC Number: 

• TP311.52