一种基于遗传算法的TSP问题多策略优化求解方法

编号 zgly0001606991

文献类型 期刊论文

文献题名 一种基于遗传算法的TSP问题多策略优化求解方法

作者 孙文彬  王江 

作者单位 中国矿业大学(北京)地球科学与测绘工程学院 

母体文献 地理与地理信息科学 

年卷期 2016年04期

年份 2016 

分类号 TP18 

关键词 TSP问题  遗传算法  优化策略  2-Opt 

文摘内容 针对遗传算法求解TSP问题解质量不高的缺陷,该文提出并设计了一种基于遗传算法的多策略优化求解方法。首先,应用最邻近法构建TSP的初始解;接着将路径长度作为适应度评价指标,构建基于遗传算法的TSP初始解优化方法,并根据试验结果确定适合的遗传算法参数;然后,针对遗传算法易陷入局部最优的缺陷,借助去交叉和小角操作进一步优化TSP解路径;在此基础上,将遗传算法进行并行化处理,通过增加遗传算法的多样性提高TSP解质量。最后,应用标准测试集(TSPLIB)进行试验,结果表明:该算法能有效提高TSP解的质量,经并行遗传算法、去交叉和小角优化后各测试数据集TSP解误差率平均下降了22.57%;解的误差率均在7.94%以内,质量明显优于最邻近法、插入法、2-Opt优化等传统方法;在节点数多的测试数据集中算法也获得了良好加速性能,8进程时算法加速比达2.51。