e-space
Manchester Metropolitan University's Research Repository

    Analysis of Independent Roulette Selection in Parallel Ant Colony Optimization

    Amos, M and Lloyd, H (2017) Analysis of Independent Roulette Selection in Parallel Ant Colony Optimization. In: The Genetic and Evolutionary Computation Conference 2017 (GECCO 2017), 15 July 2017 - 19 July 2017, Berlin, Germany. (Unpublished)

    [img]
    Preview
    Accepted Version
    Download (2MB) | Preview

    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.

    Impact and Reach

    Statistics

    Activity Overview
    6 month trend
    546Downloads
    6 month trend
    440Hits

    Additional statistics for this dataset are available via IRStats2.

    Repository staff only

    Edit record Edit record