English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  Multiplicative Drift Analysis

Doerr, B., Johannsen, D., & Winzen, C. (2010). Multiplicative Drift Analysis. In M. Pelikan, & J. Branke (Eds.), Proceedings of 12th Annual Conference on Genetic and Evolutionary Computation (pp. 1449-1456). New York, NY: ACM. doi:10.1145/1830483.1830748.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-168D-1 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0024-26BE-B
Genre: Conference Paper

Files

show Files

Locators

show

Creators

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

Content

show
hide
Free keywords: -
 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$.

Details

show
hide
Language(s): eng - English
 Dates: 20102010
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 536692
DOI: 10.1145/1830483.1830748
Other: Local-ID: C1256428004B93B8-B350C4BA1F99698EC125776500596364-DoerrJW10a
 Degree: -

Event

show
hide
Title: 12th Annual Conference on Genetic and Evolutionary Computation
Place of Event: Portland, USA
Start-/End Date: 2010-07-07 - 2010-07-11

Legal Case

show

Project information

show

Source 1

show
hide
Title: Proceedings of 12th Annual Conference on Genetic and Evolutionary Computation
  Abbreviation : GECCO 2010
Source Genre: Proceedings
 Creator(s):
Pelikan, Martin1, Editor
Branke, Jürgen1, Editor
Affiliations:
1 External Organizations, ou_persistent22            
Publ. Info: New York, NY : ACM
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 1449 - 1456 Identifier: ISBN: 978-1-4503-0072-5