一种并行ACS-2-opt算法处理TSP问题的方法

摘要：

针对基本ACS算法模型求解TSP问题的缺陷,对ACS算法添加2-opt邻域搜索策略,增强算法对TSP问题解的构造能力,提高算法对TSP问题的求解精度.同时,根据ACS算法易于并行化的特点,使用并行化ACS算法与算法参数优化混合方案,提高ACS算法求解TSP问题的速度.最终实现了对中等规模TSP问题具有较好求解性能的并行ACS-2-opt算法.实验结果表明,2-opt策略对于提升ACS算法的求解精度具有明显的效果;采用不同参数设定信息素启发因子时,求解时间具有较大差异;在采用节点距离倒数作为期望启发值时,ACS算法模型呈现退化性;在并行条件下,ACS-2-opt算法处理TSP问题时具有良好的并行性能.

关键词：2-opt邻域搜索策略、ACS算法、TSP问题、并行计算

所属期刊栏目：45

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

资助基金：国家自然科学基金项目61502165;湖南省教育厅一般项目17C0959;湖南师范大学青年基金项目11404;湖南师范大学大学生创新性实验项目201501023

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

页数：共5页

页码：138-142