Introduction
Stochastic Local Search (SLS) algorithms are fundamental tools in combinatorial optimization, widely applied in fields ranging from hardware verification to Bayesian network inference. These algorithms typically balance "greedy" moves toward local optima with "noise"—random moves intended to escape stagnation. When progress halts, practitioners often employ "hard restarts," resetting the search after a fixed number of steps. While empirically successful, hard restarts introduce non-homogeneity into the search process, as the probability of restarting depends on the time elapsed since the last reset. This dependency complicates standard Markov chain analysis, making it difficult to theoretically predict the "expected hitting time" (the time required to find a solution) or to optimize parameters systematically.
The MarkovSLS Framework
To bridge the gap between empirical success and theoretical understanding, this work introduces MarkovSLS, a generalized framework that replaces deterministic hard restarts with soft restarts. In a soft restart regime, the algorithm has a fixed probability ($p_r$) of restarting at every step. This innovation ensures that the search process remains a homogeneous Markov chain, enabling rigorous mathematical analysis.
The framework supports two primary variants:
- SoftSLS: Utilizes fixed probabilities for noise ($p_n$) and restarts ($p_r$). This allows for the exact calculation of expected hitting times using linear algebra.
- AdaptiveSLS: Dynamically adjusts $p_n$ and $p_r$ based on search progress. If the algorithm detects stagnation (e.g., frequent self-loops in the state space), it increases these probabilities to facilitate escape from local optima.
Modeling with Deceptive Markov Chains
The authors utilize Deceptive Markov Chains (DMC) to model "tricky" search landscapes characterized by local optima (traps). These 1D representations approximate the high-dimensional spaces encountered in real-world problems.
As shown in Figure 1, the DMC model explicitly incorporates the probabilities of noise and restart into the transition matrix. The authors prove that a soft restart with probability $p_r$ is functionally equivalent to a hard restart every $1/p_r$ steps in terms of expected restart time, providing a solid theoretical foundation for the soft restart approach.
Analytical Optimization and Results
By modeling the search as a DMC, the authors derived the "optimal" noise and restart probabilities mathematically. They validated these theoretical predictions through extensive simulations on synthetic deceptive functions and real-world feature selection tasks.
Figure 3 displays contour plots of expected hitting times across various problem configurations. The dark regions represent the "sweet spots" where the combination of $p_n$ and $p_r$ minimizes search time. The empirical results perfectly matched these theoretical contours, confirming the validity of the Markov chain approach.
Key findings include:
- Sensitivity of Restart: The restart parameter ($p_r$) is often more critical than noise ($p_n$); minor adjustments in $p_r$ can lead to significant changes in performance.
- Adaptivity:
AdaptiveSLSfrequently matched or outperformed the analytically optimizedSoftSLS. This suggests that real-time adaptation to the local landscape is highly effective, even without prior knowledge of the global search space. - Real-World Performance: On feature selection datasets (e.g., Wine, Diabetes),
AdaptiveSLSconsistently outperformed standard benchmarks like Simulated Annealing and AdaptiveNoise.
Conclusion
This research demonstrates that soft restarts enable a powerful Markov chain analysis of SLS algorithms. By transforming the search into a homogeneous process, researchers can analytically optimize parameters and develop robust adaptive strategies. While the current analysis relies on simplified 1D models (DMCs), it paves the way for future integration with Markov Decision Processes (MDPs) to create even more sophisticated controllers for high-dimensional optimization problems.
Summary updated