The Efficiency Threshold for the Offspring Population Size of the (μ, λ) EA

Denis Antipov, Benjamin Doerr, Quentin Yang

TL;DR

This paper investigates the critical offspring population size (λ) for the efficiency of a (µ, λ) evolutionary algorithm (EA) on the ONEMAX problem. The authors identify a precise threshold around λ ≈ eµ, showing that slightly below this, runtimes become super-polynomial, while slightly above, they become polynomial, revealing a surprisingly sharp transition.

What Problem Does This Paper Address?

Evolutionary algorithms (EAs) are powerful optimization tools, but understanding why and when they are efficient remains a significant challenge. A key question is how the population sizes, specifically the parent population (µ) and offspring population (λ), influence an EA's performance. Previous research suggested a general efficiency threshold for the (µ, λ) EA on simple problems like ONEMAX, but the precise boundary and the underlying mechanisms were not fully understood. This paper aims to precisely characterize this threshold, particularly focusing on the transition from efficient polynomial-time optimization to inefficient super-polynomial time.

Methods

The authors employ rigorous mathematical analysis, primarily using drift analysis and potential functions, to derive theoretical bounds on the runtime of the (µ, λ) EA.

  • Drift Analysis: This technique tracks the expected change in a system's state over time. By analyzing the "drift" of fitness values or population properties, they can infer how quickly an EA converges or diverges.
  • Potential Functions: A key innovation is the introduction of a novel potential function that is exponential in an individual's fitness. This allows them to circumvent the complex analysis of selection effects and focus on the overall expected increase in potential, which is directly related to fitness gains.
  • Stochastic Domination: Used to compare random variables and argue that better parents tend to produce better offspring.
  • Chernoff Bounds: Applied to bound the probabilities of deviations from expected values for sums of independent random variables, crucial for analyzing binomial distributions arising from mutation.
  • Additive Drift Theorem: A fundamental tool used to relate the expected drift of a potential function to the expected time to reach a target state (e.g., finding the optimum).

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis of the (µ, λ) EA on the ONEMAX benchmark function, which is a synthetic problem, not a dataset.

Key Insights and Ideas

  • Sharp Efficiency Threshold: The most striking finding is the existence of a very sharp efficiency threshold for λ around eµ. Even small deviations from this value drastically change the algorithm's runtime.
  • Beyond Simple Drift: The paper shows that the reasons for efficiency or inefficiency are more complex than just a positive or negative drift in the fitness of the best individuals. The interplay between population sizes and mutation dynamics is crucial.
  • Role of Population Size: The analysis reveals that not only the ratio λ/µ but also the absolute population sizes (µ and λ) play a role, especially near the threshold.
  • Stabilizing Effect of Sub-optimal Offspring: For larger population sizes in the efficient regime (λ > eµ), the authors observe that slightly worse offspring can actually stabilize sub-optimal sub-populations, preventing premature convergence and aiding overall progress.
  • Novel Potential Function: The introduction of a fitness-exponential potential function is a significant methodological contribution, simplifying the analysis of fitness gains.

Key Results

The paper establishes precise theoretical bounds on the expected runtime of the (µ, λ) EA on the ONEMAX problem:

  • Super-polynomial Runtime: If λ ≤ (1 - ε)µ for a sufficiently large ε (specifically, ε = ω(1/√n)), the expected runtime is super-polynomial in n (the problem dimension). This extends previous results for constant ε.
  • Polynomial Runtime: If µ is large enough (µ > n^(2/3)+c) and λ > eµ, the runtime is polynomial, specifically O(n log n). This is achieved even in regimes with essentially no drift.
  • Irrationality of e Matters: The paper demonstrates that the irrationality of e plays a role in determining the runtime threshold, particularly when µ is large and λ is close to eµ.

Limitations and Future Work

  • ONEMAX Specificity: The results are derived for the ONEMAX function. While ONEMAX is a standard benchmark, its simplicity might limit direct applicability to more complex, multi-modal problems.
  • Focus on Threshold: The paper primarily focuses on the behavior near the efficiency threshold. The behavior far from the threshold is less explored.
  • Multi-modal Problems: The authors raise the question of whether the observed behavior near the threshold (less rapid concentration on the best fitness level) could help EAs overcome premature convergence on multi-modal problems. This is suggested as an interesting avenue for future research.
  • Absolute Population Size: While the paper shows absolute population size matters, a deeper understanding of this role could be beneficial.

Summary updated

Abstract

Understanding when evolutionary algorithms are efficient or not, and how they efficiently solve problems, is one of the central research tasks in evolutionary computation. In this work, we make progress in understanding the interplay between parent and offspring population size of the $(μ,λ)$ EA. Previous works, roughly speaking, indicate that for $λ\ge (1+\varepsilon) e μ$, this EA easily optimizes the OneMax function, whereas an offspring population size $λ\le (1 -\varepsilon) e μ$ leads to an exponential runtime. Motivated also by the observation that in the efficient regime the $(μ,λ)$ EA loses its ability to escape local optima, we take a closer look into this phase transition. Among other results, we show that when $μ\le n^{1/2 - c}$ for any constant $c > 0$, then for any $λ\le e μ$ we have a super-polynomial runtime. However, if $μ\ge n^{2/3 + c}$, then for any $λ\ge e μ$, the runtime is polynomial. For the latter result we observe that the $(μ,λ)$ EA profits from better individuals also because these, by creating slightly worse offspring, stabilize slightly sub-optimal sub-populations. While these first results close to the phase transition do not yet give a complete picture, they indicate that the boundary between efficient and super-polynomial is not just the line $λ= e μ$, and that the reasons for efficiency or not are more complex than what was known so far.
BibTeX
@inproceedings{antipov2019efficiency,
  author = {Denis Antipov and Benjamin Doerr and Quentin Yang},
  title = {{The Efficiency Threshold for the Offspring Population Size of the (μ, λ) EA}},
  booktitle = {GECCO},
  year = {2019},
  url = {https://openreview.net/forum?id=RwH0RRc_nt9},
}
Figure