Optimal mutation rates for the (1+λ) EA on OneMax

We study the (1 + λ) EA with mutation probability c/n, where c > 0 is a constant, on the ONEMAX problem. Using an improved variable drift theorem, 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 the parameters 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.