The $(1 + 1)$-EA in Dynamic Environments
This provides theoretical validation for previously empirical observations in dynamic optimization, establishing rigorous runtime bounds for evolutionary algorithms in changing environments.
The paper proves a sharp threshold in the mutation rate for the (1+1)-EA in dynamic linear environments: below the threshold, expected optimization time is O(n log n); above it, runtime becomes 2^{Ω(n)}. For the Dynamic Binary Value problem, a second threshold is identified where reaching a certain distance from the optimum is efficient but further progress takes exponential time.
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.