A Fast Fully Parallel Ant Colony Optimization Algorithm Based on CUDA for Solving TSP
In view of the known problems of parameter sensitivity, local optimum, and slow convergence in the ant colony optimization (ACO), we aim to improve the performance of the ACO. To solve the traveling salesman problem (TSP) quickly with accurate results, we propose a fully parallel ACO (FP-ACO). Based...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2023-01-01
|
| Series: | IET Computers & Digital Techniques |
| Online Access: | http://dx.doi.org/10.1049/2023/9915769 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832559603606355968 |
|---|---|
| author | Zhi Zeng Yuxing Cai Kwok L. Chung Hui Lin Jinwei Wu |
| author_facet | Zhi Zeng Yuxing Cai Kwok L. Chung Hui Lin Jinwei Wu |
| author_sort | Zhi Zeng |
| collection | DOAJ |
| description | In view of the known problems of parameter sensitivity, local optimum, and slow convergence in the ant colony optimization (ACO), we aim to improve the performance of the ACO. To solve the traveling salesman problem (TSP) quickly with accurate results, we propose a fully parallel ACO (FP-ACO). Based on the max–min ant system (MMAS), we initiate a compensation mechanism for pheromone to constrain its value, guarantee the correctness of results and avoid a local optimum, and further enhance the convergence ability of ACO. Moreover, based on the compute unified device architecture (CUDA), the ACO is implemented as a kernel function on a graphics processing unit (GPU), which shortens the running time of massive iterations. Combined with the roulette wheel selection mechanism, FP-ACO has powerful search capabilities and is committed to obtaining better solutions. The experimental results show that, compared with the effective strategies ACO (ESACO) that runs on CPU, the speed-up ratio of the proposed algorithm reaches 35, and the running time is less than that of the max–min ant system-roulette wheel method-bitmask tabu (MMAS-RWM-BT) that runs on GPU. Furthermore, our algorithm outperforms the other two algorithms in the speed-up ratio and less runtime, proving that the proposed FP-ACO is more suitable for solving TSP. |
| format | Article |
| id | doaj-art-0c7224bf5844475092b7756ff65650ec |
| institution | Kabale University |
| issn | 1751-861X |
| language | English |
| publishDate | 2023-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | IET Computers & Digital Techniques |
| spelling | doaj-art-0c7224bf5844475092b7756ff65650ec2025-02-03T01:29:35ZengWileyIET Computers & Digital Techniques1751-861X2023-01-01202310.1049/2023/9915769A Fast Fully Parallel Ant Colony Optimization Algorithm Based on CUDA for Solving TSPZhi Zeng0Yuxing Cai1Kwok L. Chung2Hui Lin3Jinwei Wu4School of Computer Science and EngineeringSchool of Computer Science and EngineeringSchool of Computer Science and EngineeringCollege of Resources and EnvironmentSchool of Mathematics and StatisticsIn view of the known problems of parameter sensitivity, local optimum, and slow convergence in the ant colony optimization (ACO), we aim to improve the performance of the ACO. To solve the traveling salesman problem (TSP) quickly with accurate results, we propose a fully parallel ACO (FP-ACO). Based on the max–min ant system (MMAS), we initiate a compensation mechanism for pheromone to constrain its value, guarantee the correctness of results and avoid a local optimum, and further enhance the convergence ability of ACO. Moreover, based on the compute unified device architecture (CUDA), the ACO is implemented as a kernel function on a graphics processing unit (GPU), which shortens the running time of massive iterations. Combined with the roulette wheel selection mechanism, FP-ACO has powerful search capabilities and is committed to obtaining better solutions. The experimental results show that, compared with the effective strategies ACO (ESACO) that runs on CPU, the speed-up ratio of the proposed algorithm reaches 35, and the running time is less than that of the max–min ant system-roulette wheel method-bitmask tabu (MMAS-RWM-BT) that runs on GPU. Furthermore, our algorithm outperforms the other two algorithms in the speed-up ratio and less runtime, proving that the proposed FP-ACO is more suitable for solving TSP.http://dx.doi.org/10.1049/2023/9915769 |
| spellingShingle | Zhi Zeng Yuxing Cai Kwok L. Chung Hui Lin Jinwei Wu A Fast Fully Parallel Ant Colony Optimization Algorithm Based on CUDA for Solving TSP IET Computers & Digital Techniques |
| title | A Fast Fully Parallel Ant Colony Optimization Algorithm Based on CUDA for Solving TSP |
| title_full | A Fast Fully Parallel Ant Colony Optimization Algorithm Based on CUDA for Solving TSP |
| title_fullStr | A Fast Fully Parallel Ant Colony Optimization Algorithm Based on CUDA for Solving TSP |
| title_full_unstemmed | A Fast Fully Parallel Ant Colony Optimization Algorithm Based on CUDA for Solving TSP |
| title_short | A Fast Fully Parallel Ant Colony Optimization Algorithm Based on CUDA for Solving TSP |
| title_sort | fast fully parallel ant colony optimization algorithm based on cuda for solving tsp |
| url | http://dx.doi.org/10.1049/2023/9915769 |
| work_keys_str_mv | AT zhizeng afastfullyparallelantcolonyoptimizationalgorithmbasedoncudaforsolvingtsp AT yuxingcai afastfullyparallelantcolonyoptimizationalgorithmbasedoncudaforsolvingtsp AT kwoklchung afastfullyparallelantcolonyoptimizationalgorithmbasedoncudaforsolvingtsp AT huilin afastfullyparallelantcolonyoptimizationalgorithmbasedoncudaforsolvingtsp AT jinweiwu afastfullyparallelantcolonyoptimizationalgorithmbasedoncudaforsolvingtsp AT zhizeng fastfullyparallelantcolonyoptimizationalgorithmbasedoncudaforsolvingtsp AT yuxingcai fastfullyparallelantcolonyoptimizationalgorithmbasedoncudaforsolvingtsp AT kwoklchung fastfullyparallelantcolonyoptimizationalgorithmbasedoncudaforsolvingtsp AT huilin fastfullyparallelantcolonyoptimizationalgorithmbasedoncudaforsolvingtsp AT jinweiwu fastfullyparallelantcolonyoptimizationalgorithmbasedoncudaforsolvingtsp |