| 一种新的求解TSP问题的杂交算子 |
| |
| 引用本文： | 崔志华,曾建潮,徐玉斌.一种新的求解TSP问题的杂交算子[J].航空计算技术,2003,33(4):12-14. |
| |
| 作者姓名： | 崔志华 曾建潮 徐玉斌 |
| |
| 作者单位： | 太原重型机械学院,系统仿真与计算机应用研究所,山西,太原,030024 |
| |
| 基金项目： | 山西省自然科学基金资助(20031041) |
| |
| 摘 要： | TSP(TravelingSalesmanProblem)问题是最经典的NP-hard组合优化问题之一。长期以来,人们一直在寻求快速、高效的近似算法,以便在合理的时间内解决大规模问题。在文5]提出的两交换启发交叉算子的基础上,通过分析,发现该算子的杂交结果与所选择的首城市有关,因而不同的首城市的选择会大大影响该算子的效率。为此,提出了一种新的有效利用局部信息的杂交算子,该算子能够有效的保存母体信息,进一步摆脱首城市的选择问题。实例仿真证明该算子的有效性。
|
| 关 键 词： | 遗传算法 TSP问题 杂交算子 |
| 文章编号： | 1671-654X(2003)04-0012-03 |
| 修稿时间： | 2003年6月25日 |
A New Crossover Operator for TSP |
| |
| CUI Zhi-hua,ZENG Jian-chao,XU Yu-bin.A New Crossover Operator for TSP[J].Aeronautical Computer Technique,2003,33(4):12-14. |
| |
| Authors: | CUI Zhi-hua ZENG Jian-chao XU Yu-bin |
| |
| Abstract: | 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. |
| |
| Keywords: | genetic algorithm TSP problem crossover operator |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
