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

Approach to Solve TSP with Parallel ACS-2-opt

作　　者：李俊[1] 童钊[1] 王政 LI Jun;TONG Zhao;WANG Zheng(College of Mathematics and Computer Science,Hunan Normal University,Changsha 410006,China)

机构地区：[1]湖南师范大学数学与计算机科学学院,长沙410006

出　　处：《计算机科学》2018年第B11期138-142,共5页Computer Science

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

摘　　要：针对基本ACS算法模型求解TSP问题的缺陷,对ACS算法添加2-opt邻域搜索策略,增强算法对TSP问题解的构造能力,提高算法对TSP问题的求解精度。同时,根据ACS算法易于并行化的特点,使用并行化ACS算法与算法参数优化混合方案,提高ACS算法求解TSP问题的速度。最终实现了对中等规模TSP问题具有较好求解性能的并行ACS-2-opt算法。实验结果表明,2-opt策略对于提升ACS算法的求解精度具有明显的效果;采用不同参数设定信息素启发因子时,求解时间具有较大差异;在采用节点距离倒数作为期望启发值时,ACS算法模型呈现退化性;在并行条件下,ACS-2-opt算法处理TSP问题时具有良好的并行性能。According to defects in basic ACS solving TSP,this paper added 2-opt local search strategy to ACS model to improve the computing capacity and accuracy in the process of building the best tour.Moreover,since ACS algorithm is easy to be parallel processed,this paper used multithreaded concurrency and parameter optimization to enhance computing speed of basic ACS.Finally,this paper actualized parallel ACS-2-opt algorithm which has preferable performance in solving the medium TSP.According to the experimental results,2-opt strategy has obvious effect on improving the accuracy of ACS solving TSP.The time cost of ACS solving TSP is distinct with different pheromone heuristic value settings.ACS becomes vestigial when using reciprocal of distance between two nodes as the corresponding heuristic value.Under the circumstance of parallel computation,ACS-2-opt has good parallel computing on solving TSP.

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]