Journal Article
@Article
Artikel in Fachzeitschrift


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(s)

Author(s):

Doerr, Benjamin
Johannsen, Daniel
Winzen, Carola

dblp
dblp
dblp

Not MPG Author(s):

Johannsen, Daniel

BibTeX cite key*:

DoerrJW12Multi

Title

Title*:

Multiplicative Drift Analysis

Journal

Journal Title*:

Algorithmica

Journal's URL:

http://link.springer.com/journal/453

Download URL
for the article:

http://link.springer.com/article/10.1007%2Fs00453-012-9622-x

Language:

English

Publisher

Publisher's
Name:

Springer

Publisher's URL:

http://www.springer.com/?SGWID=5-102-0-0-0

Publisher's
Address:

New York, NY

ISSN:

0178-4617

Vol, No, pp, Date

Volume*:

64

Number:

4

Publishing Date:

December 2012

Pages*:

673-697

Number of
VG Pages:

38

Page Start:

673

Page End:

697

Sequence Number:


DOI:

10.1007/s00453-012-9622-x

Note, Abstract, ©

Note:


(LaTeX) Abstract:

We introduce multiplicative drift analysis as a suitable way to analyze the runtime of randomized search heuristics such as evolutionary algorithms. Our multiplicative version of the classical drift theorem allows easier analyses in the often encountered situation that the optimization progress is roughly proportional to the current distance to the optimum.

To display the strength of this tool, we regard the classical problem of how the (1+1) Evolutionary Algorithm optimizes an arbitrary linear pseudo-Boolean function. Here, we first give a relatively simple proof for the fact that any linear function is optimized in expected time $O(n \log n)$, where $n$ is the length of the bit string. Afterwards, we show that in fact any such function is optimized in expected time at most $(1+o(1))1.39 e n\ln n$, again using multiplicative drift analysis. We also prove a corresponding lower bound of $(1−o(1)) e n \ln n$ which actually holds for all functions with a unique global optimum.

We further demonstrate how our drift theorem immediately gives natural proofs (with better constants) for the best known runtime bounds for the (1+1) Evolutionary Algorithm on combinatorial problems like finding minimum spanning trees, shortest paths, or Euler tours in graphs.

URL for the Abstract:


Categories,
Keywords:

Evolutionary algorithms, Randomized search heuristics, Runtime analysis, Drift analysis

HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Internal

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Appearance:

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


BibTeX Entry:

@ARTICLE{DoerrJW12Multi,
AUTHOR = {Doerr, Benjamin and Johannsen, Daniel and Winzen, Carola},
TITLE = {Multiplicative Drift Analysis},
JOURNAL = {Algorithmica},
PUBLISHER = {Springer},
YEAR = {2012},
NUMBER = {4},
VOLUME = {64},
PAGES = {673--697},
ADDRESS = {New York, NY},
MONTH = {December},
ISBN = {0178-4617},
DOI = {10.1007/s00453-012-9622-x},
}


Entry last modified by Anja Becker, 01/30/2013
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
12/07/2012 12:33:06 PM
Revisions
4.
3.
2.
1.
0.
Editor(s)
Anja Becker
Anja Becker
Benjamin Doerr
Carola Winzen
Carola Winzen
Edit Dates
30.01.2013 10:36:30
30.01.2013 10:32:05
01/27/2013 09:13:50 AM
01/15/2013 06:22:30 PM
12/07/2012 12:33:06 PM