# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Multiplicative Drift Analysis

##### MPS-Authors

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

There are no public fulltexts stored in PuRe

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

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

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-168D-1

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