Webinar: When are evolutionary algorithms provably efficient? Runtime analysis of population-based evolutionary algorithms

Date: September 18, 2015 3:00pm (UK time)
Registration: https://attendee.gotowebinar.com/register/555560504610023682
Speaker: Dr. Per Kristian Lehre, School of Computer Science, University of Nottingham,  UK

 

 

Abstract:

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. 

Biography:

Per Kristian Lehre received MSc and PhD degrees in Computer Science from the Norwegian University of Science and Technology (NTNU) in Trondheim, Norway. He finished the PhD in 2006 under the supervision of Prof Pauline Haddow, and joined the School of Computer Science at The University of Birmingham, UK, as a Research Fellow in January 2007 with Prof Xin Yao. He was a Post Doctoral Fellow at DTU Informatics, Technical University of Denmark in Lyngby, Denmark from April 2010. He is since September 2011 a Lecturer in the School of Computer Science at the University of Nottingham, UK.

Dr Lehre's research interests are in theoretical aspects of nature-inspired search heuristics, in particular runtime analysis of population-based evolutionary algorithms.  His research has won numerous best paper awards, including GECCO (2013, 2010, 2009, 2006) and ICSTW (2008). He is vice-chair of IEEE Task Force on Theoretical Foundations of Bio-inspired Computation, and a member of the editorial board of Evolutionary Computation. He has guest-edited special issues of Theoretical Computer Science and IEEE Transaction on Evolutionary Computation on theoretical foundations of evolutionary computation. Dr Lehre has given many tutorials on evolutionary computation in summer schools (UK: 2007, France: 2009, 2010, and 2011, Estonia: 2010), as well as major conferences and workshops (GECCO 2013, 2014, 2015, CEC 2013, and 2015, ThRaSH 2013).  He is the main coordinator of the 2M euro EU-funded project SAGE which brings together theory of evolutionary
computation and population genetics.