Drift Analysis and Evolutionary Algorithms Revisited

Abstract

One of the easiest randomized greedy optimization algorithms is the following evolutionary algorithm which aims at maximizing a boolean function f:\0,1\^n R. The algorithm starts with a random search point \0,1\^n, and in each round it flips each bit of with probability c/n independently at random, where c>0 is a fixed constant. The thus created offspring ' replaces if and only if f(') f(). The analysis of the runtime of this simple algorithm on monotone and on linear functions turned out to be highly non-trivial. In this paper we review known results and provide new and self-contained proofs of partly stronger results.

Tasks

Reproductions