Learning Interpretable Heuristics for WalkSAT
Local search algorithms are well-known methods for solving large, hard instances of the satisfiability problem (SAT). The performance of these algorithms crucially depends on heuristics for setting noise parameters and scoring variables. The optimal setting for these heuristics varies for different instance distributions. In this paper, we present an approach for learning effective variable scoring functions and noise parameters by using reinforcement learning. We consider satisfiability problems from different instance distributions and learn specialized heuristics for each of them. Our experimental results show improvements with respect to both a WalkSAT baseline and another local search learned heuristic.
Code (0)
등록된 구현이 없습니다.
Tasks
reinforcement-learningSimilar Papers 제목 키워드 기반
Adapting Stochastic Search For Real-time Dynamic Weighted Constraint Satisfaction
This work presents two new algorithms for performing constraint satisfaction. The first algorithm presented, DMaxWalkSat, is a constraint solver specialized for solving dynamic, weighted constraint satisfaction problems.…
A novel approach of solving the CNF-SAT problem
In this paper, we discussed CNF-SAT problem (NP-Complete problem) and analysis two solutions that can solve the problem, the PL-Resolution algorithm and the WalkSAT algorithm. PL-Resolution is a sound and complete algori…
An Efficient Implementation for WalkSAT
Stochastic local search (SLS) algorithms have exhibited great effectiveness in finding models of random instances of the Boolean satisfiability problem (SAT). As one of the most widely known and used SLS algorithm, WalkS…
A Probabilistic Approach to Satisfiability of Propositional Logic Formulae
We propose a version of WalkSAT algorithm, named as BetaWalkSAT. This method uses probabilistic reasoning for biasing the starting state of the local search algorithm. Beta distribution is used to model the belief over b…
Approximating the Backbone in the Weighted Maximum Satisfiability Problem
The weighted Maximum Satisfiability problem (weighted MAX-SAT) is a NP-hard problem with numerous applications arising in artificial intelligence. As an efficient tool for heuristic design, the backbone has been applied …