# How Well Does the Metropolis Algorithm Cope With Local Optima?

arXiv: https://arxiv.org/abs/2304.10848 · HTML: https://mlsanity.com/paper/2304.10848/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 73 references that are in the map.
- First posted on arXiv 21 Apr 2023.

## Builds on (most cited first, 16 of 16)

- [Fast Genetic Algorithms](https://mlsanity.com/paper/1703.03334/) (2017)
- [Probabilistic Tools for the Analysis of Randomized Optimization Heuristics](https://mlsanity.com/paper/1801.06733/) (2018)
- [Does Comma Selection Help To Cope With Local Optima](https://mlsanity.com/paper/2004.01274/) (2020)
- [Self-Adjusting Evolutionary Algorithms for Multimodal Optimization](https://mlsanity.com/paper/2004.03266/) (2020)
- [A First Runtime Analysis of the NSGA-II on a Multimodal Problem](https://mlsanity.com/paper/2204.13750/) (2022)
- [Runtime Analysis for the NSGA-II: Provable Speed-Ups From Crossover](https://mlsanity.com/paper/2208.08759/) (2022)
- [From Understanding the Population Dynamics of the NSGA-II to the First Proven Lower Bounds](https://mlsanity.com/paper/2209.13974/) (2022)
- [Stagnation Detection with Randomized Local Search](https://mlsanity.com/paper/2101.12054/) (2021)
- [On the Limitations of the Univariate Marginal Distribution Algorithm to Deception and Where Bivariate EDAs might help](https://mlsanity.com/paper/1907.12438/) (2019)
- [Stagnation Detection in Highly Multimodal Fitness Landscapes](https://mlsanity.com/paper/2104.04395/) (2021)
- [Stagnation Detection Meets Fast Mutation](https://mlsanity.com/paper/2201.12158/) (2022)
- [Optimal Parameter Choices via Precise Black-Box Analysis](https://mlsanity.com/paper/1807.03403/) (2018)
- [First Steps Towards a Runtime Comparison of Natural and Artificial Evolution](https://mlsanity.com/paper/1504.06260/) (2015)
- [Choosing the Right Algorithm With Hints From Complexity Theory](https://mlsanity.com/paper/2109.06584/) (2021)
- [Comma Selection Outperforms Plus Selection on OneMax with Randomly Planted Optima](https://mlsanity.com/paper/2304.09712/) (2023)
- [How the Move Acceptance Hyper-Heuristic Copes With Local Optima: Drastic Differences Between Jumps and Cliffs](https://mlsanity.com/paper/2304.10414/) (2023)

## Built on by (most cited first, 2 of 2)

- [Hyper-Heuristics Can Profit From Global Variation Operators](https://mlsanity.com/paper/2407.14237/) (2024)
- [Speeding Up Hyper-Heuristics With Markov-Chain Operator Selection and the Only-Worsening Acceptance Operator](https://mlsanity.com/paper/2506.01107/) (2025)

## Abstract (arXiv)

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.