Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Diversification and Determinism in Local Search for Satisfiability
verfasst von : Chu Min Li, Wen Qi Huang
Erschienen in: Theory and Applications of Satisfiability Testing
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The choice of the variable to flip in the Walksat family procedures is always random in that it is selected from a randomly chosen unsatisfied clause
c
. This choice in Novelty or R-Novelty heuristics also contains some determinism in that the variable to flip is always limited to the two best variables in
c
. In this paper, we first propose a diversification parameter for Novelty (or R-Novelty) heuristic to break the determinism in Novelty and show its performance compared with the random walk parameter in Novelty+. Then we exploit promising decreasing paths in a deterministic fashion in local search using a gradient-based approach. In other words, when promising decreasing paths exist, the variable to flip is no longer selected from a randomly chosen unsatisfied clause but in a deterministic fashion to surely decrease the number of unsatisfied clauses. Experimental results show that the proposed diversification and the determinism allow to significantly improve Novelty (and Walksat).