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

被引：39

作者：

杨辉

康立山

陈毓屏

机构：

[1] 武汉大学软件工程国家重点实验室

来源：

计算机学报 | 2003年 / 12期

关键词：

遗传算法; 基因库; 最小生成树; 组合优化; 旅行商问题;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

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

引用

页码：1753 / 1758

页数：6