引入基因簇求解TSP的遗传算法

• 作者: 卢炎生 宋恩民 汤海先 马光志
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: 旅行商问题 基因簇 遗传算法
• 年，卷（期）: 2009,（6）
• 所属期刊栏目: 人工智能
• 页码范围: 248-250
• 页数: 3页
• 分类号: TP18
• 字数: 3101字
• 语种: 中文
• DOI: 10.3969/j.issn.1002-137X.2009.06.067

摘要

在用遗传算法求解TSP时,极易破坏已经发现的较短线路片段,从而使遗传算法的收敛变慢.为了保护较短的线路片段,遗传操作以基因和基因簇为单位进行,优良基因簇可完整地遗传到下一代.在获得第一个近似最优解后,粉碎已发现的基因簇并继续寻优,以期能够获得全局最优解.使用CHN144及TSPLIB中的数据进行试验,找到了CHN144问题的当前最优路径.通过对TSP225的实验获得了最短路径3859,优于目前已经公布的最短路径3916.实验表明,基于基因簇的算法具备3000个城市左右的寻优能力.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	卢炎生	华中科技大学计算机科学与技术学院	216	1989	20.0	34.0
2	马光志	华中科技大学计算机科学与技术学院	34	283	11.0	15.0
3	宋恩民	华中科技大学计算机科学与技术学院	26	266	8.0	15.0
4	汤海先	华中科技大学计算机科学与技术学院	1	3	1.0	1.0