high performance computing on graphics processing units: hgpu.org

The ant colony optimization (ACO) algorithm is a metaheuristic algorithm used for combinatorial optimization problems. It is a good choice for many hard combinatorial problems because it is more efficient that brute force methods and produces better solutions than greedy algorithms. However, ACO is computationally expensive, and it can still take a long time to compute a solution on large problem sets. Fortunately, the structure of the ACO algorithm is amenable to being parallelized. By using CUDA to implement an ACO algorithm, I achieved significant improvement in performance over a highly-tuned sequential CPU implementation. I propose several different ways to improve the performance of the ACO algorithm using GPUs, including a multi-GPU approach. I ran the CUDA-parallelized ACO algorithm on the travelling salesman problem (TSP) problem and compared our performance to a highly-tuned sequential CPU implementation.