Analysis of independent roulette selection in parallel ant colony optimization

Huw Lloyd, Martyn Amos

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

9 Citations (Scopus)
32 Downloads (Pure)

Abstract

The increased availability of high-performance parallel architectures such as the Graphics Processing Unit (GPU) has led to significant interest in modified versions of metaheuristics that take advantage of their capabilities. Parallel Ant Colony Optimization (ACO) algorithms are now widely-used, but these often present a challenge in terms of maximizing the potential for parallelism. One common bottleneck for parallelization of ACO occurs during the tour construction phase, when edges are probabilistically selected. Independent Roulette (I-Roulette) is an alternative to the standard Roulette Selection method used during this phase, and this achieves significant performance improvements on the GPU. In this paper we provide the first in-depth study of how I-Roulette works. We establish that, even though I-Roulette works in a qualitatively different way to Roulette Wheel selection, its use in two popular ACO variants does not affect the quality of the solutions obtained. However, I-Roulette significantly accelerates convergence to a solution. Our theoretical analysis shows that I-Roulette possesses several interesting and non-obvious features, and is capable of a form of dynamical adaptation during the tour construction process.
Original languageEnglish
Title of host publicationProceedings of the Genetic and Evolutionary Computation Conference (GECCO '17), July 15-19 2017, Berlin, Germany
PublisherACM
Pages19-26
Number of pages8
ISBN (Electronic)9781450349208
DOIs
Publication statusPublished - 1 Jul 2017

Fingerprint

Dive into the research topics of 'Analysis of independent roulette selection in parallel ant colony optimization'. Together they form a unique fingerprint.

Cite this