Runtime analysis of the 1-ANT ant colony optimizer

Benjamin Doerr, Frank Neumann, Dirk Sudholt, Carsten Witt

    Research output: Contribution to journalJournal articleResearchpeer-review

    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.
    Original languageEnglish
    JournalTheoretical Computer Science
    Volume412
    Issue number17
    Pages (from-to)1629-1644
    ISSN0304-3975
    DOIs
    Publication statusPublished - 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