Optimal Mutation Rates for the (1+ λ) EA on OneMax Through Asymptotically Tight Drift Analysis

We study the (1+λ) EA, a classical population-based evolutionary algorithm, with mutation probability c / n, where c> 0 and λ are constant, on the benchmark function OneMax, which counts the number of 1-bits in a bitstring. We improve a well-established result that allows to determine the first hitting time from the expected progress (drift) of a stochastic process, known as the variable drift theorem. Using our improved result, we show that upper and lower bounds on the expected runtime of the (1+λ) EA obtained from variable drift theorems are at most apart by a small lower order term if the exact drift is known. This reduces the analysis of expected optimization time to finding an exact expression for the drift. We then give an exact closed-form expression for the drift and develop a method to approximate it very efficiently, enabling us to determine approximate optimal mutation rates for the (1+λ) EA for various parameter settings of c and λ and also for moderate sizes of n. This makes the need for potentially lengthy and costly experiments in order to optimize c for fixed n and λ for the optimization of OneMax unnecessary. Interestingly, even for moderate n and not too small λ it turns out that mutation rates up to 10% larger than the asymptotically optimal rate 1 / n minimize the expected runtime. However, in absolute terms the expected runtime does not change by much when replacing 1 / n with the optimal mutation rate.