Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

 
 
DownloadE-Mail
  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

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Doerr, Benjamin1, Autor           
Johannsen, Daniel1, Autor           
Winzen, Carola1, Autor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 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$.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 20102010
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 536692
DOI: 10.1145/1830483.1830748
Anderer: Local-ID: C1256428004B93B8-B350C4BA1F99698EC125776500596364-DoerrJW10a
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: 12th Annual Conference on Genetic and Evolutionary Computation
Veranstaltungsort: Portland, USA
Start-/Enddatum: 2010-07-07 - 2010-07-11

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Proceedings of 12th Annual Conference on Genetic and Evolutionary Computation
  Kurztitel : GECCO 2010
Genre der Quelle: Konferenzband
 Urheber:
Pelikan, Martin1, Herausgeber
Branke, Jürgen1, Herausgeber
Affiliations:
1 External Organizations, ou_persistent22            
Ort, Verlag, Ausgabe: New York, NY : ACM
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 1449 - 1456 Identifikator: ISBN: 978-1-4503-0072-5