[1]苏守宝,赵威,李智.求解加权MTSP问题的CUDA并行群智能方法[J].郑州大学学报(工学版),2021,42(06):35-42.[doi:10.13705/j.issn.1671-6833.2021.04.009]
　Su Shoubao,Zhao Wei,Li Zhi,et al.A CUDA Parallel Swarm Intelligence Approach to Solving Weighted MTSP Problems[J].Journal of Zhengzhou University (Engineering Science),2021,42(06):35-42.[doi:10.13705/j.issn.1671-6833.2021.04.009]

点击复制

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

分享到：

《郑州大学学报(工学版)》[ISSN:1671-6833/CN:41-1339/T]

卷:

42卷

期数:

2021年06期

页码:

35-42

栏目:

出版日期:

2021-11-10

文章信息/Info

Title:

A CUDA Parallel Swarm Intelligence Approach to Solving Weighted MTSP Problems

作者:

苏守宝; 赵威; 李智

江苏科技大学计算机学院;金陵科技学院数据科学与智慧软件江苏省重点实验室;

Author(s):

Su Shoubao; Zhao Wei; Li Zhi;

School of Computer, Jiangsu University of Science and Technology; Data Science and Smart Software of Jinling Institute of Technology in Jiangsu Province;

关键词:

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

Keywords:

multiple traveling salesman problem(MTSP);  CUDA parallel algorithm;  cost-balanced;  particle swarm clustering;  ant colony algorithm

DOI:

10.13705/j.issn.1671-6833.2021.04.009

文献标志码:

A

摘要:

针对使用混合迭代启发式算法求解多旅行商问题（MTSP）执行速度慢的问题，根据群智能算法具有良好的并行特性，对粒子群算法和蚁群算法在GPU上并行化实现和编程优化等方面进行相关研究后，提出一种基于CUDA的混合粒子群聚类-蚁群算法（GPSO-AC）。该算法利用GPU具有多个流处理器和单指令多数据（SIMT）的架构特点，将算法中的大量独立个体的搜索过程同时执行。实验表明，该算法执行速度远快于CPU版算法且随着问题规模扩大速度差距越明显，在收敛精度上也优于同类算法，同时探讨了加入代价均衡约束后对含权MTSP问题最优解收敛精度的影响。

Abstract:

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 1 165.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.

常用功能