(1+1)-ES and the One-Fifth Rule

The (1+1) ES algorithm operates as follows. At each iteration:

One parent $x$ generates one offspring:

$$x^{\prime }=x+\sigma z,z\sim \mathcal{N}(0,I)$$

Then, we do selection:

$$x_{t+1}=\{\begin{array}{ll}{x}^{\prime }& \text{if }f(x^{\prime })<f(x)\\ x& \text{otherwise}\end{array}$$

Note that we are using $\mu =1,\lambda =1$ with elitist selection. Thus, only improvements survive.

The 1/5 rule regulates exploration by controlling step size. Specifically, we define a mutation to be successful if $f(x^{\prime })<f(x)$. The success probability is the empirical success rate over $k$ iterations, given as:

$$p_s=\frac{\text{number of successful mutations}}{k}$$

Rechenberg showed that for $f(x)=||x|{|}^2$, the maximum expected progress occurs when $p_s\approx \frac{1}{5}$. This means that too many successes means that $\sigma$ is too small, and too few successes means that $\sigma$ is too large. The optimal balance is about 20% success.

From this, we can form an adaptive rule to change $\sigma$:

$$\sigma =\{\begin{array}{ll}\sigma /c& \text{if }{p}_s>\frac{1}{5}\\ \sigma \cdot c& \text{if }{p}_s<\frac{1}{5}\\ \sigma & \text{if }{p}_s=\frac{1}{5}\end{array}$$

with $0.8\le c\le 1$.