License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.06061.8
URN: urn:nbn:de:0030-drops-5928
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2006/592/
Go to the corresponding Portal

Neumann, Frank ; Witt, Carsten

Runtime Analysis of a Simple Ant Colony Optimization Algorithm

pdf-format:
06061.WittCarsten.Paper.592.pdf (0.2 MB)

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:DagSemProc.06061.8,
  author =	{Neumann, Frank and Witt, Carsten},
  title =	{{Runtime Analysis of  a Simple Ant Colony Optimization Algorithm}},
  booktitle =	{Theory of Evolutionary Algorithms},
  pages =	{1--17},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6061},
  editor =	{Dirk V. Arnold and Thomas Jansen and Michael D. Vose and Jonathan E. Rowe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2006/592},
  URN =		{urn:nbn:de:0030-drops-5928},
  doi =		{10.4230/DagSemProc.06061.8},
  annote =	{Keywords: Randomized Search Heuristics, Ant Colony Optimization, Runtime Analysis}
}

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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI