| 引入基因簇求解TSP的遗传算法 |
| |
| 引用本文： | 马光志,卢炎生,宋恩民,汤海先. 引入基因簇求解TSP的遗传算法[J]. 计算机科学, 2009, 36(6): 248-250 |
| |
| 作者姓名： | 马光志 卢炎生 宋恩民 汤海先 |
| |
| 作者单位： | 华中科技大学计算机科学与技术学院,武汉,430074 |
| |
| 基金项目： | 国家高技术研究发展计划(863计划) |
| |
| 摘 要： | 在用遗传算法求解TSP时,极易破坏已经发现的较短线路片段,从而使遗传算法的收敛变慢.为了保护较短的线路片段,遗传操作以基因和基因簇为单位进行,优良基因簇可完整地遗传到下一代.在获得第一个近似最优解后,粉碎已发现的基因簇并继续寻优,以期能够获得全局最优解.使用CHN144及TSPLIB中的数据进行试验,找到了CHN144问题的当前最优路径.通过对TSP225的实验获得了最短路径3859,优于目前已经公布的最短路径3916.实验表明,基于基因簇的算法具备3000个城市左右的寻优能力.
|
| 关 键 词： | 旅行商问题 基因簇 遗传算法 |
| 收稿时间： | 2008-08-22 |
| 修稿时间： | 2008-11-06 |
Using Gene Clusters for TSP Solving Genetic Algorithm |
| |
| MA Guang-zhi,LU Yan-sheng,SONG En-min,TANG Hai-xian. Using Gene Clusters for TSP Solving Genetic Algorithm[J]. Computer Science, 2009, 36(6): 248-250 |
| |
| Authors: | MA Guang-zhi LU Yan-sheng SONG En-min TANG Hai-xian |
| |
| Affiliation: | School of Computer Science & Technology;Huazhong University of Science and Technology;Wuhan 430074;China |
| |
| Abstract: | When a genetic algorithm is used to solve the TSP(Traveling Salesman Problem),shorter paths found before are accessible to be destroyed,and thus the convergence of the genetic algorithm slows down.To prevent the shorter paths from being destroyed,the gene cluster was introduced into genetic operations so that the superior gene piece can be wholly inherited to descendent off-springs.After a near optimum is found,all gene clusters are smashed and the optimum finding process is continued for global optimums.Ex... |
| |
| Keywords: | Traveling salesman problem Gene cluster Genetic algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
点击此处可从《计算机科学》下载全文 |
|
