Ant colony optimization on a budget of 1000

LESLIE ANGELICA PEREZ CACERES, Manuel López-Ibáñez, Thomas Stützle

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

Ant Colony Optimization (ACO) was originally developed as an algorithmic technique for tackling NP-hard combinatorial optimization problems. Most of the research on ACO has focused on algorithmic variants that obtain high-quality solutions when computation time allows the evaluation of a very large number of candidate solutions, often in the order of millions. However, in situations where the evaluation of solutions is very costly in computational terms, only a relatively small number of solutions can be evaluated within a reasonable time. This situation may arise, for example, when evaluation requires simulation. In such a situation, the current knowledge on the best ACO strategies and the range of the best settings for various ACO parameters may not be applicable anymore. In this paper, we start an investigation of how different ACO algorithms behave if they have available only a very limited number of solution evaluations, say, 1000. We show that, after tuning the parameter settings for this type of scenario, still the original Ant System performs relatively poor compared to other ACO strategies. However, the best parameter settings for such a small evaluation budget are very different from the standard recommendations available in the literature.

Original languageEnglish
Pages (from-to)50-61
Number of pages12
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8667
StatePublished - 1 Jan 2014

Fingerprint Dive into the research topics of 'Ant colony optimization on a budget of 1000'. Together they form a unique fingerprint.

Cite this