The impact of random initialization on the runtime of randomized search heuristics
Benjamin Doerr, Carola Doerr · 2014
It has often been observed that the expected runtime of an evolutionary algorithm with random initialization does not deviate much from the expected runtime when starting in an initial solution of average fitness. Having this information a priori would greatly simplify the runtime analysis for the algorithm using random initialization. We prove such a result for the optimization of the OneMax test function via the two randomized search heuristics Randomized Local Search (RLS) and the (1+1) Evolutionary Algorithm. For both algorithms, we show that the expected runtime from a random initial solution deviates at most by a constant number of iterations from the expected runtime when starting with a solution having exactly n/2 ones.