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

Preview

Text Peake et al - Scaling Techniques for Parallel Ant Colony Optimization on Large Problem Instances AAM.pdf - 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-ofthe-art genetic algorithms, we rapidly find approximate solutions within 1 − 2% of the best known.

Actions (login required)

View Item

Downloads