pith. sign in

arxiv: 2606.13344 · v1 · pith:GJWGI3LWnew · submitted 2026-06-11 · 💻 cs.NE

Improved Runtime Bound for the (μ + 1) EA on BinVal

Joris Belder , Johannes Lengler , Raghu Raman Ravi This is my paper

Pith reviewed 2026-06-27 04:54 UTC · model grok-4.3

classification 💻 cs.NE
keywords evolutionary algorithmruntime analysisBinValOneMaxpopulation sizemutation operatoroptimization
0
0 comments X

The pith

The (μ+1) EA optimizes BinVal using at most O(μ log μ n log n) evaluations when μ is o(n/log n).

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes a tighter upper bound on the number of fitness evaluations the (μ+1) evolutionary algorithm needs to reach the optimum of the Binary Value function. The new bound improves an earlier result that depended on a high polynomial power of the population size μ. The improvement shows that the algorithm remains competitive with its performance on the simpler OneMax problem, differing only by a logarithmic factor in μ and n. Readers interested in the scaling of population-based search on weighted bit-string problems would find this relevant because it removes a large overhead that previously appeared tied to the population size.

Core claim

The (μ+1) EA needs at most O(μ log μ · n log n) function evaluations to find the optimum of BinVal when μ = o(n/log n). The result holds for standard bit mutation and several other mutation operators. As a direct consequence the runtime on BinVal exceeds the runtime on OneMax by at most a factor of O(log μ · log n).

What carries the argument

The (μ+1) population update rule that retains the best individual while introducing a single mutated offspring, analyzed under the condition that population size remains o(n/log n).

If this is right

  • The (μ+1) EA on BinVal is at most O(log μ log n) times slower than the same algorithm on OneMax.
  • The polynomial dependence on μ in earlier bounds can be reduced to a near-linear dependence multiplied by log μ.
  • The result applies uniformly to several standard mutation operators.
  • The analysis technique succeeds without requiring μ to be constant or logarithmic in n.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same proof strategy might extend to other weighted linear functions if the bit weights satisfy similar ordering properties.
  • Removing the o(n/log n) restriction on μ would require either a new technique or acceptance that the runtime could grow faster.
  • The logarithmic gap to OneMax suggests that BinVal may serve as a test case for separating the difficulty of different pseudo-Boolean landscapes in population-based search.

Load-bearing premise

The stated runtime bound holds only when the population size satisfies μ = o(n/log n).

What would settle it

A concrete counter-example run or refined analysis showing that the expected number of evaluations exceeds Ω(μ log μ n log n) for some sequence of μ = o(n/log n) and n would falsify the claim.

Figures

Figures reproduced from arXiv: 2606.13344 by Johannes Lengler, Joris Belder, Raghu Raman Ravi.

Figure 1
Figure 1. Figure 1: Logarithm of the expected runtime of the [PITH_FULL_IMAGE:figures/full_fig_p013_1.png] view at source ↗
read the original abstract

We study the $(\mu+1)$ EA on the Binary Value function BinVal. We show that it needs at most $O(\mu \log \mu \cdot n \log n)$ function evaluations to find the optimum when $\mu = o(n/\log n)$. This substantially improves upon the recent upper bound of $O(\mu^5 n \log(n/\mu^4))$ by Krejca, Neumann and Witt. Our results hold for several mutation operators including standard bit mutation. In particular, our bound implies that the $(\mu+1)$ EA is at most a factor $O(\log \mu \cdot \log n)$ slower on BinVal than on OneMax.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 1 minor

Summary. The manuscript analyzes the runtime of the (μ + 1) EA on the BinVal function. It establishes an upper bound of O(μ log μ · n log n) function evaluations to reach the optimum when μ = o(n/log n). The analysis employs a level-based approach that combines multiplicative drift with population-size-dependent selection probabilities. The bound holds for standard bit mutation and related operators, and implies that the algorithm is at most a factor O(log μ · log n) slower on BinVal than on OneMax. This improves upon the prior bound of O(μ^5 n log(n/μ^4)).

Significance. If the central claim holds, the result is significant because it substantially tightens the dependence on μ while remaining within the regime μ = o(n/log n), and it shows that BinVal is only logarithmically harder than OneMax for this algorithm. The manuscript ships a formal level-based derivation of the bound, which is a strength.

minor comments (1)
  1. [Abstract] Abstract: the claim that the bound 'substantially improves' the prior result would be strengthened by a brief parenthetical comparison of the exponents on μ.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our work, the recognition of its significance, and the recommendation for minor revision. No specific major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation uses standard drift analysis independent of inputs

full rationale

The paper derives the O(μ log μ · n log n) runtime bound via level-based analysis combining multiplicative drift with population-size-dependent selection probabilities. The μ = o(n/log n) restriction is an explicit assumption used to ensure selection probabilities remain large enough relative to the n fitness levels; it is not derived from the bound itself. No equations reduce a claimed prediction to a fitted parameter by construction, no self-citation chain is load-bearing for the central result, and the analysis does not rename known empirical patterns or smuggle ansatzes. The derivation is self-contained against external benchmarks such as prior runtime results on OneMax and BinVal.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based solely on the abstract; no free parameters, invented entities, or non-standard axioms are mentioned. The result is stated in standard asymptotic notation common to the field.

