# A Review on Single-Problem Multi-Attempt Heuristic Optimization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 108 references that are in the map.
- First posted on arXiv 30 Sep 2025.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization](https://mlsanity.com/paper/1603.06560/) (2016)
- [BOHB: Robust and Efficient Hyperparameter Optimization at Scale](https://mlsanity.com/paper/1807.01774/) (2018)
- [Population Based Training of Neural Networks](https://mlsanity.com/paper/1711.09846/) (2017)
- [On Hyperparameter Optimization of Machine Learning Algorithms: Theory and Practice](https://mlsanity.com/paper/2007.15745/) (2020)
- [Hyperparameter Optimization: Foundations, Algorithms, Best Practices and Open Challenges](https://mlsanity.com/paper/2107.05847/) (2021)
- [Fast Bayesian Optimization of Machine Learning Hyperparameters on Large Datasets](https://mlsanity.com/paper/1605.07079/) (2016)
- [Automated Algorithm Selection: Survey and Perspectives](https://mlsanity.com/paper/1811.11597/) (2018)
- [Efficient Automatic CASH via Rising Bandits](https://mlsanity.com/paper/2012.04371/) (2020)
- [A Survey of Methods for Automated Algorithm Configuration](https://mlsanity.com/paper/2202.01651/) (2022)
- [Automated Machine Learning: State-of-The-Art and Open Challenges](https://mlsanity.com/paper/1906.02287/) (2019)
- [Simulation optimization: A review of algorithms and applications](https://mlsanity.com/paper/1706.08591/) (2017)
- [To Switch or not to Switch: Predicting the Benefit of Switching between Algorithms based on Trajectory Features](https://mlsanity.com/paper/2302.09075/) (2023)
- [Large-scale Benchmarking of Metaphor-based Optimization Heuristics](https://mlsanity.com/paper/2402.09800/) (2024)
- [Sharp Bounds for Genetic Drift in Estimation of Distribution Algorithms](https://mlsanity.com/paper/1910.14389/) (2019)
- [Efficient Multi-Start Strategies for Local Search Algorithms](https://mlsanity.com/paper/1401.3894/) (2014)
- [From Understanding Genetic Drift to a Smart-Restart Parameter-less Compact Genetic Algorithm](https://mlsanity.com/paper/2004.07141/) (2020)
- [Benchmarking for Metaheuristic Black-Box Optimization: Perspectives and Open Challenges](https://mlsanity.com/paper/2007.00541/) (2020)
- [An Asymptotically Optimal Multi-Armed Bandit Algorithm and Hyperparameter Optimization](https://mlsanity.com/paper/2007.05670/) (2020)
- [HAMLET -- A Learning Curve-Enabled Multi-Armed Bandit for Algorithm Selection](https://mlsanity.com/paper/2001.11261/) (2020)
- [On the Fair Comparison of Optimization Algorithms in Different Machines](https://mlsanity.com/paper/2305.07345/) (2023)

## Abstract (arXiv)

In certain real-world optimization scenarios, practitioners are not interested in solving multiple problems but rather in finding the best solution to a single, specific problem. When the computational budget is large relative to the cost of evaluating a candidate solution, multiple heuristic alternatives can be tried to solve the same given problem, each possibly with a different algorithm, parameter configuration, initialization, or stopping criterion. In this practically relevant setting, the sequential selection of which alternative to try next is crucial for efficiently identifying the best possible solution across multiple attempts. However, suitable sequential alternative selection strategies have traditionally been studied separately across different research topics and have not been the exclusive focus of any existing review. As a result, the state-of-the-art remains fragmented for practitioners interested in this setting, with surveys either covering only subsets of relevant strategies or including approaches that rely on assumptions that are not feasible for the single-problem case. This work addresses the identified gap by providing a focused review of single-problem multi-attempt heuristic optimization. It brings together suitable strategies for this setting that have been studied separately through algorithm selection, parameter tuning, multi-start, and resource allocation. These strategies are described using a unified terminology within a common framework, which supports the construction of a taxonomy for systematically organizing and classifying them. The resulting comprehensive review facilitates both the identification and the development of strategies for the single-problem multi-attempt setting in practice.