All Mutation Rates $c/n$ for the $(1+1)$ Evolutionary Algorithm

Abstract

For every real number $c\ge 1$ and for all $\epsilon >0$, there is a fitness function $f:\{0,1{\}}^n\to \mathbb{R}$ for which the optimal mutation rate for the $(1+1)$ evolutionary algorithm on $f$, denoted $p_n$, satisfies $p_n\approx c/n$ in that $|n{p}_n-c|<\epsilon$. In other words, the set of all $c\ge 1$ for which the mutation rate $c/n$ is optimal for the $(1+1)$ EA is dense in the interval $[1,\infty )$. To show this, a fitness function is introduced which is called HillPathJump.

8 pages