Royal Road Functions and the (1 + λ) Evolutionary Algorithm

For a royal road function defined on bit-strings of length n and having block size d \ge log n + (c+1+ε) log d, we prove that the (1+λ) evolutionary algorithm with λ = \Theta(n^c) finds the optimum in an expected number of O((2^d/d^c) (n/d) log (n/d)) generations. As this does not yield the intuitively expected speed-up of λ, we provide a lower bound of O(2^d/d^c) that shows that the (1+λ) EA indeed fails to achieve a high speed-up. Our results indicate that non-trivial offspring populations may help to locate search points outside plateaus, but will not speed-up the search inside plateaus.