求解TSP的一种改进遗传算法

摘要：

TSP问题是典型的NP-hard组合优化问题,GA是求解此类问题的一种方法.但它存在如何较快地找到最优解并防止"早熟"收敛的问题.文章针对上述问题并结合TSP问题的特点,提出了改进的遗传算法.它从相似性的思想出发,按适应值相似性将群体分级,在不同的级内采用不同的操作,产生数目不等的新解并利用加速算子使其更接近局部极小值.改进后的算法较好地解决了群体多样性与收敛性的矛盾.实验结果表明,该文算法的改进是有效的.

关键词：TSP问题、遗传算法、分级、精英选择策略、启发式交叉算子、贪婪倒位变异算子

所属期刊栏目：42

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

资助基金：中国科学院资助项目70371070/G0116;湖北省自然科学基金2004ABA029;上海市教委资助项目05EZ34;上海市重点学科建设项目T0502

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

页数：共3页

页码：91-93