A lot is known about Stochastic Local Search (SLS) methods [e.g. Hoos-Stutzle ’04], especially their behavior on random 3-SAT A lot is known about Stochastic Local Search (SLS) methods [e.g. Hoos-Stutzle ’04], especially their behavior on random 3-SAT - Along with systematic search, the main SAT solution paradigm
- Walksat one of the first widely successful local search solver
- Biased random walk
- Combines greedy moves (downhill) with stochastic moves (possibly uphill) controlled by a “noise” parameter [0% .. 100%]
Yet, new surprising findings are still being discovered - Part of this work motivated by the following observation:
Our work looks at Walksat again, on large, random, 3-SAT formulas, and seeks answers to two questions: Our work looks at Walksat again, on large, random, 3-SAT formulas, and seeks answers to two questions: - Can we further characterize the “optimal noise” and the linear scaling behavior of Walksat?
- Key parameter: the clause-to-variable ratio, α
- How do runtime distributions of Walksat behave at sub-optimal noise?
- Are they concentrated around the mean or do they have “heavy tails” similar to complete search methods?
- Heavy tails very long runs more likely than we might expect
- Heavy tails not reported in local search so far
Note: Walksat still faster than current adaptive, dynamic noise solvers on these formulas; studying behavior at optimal static noise of much interest
Walksat on large, random, 3-SAT formulas: Walksat on large, random, 3-SAT formulas: - Further characterization the “optimal noise” and linear scaling:
- A detailed analysis, showing a piece-wise linear fit for optimal noise as a function of α, with transitions at interesting points (extending the previous observation that ~57% is optimal for α=4.2)
- Simple inverse polynomial dependence of runtime on α
- Runtime distributions of Walksat behave at sub-optimal noise
- Exponential decay in the high noise regime
- Heavy tails in the low noise regime First quantitative observation of heavy tails in local search [earlier insights: Hoos-Stutzle 2000]
- Preliminary Markov Chain model
Question: Question: How does the optimal noise setting vary with α and N? Experiment: - For α in [1.5...4.2], generate random 3-SAT formulas with N in [100K..400K]
- For each, find the noise setting where Walksat is the fastest (binary search)
- Average these optimal noise settings and plot against α
Experiment: Experiment: - For α in [1.5...4.2], generate random 3-SAT formulas with N in [100K..400K]
- Measure Walksat's runtime with optimal noise (#flips till solution found)
- Plot #flips/N against α (one point per run, no averaging)
Results: Inverse polynomial fit of #flips/N as a function of α - Suggesting linear scaling for α < 4.235
Standard distributions: Standard distributions: - Exponential or faster decay e.g., Normal distribution
Heavy-tailed distributions: - Power law decay e.g. Pareto-Levy distribution
Heavy-tailed distributions: - Power law decay e.g. Pareto-Levy distribution
- Signature: tail of the distribution is a line in log-log plot
- Observed in systematic search solvers
- Mechanism well-understood in terms of “bad” variable assignments that are hard to recover from [Gomes, Kautz and Selman ‘99, ’00]
- Motivated key techniques such as search restarts, algorithm portfolios
- Not previously observed in studies on local search methods
Experiment: - Generate a random 3-SAT formula with N=100K at α=4.2
- Large formulas, free of small size effects
- Very hard to solve
- Still less constrained than formulas at the phase transition (α4.26)
- Run 100K (!) runs of Walksat with noise settings around the optimal
- Plot the runtime distribution: probability of failure to find a solution as a function of #flips
[Setting: Large, random, 3-SAT formula with α=4.2] [Setting: Large, random, 3-SAT formula with α=4.2] Summary of Results: - There is a qualitative difference between noise higher that optimal (>56.7%) and lower that optimal (<56.7%)
- High noise regime: tail of P[failure] has an exponential distribution
- Low noise regime : tail of P[failure] has a power-law distribution
- Intuition captured by a (preliminary) Markov Chain model
- High noise means “guessing the solution”
- Low noise (too greedy) leads the search into “local traps”
- Optimal noise is where the two effects balance
Do'stlaringiz bilan baham: |