# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Drift Analysis and Linear Functions Revisited

##### MPS-Authors

##### 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.