Research map / Learning theory and algorithms / Prediction and decision losses

Runtime Analysis of the (μ + 1) GA: Provable Speed-Ups from Strong Drift towards Diverse Populations

AAAI 2024 · Learning theory and algorithms › Prediction and decision losses · approach: Determinantal point process inference · 8 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Theoretical runtime analysis of the (µ+1) genetic algorithm on JUMP functions showing that a diverse population on the local optima plateau persists for time exponential in µ, yielding provable crossover speed-ups for small populations.

Problem

Understanding how crossover helps evolutionary algorithms requires controlling population diversity; prior runtime analyses of the (µ+1) GA on JUMP only showed diversity lasting quadratic time and needed unusual parameters.

Approach

Shows that once the population sits on the JUMP plateau, the largest genotype class tends to shrink (strong drift toward diversity), so diverse populations persist for exp(Ω(µ)) iterations, which gives runtime bounds with logarithmic population size and any constant crossover and mutation rates.

Key results

• Diversity on the JUMP plateau persists for an expected exp(Ω(µ)) iterations, improving the previously known quadratic-in-µ bound of Dang et al. (2018).
• With constant crossover and mutation rate and µ = Ω(log n) and k ≥ 3, the runtime bound becomes O((n/χ)^(k-1)), better by a factor χ^(-k+1) for χ>1 than Dang et al.; the speed-up over the Θ(n^k) (1+1) EA is Ω(n) for such µ.
• Experiments on JUMP show distance-0 pairs quickly vanish and larger pairwise Hamming distances grow, suggesting diversity is even stronger than the proofs show.

Measured effects reported in the paper

Surprising findings

• The largest genotype class is more likely to decrease than increase, contrary to the unbiased random walk assumed in prior analysis.
• Pairwise Hamming distances grow beyond what the proofs guarantee, suggesting even stronger diversity than proven.

Limitations

• Results are asymptotic and assume k = o(n), µ = o(n), and constant crossover rate.
• Proofs show diversity lower than what experiments suggest; the Hamming-distance growth is not proven.

Experimental setup

Benchmarks: JUMP_k benchmark

Metrics: expected runtime (fitness evaluations) relative frequency of pairwise Hamming distances

Baselines: (1+1) EA Dang et al. 2018 (µ+1) GA analysis

Builds on: Dang et al. 2018 (µ+1) GA JUMP analysis Jansen and Wegener 2002 negative drift theorem (Krejca 2019) Kötzing 2016 negative drift

Closest papers by meaning

• Runtime Analysis for Multi-Objective Evolutionary Algorithms in Unbounded Integer Spaces (AAAI 2025 · similarity 0.86)
• Speeding Up the NSGA-II with a Simple Tie-Breaking Rule (AAAI 2025 · similarity 0.85)
• From Understanding Genetic Drift to a Smart-Restart Mechanism for Estimation-of-Distribution Algorithms (Journal Track) (AAAI 2025 · similarity 0.84)
• A Many-Objective Problem Where Crossover Is Provably Indispensable (AAAI 2025 · similarity 0.84)
• Diffusion Models are Evolutionary Algorithms (ICLR 2025 · similarity 0.84)
• Evolution Fine-Tuning: Learning to Discover Across 371 Optimization Tasks (NeurIPS 2026 · similarity 0.84)