| 引用本文: | 潘亮,朱华勇,沈林成,等.利用几何结构求解欧氏平面TSP的改进遗传算法.[J].国防科技大学学报,2004,26(5):109-114.[点击复制] |
| PAN Liang,ZHU Huayong,SHEN Lincheng,et al.An Improved Genetic Algorithm to Solve the Euclidean Plane TSP by Using Geometry Structure[J].Journal of National University of Defense Technology,2004,26(5):109-114[点击复制] |
|
| |
|
|
| 本文已被：浏览 6717次 下载 6078次 |
| 利用几何结构求解欧氏平面TSP的改进遗传算法 |
| 潘亮, 朱华勇, 沈林成, 常文森 |
|
(国防科技大学 机电工程与自动化学院，湖南 长沙 410073)
|
| 摘要: |
| TSP是经典的组合优化问题。根据欧氏平面TSP最优环路的性质提出了子路径及相关的概念，利用点集凸壳设计了环路构造算法，并以点集Delaunay三角剖分图为启发信息设计了改进的遗传算法，通过中国144城市TSP等验证了算法的有效性。 |
| 关键词: 欧氏平面 TSP 凸壳 Delaunay三角剖分 遗传算法 |
| DOI： |
| 投稿日期：2004-04-06 |
| 基金项目:国家部委资助项目(2003-5130801-1-3) |
|
| An Improved Genetic Algorithm to Solve the Euclidean Plane TSP by Using Geometry Structure |
| PAN Liang, ZHU Huayong, SHEN Lincheng, CHANG Wensen |
|
(College of Mechatronics Engineering and Automation, National Univ. of Defense Technology, Changsha 410073, China)
|
| Abstract: |
| The TSP is a classic combinatorial optimization problem. According to the character of the optimal tour of Euclidean plane TSP problem, the sub-path and related notions are presented. A tour construction algorithm is designed by using convex hull, and a genetic algorithm is improved to solve the problem by using Delaunay triangulation diagram as heuristic information. The experimental results in the 144 cities in China and other TSP instances show that the algorithm is effective. |
| Keywords: Euclidean plane traveling salesman problem convex hull Delaunay triangulation genetic algorithm |
|
|
