Runtime analysis of the 1-ANT ant colony optimizer

B Doerr, F Neumann, Dirk Sudholt, C Witt

Research output: Contribution to journalArticle

20 Citations (Scopus)

Abstract

The runtime analysis of randomized search heuristics is a growing field where, in the last two decades, many rigorous results have been obtained. First runtime analyses of ant colony optimization (ACO) have been conducted only recently. In these studies simple ACO algorithms such as the 1-ANT are investigated. The influence of the evaporation factor in the pheromone update mechanism and the robustness of this parameter w.r.t. the runtime behavior have been determined for the example function ONEMAX. This work puts forward the rigorous runtime analysis of the 1-ANT on the example functions LEADINGONES and BINVAL. With respect to Evolutionary Algorithms (EAs), such analyses were essential to develop methods for the analysis on more complicated problems. The proof techniques required for the 1-ANT, unfortunately, differ significantly from those for EAs, which means that a new reservoir of methods has to be built up. Again, the influence of the evaporation factor is analyzed rigorously, and it is proved that its choice has a crucial impact on the runtime. Moreover, the analyses provide insight into the working principles of ACO algorithms. Our theoretical results are accompanied by experimental results that give us a more detailed impression of the 1-ANT's performance. Furthermore, the experiments also deal with the question whether using many ant solutions in one iteration can decrease the total runtime. (C) 2010 Elsevier B.V. All rights reserved.
Original languageEnglish
Pages (from-to)1629-1644
Number of pages16
JournalTheoretical Computer Science
Volume412
Issue number17
DOIs
Publication statusPublished - 1 Apr 2011

Keywords

  • Ant colony optimization
  • Runtime analysis
  • Theory

Fingerprint

Dive into the research topics of 'Runtime analysis of the 1-ANT ant colony optimizer'. Together they form a unique fingerprint.

Cite this