7040

A Parallel Ant Colony Optimization Algorithm for the Travelling Salesman Problem: Improving Performance Using CUDA

Octavian Nitica
University of Delaware
University of Delaware, 2011

@phdthesis{nitica2011parallel,

   title={A Parallel Ant Colony Optimization Algorithm for the Travelling Salesman Problem: Improving Performance Using CUDA},

   author={Nitica, Octavian},

   year={2011}

}

Download Download (PDF)   View View   Source Source   

2557

views

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.
Rating: 2.5. From 1 vote.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: