An Adaptive Noise Mechanism for WalkSAT

AAAI 2002

TL;DR

This paper introduces an adaptive noise mechanism for WalkSAT, a popular algorithm for solving the Boolean Satisfiability Problem (SAT). Instead of relying on manual tuning of a "noise" parameter, this new mechanism dynamically adjusts it during the search, leading to robust and often improved performance across a wide range of SAT instances without requiring instance-specific parameter optimization.

What Problem Does This Paper Address?

The Boolean Satisfiability Problem (SAT) is a fundamental problem in computer science with applications in various fields like artificial intelligence, hardware verification, and constraint satisfaction. Stochastic Local Search (SLS) algorithms, particularly those in the WalkSAT family, are highly effective at finding solutions (models) for large and complex SAT instances. A crucial parameter in these algorithms is the "noise" parameter, which controls the balance between greedily moving towards a solution and randomly exploring the search space to escape local optima.

The core problem this paper addresses is that the optimal setting for this noise parameter is highly instance-dependent. This means that to achieve peak performance, researchers and practitioners must manually tune the noise parameter for each specific SAT problem instance, which is time-consuming, requires expertise, and hinders the general applicability and evaluation of WalkSAT algorithms. The paper aims to eliminate this manual tuning by introducing an adaptive mechanism that automatically adjusts the noise parameter during the search process.

Methods

The paper proposes an adaptive noise mechanism for WalkSAT that dynamically adjusts the noise parameter based on the search progress. The core idea is to use high noise levels only when the search appears to be stagnating (i.e., not making progress towards a solution).

The mechanism works as follows:

  • Initialization: The search starts with a greedy strategy (noise = 0).
  • Stagnation Detection: The algorithm monitors the time elapsed since the last improvement in the objective function (number of unsatisfied clauses). If no improvement is observed for a certain number of steps (related to the number of clauses), stagnation is detected.
  • Noise Increase: Upon detecting stagnation, the noise parameter is incrementally increased. The increase is designed to be gradual, using a formula like wp := wp + (1 − wp) · φ.
  • Noise Decrease: Once an improvement is achieved after increasing the noise, the noise parameter can be gradually decreased. The decrease is implemented as wp := wp - wp · 24.
  • Asymmetry: The mechanism uses asymmetric updates for noise increase and decrease. This is motivated by the higher computational cost of detecting stagnation compared to detecting progress, and the observation that it's advantageous to approach optimal noise levels from above.

The authors emphasize that this approach is inspired by concepts in reactive tabu search and iterated local search, aiming to use "escape" mechanisms only when truly needed.

Datasets

The paper evaluates its proposed adaptive noise mechanism on a variety of SAT instances, primarily sourced from the SATLIB Benchmark Collection. These include:

  • SAT-encoded blocksworld and logistics planning instances.
  • SAT-encoded graph coloring problems.
  • Critically constrained Uniform Random-3-SAT instances.
  • SAT-encoded all-interval-series problems.

Additionally, a new test set of 100 critically constrained, satisfiable Uniform Random-3-SAT instances with 400 variables and 1700 clauses was generated to assess scaling behavior.

Key Insights and Ideas

  • Noise Parameter Sensitivity: The noise parameter has a significant impact on WalkSAT's performance, and even small deviations from the optimal setting can drastically increase solving time, especially for hard instances.
  • Concave Noise Response: For many WalkSAT variants, the relationship between the noise setting and the local search cost (expected time to find a solution) exhibits a concave shape, with a single optimal noise value.
  • Dynamic Noise as a Solution: Instead of static, manually tuned noise, an adaptive mechanism that increases noise only when stagnation occurs can achieve robust and high performance. This is because it avoids unnecessary exploration when the search is progressing well.
  • "Homing In" Phenomenon: The adaptive mechanism might take some time to reach optimal noise levels, leading to a slight initial performance dip compared to pre-tuned static noise, but it ultimately achieves comparable or better results.
  • Generalizability: The adaptive noise concept is presented as a general principle applicable to a wider range of SLS algorithms beyond WalkSAT, and for problems other than SAT.

Key Results

  • Robust Performance: The adaptive noise mechanism for Novelty+ achieved performance levels close to, and in some cases exceeding, the peak performance of manually tuned static noise across various benchmark instances.
  • Reduced Variance: The dynamic noise variant consistently showed a significantly lower variation in local search cost (lsc) across test sets compared to the static noise approach.
  • Minimal Overhead: The adaptive noise mechanism introduced only a small overhead (typically 5-10% higher CPU time per search step) compared to standard static noise implementations. In some cases, it even led to faster search steps due to more rapid decreases in unsatisfied clauses.
  • Improved Performance on Hard Instances: In several cases, the dynamic noise mechanism achieved better performance than the approximate optimal static noise, particularly on hard instances.
  • General Applicability: Preliminary results suggest the adaptive mechanism also works well for WalkSAT/SKC and R-Novelty+, using the same parameter settings.

Limitations and Future Work

  • Parameter Tuning for the Adaptive Mechanism: While the adaptive mechanism eliminates instance-specific tuning of the noise parameter, it introduces two internal parameters (θ and φ) that control its behavior. The authors found fixed values for these parameters worked well across all tested instances, but acknowledge that further optimization of these could potentially yield even better results.
  • Stagnation Criteria: The paper uses a simple stagnation detection criterion. The authors suggest that more sophisticated criteria, incorporating measures like search mobility or McAllester et al.'s "invariants," could further improve performance.
  • Integration with Other Techniques: Future work could explore integrating machine learning techniques for detecting stagnation or predicting optimal noise values, and applying the adaptive noise concept to other high-performance SLS algorithms and combinatorial problems.
  • Theoretical Understanding: The paper notes that the deeper reasons behind the characteristic concave shape of the noise response curve and the corresponding runtime distributions remain unknown, suggesting this is an area for future theoretical investigation.

Summary updated

BibTeX
@inproceedings{2002adaptive,
  title = {{An Adaptive Noise Mechanism for WalkSAT}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2002},
}
Figure