Warum übertrifft WSAT Simulated Annealing?

Question

auf einigen Zeitschriften las ich, dass WSAT (Walking SAT) Algorithmus hat bessere Leistungen als Simulated Annealing-Algorithmus in der Auflösung von SAT-Problem.

Also meine Frage ist, kann jemand freundlicherweise erklären, warum wir dieses Ergebnis haben? Könnte sein, weil SA mehr wie ein Allzweck-Algorithmus ist?

---

Edit: Here vielleicht das relevanteste Dokument i zu lesen.

Answer 1

Simulated Annealing bewertet einen zufällig ausgewählten Nachbarn, der Algorithmus immer bewegt sich zum Nachbarn, wenn es besser ist, einer Intuition aus der Physik folgend. Aber WalkSAT ist besser, wenn man manchmal zu einem Nachbarn wechselt, auch wenn es besser ist.

Wenn Sie beginnen, eine 3-CNF mit WalkSAT erfüllbar zu lösen: oder Sie bereits Ihr Problem gelöst, oder eine Klausel sind nicht zufrieden. Die Tatsache, dass eine Klausel nicht erfüllt ist, bedeutet, dass mindestens eine der Variablen in der Klausel gewendet werden muss, um eine Lösung zu finden. Wenn Variablen zufällig aus dem Satz mit der Länge gleich 3 gewählt werden, ist es leicht zu sehen, dass jedes Umdrehen eine 33% ige oder bessere Chance hat, korrekt zu sein [1].

SA hat nicht so hohe Wahrscheinlichkeit, erfolgreich zu sein und hat ein hohes Risiko in einem lokalen Maximum stecken ...

Dies ist, wie ich mich erklären würde, warum WalkSAT ist besser als SA, aber es ist wahrscheinlich schon eine Studie zu diesem Problem;) Sie sollten sich this paper [2] genauer anschauen und einen detaillierten Vergleich zwischen SA und WalkSAT geben.

---

[1] Papadimitrou, C. H., & Steiglitz, K. (1982). Kombinatorische Optimierung: Algorithmen und Komplexität. Herausgeber: Prentice Hall.

[2] Selman, B., Kautz, H.A., & Cohen, B. (1994). Lärmstrategien zur Verbesserung der lokalen Suche. In AAAI (Vol. 94, pp. 337-343).