Population Size vs. Runtime of a Simple Evolutionary Algorithm

Abstract

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 like 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 does neither make 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 so far best known gap 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.