An Improved Generic Bet-and-Run Strategy with Performance Prediction for Stochastic Local Search

Thomas Weise, Zijun Wu, Markus WagnerAAAI 2019 · DOI

Introduction

Stochastic local search (SLS) algorithms are fundamental tools for solving NP-hard optimization problems. However, their performance is often limited by their tendency to converge to local optima. A common mitigation strategy is the use of restarts, where the search is re-initialized with a different random seed.

The "Bet-and-Run" (BAR) strategy refines this by initiating multiple parallel runs and selecting the most promising one to continue after a short observation period. While effective, standard BAR typically selects the run that is currently performing best, ignoring the potential for other runs to eventually yield superior results. This paper introduces an enhanced BAR framework that utilizes machine learning and regression to predict long-term performance, thereby bridging the "prediction gap."

The Three-Phase Framework

The authors formalize the Bet-and-Run strategy into a generalized three-phase process:

  1. Phase 1 (Initialization): $k$ independent runs are executed for a duration $t_1$.
  2. Phase 2 (Decision): A Decision Maker ($D$) analyzes the performance history of these runs to select $m$ runs for continuation. This phase incurs a time cost $t_2$.
  3. Phase 3 (Execution): The selected runs are resumed for the remaining time budget $t_3$.
The three-phase Bet-and-Run framework.

The Prediction Gap

The central challenge in BAR is identifying which run will ultimately achieve the best solution quality. The standard approach, currentBest, assumes that early leaders will remain leaders. However, empirical data reveals a significant "prediction gap." In the Minimum Vertex Cover (MVC) problem, for instance, the authors found that in up to 78% of instances, a run discarded by the currentBest strategy would have eventually outperformed the chosen one.

Comparison of initially best runs vs. runs that are best at the end for MVC and TSP.

Predictive Decision Makers

To address this gap, the authors evaluated several Decision Makers beyond simple baselines:

  • Baselines: currentBest, random, and currentWorst.
  • Heuristics: mostImprovements (frequency of improvement) and logTimeSum.
  • Model-Based Predictors: These fit Phase 1 data to models like linear, quadratic, and cubic polynomials, as well as small perceptrons (trained on the fly via CMA-ES) to forecast final quality.
  • Diminishing Returns: A logic-based approach modeling the increasing difficulty of finding improvements as time progresses.

Experimental Evaluation and Results

The strategy was evaluated using a massive simulation involving over 157 million experiments based on real run data from two classic NP-hard problems: Minimum Vertex Cover (MVC) and the Traveling Salesperson Problem (TSP).

Key findings include:

  • Outperforming the State-of-the-Art: Perceptron-based predictors and the "diminishing returns" approach consistently yielded better results than the standard currentBest BAR strategy, particularly on the MVC problem.
  • Problem-Specific Success: Advanced predictors were more successful on MVC than on TSP, suggesting that MVC solver trajectories are more predictable or have higher variance that can be exploited.
  • Neural Net Efficiency: Even very small perceptrons (0 to 3 hidden nodes) were sufficient to model the behavior of the optimization algorithms effectively, keeping the decision cost ($t_2$) low.

Conclusion and Future Work

By shifting the focus from current performance to predicted future quality, the enhanced Bet-and-Run strategy significantly improves optimization outcomes within a fixed time budget. While the "current best" remains a strong baseline, predictive models offer a clear advantage when the search trajectories are sufficiently predictable. Future work will explore incorporating problem-specific features and extending the framework to choose between different algorithm configurations in a portfolio.

Summary updated

BibTeX
@inproceedings{weise2019improved,
  author = {Thomas Weise and Zijun Wu and Markus Wagner},
  title = {{An Improved Generic Bet-and-Run Strategy with Performance Prediction for Stochastic Local Search}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33012395},
}
Figure