|
|||||
|
|
| 引入基因簇求解TSP的遗传算法 | |
| 作者姓名： | 马光志 卢炎生 宋恩民 汤海先 |
| 作者单位： | 华中科技大学计算机科学与技术学院,武汉,430074 |
| 基金项目： | 国家高技术研究发展计划(863计划) |
| 摘 要： | 在用遗传算法求解TSP时,极易破坏已经发现的较短线路片段,从而使遗传算法的收敛变慢.为了保护较短的线路片段,遗传操作以基因和基因簇为单位进行,优良基因簇可完整地遗传到下一代.在获得第一个近似最优解后,粉碎已发现的基因簇并继续寻优,以期能够获得全局最优解.使用CHN144及TSPLIB中的数据进行试验,找到了CHN144问题的当前最优路径.通过对TSP225的实验获得了最短路径3859,优于目前已经公布的最短路径3916.实验表明,基于基因簇的算法具备3000个城市左右的寻优能力. |
| 关 键 词： | 旅行商问题 基因簇 遗传算法 |
| 收稿时间： | 2008-08-22 |
| 修稿时间： | 2008-11-06 |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |