Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








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

URL of the conference:


URL for downloading the paper:


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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
DoerrJohannsen_2007_RefinedRuntimeAnalysisOfABasicAntColonyOptimizationAlgorithm.pdf