Noise Strategies for Improving Local Search

Bart Selman, Henry A. Kautz, Bram CohenAAAI 1994 · OpenReview

Abstract

It has recently been shown that local search is surprisingly good at finding satisfying assignments for certain computationally hard classes of CNF formulas. The performance of basic local search methods can be further enhanced by introducing mechanisms for escaping from local minima in the search space. We will compare three such mechanisms: simulated annealing, random noise, and a strategy called "mixed random walk". We show that mixed random walk is the superior strategy. We also present results demonstrating the effectiveness of local search with walk for solving circuit synthesis and circuit diagnosis problems. Finally, we demonstrate that mixed random walk improves upon the best known methods for solving MAX-SAT problems.

Introduction

In the early 1990s, Boolean Satisfiability (SAT) was primarily addressed through systematic search procedures like the Davis-Putnam (DP) algorithm. While DP is complete, it often struggled with large, complex instances. Local search algorithms, such as GSAT, emerged as a powerful alternative, starting with random assignments and greedily flipping variables to minimize unsatisfied clauses. However, GSAT frequently encountered "plateaus" or local minima where no single flip improved the objective. This paper explores "focused noise" strategies, specifically the "mixed random walk," to effectively escape these regions and solve significantly larger problems.

Methods for Escaping Local Minima

The authors evaluate four primary strategies for preventing local search from becoming trapped:

  1. Basic GSAT: Greedy flips with sideways moves on plateaus.
  2. Simulated Annealing: Probabilistically accepts "uphill" moves based on a cooling temperature parameter.
  3. Random Noise: With probability $p$, flips a completely random variable; otherwise, performs a standard GSAT move.
  4. Mixed Random Walk: With probability $p$, flips a variable chosen from an unsatisfied clause. With probability $1-p$, performs a greedy GSAT move.

A refined version, WSAT (WalkSAT), is also introduced. WSAT first selects an unsatisfied clause at random and then chooses a variable within that clause to flip, subtly favoring variables that appear in multiple unsatisfied clauses.

Experimental Results

Scaling on Random 3CNF Formulas

The mixed random walk strategy demonstrated remarkable scaling on hard random 3CNF formulas generated at the critical ratio ($L/N \approx 4.3$). While basic GSAT and simulated annealing struggled as problem size increased, the walk strategy successfully solved instances with up to 2,000 variables.

Comparison of GSAT variants and Simulated Annealing on hard random 3CNF formulas.

As shown in the data, GSAT with walk requires significantly fewer flips and less time than basic GSAT or random noise as the number of variables ($N$) increases. For $N=2000$, the walk strategy remains efficient while other methods fail to find solutions within reasonable time limits.

Breakthroughs in Structured Problems

A significant finding of this work is that local search is not just for random problems. On structured instances like circuit synthesis—where logical circuits are derived from input-output behavior—the WSAT algorithm outperformed systematic solvers by orders of magnitude.

Performance of systematic search (DP) vs. local search (WSAT) on circuit synthesis problems.

For complex adder circuits (e.g., 3bitadd_32), the Davis-Putnam procedure failed to find solutions (indicated by asterisks), whereas WSAT found them in approximately one second. This demonstrated that the "focused noise" of the random walk is particularly effective at navigating the search space of structured problems.

Planning and MAX-SAT

In planning benchmarks like the "huge" Towers of Hanoi problem, the random walk strategy was over 100x faster than simulated annealing. Furthermore, in MAX-SAT benchmarks, where the goal is to satisfy the maximum number of clauses, the mixed random walk consistently found higher-quality solutions (fewer unsatisfied clauses) than previous state-of-the-art methods like "zsamd".

Discussion and Limitations

The primary advantage of the mixed random walk is its "focused" nature: by restricting noise to variables in unsatisfied clauses, the algorithm perturbs the specific parts of the assignment causing issues. This pushes the search off plateaus more effectively than unfocused random noise.

However, local search remains an incomplete method; it cannot prove unsatisfiability. Additionally, performance is sensitive to the noise parameter $p$, though $p \approx 0.5$ proved robust across many domains. Future work suggests applying these focused noise strategies to broader Constraint Satisfaction Problems (CSPs).

Summary updated

Abstract

It has recently been shown that local search is surprisingly good at finding satisfying assignments for certain computationally hard classes of CNF formulas. The performance of basic local search methods can be further enhanced by introducing mechanisms for escaping from local minima in the search space. We will compare three such mechanisms: simulated annealing, random noise, and a strategy called "mixed random walk". We show that mixed random walk is the superior strategy. We also present results demonstrating the effectiveness of local search with walk for solving circuit synthesis and circuit diagnosis problems. Finally, we demonstrate that mixed random walk improves upon the best known methods for solving MAX-SAT problems.
BibTeX
@inproceedings{selman1994noise,
  author = {Bart Selman and Henry A. Kautz and Bram Cohen},
  title = {{Noise Strategies for Improving Local Search}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
  url = {https://openreview.net/forum?id=HyNbd0lObS},
}
Figure