e-space
Manchester Metropolitan University's Research Repository

Scaling Techniques for Parallel Ant Colony Optimization on Large Problem Instances

Peake, Joshua and Amos, Martyn and Yiapanis, Paraskevas and Lloyd, Huw (2019) Scaling Techniques for Parallel Ant Colony Optimization on Large Problem Instances. In: Genetic and Evolutionary Computation Conference (GECCO) 2019, 13 July 2019 - 17 July 2019, Prague, Czech Republic. (In Press)

[img]
Restricted to Repository staff only

Download (6MB)

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 ofMAX-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.

Impact and Reach

Statistics

Downloads
Activity Overview
1Download
102Hits

Additional statistics for this dataset are available via IRStats2.

Actions (login required)

Edit Item Edit Item