Research map / Learning theory and algorithms / Sample complexity
From Understanding Genetic Drift to a Smart-Restart Mechanism for Estimation-of-Distribution Algorithms (Journal Track)
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.
Proposes a smart-restart mechanism for EDAs that aborts runs after a budget b·μ² evaluations and doubles the hypothetical population size, with runtime guarantees and experiments on cGA and PBIL.
Problem
Choosing the population size of estimation-of-distribution algorithms is critical: small sizes cause genetic drift and poor performance, while large sizes slow the algorithm down.
Approach
Use the quantified genetic-drift time scale (about μ² evaluations) to abort runs with an increasing population size after a budget of b·μ² evaluations, so the EDA always runs in a low-drift regime without tuning μ.
Key results
- On Jump with n=50, k=10, the original cGA with a well-chosen population size reaches a median runtime of about 4·10^6 evaluations, while the classic (1+1) EA would need more than 10^17 iterations.
- Smart-restart cGA with budget factor 1/ln n performs close to the best static population size on four benchmarks, avoiding the catastrophic runtimes of small static sizes.
- Theory: smart-restart with b=Θ(1/log n) achieves the same asymptotic runtime as the EDA with optimal population size for cGA/UMDA on OneMax, Jump and LeadingOnes/DLB (UMDA).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use smart restarts with cautious budget factor b=1/\ln(n) instead of a static population size | cGA · Jump and DeceptiveLeadingBlocks | runtime | Helped |
| Use smart restarts with budget factor b=1/\ln(n) rather than b=16 | cGA · Jump and DeceptiveLeadingBlocks | runtime | Helped |
| Use the population size suggested by smart restart instead of the hand-crafted literature value | PBIL · Max-cut and bipartition | performance | Helped |
| Use the smart-restart mechanism instead of the two alternative restart strategies | PBIL · Max-cut and bipartition | performance | Helped |
| Use population sizes suggested by the theoretical analysis rather than the smaller values needed experimentally | cGA · Noisy OneMax | runtime: roughly by a factor of 1{,}000 | Hurt |
| Use the optimal static population size rather than either parameter-less strategy | cGA · OneMax, LeadingOnes, Jump, and DeceptiveLeadingBlocks, with and without noise | runtime | Hurt |
| Reduce the static population size below the efficient range | cGA · Jump | runtime | Hurt |
Surprising findings
- Experiments did not reproduce the bimodal runtime pattern for cGA on OneMax reported in prior work.
- Optimal population size for LeadingOnes was relatively independent of noise level, which the authors could not explain.
Limitations
- Theory relies on an assumption (L) that runtime is roughly linear in population size above a threshold, which is not proven for all cases.
- Experiments use relatively small problem sizes (e.g., n=30 to 100) due to long runtimes.
- Performance depends on choosing budget factor b and update factor U, though these were reported as not critical.
Experimental setup
Datasets: OneMax LeadingOnes Jump DeceptiveLeadingBlocks max-cut instances bipartition instances
Benchmarks: OneMax LeadingOnes Jump DeceptiveLeadingBlocks max-cut bipartition
Metrics: number of fitness evaluations until optimum found median runtime with quartiles
Baselines: original cGA with static population sizes parallel-run cGA Harik-Lobo restart strategies PBIL with hand-crafted parameters
Builds on: compact genetic algorithm UMDA parallel-run EDA mechanism IPOP-CMA-ES restart Doerr-Zheng genetic drift analysis
Closest papers by meaning
- Runtime Analysis of the (μ + 1) GA: Provable Speed-Ups from Strong Drift towards Diverse Populations (AAAI 2024 · similarity 0.84)
- Optimistic Algorithms for Adaptive Estimation of the Average Treatment Effect (ICML 2025 · similarity 0.82)
- Statistical Properties of Robust Satisficing (ICML 2024 · similarity 0.82)
- The Bias-Variance Tradeoff in Data-Driven Optimization: A Local Misspecification Perspective (NeurIPS 2025 · similarity 0.82)
- Speeding Up the NSGA-II with a Simple Tie-Breaking Rule (AAAI 2025 · similarity 0.82)
- Towards Running Time Analysis of Interactive Multi-Objective Evolutionary Algorithms (AAAI 2024 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.