[Paper] The $(1 + 1)$-EA in Dynamic Environments
Source: arXiv - 2606.13360v1
Overview
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 $χ$ for mutation rate $χ/n$. Below the threshold, the expected optimisation time is $\mathcal{O}(n\log n)$, whereas above it the runtime becomes $2^{Ω(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.
Key Contributions
This paper presents research in the following areas:
- cs.NE
- cs.DS
Methodology
Please refer to the full paper for detailed methodology.
Practical Implications
This research contributes to the advancement of cs.NE.
Authors
- Georg Hasebe
- Johannes Lengler
- Raghu Raman Ravi
Paper Information
- arXiv ID: 2606.13360v1
- Categories: cs.NE, cs.DS
- Published: June 11, 2026
- PDF: Download PDF