de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

Drift Analysis and Linear Functions Revisited

MPS-Authors
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;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Doerr, B., Johannsen, D., & Winzen, C. (2010). Drift Analysis and Linear Functions Revisited. In Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2010). - Pt. 3 (pp. 1967-1974). Piscataway, NJ: IEEE. doi:10.1109/CEC.2010.5586097.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-1645-1
Abstract
We regard the classical problem how the (1+1)~Evolutionary Algorithm optimizes an arbitrary linear pseudo-Boolean function. We show that any such function is optimized in time ${(1+o(1)) 1.39 e n\ln (n)}$, where ${n}$ is the length of the bit string. We also prove a lower bound of ${(1-o(1))e n\ln(n)}$, which in fact holds for all functions with a unique global optimum. This shows that for linear functions, even though the optimization behavior might differ, the resulting runtimes are very similar. Our experimental results suggest that the true optimization times are even closer than what the theoretical guarantees promise.