de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

Multiplicative Drift Analysis

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44338

Doerr,  Benjamin
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44705

Johannsen,  Daniel
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45750

Winzen,  Carola
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-168D-1
Zusammenfassung
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$.