求解TSP的启发式顺序交叉算子  

Heuristic ordered crossover operator for TSP

作　　者：周鹏[1] 

机构地区：[1]湖北汽车工业学院,湖北十堰442002

出　　处：《计算机工程与设计》2007年第8期1896-1897,1900,共3页Computer Engineering and Design

基　　金：湖北省教育厅科学技术研究基金项目(B200623002)

摘　　要：旅行商问题是经典的NP难组合优化问题之一。在用遗传算法求解旅行商问题时,顺序交叉算子是一种较为常用的遗传交叉算子。使用顺序交叉算子时的交叉点位置是随机指定的,不能反映关键遗传信息,导致算法执行效率较低。在顺序交叉算子的基础上,提出了一种启发式顺序交叉算子。该算子结合顺序交叉算子和启发式算法以得到双亲中交叉点位置,保留了双亲中关键的城市顺序信息。该算子改善了使用顺序交叉算子执行效率低的问题。实验结果表明了该算子的有效性。Traveling salesman problem is one of the typical NP-hard problems in combinatorial optimization.Ordered crossover operator is a kind of in common use genetic crossover operator to solve traveling salesman problem. But when ordered crossover operator is used,the points of intersection are specified randomly. The points can＇t reflect the key genetic information and cause the calculate way efficiency is lowly. Based on ordered crossover operator, a new heuristic ordered crossover operator is presented. It combines ordered crossover operator and heuristic algorithm in order to get the position of cut points in parent, thereby key order information from parent is saved. This improved operator can overcome the shortcoming of low efficiency in ordered crossover operator. The optimization computing of some examples is made to show that the new operator is useful and simple.

关 键 词：旅行商问题 组合优化 遗传算法 遗传算子 启发式顺序交叉算子 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]