License
When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-5928
URL: http://drops.dagstuhl.de/opus/volltexte/2006/592/
Go to the corresponding Portal


Neumann, Frank ; Witt, Carsten

Runtime Analysis of a Simple Ant Colony Optimization Algorithm

pdf-format:
Document 1.pdf (201 KB)


Abstract

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

@InProceedings{neumann_et_al:DSP:2006:592,
  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 =		{http://drops.dagstuhl.de/opus/volltexte/2006/592},
  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