Tutorial
A Gentle Introduction to the Time Complexity Analysis of Evolutionary Algorithms Pietro S. Oliveto |
Outline
Great advances have been made in recent years towards the runtime complexity analysis of evolutionary algorithms for combinatorial optimisation problems. Much of this progress has been due to the application of techniques from the study of randomised algorithms. The first pieces of work, started in the 90s, were directed towards analysing simple toy problems with significant structures. This work had two main goals:
- to understand on which kind of landscapes EAs are efficient, and when they are not
- to develop the first basis of general mathematical techniques needed to perform the analysis.
Thanks to this preliminary work, nowadays, it is possible to analyse the runtime of evolutionary algorithms on different combinatorial optimisation problems. In this beginners’ tutorial, we give a basic introduction to the most commonly used techniques, assuming no prior knowledge about time complexity analysis.
Goals
By the end of the tutorial participants will be able:
1) to understand theoretically the behaviour of EAs on different problems;
2) to perform runtime complexity analyses of simple EAs on the most common toy problems;
3) to understand more complicated work on the analysis of EAs for combinatorial
optimisation;
4) to have the basic skills to start independent research in the area.
Content
1. Review of basic notions from probability theory:
- Sample space, events, probabilities
- Random variables and their expectation
2. Fundamental definitions about runtime complexity analysis:
- Asymptotic notation
- Expected runtime
- Success probability
3. Basic techniques:
- Modelling EAs with Markov chains
- Tail inequalities (Markov’s inequality and Chernoff bounds)
- Artificial fitness layers
- Coupon collector theorem
- Gambler ruin problem
- Drift analysis
- Typical runs
4. Application of the techniques to analyse the runtime of simple EAs:
- Random Local Search (RLS)
- ( 1 + 1 ) Evolutionary Algorithm
on toy problems
- Onemax
- LeadingOnes
- Needle
- Trap functions
- plateaus / short path functions
5. Extension of the techniques to more realistic population-based EAs:
- ( 1 + ) - EA ;
- ( µ + 1 ) - EA;
- ( µ + ) - EA;
- Non-elitist EAs (i.e. comma selection, fitness proportional selection, tournament selection);
- Genetic Algorithms.
6. Overview of the application of the techniques to the analysis of EAs for classical combinatorial optimisation problems.
Expected Audience
The tutorial is targeted at scientists and engineers who wish to:
- theoretically understand the behaviour and performance of the search algorithms they design;
- familiarise with the techniques used in the runtime analysis of EAs;
- pursue research in the area of time complexity analysis of randomised algorithms in general and EAs in particular.
Last Last year’s tutorial at WCCI 2012 attracted over 30 participants. The slides online at http://www.cs.bham.ac.uk/~olivetps/images/Oliveto2012Tutorial.pdf have been downloaded over 70 times in the last year.
Biography:
Pietro Simone Oliveto is an EPSRC funded Postdoctoral Fellow in Theoretical Computer Science at the University of Birmingham, UK. He received the Laurea degree and PhD degree in computer science respectively from the University of Catania, Italy in 2005 and from the University of Birmingham, UK in 2009. From October 2007 to April 2008, he was a visiting researcher of the Efficient Algorithms and Complexity Theory Institute at the Department of Computer Science of the University of Dortmund where he collaborated with Prof. Ingo Wegener’s research group. From 2009 to 2010 he was a Research fellow at Birmingham funded by EPSRC under the PhD+ funding scheme. He frequently collaborates with researchers from DTU in Lyngby (Denmark), MPI in Saarbruecken (Germany) and AT&T Research Labs in New Jersey (USA).
His main research interest is the time complexity analysis of randomised search heuristics for combinatorial optimisation problems. He has published several runtime analysis papers on Evolutionary Algorithms (EAs), Artificial Immune Systems (AIS) and Ant Colony Optimisation (ACO) algorithms for classical NP-Hard combinatorial optimisation problems such as vertex cover, mincut and spanning trees with maximal number of leaves together with a review paper of the field of time complexity analysis of EAs for combinatorial optimisation problems and a book chapter containing a tutorial on the runtime analysis of EAs. He has won best paper awards at the GECCO’08 and ICARIS’11 conferences and got very close at PPSN’08, CEC’09 and at ECTA’11 through best paper nominations.
Dr. Oliveto gave a Tutorial on the runtime analysis of EAs at the 2012 World Congress on Computational Intelligence (WCCI 2012) which attracted approximately 30 participants and will give a tutorial on the topic at the 2013 Conference on Genetic and Evolutionary Computation (GECCO 2013). He is part of the Steering Committee of the annual workshop on Theory of Randomized Search Heuristics (ThRaSH), IEEE member and Chair of the IEEE CIS Task Force on “Theoretical Foundations of Bio-inspired Computation”. Since 2008 he has been invited to the Dagstuhl seminar series on the Theory of Evolutionary Algorithms.
The length of the tutorial:
Four Hours (the tutorial will be divided in two parts of 2 hours each).