The impact of random initialization on the runtime of randomized search heuristics

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. For RLS we can precisely compute that this constant is-1/2 ± o(1). This leads to an extremely precise bound for the expected runtime. The expected number of fitness evaluations until an optimal search point is found, is nH_n/2-1/ 2±o(1), where H_n/2 denotes the (n/2)th harmonic number when n is even, and H_n/2 := (H⌊_n/2⌋ +H⌈_n/2⌉)=2 when n is odd. The main technique to obtain these results is a coupling of the optimization process starting from different fitness levels. We believe this technique to be interesting also much beyond the specific results mentioned above; e.g., for the study of other optimization problems.