Scaling Techniques for Parallel Ant Colony Optimization on Large Problem Instances

Peake, Joshua, Amos, Martyn, Yiapanis, Paraskevas and Lloyd, Huw ORCID: 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.

Preview

Accepted Version Available under License In Copyright. 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.