All Constant Mutation Rates for the $(1+1)$ Evolutionary Algorithm

Abstract

For every mutation rate $p\in (0,1)$, and for all $\epsilon >0$, there is a fitness function $f:\{0,1{\}}^n\to \mathbb{R}$ with a unique maximum for which the optimal mutation rate for the $(1+1)$ evolutionary algorithm on $f$ is in $(p-\epsilon ,p+\epsilon )$. In other words, the set of optimal mutation rates for the $(1+1)$ EA is dense in the interval $[0,1]$. To show that, this paper introduces DistantSteppingStones, a fitness function which consists of large plateaus separated by large fitness valleys.

12 pages, version 2