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

点击复制

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

分享到：

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

卷:

42

期数:

2021年6期

页码:

35-42

栏目:

出版日期:

2021-11-10

文章信息/Info

Title:

CUDA-based Parallel Swarm Intelligence Method for Solving Weighted MTSP

作者:

苏守宝^1,2,赵威^1,2,李智^1,2

1．江苏科技大学 计算机学院，江苏 镇江 212003; 2．金陵科技学院 数据科学与智慧软件江苏省重点实验室，江苏 南京 211169

Author(s):

Su Shoubao^1,2; Zhao Wei^1,2; Li Zhi^1,2;

1．School of Computer，Jiangsu University of Science and Technology，Zhenjiang 212003，China; 2．Jiangsu Key Laboratory of Data Science and Smart Software，Jinling Institute of Technology，Nanjing 211169，China

关键词:

多旅行商问题; 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

摘要:

针对 混 合 迭代 算法 执行 时间 长 的问题 ， 根 据 粒 子 群 优 化 ( 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 在不 考 虑代价 均 衡 、 代价 均 衡 约束 、 加权 代价 均 衡 的 情况 下 的 代价 标 准 差 分 别为 1 165. 26 、 54. 97 、 6. 74 。 结果 表明 : 在 求 解一 般 MTSP 问题及 其 衍 生 加权 、 代价 均 衡 MSTP 问题 上 ， GPSO-AC 在 执行 速度和收敛 精 度 上均 优 于 CPU 串 行 算法 ， 且 随 着 模 型 规 模 增 加 ， 其速度 优 势 更 加 明 显 。

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.

常用功能