计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (9): 37-39.
• 理论研究 • 上一篇 下一篇
周 聪,郑金华
收稿日期:
修回日期:
出版日期:
发布日期:
通讯作者:
ZHOU Cong,ZHENG Jin-hua
Received:
Revised:
Online:
Published:
Contact:
摘要： 旅行商问题（TSP，Traveling Salesman Problem）是一种经典的NP组合优化问题。遗传算法在求解这类组合问题方面明显优于传统算法，同时也提出了许多求解较好路径的交叉算子。在对比分析唐立新提出的两种启发式交叉算法的基础上，提出了一种新的交叉算子。该算子通过判断父代的城市是否相邻来保存有效基因片断，通过加入一个移动的窗口来加快算法收敛。实验结果表明了该算子的有效性。
关键词: 遗传算法, TSP问题, 启发交叉算子, 移动窗口, 有效基因保留
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启发交叉算子[J]. 计算机工程与应用, 2008, 44(9): 37-39.
ZHOU Cong,ZHENG Jin-hua. Improved heuristic crossover operator for TSP[J]. Computer Engineering and Applications, 2008, 44(9): 37-39.
0 / 推荐
导出引用管理器 EndNote|Ris|BibTeX
链接本文: http://cea.ceaj.org/CN/
http://cea.ceaj.org/CN/Y2008/V44/I9/37
