pith. sign in

arxiv: 2606.13360 · v1 · pith:TKJOC5MJnew · submitted 2026-06-11 · 💻 cs.NE · cs.DS

The (1 + 1)-EA in Dynamic Environments

Georg Hasebe , Johannes Lengler , Raghu Raman Ravi This is my paper

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

classification 💻 cs.NE cs.DS
keywords evolutionary algorithmsdynamic optimizationruntime analysismutation rate(1+1)-EAlinear functionsthreshold behavior
0
0 comments X

The pith

The (1+1)-EA has a sharp mutation rate threshold separating O(n log n) from exponential runtime on dynamic linear problems.

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

This paper analyzes the performance of the (1+1) evolutionary algorithm when the objective function is a new random linear function in every generation. It establishes that the expected time to find the optimum depends critically on the mutation rate parameter χ. For mutation rates χ/n below a certain threshold the time is O(n log n), but above the threshold it becomes 2^Ω(n). The same threshold behavior appears in both the dynamic binary value model and the uniform weight model. For the binary value case the analysis further shows a stagnation distance that can be reached quickly but cannot be improved upon efficiently.

Core claim

For both the Dynamic Binary Value problem and the Uniform weight variant, the (1+1)-EA exhibits a sharp threshold in the mutation parameter χ: when using mutation rate χ/n with χ below the threshold the expected optimisation time is O(n log n), while above the threshold the runtime is 2^Ω(n). In the exponential regime for Dynamic Binary Value there is an additional threshold distance from the optimum that the process reaches efficiently, but from which further progress requires exponential time.

What carries the argument

The sharp threshold value of the mutation parameter χ for mutation rate χ/n when the linear fitness function is resampled independently each generation.

If this is right

  • Below the threshold the algorithm reaches the optimum in polynomial time despite the changing environment.
  • Above the threshold the search stagnates and fails to reach the optimum in polynomial time.
  • For Dynamic Binary Value the process efficiently reaches a specific positive distance from the optimum but cannot close the gap further without exponential time.
  • The threshold statements apply to both the permutation-based and the independent uniform weight models.

Where Pith is reading between the lines

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

  • If fitness functions were correlated across generations instead of independent the location or existence of the threshold could change.
  • The same mutation parameter might control runtime in other dynamic problems that use linear or near-linear fitness.
  • An adaptive mutation rate that lowers itself when the environment changes rapidly could avoid the exponential regime.

Load-bearing premise

The linear function is sampled completely independently in every generation with all weights strictly positive.

What would settle it

Running the (1+1)-EA on either model with mutation rate χ/n just below and just above the threshold and checking whether runtime jumps from O(n log n) to 2^Ω(n).

Figures

Figures reproduced from arXiv: 2606.13360 by Georg Hasebe, Johannes Lengler, Raghu Raman Ravi.

Figure 1
Figure 1. Figure 1: Visualization of the DBV plateau location from Theorem 4 (3). For 0 < χ < χdbv, the (1 + 1)-EA reaches the optimum efficiently, so the plotted plateau fraction of correct bits is 1. For χ > χdbv, the algorithm gets stuck at plateau fraction 1− α ∗ (χ), where α ∗ (χ) is given in Equation (17). The dotted line marks the critical threshold χdbv ≈ 1.59362. As discussed earlier, the proof in [25,27] has a gap, … view at source ↗
read the original abstract

We study the $(1 + 1)$-EA in dynamic linear environments, where in every generation selection is performed with respect to a freshly sampled linear function with positive weights. We consider the Dynamic Binary Value problem, where each generation uses a uniformly random permutation of $1,2,4,\dots,2^{n-1}$, and a Uniform weight variant, where the weights are drawn independently from $\mathrm{Unif}(0,1)$. Both of them have recently been integrated into the IOHprofiler platform and empirically studied. For both models we prove a sharp threshold in the mutation parameter $\chi$ for mutation rate $\chi/n$. Below the threshold, the expected optimisation time is $\mathcal{O}(n\log n)$, whereas above it the runtime becomes $2^{\Omega(n)}$. For the Dynamic Binary Value problem in the exponential regime, we also quantify at what distance from the optimum the optimisation process stagnates. We show that there is a second threshold: a distance that is efficiently reached, but reaching any smaller distance takes exponential time. This quantifies and proves previous empirical findings.

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 / 3 minor

