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

摘要：

在分析了已有的求解TSP问题的优化算法后,提出了一种将建立基因库(Ge)与遗传算法结合起来的新算法(Ge_GA).该算法的目的是用基因库指导整个种群的进化,其核心问题是基因库的建立及如何将基因库运用到遗传算法中.试验结果表明,基因库有效地提高了群体演化的质量,局部搜索与全局搜索的结合大大提高了算法收敛速度.对于每个测试的实例,其结果与最优解的误差都不超过0.001%.特别是对难于求解的TSP问题,如pcb442和fl1577,都能够在理想的时间内找到最优解.

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

所属期刊栏目：30

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

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

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

页数：共3页

页码：60-62