Population size versus runtime of a simple evolutionary algorithm

Evolutionary algorithms (EAs) find numerous applications, and practical knowledge on EAs is immense. In practice, sophisticated population-based EAs employing selection, mutation and crossover are applied. In contrast, theoretical analysis of EAs often concentrates on very simple algorithms such as the (1+1) EA, where the population size equals 1. In this paper, the question is addressed whether the use of a population by itself can be advantageous. A population-based EA that neither makes use of crossover nor any diversity-maintaining operator is investigated on an example function. It is shown that an increase of the population size by a constant factor decreases the expected runtime from exponential to polynomial. Thereby, the best gap known so far is improved from superpolynomial vs. polynomial to exponential vs. polynomial. Moreover, it is proved that the exponential and polynomial runtime bounds occur with a probability exponentially close to one if the population size is a constant (resp., a small polynomial). Finally, a second example function, where only a small population leads to a polynomial runtime, and a hierarchy result on the appropriate population size are presented. The analyses show formally how the population size can lead to different attractors in the search space.