一种基于构建基因库求解TSP问题的遗传算法

• 作者: 康立山 杨辉 陈毓屏
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 遗传算法 基因库 最小生成树 组合优化 旅行商问题
• 年，卷（期）: 2003,（12）
• 所属期刊栏目: 短文
• 页码范围: 1753-1758
• 页数: 6页
• 分类号: TP301
• 字数: 5595字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2003.12.021

摘要

传统的遗传算法通常被认为是自适应的随机搜索算法.该文在分析其特点后针对TSP问题提出了一种将建立基因库(Ge)与遗传算法结合起来的新算法(Ge_GA).该算法利用基因库指导种群的进化方向,并在此基础上使用全局搜索算子和局部搜索算子增强遗传算法的"探测"和"开发"能力.Ge_GA算法大大加快了遗传算法的收敛速度和寻优能力.作者测试了TSPLIB中的多个实例(城市数目从70～1577),试验结果与最优解的误差都不超过0.001%.特别是对于难求解的TSP问题,如att532和fl1577,都能够在理想的时间内找到最优解.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	康立山	武汉大学软件工程国家重点实验室	127	2409	27.0	44.0
2	陈毓屏	武汉大学软件工程国家重点实验室	47	670	15.0	25.0
3	杨辉	武汉大学软件工程国家重点实验室	18	115	4.0	10.0