axioms (1)
  • standard math Standard mathematical tools of runtime analysis including big-O notation and probabilistic bounds on mutation success probabilities.
    The claim is expressed using asymptotic notation that presupposes these background tools.

pith-pipeline@v0.9.1-grok · 5648 in / 1181 out tokens · 49038 ms · 2026-06-27T04:54:07.184000+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

24 extracted references · 19 canonical work pages · 1 internal anchor

  1. [1]

    Algorithmica 83(4), 1054–1095 (2021).https://doi.org/10.1007/S00453-020-00731-5

    Antipov, D., Doerr, B.: A tight runtime analysis for the (µ+λ) EA. Algorithmica 83(4), 1054–1095 (2021).https://doi.org/10.1007/S00453-020-00731-5

    work page doi:10.1007/s00453-020-00731-5 2021

  2. [2]

    In: Proceedings of the Genetic and Evolutionary Computation Conference

    Antipov, D., Doerr, B., Yang, Q.: The efficiency threshold for the offspring population size of the (µ, λ) EA. In: Proceedings of the Genetic and Evolutionary Computation Conference. pp. 1268–1276. ACM (July 2019). https://doi.org/10.1145/3321707. 3321851

    work page doi:10.1145/3321707 2019

  3. [3]

    IEEE Transactions on Evolutionary Computation22(3), 484–497 (Jun 2018)

    Dang, D.C., Friedrich, T., Kotzing, T., Krejca, M.S., Lehre, P .K., Oliveto, P .S., Sudholt, D., Sutton, A.M.: Escaping local optima using crossover with emergent diversity. IEEE Transactions on Evolutionary Computation22(3), 484–497 (Jun 2018). https: //doi.org/10.1109/tevc.2017.2724201

    work page doi:10.1109/tevc.2017.2724201 2018

  4. [4]

    Proceedings of the AAAI Conference on Artificial Intelligence38(18), 20683–20691 (Mar 2024)

    Doerr, B., Echarghaoui, A., Jamal, M., Krejca, M.S.: Runtime analysis of the (µ+ 1) GA: Provable speed-ups from strong drift towards diverse populations. Proceedings of the AAAI Conference on Artificial Intelligence38(18), 20683–20691 (Mar 2024). https://doi.org/10.1609/aaai.v38i18.30055

    work page doi:10.1609/aaai.v38i18.30055 2024

  5. [5]

    Algorithmica65(1), 224–250 (2013)

    Doerr, B., Goldberg, L.A.: Adaptive drift analysis. Algorithmica65(1), 224–250 (2013). https://doi.org/10.1007/S00453-011-9585-3

    work page doi:10.1007/s00453-011-9585-3 2013

  6. [6]

    Evolutionary Computation21(1), 1–27 (2013)

    Doerr, B., Jansen, T., Sudholt, D., Winzen, C., Zarges, C.: Mutation rate matters even when optimizing monotonic functions. Evolutionary Computation21(1), 1–27 (jul 2013).https://doi.org/10.1162/EVCO_A_00055

    work page doi:10.1162/evco_a_00055 2013

  7. [7]

    Algorithmica 64(4), 673–697 (Dec 2012)

    Doerr, B., Johannsen, D., Winzen, C.: Multiplicative drift analysis. Algorithmica 64(4), 673–697 (Feb 2012).https://doi.org/10.1007/s00453-012-9622-x

    work page doi:10.1007/s00453-012-9622-x 2012

  8. [8]

    Theoretical Com- puter Science561, 3–23 (Jan 2015)

    Doerr, B., Künnemann, M.: Optimizing linear functions with the (1 +λ) evolutionary algorithm—different asymptotic runtimes for different instances. Theoretical Com- puter Science561, 3–23 (Jan 2015). https://doi.org/10.1016/j.tcs.2014.03.015

    work page doi:10.1016/j.tcs.2014.03.015 2015

  9. [9]

    Theoretical Computer Science276(1–2), 51–81 (Apr 2002)

    Droste, S., Jansen, T., Wegener, I.: On the analysis of the (1 + 1) evolutionary algorithm. Theoretical Computer Science276(1–2), 51–81 (Apr 2002). https://doi. org/10.1016/s0304-3975(01)00182-7

    work page doi:10.1016/s0304-3975(01)00182-7 2002

  10. [10]

    Natural Computing3(1), 21–35 (2004)

    He, J., Yao, X.: A study of drift analysis for estimating computation time of evo- lutionary algorithms. Natural Computing3(1), 21–35 (2004). https://doi.org/10. 1023/B:NACO.0000023417.31393.c7

    arXiv 2004

  11. [11]

    Anytime Analysis on BinVal: Adaptive Parameters Help

    Kötzing, T., Sander, J.: Anytime analysis on BinVal: Adaptive parameters help (2026). https://doi.org/10.48550/ARXIV.2604.06976

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2604.06976 2026

  12. [12]

    In: Proceedings of the Foundations of Genetic Algorithms

    Krejca, M.S., Neumann, F., Witt, C.: Population dynamics and improved runtime guarantees for the (µ+ 1) EA on BinVal. In: Proceedings of the Foundations of Genetic Algorithms. pp. 142–153. FOGA ’25, ACM (Aug 2025). https://doi.org/ 10.1145/3729878.3746614

    work page doi:10.1145/3729878.3746614 2025

  13. [13]

    Lengler, J.: Drift analysis, pp. 89–131. Springer (Nov 2019). https://doi.org/10. 1007/978-3-030-29414-4_2

    2019

  14. [14]

    IEEE Transactions on Evolutionary Computation24(6), 995–1009 (2020)

    Lengler, J.: A general dichotomy of evolutionary algorithms on monotone functions. IEEE Transactions on Evolutionary Computation24(6) (May 2019). https://doi. org/10.1109/TEVC.2019.2917014

    work page doi:10.1109/tevc.2019.2917014 2019

  15. [15]

    In: Bäck, T., Preuss, M., Deutz, A.H., Wang, H., Doerr, C., Em- merich, M.T.M., Trautmann, H

    Lengler, J., Meier, J.: Large population sizes and crossover help in dynamic environments. In: Bäck, T., Preuss, M., Deutz, A.H., Wang, H., Doerr, C., Em- merich, M.T.M., Trautmann, H. (eds.) Proceedings of the Parallel Problem Solving from Nature. pp. 610–622. Lecture Notes in Computer Science, Springer (2020). https://doi.org/10.1007/978-3-030-58112-1_42

    work page doi:10.1007/978-3-030-58112-1_42 2020

  16. [16]

    SN Computer Science3(4) (Jun 2022)

    Lengler, J., Riedi, S.: Runtime analysis of the (µ+ 1)-EA on the dynamic Bin- Val function. SN Computer Science3(4) (Jun 2022). https://doi.org/10.1007/ s42979-022-01203-z 16 J. Belder, J. Lengler, R. Ravi

    2022

  17. [17]

    In: Proceedings of the IEEE Symposium Series on Computational Intelligence

    Lengler, J., Schaller, U.: The (1 + 1)-EA on noisy linear functions with random positive weights. In: Proceedings of the IEEE Symposium Series on Computational Intelligence. pp. 712–719. IEEE (may 2018). https://doi.org/10.1109/SSCI.2018. 8628785

    work page doi:10.1109/ssci.2018 2018

  18. [18]

    Lengler, J., Steger, A.: Drift analysis and evolutionary algorithms revisited. Comb. Probab. Comput.27(4), 643–666 (2018). https://doi.org/10.1017/ S0963548318000275

    2018

  19. [19]

    Theoretical Computer Science875, 28–51 (Jul 2021)

    Lengler, J., Zou, X.: Exponential slowdown for larger populations: The (µ+ 1)- EA on monotone functions. Theoretical Computer Science875, 28–51 (Jul 2021). https://doi.org/10.1016/j.tcs.2021.03.025

    work page doi:10.1016/j.tcs.2021.03.025 2021

  20. [20]

    Algorithmica78(2), 641–659 (December 2016)

    Lissovoi, A., Witt, C.: A runtime analysis of parallel evolutionary algorithms in dynamic optimization. Algorithmica78(2), 641–659 (December 2016). https://doi. org/10.1007/s00453-016-0262-4

    work page doi:10.1007/s00453-016-0262-4 2016

  21. [21]

    Sudholt, D.: The benefits of population diversity in evolutionary algorithms: A survey of rigorous runtime analyses, pp. 359–404. Springer (Nov 2019). https: //doi.org/10.1007/978-3-030-29414-4_8

    work page doi:10.1007/978-3-030-29414-4_8 2019

  22. [22]

    Evolutionary Computation14(1), 65–86 (Mar 2006)

    Witt, C.: Runtime analysis of the (µ+ 1) EA on simple pseudo-Boolean functions. Evolutionary Computation14(1), 65–86 (Mar 2006). https://doi.org/10.1162/ evco.2006.14.1.65

    2006

  23. [23]

    Sousa, C

    Witt, C.: Population size versus runtime of a simple evolutionary algorithm. Theo- retical Computer Science403(1), 104–120 (Aug 2008). https://doi.org/10.1016/j. tcs.2008.05.011

    work page doi:10.1016/j 2008

  24. [24]

    intermediate

    Witt, C.: Tight bounds on the optimization time of a randomized search heuristic on linear functions. Combinatorics, Probability and Computing22(2), 294–318 (Jan 2013).https://doi.org/10.1017/s0963548312000600

    work page doi:10.1017/s0963548312000600 2013