计算机与现代化 ›› 2010, Vol. 1 ›› Issue (5): 33-35,3.doi: 10.3969/j.issn.1006-2475.2010.05.010
• 人工智能 • 上一篇 下一篇
王兴起，薛晓春
收稿日期:
修回日期:
出版日期:
发布日期:
WANG Xing-qi, XUE Xiao-chun
Received:
Revised:
Online:
Published:
摘要： TSP问题是一个经典的组合优化问题。本文采用基于凸多边形的插入方法来构造路径，然后使用调整算法对路径进行调整以缩短回路长度，最后采用遗传算法中的交叉算子，再对路径进行优化。实验结果表明，该算法具有较高精度和较强实用性。
关键词: 旅行商问题, 组合优化, 凸多边形, 交叉算子
Abstract: Traveling salesman problem(TSP) is a classic combinatorial optimization problem. This paper uses an insertion method which is based on convex polygon to form loop, then applies the adjustment algorithm to shorten the loop. At last the paper uses the crossover operator which is from the genetic algorithm to optimize the loop. The result of calculation shows that the method has high precision and good practicability.
Key words: TSP, combinatorial optimization, convex polygon, crossover operator
中图分类号:
TP301.6
王兴起;薛晓春. 一种求解欧式平面TSP问题的混合算法[J]. 计算机与现代化, 2010, 1(5): 33-35,3.
WANG Xing-qi;XUE Xiao-chun. A New Hybrid Algorithm to Solve Euclidean Plane TSP[J]. Computer and Modernization, 2010, 1(5): 33-35,3.
0 / / 推荐
导出引用管理器 EndNote|Ris|BibTeX
链接本文: http://www.c-a-m.org.cn/CN/10.3969/j.issn.1006-2475.2010.05.010
http://www.c-a-m.org.cn/CN/Y2010/V1/I5/33
