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.

通过对CLIFF基准的数学运行时间分析，我们发现-除了一个局部最优之外-大多数悬崖函数仅需要接受一个较差的解来进行优化。虽然Metropolis算法表面上能够从其工作原理中获利，但即使在最佳温度下，大多数悬崖函数的优化效率还不如简单的精英进化算法，因此MA的成功实践仍有待完善，目前的解决办法是发展全局变异算子。

大都市算法处理局部最优解的效果如何？