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

摘要：

针对混合迭代算法执行时间长的问题,根据粒子群优化(PSO)算法和蚁群优化(ACO)算法的并行特点,结合其在GPU上并行化实现技术和编程优化技巧,提出一种基于CUDA的粒子群聚类蚁群的并行群智能混合方法GPSO-AC.该算法利用GPU的多个流处理器(SM)和单指令多线程(SIMT)的指令架构,将GP SO-A C算法在运行中的独立个体的搜索过程同时并行执行,在保证算法精度的基础上,加快混合迭代法的执行速度.考虑到实际场景中旅行商在每个路段上各项开销不同,可以抽象为每段路程区间上都有一个与之对应的代价,将路程代价考虑到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串行算法,且随着模型规模增加,其速度优势更加明显.

关键词：多旅行商问题;CUDA并行算法;代价均衡;粒子群聚类;蚁群算法

所属期刊栏目：42

分类号：TP18;TP303.6(自动化基础理论)

资助基金：国家自然科学基金资助项目;金陵科技学院高层次引进人才科研项目

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

页数：共8页

页码：34-41