为什么WSAT优于模拟退火？

Question

在一些期刊上，我发现WSAT ( Walking SAT )算法在解决SAT问题方面比模拟退火算法有更好的性能。

所以我的问题是，有人能解释一下为什么我们会得到这个结果吗？可能是因为SA更像是一种通用算法？

编辑：这里也许是我读过的最相关的文档。

Answer 1

模拟退火评估随机选择的邻居，算法总是移动到邻居，如果它是更好的，从物理直觉。但是WalkSAT做得更好，有时而不是搬到邻居那里，即使它更好。

当您开始用WalkSAT解决一个3-CNF可满足的问题时:或者您已经解决了您的问题，或者某些子句不满意。子句不满意的事实意味着，必须翻转子句中的至少一个变量才能找到解决方案。如果从长度等于3的从句中随机选择变量，那么很容易看出每一次翻转都有33%或更好的机会正确1。

SA没有那么高的成功概率，而且被困在局部最大值的风险很高。

这就是我解释为什么WalkSAT比SA更好的原因，但是可能已经有关于这个问题的研究了;)您应该仔细看看本论文 2，提供SA和WalkSAT之间的详细比较。

1 Papadimitrou，C.H.，& Steiglitz，K. (1982)。组合优化:算法和复杂性。出版商:普伦提斯·霍尔。

2 Selman，B.Kautz，H.A.，& Cohen，B.B.(1994年)。改进局部搜索的噪声策略。载于AAAI (第94卷，第337-343页)。