Parallelization Strategies for GPU- Based Ant Colony Optimization Applied to TSP

Menezes Breno, de Araujo Pessoa L F, Kuchen H, Buarque de Lima Neto F

Abstract

Graphics Processing Units (GPUs) have been widely used to speed up the execu-tion of various meta-heuristics for solving hard optimization problems. In the caseof Ant Colony Optimization (ACO), many implementations with very distinct par-allelization strategies and speedups have been already proposed and evaluated onthe Traveling Salesman Problem (TSP). On the one hand, a coarse-grained strategyapplies the parallelization on the ant-level and is the most intuitive and commonstrategy found in the literature. On the other hand, a fine-grained strategy also par-allelizes the internal work of each ant, creating a higher degree of parallelization.Although many parallel implementations of ACO exist, the influence of the algo-rithm parameters (e.g., the number of ants) and the problem configurations (e.g.,the number of nodes in the graph) on the performance of coarse- and fine-grainedparallelization strategies has not been investigated so far. Thus, this work performsa series of experiments and provides speedup analyses of two distinct ACO par-allelization strategies compared to a sequential implementation for different TSPconfigurations and colony sizes. The results show that the considered factors cansignificantly impact the performance of parallelization strategies, particularly forlarger problems. Furthermore, we provide a recommendation for the parallelizationstrategy and colony size to use for a given problem size and some insights for thedevelopment of other GPU-based meta-heuristics.