Level-Based Analysis of Genetic Algorithms and Other Search Processes

Dogan Corus, Duc-Cuong Dang, Anton V. Eremeev, and Per Kristian Lehre

Abstract

Understanding how the time-complexity of evolutionary algorithms (EAs) depend on their parameter settings and characteristics of fitness landscapes is a fundamental problem in evolutionary computation. Most rigorous results were derived using a handful of key analytic techniques, including drift analysis. However, since few of these techniques apply effortlessly to population-based EAs, most time-complexity results concern simplified EAs, such as the (1+1) EA. This paper describes the level-based theorem, a new technique tailored to population-based processes. It applies to any non-elitist process where offspring are sampled independently from a distribution depending only on the current population. Given conditions on this distribution, our technique provides upper bounds on the expected time until the process reaches a target state.

We demonstrate the technique on several pseudo-Boolean functions, the sorting problem, and approximation of optimal solutions in combinatorial optimisation. The conditions of the theorem are often straightforward to verify, even for Genetic Algorithms and Estimation of Distribution Algorithms which were considered highly non-trivial to analyse. Finally, we prove that the theorem is nearly optimal for the processes considered. Given the information the theorem requires about the process, a much tighter bound cannot be proved.

• Preprint arXiv:1407.7663 (available Oct 28th 2016)

Applications

• Self-adaptive evolutionary algorithms
  Duc-Cuong Dang and Per Kristian Lehre, Self-adaptation of Mutation Rates in Non-elitist Populations, to appear in Proceedings of 14th International Conference on Parallel Problem Solving from Nature (PPSN) 2016. arXiv:1606.05551
• Partially observable fitness functions
  Duc-Cuong Dang and Per Kristian Lehre. Evolution under partial information. In Proceedings of the 16th Annual Conference on Genetic and Evolutionary Computation, (GECCO 2014), pages 1359-1366, New York, NY, USA, 2014. ACM. (Nominated for best paper award.)
• Stochastic fitness functions
  Duc-Cuong Dang, Per Kristian Lehre: Efficient Optimisation of Noisy Fitness Functions with Population-based Evolutionary Algorithms. In Proceedings of Foundations of Genetic Algorithms (FOGA 2015), Aberystwyth, January 2015.
• Dynamic fitness functions
  Duc-Cuong Dang and Thomas Jansen and Per Kristian Lehre, Populations can be essential in tracking dynamic optima. To appear in Algorithmica.
• Genetic Algorithms with crossover operator
  Dogan Corus, Duc-Cuong Dang, Anton V. Eremeev and Per Kristian Lehre, Level-based Analysis of Genetic Algorithms and other Search Processes, arXiv:1407.7663
• Univariate Marginal Distribution Algorithm (UMDA)
  Duc-Cuong Dang and Per Kristian Lehre: Simplified Runtime Analysis of Estimation of Distribution Algorithms, To appear in Proceedings of the 17th annual Genetic and Evolutionary Computation Conference (GECCO 2015), Madrid, Spain, July 11-15, 2015.
• Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA)
  Hoog, I.D. van der: Applying Level Based Analysis to Optimal Mixing Evolutionary Algorithms, Bachelor thesis, Utrecht University, 2016
• Shortest paths with genetic algorithms
  Dogan Corus and Per Kristian Lehre: Theory-driven Design of efficient Genetic Algorithms for a classical Graph Problem. To appear in Proceedings of the 11th Metaheuristics International Conference (MIC 2015), June 7-10th 2015, Agadir, Morocco.

Old material

The following material refer to the old version of the level-based theorem, as published in the proceedings of PPSN 2014.

• Tutorial at CEC2015 in May 2015 (covers also the negative drift theorem for populations)
• Paper preprint and DOI
• PPSN Poster (PDF)
(old version of theorem)
• BibTeX,
• See also drift analysis and our other publications.