When are evolutionary algorithms provably efficient? (IEEE CIS Webinar)
Channel: Per Kristian Lehre
Date: 2015-09-18

IEEE CIS Webinar September 18th 2015
Speaker: Dr Per Kristian Lehre (University of Nottingham)
Host: Dr Dirk Sudholt (University of Sheffield)

(For slides etc., please see http://www.cs.nott.ac.uk/~pkl/populations/)

Populations are at the heart of evolutionary algorithms (EAs). They provide the genetic variation which selection acts upon. A complete picture of EAs and their efficiency can only be obtained if we understand their population dynamics. A rich theory on runtime analysis (also called time-complexity analysis) of EAs has been developed over the last 20 years. The goal of this theory is to show, via rigorous mathematical means, how the efficiency of EAs depends on their parameter settings and the characteristics of the underlying fitness landscapes. Initially, runtime analysis of EAs was mostly restricted to simplified EAs that do not employ large populations, such as the (1+1) EA.
 
This webinar introduces recent, and easy to use techniques that make runtime analysis of complex, population-based evolutionary algorithms possible. It first offers an overview of population-based evolutionary algorithms. In particular, it defines common stochastic selection mechanisms and explains how to measure their selective pressure.  The main part of the webinar covers in detail widely applicable techniques tailored to the analysis of populations, in particular drift analysis and level-based analysis.
 
To illustrate the application of these techniques, we consider several fundamental questions: When are populations necessary for efficient optimisation with EAs? What is the appropriate balance between exploration and exploitation and how does this depend on relationships between mutation and selection rates? What determines an EA's tolerance for uncertainty, e.g. in form of noisy or partially available fitness? The webinar is aimed at students and researchers who wish to gain a deeper theoretical understanding of evolutionary algorithms, and possibly initiate their own research in runtime analysis. No more than a basic knowledge of probability theory will be required.