Doerr
- Daniel Johannsen
- |
    Carola Winzen[^1]\
    Max-Planck-Institut für Informatik\
    Campus E1 4\
    66123 Saarbrücken, Germany\
date: Submitted January 2011
title: Multiplicative Drift Analysis
---

Introduction {#sec:introduction}
============

An innocent looking problem is the question how long the (1+1) Evolutionary Algorithm ((1+1) EA) needs to find the optimum of a given linear function. However, this is in fact one of the problems that was most influential for the theory of evolutionary algorithms.

While particular linear functions like the functions [<span style="font-variant:small-caps;">OneMax</span>]{}and [<span style="font-variant:small-caps;">BinVal</span>]{}were easily analyzed, it took a major effort by Droste, Jansen and Wegener [@DrosteJW02] to solve the problem in full generality. Their proof, however, is highly technical.

A major breakthrough spurred by this problem is the work by He and Yao [@HeY01; @HeY04], who introduced *drift analysis* to the field of evolutionary computation. This allowed a significantly simpler proof for the linear functions problem. Even more important, it quickly became one of the most powerful tools for both proving upper and lower bounds on the expected optimization times of evolutionary algorithms. For example, see [@HeY04; @GielWstacs03; @GielL06; @HappJKN08; @NeumannOW09; @OlivetoW10].

Another great progress was made by Jägersküpper [@Jagerskupper08], who combined drift analysis with a clever averaging argument 