on some journal i read that WSAT ( Walking SAT ) algorithm has better performances than Simulated Annealing algorithm in the resolution of SAT problem.
So my question is, can someone kindly explain why we got this result ? Could be because SA is more like a general purpose algorithm ?
Edit: Here maybe the most relevant document i read about.
Simulated annealing evaluates a randomly chosen neighbor, the algorithm always moves to the neighbor if it is better, following an intuition from physics. But WalkSAT does better by sometimes not moving to a neighbor even if it is better.
When you start solving a 3-CNF satisfiable with WalkSAT: or you already solved your problem, or some clause are unsatisfied. The fact that a clause is unsatisfied means that at least one of the variables in the clause must be flipped to find a solution. If variables are chosen randomly from the clause with length equals to 3 it is easy to see that each flip as a 33% or better chance of being correct [1].
SA does not have such high probability to succeed and has a high risk of being stuck in a local maximum...
This is how I would explain myself why WalkSAT is better than SA, but there is probably already a study on this problem ;) You should take a closer look to this paper [2] providing a detailed comparison between SA and WalkSAT.
[ 1 ] Papadimitrou, C. H., & Steiglitz, K. (1982). Combinatorial optimization: algorithms and complexity. Publisher: Prentice Hall.
[ 2 ] Selman, B., Kautz, H. A., & Cohen, B. (1994). Noise strategies for improving local search. In AAAI (Vol. 94, pp. 337-343).