一种新的求解TSP问题的杂交算子  

A New Crossover Operator for TSP

作　　者：崔志华[1] 曾建潮[1] 徐玉斌[1] 

机构地区：[1]太原重型机械学院系统仿真与计算机应用研究所,山西太原030024

出　　处：《航空计算技术》2003年第4期12-14,共3页Aeronautical Computing Technique

基　　金：山西省自然科学基金资助(20031041)

摘　　要：TSP(TravelingSalesmanProblem)问题是最经典的NP-hard组合优化问题之一。长期以来,人们一直在寻求快速、高效的近似算法,以便在合理的时间内解决大规模问题。在文[5]提出的两交换启发交叉算子的基础上,通过分析,发现该算子的杂交结果与所选择的首城市有关,因而不同的首城市的选择会大大影响该算子的效率。为此,提出了一种新的有效利用局部信息的杂交算子,该算子能够有效的保存母体信息,进一步摆脱首城市的选择问题。实例仿真证明该算子的有效性。The TSP (Traveling Salesman Problem) is one of the typical NP-hard problems in combinatorial optimization problem. The fast and effective approximate algorithms are needed to solve the large-scale problem in reasonable computing time. Based on 2-exchange crossover heuristic introduced by Tang Li-xin, whose efficiency is relation with the first city greatly, a new crossover operator is conducted using the local information effectively and being little relation with the first city. The optimization computing of some examples is made to show that the new crossover operator is useful and simple.

关 键 词：旅行商问题 TSP问题 杂交算子 遗传算法 城市 路径优化 

分 类 号：O221[理学—运筹学与控制论]