TITLE: Rigorous Analysis of Population-dynamics in Evolutionary Algorithms
SPEAKER: Per Kristian Lehre (University of Nottingham)

ABSTRACT:
Evolutionary algorithms -- computer simulations of natural evolution --
have been applied for decades to tackle hard, real-world optimisation
problems in logistics, the automotive industry, the pharmaceutical
industry, and elsewhere. Despite their wide-spread use, the theoretical
understanding of evolutionary algorithms is still relatively poorly
developed.  The complex, stochastic population-dynamics of these
algorithms makes it challenging to characterise the conditions under
which these algorithms are efficient.

The first part of this talk describes two analytical methods, drift
analysis and level-based analysis, which are used to prove statements
about the running time of evolutionary algorithms. Drift analysis is
well established in theory of evolutionary computation, and is most
easily applied to EAs without populations, such as the (1+1) EA. The
level-based method is a recently introduced technique which simplifies
the analysis of more complex, population-based algorithms significantly.

The second part of the talk discusses new insights about the
population-dynamics of evolutionary algorithms gained from applying
these methods. We focus on conditions where the algorithm is stretched
to its limit, either by imposing very high mutation rates, very low
selective pressure, or by restricting the amount of information that is
available to the algorithm (e.g., through noisy or partially missing
fitness values). When pushed beyond these limits, we show that the
expected running time of the algorithm shifts dramatically from
polynomial to exponential.  However, with appropriate mutation rates,
selective pressure, and sufficiently large population sizes, we also
prove that evolutionary algorithms can be surprisingly resilient to high
levels of uncertainty.