On the Runtime Analysis of the 1-ANT ACO Algorithm
Date
2007
Authors
Doerr, B.
Neumann, F.
Sudholt, D.
Witt, C.
Editors
Lipson, H.
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Conference paper
Citation
GECCO 2007 : Genetic and Evolutionary Computation Conference, July 7-11, 2007 University College London, London, UK / Dirk Thierens, et al. (eds.), pp. 33-40
Statement of Responsibility
Benjamin Doerr, Frank Neumann, Dirk Sudholt, Carsten Witt
Conference Name
Genetic and Evolutionary Computation Conference (9th : 2007 : London, England)
Abstract
The runtime analysis of randomized search heuristics is a growing field where, in the last two decades, many rigorous results have been obtained. These results, however, apply particularly to classical search heuristics such as Evolutionary Algorithms (EAs) and Simulated Annealing. First runtime analyses of modern search heuristics have been conducted only recently w.r.t a simple Ant Colony Optimization (ACO) algorithm called 1-ANT. In particular, 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 paper puts forward the rigorous runtime analysis of the 1-ANT on example functions, namely on the functions LeadingOnes and BinVal. With respect to EAs, such analyses have been 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 can be very crucial to allow efficient runtimes. Moreover, the analyses provide insight into the working principles of ACO algorithms and, in terms of their robustness, describe essential differences to other randomized search heuristics.
School/Discipline
Dissertation Note
Provenance
Description
Access Status
Rights
Copyright 2007 ACM