Tutorial
Drift Analysis of Evolutionary Algorithms Dr. Per Kristian Lehre |
Abstract:
The time complexity of an evolutionary algorithm (EA) on a given problem refers to the number of times the EA evaluates the fitness function before a solution of acceptable quality has been found. Time complexity analysis of EAs has developed into a very active research area in recent years. Drift analysis is among the most powerful theoretical tools available for estimating the time complexity of EAs and other meta-heuristics. Informally, it shows how the challenging problem of predicting the long-term behaviour of an EA can be reduced to the often trivial problem of describing how the state of the EA changes during one generation.
Drift analysis has dramatically simplified the analysis of EAs, and has led to significant advances in the theory of evolutionary computation. Many of the most important results about the time complexity of EAs were obtained with the help of drift analysis.
This tutorial gives a gentle, yet comprehensive, introduction to drift analysis, assuming only basic knowledge of probability theory. We approach the area by examining a few simple drift theorems that are both straightforward to apply, and that yield useful bounds on the expected optimisation time of basic EAs. We then turn to more sophisticated drift theorems that, while needing stronger conditions, provide very precise statements about the success probability of EAs. Finally, we show how to investigate complex EAs with the aid of a new population-drift theorem that was discovered recently.
Illustrative examples showing how the drift theorems can be applied in evolutionary computation will be given throughout the tutorial.
Outline of contents:
1. Fundamentals of Probability Theory
- Probability triple, events, random variables
- Conditional expectation
- Stochastic processes and stopping times
- Martingales
2. Introduction to Drift Analysis
- What is drift analysis, and why is it so useful?
- Expected runtime and success probability of EAs
- Relationship with other techniques, such as Markov chain theory
3. Additive Drift Theorems
- Theorems for upper and lower bounds
- Proof ideas
- Example application: (1+1) EA on toy problems
* Choosing the distance function
* Estimating the drift
* Deriving bounds on the expected runtime
4. Variable Drift Theorems
- Multiplicative drift theorem
- Variable drift theorem
- Proof ideas
- Example applications:
* Expected runtime of EAs on linear fitness functions, the minimum
* spanning tree problem, and other classical combinatorial
* optimisation problems
5. Supermartingale drift
- Drift by variance
- Example applications:
* Expected runtime of EAs on neutral fitness landscapes
6. Hajek's Drift Theorem
- Stochastic dominance
- Moment-generating functions
- Hajek's theorem with proof ideas
- Simplified drift theorem with proof ideas
- Example applications:
* Success probability of EAs on easy and hard problems
7. Population drift
- Drift in population-based EAs
- Reproductive rate as a measure of selection pressure
- Statement of population drift theorem with proof ideas
- Example applications:
* When is the mutation rate too high in an EA?
* How to tune the selective pressure in an EA?
* Analysis of EAs with linear ranking selection,
* tournament selection, fitness proportionate selection.
Summary and Conclusion
(The amount of content to cover will be adjusting according to the length of the tutorial.)
Expected enrolment
The tutorial is designed as a follow-up to the tutorial "A Gentle Introduction to the Time Complexity Analysis of Evolutionary Algorithms". It is aimed at researchers in evolutionary computation who wish to:
- Obtain a deeper, theoretical understanding of EAs and the stochastic processes that underlie them
- Initiate own research in time complexity analysis of EAs and other meta-heuristics
- Analyse more complex meta-heuristics, and more complex problems
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. He is vice-chair of IEEE Task Force on Theoretical Foundations of Bio-inspired Computation. He is member of editorial board of Evolutionary Computation, and has guest-edited a special issue of Theoretical Computer Science on Foundations of Evolutionary Computation.
The length of the tutorial:
two hours.