An analysis of the role of offspring population size in EAs
Thomas Jansen, Kenneth Alan De Jong · 2002
Evolutionary algorithms (EAs) are general stochastic search heuristics often used to solve complex optimization problems. Unfortunately, EA theory is still somewhat weak with respect to providing a deeper understanding of EAs and guidance for the practitioner. In this paper we improve this situation by extending existing theory on the well-known (1+1) EA to cover the (1 + λ) EA, an EA that maintains an offspring population of size λ. Our goal is to understand how the value of λ affects expected optimization time. We compare the (1 + λ) EA with the (1+1) EA and prove that on simple unimodal functions no improvements are obtained for λ > 1. By contrast there are more complex functions for which sensible values of A can decrease the optimization time from exponential to a polynomial of small degree with overwhelming probability. These results shed light on the role of λ and provide some guidelines for the practitioner.