zbMATH — the first resource for mathematics

Combining adaptive noise and look-ahead in local search for SAT. (English) Zbl 1214.68362
Marques-Silva, João (ed.) et al., Theory and applications of satisfiability testing – SAT 2007. 10th international conference, Lisbon, Portugal, May 28–31, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-72787-3/pbk). Lecture Notes in Computer Science 4501, 121-133 (2007).
Summary: The adaptive noise mechanism was introduced in Novelty+ to automatically adapt noise settings during the search. The local search algorithm G\( ^{2}\)WSAT deterministically exploits promising decreasing variables to reduce randomness and consequently the dependence on noise parameters. In this paper, we first integrate the adaptive noise mechanism in G\( ^{2}\)WSAT to obtain an algorithm adaptG\( ^{2} \)WSAT, whose performance suggests that the deterministic exploitation of promising decreasing variables cooperates well with this mechanism. Then, we propose an approach that uses look-ahead for promising decreasing variables to further reinforce this cooperation. We implement this approach in adaptG\( ^{2}\)WSAT, resulting in a new local search algorithm called adaptG\( ^{2} \)WSAT\( _{\text{P}}\). Without any manual noise or other parameter tuning, adaptG\( ^{2} \)WSAT\( _{\text{P}}\) shows generally good performance, compared with G\( ^{2} \)WSAT with approximately optimal static noise settings, or is sometimes even better than G\(^{2} \)WSAT. In addition, adaptG\( ^{2} \)WSAT\( _{\text{P} }\) is favorably compared with state-of-the-art local search algorithms such as R+adaptNovelty+ and VW.
For the entire collection see [Zbl 1120.68007].

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Full Text: DOI