| 利用几何结构求解欧氏平面TSP的改进遗传算法 |
| |
| 引用本文： | 潘亮,朱华勇,沈林成,常文森.利用几何结构求解欧氏平面TSP的改进遗传算法[J].国防科技大学学报,2004,26(5):109-114. |
| |
| 作者姓名： | 潘亮 朱华勇 沈林成 常文森 |
| |
| 作者单位： | 国防科技大学机电工程与自动化学院,湖南,长沙,410073;国防科技大学机电工程与自动化学院,湖南,长沙,410073;国防科技大学机电工程与自动化学院,湖南,长沙,410073;国防科技大学机电工程与自动化学院,湖南,长沙,410073 |
| |
| 基金项目： | 国家部委资助项目(2003-5130801-1-3) |
| |
| 摘 要： | TSP是经典的组合优化问题。根据欧氏平面TSP最优环路的性质提出了子路径及相关的概念,利用点集凸壳设计了环路构造算法,并以点集Delaunay三角剖分图为启发信息设计了改进的遗传算法,通过中国144城市TSP等验证了算法的有效性。
|
| 关 键 词： | 欧氏平面 TSP 凸壳 Delaunay三角剖分 遗传算法 |
| 文章编号： | 1001-2486(2004)05-0109-06 |
| 收稿时间： | 4/6/2004 12:00:00 AM |
| 修稿时间： | 2004年4月6日 |
An Improved Genetic Algorithm to Solve the Euclidean Plane TSP by Using Geometry Structure |
| |
| PAN Liang,ZHU Huayong,SHEN Lincheng and CHANG Wensen.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. |
| |
| Authors: | PAN Liang ZHU Huayong SHEN Lincheng and CHANG Wensen |
| |
| Institution: | College of Mechatronics Engineering and Automation, National Univ. of Defense Technology, Changsha 410073, China;College of Mechatronics Engineering and Automation, National Univ. of Defense Technology, Changsha 410073, China;College of Mechatronics Engineering and Automation, National Univ. of Defense Technology, Changsha 410073, China;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 |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《国防科技大学学报》浏览原始摘要信息 |
| 点击此处可从《国防科技大学学报》下载免费的PDF全文 |
|
