求解加权MTSP问题的CUDA并行群智能方法

CUDA-based Parallel Swarm Intelligence Method for Solving Weighted MTSP

针对混合迭代算法执行时间长的问题,根据粒子群优化(PSO)算法和蚁群优化(ACO)算法的并行特点,结合其在GPU上并行化实现技术和编程优化技巧,提出一种基于CUDA的粒子群聚类蚁群的并行群智能混合方法GPSO-AC。该算法利用GPU的多个流处理器(SM)和单指令多线程(SIMT)的指令架构,将GPSO-AC算法在运行中的独立个体的搜索过程同时并行执行,在保证算法精度的基础上,加快混合迭代法的执行速度。考虑到实际场景中旅行商在每个路段上各项开销不同,可以抽象为每段路程区间上都有一个与之对应的代价,将路程代价考虑到MTSP问题中。采用TSPLIB库中6个测试数据集,将GPSO-AC与PSO-AC、TPHA、K-means-AC等算法进行比较,并进一步探讨了加入代价均衡约束后对加权MTSP问题最优解收敛性能的影响。使用chn31数据集上不同旅行商数时,GPSO-AC在不考虑代价均衡、代价均衡约束、加权代价均衡的情况下的代价标准差分别为1165.26、54.97、6.74。结果表明:在求解一般MTSP问题及其衍生加权、代价均衡MSTP问题上,GPSO-AC在执行速度和收敛精度上均优于CPU串行算法,且随着模型规模增加,其速度优势更加明显。

To solve the low running speed of the multi-traveling salesman problem(MTSP)using the heuristic method,a CUDA-based hybrid particle swarm clustering-ant colony algorithm(GPSO-AC)was proposed by integrating their parallel characteristics with programming techniques optimally.GPSO-AC used GPU′s instruction architecture with multiple stream processors(SM)and single instruction multithreading(SIMT)to parallel the search process of numerous independent individuals,so as to accelerate the execution speed of the hybrid iterative method.GPSO-AC was tested on 6 datasets compared with other methods,such as PSO-AC,TPHA and K-means-AC.Then the influence of cost equilibrium constraint on the convergence performance of the optimal solution of weighted MTSP problem was discussed.Furthermore,the cost standard deviations obtained from GPSO-AC on chn31 with different traveling salesmen,were 1165.26,54.97 and 6.74 in the three cases respectively.The experimental results showed that the proposed algorithm was much faster than other CPU based algorithms and the advantage becomed more obvious with the expansion of the model size,and the convergence precision of the algorithm was better than the similar algorithms for solving MTSP problems.