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