Analysis of independent roulette selection in parallel ant colony optimization

Lloyd, Huw and Amos, Martyn (2017) Analysis of independent roulette selection in parallel ant colony optimization. In: Proceedings of the Genetic and Evolutionary Computation Conference on - GECCO '17. Association for Computing Machinery, pp. 19-26. ISBN 978-1-4503-4920-8

[img] Text (Full text)
Lloyd, Amos - Analysis of Independent Roule�tte Selection AAM.pdf - Accepted Version

Download (2MB)
Official URL: http://dx.doi.org/10.1145/3071178.3071308

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.

Item Type: Book Section
Uncontrolled Keywords: Ant Colony Optimization; Roulette Wheel; Convergence; Solution Quality; GPU Computing
Subjects: G400 Computer Science
Department: Faculties > Engineering and Environment > Computer and Information Sciences
Depositing User: Becky Skoyles
Date Deposited: 18 Sep 2018 10:55
Last Modified: 21 Mar 2020 10:30
URI: https://nrl.northumbria.ac.uk/id/eprint/35760

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics