Drift Analysis for Tomorrow

[Gautham Anil]

On 3/18 we will examine drift analysis. Drift analysis is a useful
tool for run-time analysis on dynamical systems. It involves using a
proven theorem and applying it to the system at hand. Certain versions
of this theorem are more flexible than others, allowing a wider
variety of applications. We will examine a few drift analysis theorems
with different levels of flexibility. We will also examine example
applications of these theorem, but we will not be examining proofs of
the theorems themselves. The simplest is Classical Drift Theorem which
will be explained. But we will focus on the one presented in [1] which
is likely to be useful for run-time analysis of EAs. The attached
presentation is based on [1]. If there is time, we will examine [2]
which provides a more flexible formulation.

[1] Benjamin Doerr, Daniel Johannsen, Carola Winzen. Multiplicative
Drift Analysis. GECCO '10
[2] Jun He, Xin Yao. Drift analysis and average time complexity of
evolutionary algorithms. Artificial Intelligence 127 (2001) 57-85