A CUDA Parallel Swarm Intelligence Approach to Solving Weighted MTSP Problems
[1]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]
Copy
Journal of Zhengzhou University (Engineering Science)[ISSN
1671-6833/CN
41-1339/T] Volume:
42
Number of periods:
2021 06
Page number:
35-42
Column:
Public date:
2021-11-10
- Title:
- A CUDA Parallel Swarm Intelligence Approach to Solving Weighted MTSP Problems
- Keywords:
- multiple traveling salesman problem(MTSP); CUDA parallel algorithm; cost-balanced; particle swarm clustering; ant colony algorithm
- CLC:
- -
- DOI:
- 10.13705/j.issn.1671-6833.2021.04.009
- 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.
- References:
-
[1] 寿涛,刘朝晖.基于Delaunay三角剖分处理二维欧式空间MTSP的近似算法[J].华东理工大学学报(自然科学版),2017,43(6):895-898.[2] 刘楠.巡检线路的哈密顿圈分割模型及算法[J].甘肃科学学报,2018,30(3):15-18.[3] TRIGUI S,CHEIKHROUHOU O,KOUBAA A,et al.FL-MTSP:a fuzzy logic approach to solve the multi-objective multiple traveling salesman problem for multi-robot systems[J].Soft computing,2017,21(24):7351-7362.[4] 张美燕,蔡文郁.基于多AUV间任务协作的水下多目标探测路径规划[J].传感技术学报,2018,31(7):1101-1107.[5] XU X L,YUAN H,LIPTROTT M,et al.Two phase heuristic algorithm for the multiple-travelling salesman problem[J].Soft computing,2018,22(19):6567-6581.[6] ZHAO M R,TANG H L,GUO J,et al.Data clustering using particle swarm optimization [J]. Lecture notes in electrical engineering,2014,309:607-612.[7] SU S B, CAO X B. Jumping PSO with expanding neighborhood search for TSP on a cuboid[J].Chinese journal of electronics, 2013, 22(1)：202-208.[8] TUANI A F,KEEDWELL E,COLLETT M.Heterogenous adaptive ant colony optimization with 3-opt local search for the travelling salesman problem[J].Applied soft computing,2020,97:106720.[9] 许凯波,鲁海燕,程毕芸,等.求解TSP的改进信息素二次更新与局部优化蚁群算法[J].计算机应用,2017,37(6):1686-1691.[10] 叶多福,刘刚,何兵.一种多染色体遗传算法解决多旅行商问题[J].系统仿真学报,2019,31(1):36-42.[11] TUANI A F,KEEDWELL E,COLLETT M.H-ACO:a heterogeneous ant colony optimisation approach with application to the travelling salesman problem[C]// International Conference on Artificial Evolution.Berlin:Springer,2018: 144-161.[12] BALI O,ELLOUMI W,ABRAHAM A,et al.ACO-PSO optimization for solving TSP problem with GPU acceleration[C]//Intelligent systems design and applications.Berlin:Springer,2017: 559-569.[13] JIANG C,WAN Z P,PENG Z H.A new efficient hybrid algorithm for large scale multiple traveling salesman problems[J].Expert systems with applications,2020,139:112867.[14] 梁静,刘睿,瞿博阳,等.进化算法在大规模优化问题中的应用综述[J].郑州大学学报(工学版),2018,39(3):15-21.
- Similar References:
Memo
-
Last Update:
2021-12-17