Level-Based Analysis of Genetic Algorithms and Other Search Processes

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

Introduction

In the field of Evolutionary Computation (EC), establishing the exact time an algorithm requires to solve a problem is a fundamental challenge. For decades, rigorous runtime analysis was largely confined to the (1+1) Evolutionary Algorithm (EA)—a simplified model featuring a single individual and elitist selection. However, real-world Genetic Algorithms (GAs) typically utilize large populations, recombination (crossover), and non-elitist selection, where even the best individuals might be discarded to preserve diversity. These complexities historically made analyzing GAs a non-trivial task, often requiring unique and complex proofs for every new problem. This paper introduces the level-based theorem, a unified mathematical framework designed to derive upper bounds on the expected optimization time for these complex, population-based processes.

The Level-Based Theorem

The core contribution of this research is a general-purpose "recipe" for runtime analysis based on drift analysis, tailored specifically for population dynamics. To apply the theorem, researchers follow a structured five-step process centered on three critical conditions:

  1. Partitioning the Search Space: The space of all possible solutions is divided into "levels" ($A_1, A_2, \dots, A_m$) based on their quality.
  2. Condition G1 (Upward Probability): There must be a minimum probability ($z_j$) of creating an individual in a higher level, given that a sufficient portion of the current population has reached the current level.
  3. Condition G2 (Growth Rate): Once a level is reached, the number of individuals at or above that level must tend to increase by a multiplicative factor ($1 + \delta$), representing selection pressure.
  4. Condition G3 (Population Size): The population size ($\lambda$) must be large enough to prevent the "extinction" of high-quality traits due to stochastic noise.

By satisfying these conditions, the theorem provides a formula to calculate an upper bound on the expected optimization time. A key strength of this framework is its generality; it remains valid regardless of whether new individuals are generated via mutation, crossover, or probabilistic modeling, provided the population distribution meets the specified conditions.

Key Results and Applications

The authors demonstrate the theorem's power by providing new runtime bounds for several standard benchmark functions and algorithms:

  • OneMax: The theorem proves that a non-elitist GA solves the OneMax problem in $O(n\lambda)$ generations, demonstrating that populations can provide a linear parallel speedup.
  • UMDA: The framework offers the first simplified runtime analysis for the Univariate Marginal Distribution Algorithm (UMDA) on OneMax ($O(n\lambda \ln \lambda)$), bypassing the need for complex Markov chain theory.
  • Combinatorial Problems: For the sorting problem, the authors establish a runtime of $O(n^2\lambda)$, which is competitive with simpler (1+1) algorithms while incorporating population benefits.
  • Approximation Performance: The theorem is applied to NP-hard problems like Max-SAT and Max-CUT, proving that a GA can find a 1/2-approximate solution within $O(m' \lambda \ln \lambda + nm')$ fitness evaluations.

Insights and Limitations

One of the most significant theoretical advances is the handling of crossover. Historically difficult to analyze due to parent interactions, the level-based framework treats crossover by simply measuring the probability that any pair of parents produces a superior offspring. The parameter $\delta$ (selection pressure) is also highlighted as a critical factor; even small values of $\delta$ can lead to efficient optimization if the population is sufficiently large. Furthermore, the authors prove that the theorem is "nearly optimal," meaning the bounds are as tight as possible given the information required by the conditions.

Despite its power, the theorem has limitations. It provides a sufficient population size but does not determine the minimum necessary size. Additionally, it focuses on upper bounds; a general framework for lower bounds remains an open challenge. Finally, the theorem applies to memory-less processes, and its application to algorithms with long-term memory or external archives requires further investigation.

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 simple EAs, such as the (1+1) EA. We present the level-based theorem, a new technique tailored to population-based processes. It applies to any nonelitist 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. The technique is demonstrated on pseudo-Boolean functions, the sorting problem, and approximation of optimal solutions in combinatorial optimization. The conditions of the theorem are often straightforward to verify, even for genetic algorithms and estimation of distribution algorithms which were considered highly nontrivial to analyze. The proofs for the example applications are available in the supplementary materials. 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