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 is1/2p2 ((1 - p)-n+1 - (1 - p)). For the standard value of p ≅ 1/n, this is approximately 0.86n2. 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.77n2. 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.68n2, 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.Süntje Böttcher, Benjamin Doerr and Frank Neuman