All Constant Mutation Rates for the $(1+1)$ Evolutionary Algorithm
Provides a theoretical result for evolutionary computation researchers, showing that no single mutation rate is universally optimal.
The paper proves that for any mutation rate in (0,1), there exists a fitness function where that rate is optimal for the (1+1) EA, showing the set of optimal mutation rates is dense in [0,1].
For every mutation rate $p \in (0, 1)$, and for all $\varepsilon > 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-\varepsilon, p+\varepsilon)$. 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.