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:




Library Locked Library locked




Author, Editor

Author(s):

Doerr, Benjamin
Johannsen, Daniel
Winzen, Carola

dblp
dblp
dblp



Editor(s):

Pelikan, Martin
Branke, Jürgen

dblp
dblp

Not MPII Editor(s):

Pelikan, Martin
Branke, Jürgen

BibTeX cite key*:

DoerrJW10a

Title, Booktitle

Title*:

Multiplicative Drift Analysis

Booktitle*:

Proceedings of 12th Annual Conference on Genetic and Evolutionary Computation (GECCO-2010)

Event, URLs

URL of the conference:

http://www.sigevo.org/gecco-2010/index.html

URL for downloading the paper:


Event Address*:

Portland, USA

Language:

English

Event Date*
(no longer used):


Organization:

Association for Computing Machinery (ACM)

Event Start Date:

7 July 2010

Event End Date:

11 July 2010

Publisher

Name*:

ACM

URL:


Address*:

New York, NY

Type:


Vol, No, Year, pp.

Series:


Volume:


Number:


Month:


Pages:

1449-1456

Year*:

2010

VG Wort Pages:

37

ISBN/ISSN:

978-1-4503-0072-5

Sequence Number:


DOI:

10.1145/1830483.1830748



Note, Abstract, ©

Note:

Best Paper Award

(LaTeX) Abstract:

Drift analysis is one of the strongest tools in the analysis
of evolutionary algorithms. Its main weakness is that it is
often very hard to find a good drift function.
In this paper, we make progress in this direction. We
prove a multiplicative version of the classical drift theorem.
This allows easier analyses in those settings, where the optimization progress is roughly proportional to the current
objective value.
Our drift theorem immediately gives natural proofs for
the best known run-time bounds for the (1+1) Evolutionary
Algorithm computing minimum spanning trees and shortest
paths, since here we may simply take the objective function
as drift function.
As a more challenging example, we give a relatively simple
proof for the fact that any linear function is optimized in
time $O(n \log n)$. In the multiplicative setting, a simple linear
function can be used as drift function (without taking any
logarithms).
However, we also show that, both in the classical and the
multiplicative setting, drift functions yielding good results
for all linear functions exist only if the mutation probability
is at most $c/n$ for a small constant $c$.

Keywords:

Evolutionary Computation, Evolutionary Algorithms, Theory of Randomized Search Heuristics, Theory



Download
Access Level:

Internal

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

popular

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{DoerrJW10a,
AUTHOR = {Doerr, Benjamin and Johannsen, Daniel and Winzen, Carola},
EDITOR = {Pelikan, Martin and Branke, J{\"u}rgen},
TITLE = {Multiplicative Drift Analysis},
BOOKTITLE = {Proceedings of 12th Annual Conference on Genetic and Evolutionary Computation (GECCO-2010)},
PUBLISHER = {ACM},
YEAR = {2010},
ORGANIZATION = {Association for Computing Machinery (ACM)},
PAGES = {1449--1456},
ADDRESS = {Portland, USA},
ISBN = {978-1-4503-0072-5},
DOI = {10.1145/1830483.1830748},
NOTE = {Best Paper Award},
}


Entry last modified by Carola Winzen, 02/14/2011
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)
[Library]
Created
07/19/2010 06:16:21 PM
Revisions
2.
1.
0.

Editor(s)
Carola Winzen
Anja Becker
Carola Winzen

Edit Dates
01/04/2011 10:49:33 AM
03.01.2011 13:40:17
07/19/2010 06:16:21 PM