Rigorous analyses of fitness-proportional selection for optimizing linear functions
Edda Happ, Daniel Johannsen, Christian Klein, Frank Neumann · 2008
Rigorous runtime analyses of evolutionary algorithms (EAs) mainly investigate algorithms that use elitist selection methods. Two algorithms commonly studied are Randomized Local Search (RLS) and the (1+1) EA and it is well known that both optimize any linear pseudo-Boolean function on n bits within an expected number of O(n log n) fitness evaluations. In this paper, we analyze variants of these algorithms that use fitness proportional selection.