2016/08/10 by Lengler, Johannes, Steger, Angelika · 1 citation
#60G40 #60J10 #68W20 #68W40 #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #G.3 #Neural and Evolutionary Computing (cs.NE) #Probability (math.PR)
paper · doi:10.48550/arxiv.1608.03226
One of the easiest randomized greedy optimization algorithms is the following evolutionary algorithm which aims at maximizing a boolean function f:\0,1\n → \mathbb 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.