e-space
Manchester Metropolitan University's Research Repository

    Scaling Techniques for Parallel Ant Colony Optimization on Large Problem Instances

    Peake, Joshua, Amos, Martyn, Yiapanis, Paraskevas and Lloyd, Huw ORCID logoORCID: https://orcid.org/0000-0001-6537-4036 (2019) Scaling Techniques for Parallel Ant Colony Optimization on Large Problem Instances. In: GECCO '19: Proceedings of the Genetic and Evolutionary Computation Conference, 13 July 2019 - 17 July 2019, Prague, Czech Republic.

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

    Abstract

    Ant Colony Optimization (ACO) is a nature-inspired optimization metaheuristic which has been successfully applied to a wide range of different problems. However, a significant limiting factor in terms of its scalability is memory complexity; in many problems, the pheromone matrix which encodes trails left by ants grows quadratically with the instance size. For very large instances, this memory requirement is a limiting factor, making ACO an impractical technique. In this paper we propose a restricted variant of the pheromone matrix with linear memory complexity, which stores pheromone values only for members of a candidate set of next moves. We also evaluate two selection methods for moves outside the candidate set. Using a combination of these techniques we achieve, in a reasonable time, the best solution qualities recorded by ACO on the Art TSP Traveling Salesman Problem instances, and the first evaluation of a parallel implementation of MAX-MIN Ant System on instances of this scale (≥ 105 vertices). We find that, although ACO cannot yet achieve the solutions found by state-of-the-art genetic algorithms, we rapidly find approximate solutions within 1 -- 2% of the best known.

    Impact and Reach

    Statistics

    Activity Overview
    6 month trend
    159Downloads
    6 month trend
    293Hits

    Additional statistics for this dataset are available via IRStats2.

    Altmetric

    Repository staff only

    Edit record Edit record