Summary. The paper analyzes the (1+1)-EA on two dynamic linear optimization models in which a fresh linear function with strictly positive weights is sampled independently each generation. For the Dynamic Binary Value problem (uniform random permutation of weights 1,2,4,...,2^{n-1}) and the Uniform model (independent Unif(0,1) weights), it proves a sharp threshold on the mutation parameter χ for mutation rate χ/n: expected optimization time is O(n log n) below the threshold and 2^Ω(n) above it. For Dynamic Binary Value in the super-critical regime, a second threshold is established quantifying the distance from the optimum at which the process stagnates.

Significance. If the proofs hold, the work supplies the first rigorous sharp-threshold analysis of the (1+1)-EA in fully dynamic linear environments with per-generation independent resampling. The explicit model definitions, the matching of empirical IOHprofiler observations, and the additional stagnation-distance result for the exponential regime constitute a clear advance for the theory of evolutionary algorithms on changing landscapes.

minor comments (3)
  1. [Abstract] The abstract states that both models 'have recently been integrated into the IOHprofiler platform' but supplies no citation; adding the reference would improve traceability.
  2. [Model definitions] Notation for the two models (Dynamic Binary Value vs. Uniform) is introduced clearly in the abstract but should be repeated with a short table or bullet list at the start of the model-definition section for quick reference.
  3. [Section 2] The statement that weights are 'strictly positive' is used repeatedly; a single sentence confirming that zero weights are excluded by construction (rather than occurring with probability zero) would eliminate any ambiguity for readers.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive evaluation of our work on sharp thresholds for the (1+1)-EA in dynamic linear environments and for recommending minor revision. The report accurately captures the main contributions regarding the mutation parameter threshold for both Dynamic Binary Value and Uniform models, as well as the stagnation-distance result.

Circularity Check

0 steps flagged

No significant circularity; proofs are self-contained probabilistic analysis

full rationale

The paper derives sharp thresholds on expected runtime for the (1+1)-EA via direct probabilistic arguments on explicitly defined dynamic models (independent uniform random linear functions with positive weights each generation). No equations reduce a claimed prediction to a fitted parameter defined by the same analysis, no load-bearing self-citations are invoked to justify uniqueness or ansatzes, and the model assumptions (independence, positivity) are stated upfront rather than smuggled in. The derivation chain is external to the result itself and does not collapse by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The analysis rests on standard probabilistic tools for runtime analysis of evolutionary algorithms (drift theorems, Chernoff bounds) that are external to the paper; no free parameters are fitted to data and no new entities are postulated.

axioms (1)
  • standard math Standard concentration inequalities and drift analysis lemmas from prior EA theory literature apply directly to the dynamic linear setting.
    Invoked implicitly to establish the polynomial vs exponential regimes.

pith-pipeline@v0.9.1-grok · 5724 in / 1335 out tokens · 32104 ms · 2026-06-27T04:50:58.685171+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

