Combining Adaptive Noise and Look-Ahead in Local Search for SAT

Abstract. The adaptive noise mechanism was introduced in Novelty+ to automatically adapt noise settings during the search [4]. The local search algorithm G 2 W SAT 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 W SAT to obtain an algorithm adaptG 2 W SAT, 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 W SAT, resulting in a new local search algorithm called adaptG 2 W SATP. Without any manual noise or other parameter tuning, adaptG 2 W SATP shows generally good performance, compared with G 2 W SAT with approximately optimal static noise settings, or is sometimes even better than G 2 W SAT. In addition, adaptG 2 W SATP is favorably compared with state-of-the-art local search algorithms such as R+adaptNovelty+ and V W.