  In recent work, Lissovoi, Oliveto, and Warwicker (Artificial Intelligence
(2023)) proved that the Move Acceptance Hyper-Heuristic (MAHH) leaves the local
optimum of the multimodal CLIFF benchmark with remarkable efficiency. The
$O(n^3)$ runtime of the MAHH, for almost all cliff widths $d\ge 2,$ is
significantly better than the $\Theta(n^d)$ runtime of simple elitist
evolutionary algorithms (EAs) on CLIFF.
  In this work, we first show that this advantage is specific to the CLIFF
problem and does not extend to the JUMP benchmark, the most prominent
multi-modal benchmark in the theory of randomized search heuristics. We prove
that for any choice of the MAHH selection parameter $p$, the expected runtime
of the MAHH on a JUMP function with gap size $m = O(n^{1/2})$ is at least
$\Omega(n^{2m-1} / (2m-1)!)$. This is significantly slower than the $O(n^m)$
runtime of simple elitist EAs. Encouragingly, we also show that replacing the
local one-bit mutation operator in the MAHH with the global bit-wise mutation
operator, commonly used in EAs, yields a runtime of $\min\{1,
O(\frac{e\ln(n)}{m})^m\} \, O(n^m)$ on JUMP functions. This is at least as good
as the runtime of simple elitist EAs. For larger values of $m$, this result
proves an asymptotic performance gain over simple EAs. As our proofs reveal,
the MAHH profits from its ability to walk through the valley of lower objective
values in moderate-size steps, always accepting inferior solutions. This is the
first time that such an optimization behavior is proven via mathematical means.
Generally, our result shows that combining two ways of coping with local
optima, global mutation and accepting inferior solutions, can lead to
considerable performance gains.
