Runtime Analysis of Evolutionary Algorithms: Basic Introduction

Tutorial at GECCO 2018, Kyoto, Japan, July 2018.

(Updated: July 16th 2018)


  • Per Kristian Lehre (University of Birmingham)
  • Pietro S. Oliveto (University of Sheffield)
  • Abstract

    Evolutionary algorithm theory has studied the time complexity of evolutionary algorithms for more than 20 years. Different aspects of this rich and diverse research field were presented in three different advanced or specialized tutorials at last year's GECCO. This tutorial presents the foundations of this field. We introduce the most important notions and definitions used in the field and consider different evolutionary algorithms on a number of well-known and important example problems. Through a careful and thorough introduction of important analytical tools and methods, including fitness-based partitions, typical events and runs and drift analysis, by the end of the tutorial the attendees will be able to apply these techniques to derive relevant runtime results for non-trivial evolutionary algorithms. Moreover, the attendees will be fully prepared to follow the more advanced tutorials that cover more specialized aspects of the field, including the new advanced runtime analysis tutorial on realistic population-based EAs. To assure the coverage of the topics required in the specialised tutorials, this introductory tutorial will be coordinated with the presenters of the more advanced ones. In addition to custom-tailored methods for the analysis of evolutionary algorithms we also introduce the relevant tools and notions from probability theory in an accessible form. This makes the tutorial appropriate for everyone with an interest in the theory of evolutionary algorithms without the need to have prior knowledge of probability theory and analysis of randomized algorithms. The last four editions of this tutorial at GECCO 2013, GECCO 2014, GECCO 2015, and PPSN 2016 attracted well over 50 participants each. The tutorial will be based on the 'theoretical analysis of stochastic search heuristics' chapter of the forthcoming Springer Handbook of Heuristics.