Scaling Techniques for Parallel Ant Colony Optimization on Large Problem Instances

Joshua Peake, Martyn Amos, Paraskevas Yiapanis, Huw Lloyd

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

11 Citations (Scopus)
71 Downloads (Pure)

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.
Original languageEnglish
Title of host publicationProceedings of the Genetic and Evolutionary Computation Conference (GECCO '19)
Subtitle of host publicationJuly 13–17, 2019, Prague, Czech Republic
Place of PublicationNew York, NY, USA
PublisherACM
Pages47-54
Number of pages8
ISBN (Electronic)9781450361118
DOIs
Publication statusPublished - 13 Jul 2019
EventThe Genetic and Evolutionary Computation Conference 2019 - Prague Conference Center, Prague, Czech Republic
Duration: 13 Jul 201917 Jul 2019
https://gecco-2019.sigevo.org/index.html/HomePage

Conference

ConferenceThe Genetic and Evolutionary Computation Conference 2019
Abbreviated titleGECCO'19
Country/TerritoryCzech Republic
CityPrague
Period13/07/1917/07/19
Internet address

Fingerprint

Dive into the research topics of 'Scaling Techniques for Parallel Ant Colony Optimization on Large Problem Instances'. Together they form a unique fingerprint.

Cite this