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

摘要：

遗传算法(GA)是基于生物进化论的一种全局优化搜索算法,是求解TSP问题的一种方法,但它存在如何较快地找到最优解并防止"早熟"收敛的问题.结合TSP问题最优解一般包含城市与其最近城市的相连的特点,提出了贪婪两点插入变异算子,改进了启发式杂交算子,并根据个体适应度与群平均适应度根据个体的适应度赋予不同的变异概率,使得较好的个体探测路径,较差个体开发新个体.对初始群体作局部优化提高其质量加快算法的收敛速度,最优个体连续几代一直保留,则采用局部微调算子使子代中的最优个体跳离局部解.通过实验分析,改进的算法能较快的收敛到TSP问题的已知最优解;其测试结果与国际标准测试库TSPLIB中的最优路径相比,或接近或优于.

关键词：遗传算法、TSP问题、贪婪变异算子、启发式杂交算子

所属期刊栏目：27

分类号：TP18(自动化基础理论)

资助基金：国家自然科学基金10501009;10661005

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

页数：共4页

页码：287-290