基于改进郭涛算法的TSP问题求解

摘要：

郭涛算法可能是目前求解TSP问题最快的演化算法[1],其算法的核心在于Inver-over算子的设计,但在城市规模超过80时,该算子寻找全局最优解的能力就会下降.将原Inver-over算子的线性逆转改为环形逆转,改进逆转方式后,被逆转的基因片段可以包括整个染色体,这样能有效地防止解的早熟.同时,在原算法的基础上,引入了映射模块,能使父代中好的基因片段得到遗传,使好的基因片段能让更多的染色体所享有,不会因为父代被替代而让好的基因模式丢失.实验表明:改进后的算法增强了原Inver-over算子对最优解的搜索能力,并且对TSPLB中大部分实例均可搜索到最优解.

关键词：遗传算法、郭涛算法、Inver-over算子、TSP、基因映射

所属期刊栏目：27

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

资助基金：中国科学院资助项目60483081

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

页数：共3页

页码：744-745,751