38 extracted references · 14 canonical work pages

  1. [1]

    Evolutionary Computation14(3), 291–308 (2006) 34 G

    Arnold, D., Beyer, H.G.: Optimum tracking with Evolution Strategies. Evolutionary Computation14(3), 291–308 (2006) 34 G. Hasebe, J. Lengler, R. Ravi

    2006

  2. [2]

    Probability Surveys 16, 1–61 (2019)

    Arratia, R., Goldstein, L., Kochman, F.: Size bias for one and all. Probability Surveys 16, 1–61 (2019)

    2019

  3. [3]

    Baricz, Á.: Generalized Bessel functions of the first kind, Lecture Notes in Mathemat- ics, vol. 1994. Springer, Berlin (2010). https://doi.org/10.1007/978-3-642-12230-9

    work page doi:10.1007/978-3-642-12230-9 1994

  4. [4]

    Branke, J.: Evolutionary optimization in dynamic environments, vol. 1. Springer (2002)

    2002

  5. [5]

    Algorithmica78(2), 660–680 (2017)

    Dang, D.C., Jansen, T., Lehre, P .K.: Populations can be essential in tracking dynamic optima. Algorithmica78(2), 660–680 (2017)

    2017

  6. [6]

    https://dlmf.nist.gov/, Release 1.2.5 of 2025-12-15, https://dlmf.nist.gov/, f

    NIST Digital Library of Mathematical Functions. https://dlmf.nist.gov/, Release 1.2.5 of 2025-12-15, https://dlmf.nist.gov/, f. W. J. Olver, A. B. Olde Daalhuis, D. W. Lozier, B. I. Schneider, R. F. Boisvert, C. W. Clark, B. R. Miller, B. V . Saunders, H. S. Cohl, and M. A. McClain, eds

    2025

  7. [7]

    In: Theory of evolutionary computation: Recent developments in discrete optimiza- tion, pp

    Doerr, B.: Probabilistic tools for the analysis of randomized optimization heuristics. In: Theory of evolutionary computation: Recent developments in discrete optimiza- tion, pp. 1–87. Springer (2019)

    2019

  8. [8]

    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 (2013). https://doi.org/10.1162/EVCO_a_00055

    work page doi:10.1162/evco_a_00055 2013

  9. [9]

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

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

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

  10. [10]

    Applied Soft Computing88, 106027 (Mar 2020)

    Doerr, C., Ye, F., Horesh, N., Wang, H., Shir, O.M., Bäck, T.: Benchmarking discrete optimization heuristics with IOHprofiler. Applied Soft Computing88, 106027 (Mar 2020). https://doi.org/10.1016/j.asoc.2019.106027

    work page doi:10.1016/j.asoc.2019.106027 2020

  11. [11]

    In: Proceedings of the Congress on Evolutionary Computation

    Droste, S.: Analysis of the (1 + 1) EA for a dynamically changing OneMax-variant. In: Proceedings of the Congress on Evolutionary Computation. vol. 1, pp. 55–60. IEEE (2002)

    2002

  12. [12]

    In: Proceedings of the Genetic and Evolutionary Computation Conference

    Droste, S.: Analysis of the (1 + 1) EA for a dynamically bitwise changing OneMax. In: Proceedings of the Genetic and Evolutionary Computation Conference. pp. 909–921. Springer (2003)

    2003

  13. [13]

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

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

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

  14. [14]

    Thorsten-V oice Dataset 2022.10,

    Hasebe, G.: Numerical verification for the (1 + 1) EA on dynamic linear functions with Uniform(0,1) weights. Zenodo (Mar 2026). https://doi.org/10.5281/zenodo. 19232932

    work page doi:10.5281/zenodo 2026

  15. [15]

    Theoretical Computer Science971, 114072 (2023)

    Janett, D., Lengler, J.: Two-dimensional drift analysis: Optimizing two functions simultaneously can be hard. Theoretical Computer Science971, 114072 (2023). https://doi.org/10.1016/j.tcs.2023.114072

    work page doi:10.1016/j.tcs.2023.114072 2023

  16. [16]

    In: Proceedings of the Genetic and Evolutionary Computation Conference

    Jansen, T., Schellbach, U.: Theoretical analysis of a mutation-based evolutionary algorithm for a tracking problem in the lattice. In: Proceedings of the Genetic and Evolutionary Computation Conference. pp. 841–848 (2005)

    2005

  17. [17]

    In: Proceedings of the Genetic and Evolutionary Computation Conference

    Jansen, T., Zarges, C.: Evolutionary algorithms and artificial immune systems on a bi-stable dynamic optimisation problem. In: Proceedings of the Genetic and Evolutionary Computation Conference. pp. 975–982 (2014)

    2014

  18. [18]

    SN Computer Science6(5), 512 (2025)

    Kaufmann, M., Larcher, M., Lengler, J., Sieberling, O.: Hardest monotone functions for evolutionary algorithms. SN Computer Science6(5), 512 (2025). https://doi. org/10.1007/s42979-025-03999-y

    work page doi:10.1007/s42979-025-03999-y 2025

  19. [19]

    In: Proceedings of the Foundations of Genetic Algorithms

    Kötzing, T., Lissovoi, A., Witt, C.: (1 + 1) EA on generalized dynamic OneMax. In: Proceedings of the Foundations of Genetic Algorithms. pp. 40–51 (2015) The(1+1)-EA in Dynamic Environments 35

    2015

  20. [20]

    In: Proceedings of the Parallel Problem Solving from Nature

    Kötzing, T., Molter, H.: ACO beats EA on a dynamic pseudo-Boolean function. In: Proceedings of the Parallel Problem Solving from Nature. pp. 113–122. Springer (2012)

    2012

  21. [21]

    In: Proceedings of the Genetic and Evolutionary Computation Conference

    Lässig, J., Sudholt, D.: The benefit of populations and migration in dynamic opti- mization. In: Proceedings of the Genetic and Evolutionary Computation Conference. pp. 1267–1274 (2010)

    2010

  22. [22]

    In: Doerr, B., Neumann, F

    Lengler, J.: Drift analysis. In: Doerr, B., Neumann, F. (eds.) Theory of evolutionary computation: Recent developments in discrete optimization, pp. 89–131. Springer International Publishing, Cham (2020). https://doi.org/10.1007/978-3-030-29414-4_ 2

    work page doi:10.1007/978-3-030-29414-4_ 2020

  23. [23]

    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), 995–1009 (2020). https://doi. org/10.1109/TEVC.2019.2917014

    work page doi:10.1109/tevc.2019.2917014 2020

  24. [24]

    In: Proceedings of the Analytic Algorithmics and Combinatorics

    Lengler, J., Martinsson, A., Steger, A.: When does hillclimbing fail on monotone functions: An entropy compression argument. In: Proceedings of the Analytic Algorithmics and Combinatorics. pp. 94–102. SIAM (2019)

    2019

  25. [25]

    Natural Computing23(1), 115–129 (2024)

    Lengler, J., Meier, J.: Large population sizes and crossover help in dynamic en- vironments. Natural Computing23(1), 115–129 (2024). https://doi.org/10.1007/ s11047-022-09915-0

    2024

  26. [26]

    SN Computer Science3(4), 324 (2022)

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

    2022

  27. [27]

    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 (Nov 2018). https://doi.org/10.1109/SSCI.2018.8628785

    work page doi:10.1109/ssci.2018.8628785 2018

  28. [28]

    Theoretical Computer Science875, 28–51 (2021)

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

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

  29. [29]

    Levin, D.A., Peres, Y.: Markov chains and mixing times, vol. 107. American Mathe- matical Soc. (2017)

    2017

  30. [30]

    Theoretical Computer Science561(Part A), 73–85 (2015)

    Lissovoi, A., Witt, C.: Runtime analysis of ant colony optimization on dynamic shortest path problems. Theoretical Computer Science561(Part A), 73–85 (2015)

    2015

  31. [31]

    Swarm and Evolutionary Computation6, 1–24 (2012)

    Nguyen, T.T., Yang, S., Branke, J.: Evolutionary dynamic optimization: A survey of the state of the art. Swarm and Evolutionary Computation6, 1–24 (2012). https: //doi.org/10.1016/j.swevo.2012.05.001

    work page doi:10.1016/j.swevo.2012.05.001 2012

  32. [32]

    Oliveto, P .S., Witt, C.: Erratum: Simplified drift analysis for proving lower bounds in evolutionary computation (2012), https://arxiv.org/abs/1211.7184

    Pith/arXiv arXiv 2012

  33. [33]

    In: Proceedings of the Genetic and Evolutionary Computation Conference

    Oliveto, P .S., Zarges, C.: Analysis of diversity mechanisms for optimisation in dynamic environments with low frequencies of change. In: Proceedings of the Genetic and Evolutionary Computation Conference. pp. 837–844 (2013)

    2013

  34. [34]

    In: Proceedings of the Genetic and Evolutionary Computation Conference

    Rohlfshagen, P ., Lehre, P .K., Yao, X.: Dynamic evolutionary optimisation: an anal- ysis of frequency and magnitude of change. In: Proceedings of the Genetic and Evolutionary Computation Conference. pp. 1713–1720 (2009)

    2009

  35. [35]

    Probability Surveys8, 210–293 (2011)

    Ross, N.: Fundamentals of Stein’s method. Probability Surveys8, 210–293 (2011)

    2011

  36. [36]

    In: Proceedings of the Parallel Problem Solving from Nature

    Vermetten, D., Lengler, J., Rusin, D., Bäck, T., Doerr, C.: Empirical analysis of the dynamic Binary Value problem with IOHprofiler. In: Proceedings of the Parallel Problem Solving from Nature. pp. 20–35. Springer (2024)

    2024

  37. [37]

    intermediate

    Witt, C.: Tight bounds on the optimization time of a randomized search heuristic on linear functions. Combinatorics, Probability and Computing22(2), 294–318 (2013). https://doi.org/10.1017/S0963548312000600 36 G. Hasebe, J. Lengler, R. Ravi A Appendix A.1 A mistake in the previous proof To treat states away from the optimum, the proof of [ 27, Theorem 4 a...

    work page doi:10.1017/s0963548312000600 2013

  38. [38]

    Combining the Equation (46) and Equation (47) we conclude that for all k≥0 and allα∈[0, 1], Sk(α) =k(2−k)p A(k, 1)α+R k(α),|R k(α)| ≤ 3 2 k3α2

    pairs, P[Bin(k,α)≥2]≤ k 2 α2 ≤ k2 2 α2, (47) and therefore thei≥2 contribution is bounded (in absolute value) by 1 2 k3α2. Combining the Equation (46) and Equation (47) we conclude that for all k≥0 and allα∈[0, 1], Sk(α) =k(2−k)p A(k, 1)α+R k(α),|R k(α)| ≤ 3 2 k3α2. (48) Insert Equation (48) into Equation (45). Writing K∼Poi(χ) and observing that the term...