English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  Multiplicative Drift Analysis

Doerr, B., Johannsen, D., & Winzen, C. (2012). Multiplicative Drift Analysis. Algorithmica, 64(4), 673-697. doi:10.1007/s00453-012-9622-x.

Item is

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Doerr, Benjamin1, Author           
Johannsen, Daniel1, Author           
Winzen, Carola1, 2, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2International Max Planck Research School, MPI for Informatics, Max Planck Society, ou_1116551              

Content

show
hide
Free keywords: Evolutionary algorithms, Randomized search heuristics, Runtime analysis, Drift analysis
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2012-02-292012
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: DOI: 10.1007/s00453-012-9622-x
Other: Local-ID: 2CFCFE782727C478C1257ACD003F74DC-DoerrJW12Multi
BibTex Citekey: DoerrJW12Multi
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Algorithmica
Source Genre: Journal
 Creator(s):
Affiliations:
Publ. Info: New York, NY : Springer
Pages: - Volume / Issue: 64 (4) Sequence Number: - Start / End Page: 673 - 697 Identifier: ISSN: 0178-4617