Royal road functions and the (1 + λ) evolutionary algorithm: Almost no speed-up from larger offspring populations
Benjamin Doerr, Marvin Künnemann · 2013
We analyze the runtime of the (1 + λ) evolutionary algorithm (EA) on the classic royal road test function class. For a royal road function defined on bit-strings of length n having block sized ≥ log n + (c + 1 + ε) log d, we prove that the (1 + λ) EA with λ = Θ(nc) finds the optimum in an expected number of O(2d/dc· n/d log n/d) generations. Together with our lower bound of Ω(2d/dc), this shows that for royal road functions even very large offspring populations do not reduce the runtime significantly.