| Evolutionary algorithms (EAs) are widely applied in practice, yet most theoretically rigorous analyses of their performance are restricted to rather simple settings, since these processes are highly non-trivial to analyze. We aim to contribute to the theoretical understanding of EAs by examining the runtime of an evolutionary algorithm with a non-trivial offspring population on an interesting test function class.
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. |
