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

Approach to Solve TSP with Parallel ACS-2-opt

针对基本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.