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
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
Conference URL::
http://www.sigevo.org/gecco-2010/index.html
Downloading URL:
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
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