Optimal fixed and adaptive mutation rates for the LeadingOnes problem

We reconsider a classical problem, namely how the (1+1) evolutionary algorithm optimizes the LeadingOnes function. We prove that if a mutation probability of p is used and the problem size is n, then the optimization time is 1/2p²((1 - p)^-n+1-(1 - p)). For the standard value of p = 1/n, this is approximately 0.86 n². As our bound shows, this mutation probability is not optimal: For p ≈ 1.59/n, the optimization time drops by more than 16% to approximately 0.77n². Our method also allows to analyze mutation probabilities depending on the current fitness (as used in artificial immune systems). Again, we derive an exact expression. Analysing it, we find a fitness dependent mutation probability that yields an expected optimization time of approximately 0.68n², another 12% improvement over the optimal mutation rate. In particular, this is the first example where an adaptive mutation rate provably speeds up the computation time. In a general context, these results suggest that the final word on mutation probabilities in evolutionary computation is not yet spoken.