|
||||||
|
||||||
| Undergraduate Honours Projects | ||||||
|
Carleton University - School of Computer Science Undergraduate Honours Project Winter 2011 Ant Colony Optimization Parallel Algorithm for GPU Karim Tantawy 
ABSTRACT In nature, ants in a colony work together to forage for food by laying pheromone trails as guides towards food sources. The Ant Colony Optimization algorithm works by the same principle: simulated ants construct solutions to decision problems, and pheromone values are updated to favour better solutions. We apply this to the Travelling Salesman Problem, where the goal is to find the shortest tour between a set of cities such that each city is visited exactly once. Ant Colony Optimization is well suited to this problem due to the large search space, for example with 50 cities, the number of possible tours exceeds the number of atoms in the known universe. We implement the Ant Colony Optimization algorithm using NVIDIA CUDA to run on the Graphical Processing Unit to take advantage of the parallel nature of the heuristic. GPUs allow multiple threads to run in parallel, and these threads are arranged into thread blocks. We create one thread block per ant which is responsible for maintaining the necessary state information and generating the tour. The number of threads per block becomes the critical factor, we found that 64 threads works best as CUDA issues thread instructions in groups of 32. We achieved a greater than ten factor speedup for problem instances with up to 1,291 cities for the tour construction phase. |
||||||
|
