Journal Article @Article Artikel in Fachzeitschrift
 Show entries of: this year (2020) | last year (2019) | two years ago (2018) | Notes URL
 Action: login to update Options: Library locked Goto entry point

 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

 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: (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},