Runtime Analysis of Evolutionary Algorithms

(Photo by Markus Tacker)

Speaker

Per Kristian Lehre, School of Computer Science, University of Birmingham, United Kingdom

Abstract

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 performance 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. More recently, the theory has been extended to cover complex evolutionary algorithms on realistic problems.

This tutorial gives an introduction to runtime analysis, focusing on methods for runtime analysis of population-based evolutionary algorithms. The tutorial begins with a brief overview of the population-based EAs that are covered by the techniques. We recall the common stochastic selection mechanisms and how to measure the selection pressure they induce. The main part of the tutorial covers in detail widely applicable techniques tailored to the analysis of populations. To illustrate how these techniques can be applied, we consider several fun- damental questions: When are populations necessary for efficient optimisation with EAs? What is the appropriate balance between exploration and exploita- tion 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?

Biography

Professor Per Kristian Lehre is affiliated with the School of Computer Science at the University of Birmingham (since Jan 2017). Before joining Birmingham, he was Assistant Professor with the University of Nottingham since 2011. He obtained MSc and PhD degrees in Computer Science from the Norwegian University of Science and Technology (NTNU) in Trondheim, He completed 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 Postdoctoral Fellow at DTU Informatics, Technical University of Denmark in Lyngby, Denmark from April 2010. Professor 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), ICSTW (2008), and ISAAC (2014). He was vice-chair of IEEE Task Force on Theoretical Foundations of Bio-inspired Computation, and a member of the editorial board of Evolutionary Computation and previously associate editor of IEEE Transactions on Evolutionary Compu- tation. 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, as well as major conferences and workshops. He was the main coordinator of the 1.58M euro EU-funded project SAGE which brought together theories of evolutionary computation and population genetics. He is also a Turing AI Acceleration Fellow funded by the UKRI with a £1.26M project on Runtime Analysis of Co-evolutionary Algorithms.