Novelty + and Adaptive Novelty +
Holger H. Hoos, Dave A. D. Tompkins · 2004
In this paper we briefly describe Novelty and Adaptive Novelty, two high-performance, stochastic local search (SLS) algorithms for SAT. Based on the WalkSAT architecture, these algorithms combine search intensification and diversification feautures that lead to good peformance on a broad range of SAT instances. The performance of the Novelty algorithm critically depends on the setting of a socalled noise parameter, which effectively controls the relative amount of search diversification. Adaptive Novelty exploits insights in this performance dependence to dynamically adjust the noise parameter throughout the search, depending on search progress and stagnation.