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

de Melo Menezes B A, 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.

Keywords
Parallel Ant Colony Optimization, Graphic Processing Units, Parallelization Strategies



Publication type
Conference Paper

Peer reviewed
Yes

Publication status
Published

Year
2020

Conference
PARCO2019

Venue
Prag, Tschechische Republik

Book title
Parallel Computing: Technology Trends

Editor
Ian Foster, Gerhard R. Joubert, Luděk Kučera, Wolfgang E. Nagel, Frans Peters

Publisher
IOS Press

ISBN
978-1-64368-070-5

DOI