Level-based Analysis of Genetic Algorithms and other Search Processes

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

Abstract

Understanding how the time-complexity of evolutionary algorithms (EAs) depends 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.

Introduction

A central challenge in evolutionary computation is determining the expected runtime of search heuristics. While rigorous tools like drift analysis have been successful for simple algorithms like the (1+1) EA, they often struggle with population-based processes. Real-world Genetic Algorithms (GAs) and Estimation of Distribution Algorithms (EDAs) utilize populations, crossover, and non-elitist selection—features that introduce significant mathematical complexity. Historically, theoretical results often simplified these algorithms by ignoring recombination or assuming infinite populations. This paper introduces the level-based theorem, a general framework designed to provide upper bounds on the expected runtime of finite-population, non-elitist algorithms that use any combination of mutation and recombination.

The Level-Based Theorem

The core methodology involves partitioning the search space into an ordered sequence of subsets, or "levels" ($A_1, A_2, \dots, A_m$), where the final level $A_m$ represents the target solutions. The theorem provides a recipe for calculating the expected time $E[T]$ to reach this target by verifying three conditions:

  1. (G1) Progress: Given a specific fraction of the population at or above level $j$, what is the probability that a newly generated individual will reach level $j+1$?
  2. (G2) Amplification: If a portion of the population has already reached level $j+1$, does the algorithm's selection mechanism tend to increase this fraction in the subsequent generation?
  3. (G3) Population Size: Is the population size $\lambda$ sufficient to mitigate stochastic noise?

By satisfying these conditions, researchers can derive concrete runtime bounds without navigating the complexities of underlying Markov chains or manual drift calculations.

Applications and Benchmarks

The versatility of the level-based theorem is demonstrated across several problem domains and fitness landscapes:

  • Pseudo-Boolean Functions: Analysis of OneMax, LeadingOnes, Linear functions, Jump, and Royal Road functions.
  • Permutation Problems: The Sorting problem, analyzed using the inversion (Inv) measure.
  • Combinatorial Optimization: Proving that non-elitist GAs can reach a 1/2-approximation for NP-hard problems like Max-SAT and Max-CUT in polynomial time, matching the performance of simpler local search heuristics within a more complex GA framework.

Key Insights

Theoretical Optimality

The authors demonstrate that the theorem is "nearly optimal." Given the specific information required by the theorem's conditions, it is generally impossible to prove significantly tighter upper bounds, establishing it as a robust and reliable tool for the field.

Simplifying EDAs and Crossover

Estimation of Distribution Algorithms, such as the Univariate Marginal Distribution Algorithm (UMDA), were previously considered notoriously difficult to analyze. The level-based framework simplifies these proofs significantly. Furthermore, unlike previous analytical tools that struggled with recombination, this theorem treats crossover as an integral part of the probability distribution, making it a "first-class citizen" in the analysis.

Parallelization and Scalability

The results suggest that for many problems, increasing the population size $\lambda$ does not significantly increase the total number of function evaluations (up to a certain threshold). This implies that these algorithms can be efficiently parallelized without a massive search penalty, providing theoretical backing for large-scale population use.

Results Summary

The paper establishes several key runtime bounds for various algorithms:

  • OneMax: $O(n\lambda)$ for GAs; $O(n\lambda \ln \lambda)$ for UMDA.
  • LeadingOnes: $O(n^2 + n\lambda \ln \lambda)$ for both GAs and UMDA.
  • Sorting: $O(n^2\lambda)$, providing a population-aware counterpart to existing (1+1) EA results.

Limitations and Future Work

While powerful, the theorem has specific requirements:

  • Memory-less Processes: It applies only to algorithms where the next generation depends solely on the current population. It cannot currently handle algorithms with long-term memory or external state, such as Ant Colony Optimization (ACO).
  • Level Construction: The burden remains on the researcher to define an effective partition of the search space. Poorly chosen levels may result in loose bounds.
  • Upper Bounds Only: The theorem focuses on upper bounds; while it is tight relative to its inputs, it does not directly provide lower bounds on runtime.

Summary updated

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.
BibTeX
@inproceedings{corus2014level,
  author = {Dogan Corus and Duc-Cuong Dang and Anton V. Eremeev and Per Kristian Lehre},
  title = {{Level-based Analysis of Genetic Algorithms and other Search Processes}},
  booktitle = {PPSN},
  year = {2014},
  doi = {10.1007/978-3-319-10762-2\_90},
}
Figure