A lot is known about Stochastic Local Search (sls) methods [e g. Hoos-Stutzle ’04], especially their behavior on random 3-sat


Download 515 b.
Sana04.02.2018
Hajmi515 b.
#25971



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:



  • 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


















Download 515 b.

Do'stlaringiz bilan baham:




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling