MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Doerr, Benjamin
Johannsen, Daniel
dblp
dblp
Editor(s):
BibTeX cite key*:
DoerrJohannsen2007b
Title, Booktitle
Title*:
Refined Runtime Analysis of a Basic Ant Colony Optimization Algorithm
DoerrJohannsen_2007_RefinedRuntimeAnalysisOfABasicAntColonyOptimizationAlgorithm.pdf (237.88 KB)
Booktitle*:
IEEE Congress on Evolutionary Computation 2007
Event, URLs
Conference URL::
Downloading URL:
Event Address*:
Singapore
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
16 January 2008
Event End Date:
16 January 2008
Publisher
Name*:
IEEE
URL:
Address*:
Vancouver, CA
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
Pages:
501-507
Year*:
2007
VG Wort Pages:
19
ISBN/ISSN:
1-4244-1339-7
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
Neumann and Witt (2006) analyzed the runtime of
the basic ant colony optimization (ACO) algorithm
{\sc 1-Ant} on pseudo-boolean optimization problems.
For the problem {\sc OneMax} they showed how the runtime depends
on the evaporation factor. In particular, they proved a phase
transition from exponential to polynomial runtime.
In this work, we simplify the view on this problem by
an appropriate translation of the pheromone model.
This results in a profound simplification of
the pheromone update rule and, by that,
a refinement of the results of Neumann and Witt.
In particular, we show how the exponential runtime bound
gradually changes to a polynomial bound inside the phase of
transition.
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
experts only
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{DoerrJohannsen2007b,
AUTHOR = {Doerr, Benjamin and Johannsen, Daniel},
TITLE = {Refined Runtime Analysis of a Basic Ant Colony Optimization Algorithm},
BOOKTITLE = {IEEE Congress on Evolutionary Computation 2007},
PUBLISHER = {IEEE},
YEAR = {2007},
PAGES = {501--507},
ADDRESS = {Singapore},
ISBN = {1-4244-1339-7},
}


Entry last modified by Daniel Johannsen, 02/15/2009
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Süntje Böttcher
Created
01/16/2008 11:54:41 AM
Revisions
11.
10.
9.
8.
7.
Editor(s)
Daniel Johannsen
Daniel Johannsen
Daniel Johannsen
Daniel Johannsen
Daniel Johannsen
Edit Dates
02/15/2009 07:51:04 PM
02/15/2009 07:49:41 PM
21.08.2008 17:50:14
21.08.2008 17:49:14
21.08.2008 17:47:47


File Attachment Icon
DoerrJohannsen_2007_RefinedRuntimeAnalysisOfABasicAntColonyOptimizationAlgorithm.pdf