Proves sharp threshold on mutation parameter χ for (1+1)-EA on Dynamic Binary Value and Uniform weight dynamic linear problems, yielding O(n log n) runtime below threshold and 2^Ω(n) above, plus a second stagnation-distance threshold for the former.
Algorithmica 64(4), 673–697 (Dec 2012)
4 Pith papers cite this work. Polarity classification is still indexing.
4
Pith papers citing it
citation-role summary
method 1
citation-polarity summary
fields
cs.NE 4years
2026 4verdicts
UNVERDICTED 4roles
method 1polarities
use method 1representative citing papers
The (μ+1) EA optimizes BinVal in O(μ log μ · n log n) evaluations for μ = o(n/log n), improving the prior O(μ^5 n log(n/μ^4)) bound.
In the dueling bandit setting, the (1+1) EA selects the Condorcet winner with only constant probability when its advantage is Ω(1/n), while a Max-Min Ant System EDA selects it with probability 1-Θ(p), and repeated duels improve the EA's performance.
Self-adjusting mutation rates let the (1+1) EA optimize the top k bits of BinVal in O(k^{1+ε}) time independent of n for all k in o(n) simultaneously.
citing papers explorer
-
The $(1 + 1)$-EA in Dynamic Environments
Proves sharp threshold on mutation parameter χ for (1+1)-EA on Dynamic Binary Value and Uniform weight dynamic linear problems, yielding O(n log n) runtime below threshold and 2^Ω(n) above, plus a second stagnation-distance threshold for the former.
-
Improved Runtime Bound for the $(\mu + 1)$ EA on BinVal
The (μ+1) EA optimizes BinVal in O(μ log μ · n log n) evaluations for μ = o(n/log n), improving the prior O(μ^5 n log(n/μ^4)) bound.
-
Analysis of Search Heuristics in the Multi-Armed Bandit Setting
In the dueling bandit setting, the (1+1) EA selects the Condorcet winner with only constant probability when its advantage is Ω(1/n), while a Max-Min Ant System EDA selects it with probability 1-Θ(p), and repeated duels improve the EA's performance.
-
Anytime Analysis on BinVal: Adaptive Parameters Help
Self-adjusting mutation rates let the (1+1) EA optimize the top k bits of BinVal in O(k^{1+ε}) time independent of n for all k in o(n) simultaneously.