Computer Engineering and Applications ›› 2008, Vol. 44 ›› Issue (9): 37-39.

• 理论研究 • Previous Articles     Next Articles

Improved heuristic crossover operator for TSP

ZHOU Cong,ZHENG Jin-hua   

  1. Institute of Information and Engineering,Xiangtan University,Xiangtan,Hunan 411105,China
  • Received:2007-09-18 Revised:2007-12-03 Online:2008-03-21 Published:2008-03-21
  • Contact: ZHOU Cong

一种改进的TSP启发交叉算子

周 聪,郑金华   

  1. 湘潭大学 信息工程学院,湖南 湘潭 411105
  • 通讯作者: 周 聪

Abstract: TSP(Traveling Salesman Problem) is one of the typical NP_hard problem in combination optimization.For solving the problem,genetic algorithm is better than traditional ones obviously,and there are also many crossover operators used to get hypo-optimization route.Based on heuristic crossover by Tanglixin,a new crossover operator is conducted.The crossover preserver the snippet of effective genes,and a moving window is used to fasten the algorithm convergence.The example shows that the new crossover operator is useful.

Key words: genetic algorithm, TSP, heuristic crossover, moving window, preserver genes snippet

摘要: 旅行商问题(TSP,Traveling Salesman Problem)是一种经典的NP组合优化问题。遗传算法在求解这类组合问题方面明显优于传统算法,同时也提出了许多求解较好路径的交叉算子。在对比分析唐立新提出的两种启发式交叉算法的基础上,提出了一种新的交叉算子。该算子通过判断父代的城市是否相邻来保存有效基因片断,通过加入一个移动的窗口来加快算法收敛。实验结果表明了该算子的有效性。

关键词: 遗传算法, TSP问题, 启发交叉算子, 移动窗口, 有效基因保留