Drift Analysis and Evolutionary Algorithms Revisited
Johannes Lengler, Angelika Steger · Combinatorics Probability Computing · 2018
One of the easiest randomized greedy optimization algorithms is the following evolutionary algorithm which aims at maximizing a functionf: {0,1}n→ ℝ. The algorithm starts with a random search point ξ ∈ {0,1}n, and in each round it flips each bit of ξ with probabilityc/nindependently at random, wherec> 0 is a fixed constant. The thus created offspring ξ' replaces ξ if and only iff(ξ') ≥f(ξ). The analysis of the runtime of this simple algorithm for monotone and for 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.