  The Metropolis algorithm (MA) is a classic stochastic local search heuristic.
It avoids getting stuck in local optima by occasionally accepting inferior
solutions. To better and in a rigorous manner understand this ability, we
conduct a mathematical runtime analysis of the MA on the CLIFF benchmark. Apart
from one local optimum, cliff functions are monotonically increasing towards
the global optimum. Consequently, to optimize a cliff function, the MA only
once needs to accept an inferior solution. Despite seemingly being an ideal
benchmark for the MA to profit from its main working principle, our
mathematical runtime analysis shows that this hope does not come true. Even
with the optimal temperature (the only parameter of the MA), the MA optimizes
most cliff functions less efficiently than simple elitist evolutionary
algorithms (EAs), which can only leave the local optimum by generating a
superior solution possibly far away. This result suggests that our
understanding of why the MA is often very successful in practice is not yet
complete. Our work also suggests to equip the MA with global mutation
operators, an idea supported by our preliminary experiments.
