| 基于路径共同顺序的TSP遗传算法 |
| |
| 引用本文： | 张金强,操云甫,王常青,戴国忠,杨富春.基于路径共同顺序的TSP遗传算法[J].计算机工程与应用,2004,40(20):58-61. |
| |
| 作者姓名： | 张金强 操云甫 王常青 戴国忠 杨富春 |
| |
| 作者单位： | 中科院软件研究所,北京,100080 |
| |
| 基金项目： | 国家863高技术研究发展计划基金(编号:2001AA414610，2002AA111080，2002AA414010) |
| |
| 摘 要： | 遗传算法是一种解决TSP问题的有效算法。文章提出了一种基于路径共同顺序的新型遗传操作方法,即首先寻找父辈的共有路径信息,然后构建后代,该方法缩小了搜索优解的范围,加快了优化过程的收敛速度。在此基础上针对TSP实例,实现了基于共同顺序的优化方法来解决小规模TSP问题,以及更有效的基于共同顺序的循环优化方法来解决大规模TSP问题。实验结果验证了该方法的有效性。
|
| 关 键 词： | 共同顺序 遗传算法 TSP |
| 文章编号： | 1002-8331-(2004)20-0058-04 |
A Genetic Algorithm Based on Common Path for TSP |
| |
| Zhang Jinqiang Cao Yunfu Wang Changqing Dai,Guozhong Yang Fuchun.A Genetic Algorithm Based on Common Path for TSP[J].Computer Engineering and Applications,2004,40(20):58-61. |
| |
| Authors: | Zhang Jinqiang Cao Yunfu Wang Changqing Dai Guozhong Yang Fuchun |
| |
| Abstract: | Genetic algorithm is a promising approach for solving Traveling Salesman Problem(TSP).This paper presents an original GA operator that first finds the common path of two parent paths and then constructs the child paths.This approach constructs offspring based on common path,decreases the search space of optima and accelerates optimal con-vergent rate.For TSP problems ,first an optimal method based on common path for TSP of small scale is given,then a more efficient method based on common path with loop optimization for TSP of large scale is given.Experiment analysis proves its efficacy. |
| |
| Keywords: | common path genetic algorithm TSP |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
