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

A New Dynamic Crossover Operator for TSP

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

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

出　　处：《计算机工程与应用》2004年第23期74-75,101,共3页Computer Engineering and Applications

基　　金：山西省青年科学基金(编号:20041017);太原重型机械学院青年基金资助

摘　　要：TSP(TravelingSalesmanProblem)问题是最经典的NP-hard组合优化问题之一。长期以来,人们一直在寻求快速、高效的近似算法,以便在合理的时间内解决大规模问题。论文在文犤5犦提出的两交换启发交叉算子的基础上,通过分析,发现该算子的杂交结果与所选择的首城市有关,因而不同的首城市的选择会大大影响该算子的效率,此外,在杂交母体范围内执行贪婪策略也导致了算法的效率较低。为此,提出了一种新的有效利用局部信息的杂交算子,该算子能够有效地保存母体信息,进一步摆脱首城市的选择问题。实例仿真证明了该算子的有效性。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 on2-exchange crossover heuristic introduced by Tang Lixin ,whose efficiency is relation with the selection of the first city and greedy selection strategy 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问题 动态杂交算子 NP-hard组合优化问题 两交换启发交叉算子 

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