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:
- Phase 1 (Initialization): $k$ independent runs are executed for a duration $t_1$.
- 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$.
- Phase 3 (Execution): The selected runs are resumed for the remaining time budget $t_3$.
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.
Predictive Decision Makers
To address this gap, the authors evaluated several Decision Makers beyond simple baselines:
- Baselines:
currentBest,random, andcurrentWorst. - Heuristics:
mostImprovements(frequency of improvement) andlogTimeSum. - 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
currentBestBAR 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