When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-5928
Go to the corresponding Portal

Neumann, Frank ; Witt, Carsten

Runtime Analysis of a Simple Ant Colony Optimization Algorithm

06061.WittCarsten.Paper.592.pdf (0.2 MB)


Ant Colony Optimization (ACO) has become quite popular in recent years. In contrast to many successful applications, the theoretical foundation of this randomized search heuristic is rather weak. Building up such a theory is demanded to understand how these heuristics work as well as to come up with better algorithms for certain problems. Up to now, only convergence results have been achieved showing that optimal solutions can be obtained in a finite amount of time. We present the first runtime analysis of a simple ACO algorithm that transfers many rigorous results with respect to the expected runtime of a simple evolutionary algorithm to our algorithm. In addition, we examine the choice of the evaporation factor, which is a crucial parameter in such an algorithm, in greater detail and analyze its effect with respect to the runtime.

BibTeX - Entry

  author =	{Frank Neumann and Carsten Witt},
  title =	{Runtime Analysis of  a Simple Ant Colony Optimization Algorithm},
  booktitle =	{Theory of Evolutionary Algorithms},
  year =	{2006},
  editor =	{Dirk V. Arnold and Thomas Jansen and Michael D. Vose and Jonathan E. Rowe},
  number =	{06061},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{},
  annote =	{Keywords: Randomized Search Heuristics, Ant Colony Optimization, Runtime Analysis}

Keywords: Randomized Search Heuristics, Ant Colony Optimization, Runtime Analysis
Seminar: 06061 - Theory of Evolutionary Algorithms
Issue Date: 2006
Date of publication: 07.07.2006

DROPS-Home | Fulltext Search | Imprint Published by LZI