Scaling Techniques for Parallel Ant Colony Optimization on Large Problem Instances

Peake, Joshua, Amos, Martyn, Yiapanis, Paraskevas and Lloyd, Huw (2019) Scaling Techniques for Parallel Ant Colony Optimization on Large Problem Instances. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '19): July 13–17, 2019, Prague, Czech Republic. GECCO (19). ACM, New York, NY, USA, pp. 47-54. ISBN 9781450361118

[img]
Preview
Text
Peake et al - Scaling Techniques for Parallel Ant Colony Optimization on Large Problem Instances AAM.pdf - Accepted Version

Download (6MB) | Preview
Official URL: https://doi.org/10.1145/3321707.3321832

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-ofthe-art genetic algorithms, we rapidly find approximate solutions within 1 − 2% of the best known.

Item Type: Book Section
Subjects: G400 Computer Science
Department: Faculties > Engineering and Environment > Computer and Information Sciences
Related URLs:
Depositing User: Paul Burns
Date Deposited: 17 Apr 2019 16:46
Last Modified: 11 Oct 2019 09:52
URI: http://nrl.northumbria.ac.uk/id/eprint/39016

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics


Policies: NRL Policies | NRL University Deposit Policy | NRL Deposit Licence