Level-Based Analysis of Genetic Algorithms and Other Search Processes

Doğan Çörüş, Duc-Cuong Dang, Anton V. Eremeev, Per Kristian Lehre

Introduction

The field of evolutionary computation has long grappled with a significant "theory gap." While practitioners frequently employ complex, population-based algorithms—often incorporating crossover and non-elitist selection—theoretical analysis has historically lagged behind. Most rigorous runtime results have been confined to simplified "toy" models, such as the (1+1) Evolutionary Algorithm (EA), which tracks only a single individual and its mutant offspring.

The primary obstacle to analyzing population-based EAs is mathematical complexity. Traditional tools like drift analysis, which measure expected progress toward an optimum, become increasingly difficult to apply when researchers must account for the simultaneous interactions of many individuals. This paper introduces the level-based theorem, a general-purpose analytical framework designed to bridge this gap by providing a structured "recipe" for proving the time-complexity of population-based search processes.

The Level-Based Framework

The core innovation of the level-based theorem is the abstraction of the search space into an ordered sequence of "levels" ($A_1, A_2, \dots, A_m$), where the final level $A_m$ represents the target state or global optimum. Rather than tracking the specific trajectory of every individual in a population, the theorem focuses on the distribution of the population across these levels.

To derive an upper bound on the expected time to reach the target, the theorem requires the verification of three fundamental conditions regarding the algorithm's distribution:

  1. Discovery (G1): Given that a specific fraction of the population has reached level $j$, there must be a minimum probability ($z_j$) that a newly sampled individual will reach a higher level ($j+1$ or above).
  2. Amplification (G2): If the population already contains individuals at level $j+1$, the selection mechanism must be sufficiently strong to likely increase the representation of that level in the subsequent generation.
  3. Population Size (G3): The population size $\lambda$ must be large enough—typically logarithmic relative to the problem size—to ensure that these probabilistic transitions occur with high reliability.

This abstraction allows the theorem to remain agnostic to the specific operators used (e.g., mutation, crossover, or probabilistic modeling), provided the resulting offspring distribution satisfies these conditions.

Applications and Theoretical Results

The authors demonstrate the versatility of the level-based theorem by applying it to a wide array of benchmark problems and algorithms that were previously considered highly non-trivial to analyze.

Benchmark Functions and Problems

The theorem was tested against standard pseudo-Boolean functions and combinatorial challenges, including:

  • OneMax and LeadingOnes: Fundamental landscapes used to measure basic search efficiency and the impact of population size.
  • Jump and Royal Road Functions: Landscapes characterized by plateaus or "gaps" that require significant jumps in fitness, testing the algorithm's ability to traverse fitness valleys.
  • Sorting: The classic problem of ordering $n$ elements, where the theorem proved an expected time of $O(n^2\lambda)$.
  • Combinatorial Optimization: The theorem provides approximation guarantees for NP-hard problems, showing that non-elitist GAs can reach a 1/2-approximate solution for Max-SAT and Max-CUT in polynomial time.

Algorithm Classes

A major contribution of this work is its applicability to Genetic Algorithms (GAs) and Estimation of Distribution Algorithms (EDAs). Notably, the framework naturally incorporates crossover, a feature often omitted in theoretical studies for the sake of simplicity, by including it in the "Discovery" condition.

Significance and Tightness

The level-based theorem is not merely a convenient tool; the authors prove it is "nearly optimal." This means that given only the information the theorem requires (the level-based probabilities), it is mathematically impossible to derive a significantly tighter bound. This establishes the theorem as a fundamental limit on what can be proven using level-based information alone.

Limitations and Future Directions

While the level-based theorem is a powerful addition to the theorist's toolkit, it has specific boundaries:

  • Non-Elitism: The theorem is specifically tailored for non-elitist processes where the best individuals are not guaranteed to survive. While many EAs use non-elitism to maintain diversity, extending this framework to elitist "plus" strategies remains a separate challenge.
  • Independent Sampling: The assumption that offspring are sampled independently fits most standard GAs and EDAs but may not apply to "island models" or algorithms with high spatial correlation.
  • Landscape Ruggedness: The framework relies on a discernible path of progress through levels. Highly rugged or fractal landscapes, where no clear hierarchy of levels exists, still pose a challenge for this method.

In conclusion, the level-based theorem provides a robust, standardized methodology for analyzing population-based search, offering a path forward for the rigorous study of the complex evolutionary algorithms used in modern optimization.

Summary updated

Abstract

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 o spring 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 combina-torial optimisation. The conditions of the theorem are often straightfor-ward 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 = {Doğan Çörüş 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