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 language | English |
---|---|
Title of host publication | Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '19) |
Subtitle of host publication | July 13–17, 2019, Prague, Czech Republic |
Place of Publication | New York, NY, USA |
Publisher | ACM |
Pages | 47-54 |
Number of pages | 8 |
ISBN (Electronic) | 9781450361118 |
DOIs | |
Publication status | Published - 13 Jul 2019 |
Event | The Genetic and Evolutionary Computation Conference 2019 - Prague Conference Center, Prague, Czech Republic Duration: 13 Jul 2019 → 17 Jul 2019 https://gecco-2019.sigevo.org/index.html/HomePage |
Conference
Conference | The Genetic and Evolutionary Computation Conference 2019 |
---|---|
Abbreviated title | GECCO'19 |
Country/Territory | Czech Republic |
City | Prague |
Period | 13/07/19 → 17/07/19 |
Internet address |