Using CUDA GPU to Accelerate the Ant Colony Optimization Algorithm

Kai-Cheng Wei, Chao-Chin Wu, Chien-Ju Wu
Computer Science and Information Engineering, National Changhua University of Education, Changhua 500, Taiwan
14’th International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT’13), 2013


   title={Using CUDA GPU to Accelerate the Ant Colony Optimization Algorithm},

   author={Wei, Kai-Cheng and Wu, Chao-Chin and Wu, Chien-Ju},



Download Download (PDF)   View View   Source Source   



Graph Processing Units (GPUs) have recently evolved into a super multi-core and a fully programmable architecture. In the CUDA programming model, the programmers can simply implement parallelism ideas of a task on GPUs. The purpose of this paper is to accelerate Ant Colony Optimization (ACO) for Traveling Salesman Problems (TSP) with GPUs. In this paper, we propose a new parallel method, which is called the Transition Condition Method. Experimental results are extensively compared and evaluated on the performance side and the solution quality side. The TSP problems are used as a standard benchmark for our experiments. In terms of experimental results, our new parallel method achieves the maximal speed-up factor of 4.74 than the previous parallel method. On the other hand, the quality of solutions is similar to the original sequential ACO algorithm. It proves that the quality of solutions does not be sacrificed in the cause of speed-up.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: