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

摘要：

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

关键词：遗传算法、基因库、最小生成树、组合优化、旅行商问题

所属期刊栏目：26

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金70071042,60073043,60133030

在线出版日期：2004-04-09（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：1753-1758