Research On Graph Neural Network Based Method Of Solving Satisfiability Problem

The satisfiability problem(Satisfiability Problem,SAT)is one of the classic problems in artificial intelligence research.A large number of scheduling,planning,and configuration problems in the real world can be modeled as satisfiability problems.Efficient solving algorithms have always been a key issue in the computer field.research hotspots.Graph neural network is a framework that uses deep learning to directly learn graph-structured data,and its excellent performance has attracted great attention from scholars.In this paper,the graph neural network is applied to the solution of the satisfiability problem,and the satisfiability problem is expressed as a graph structure,and the data distribution characteristics of the problem are learned through the neural network,so as to improve the solution efficiency of the satisfiability problem.Stochastic local search is one of the classic methods for solving SAT problems,but there are still some problems that need to be solved urgently in the current stochastic local search method.On the one hand,traditional stochastic local search methods start with random initial assignments and continuously search the solution space.The closer the initial assignment is to the real solution,the better it is to quickly search the solution space,while the random initialization assignment method has greater uncertainty.On the other hand,the essence of random local search algorithm is to use artificial heuristics to guide the search direction,and the design of heuristics is particularly important for the solution effect of the algorithm.Traditional heuristic methods usually require sufficient expert domain knowledge and careful design.In the latest research,a learning heuristic method has emerged,which opens up a new direction for SAT solving.However,the current research is still in its infancy,and the existing methods still have the problem of insufficient learning ability,and there is still room for improvement in solution efficiency and generalization performance.In view of the above two problems,this paper makes the following two improvements to the random local search method:First of all,this paper proposes a graph neural network initialization method based on the noise strategy,which replaces the random initialization method and obtains an initialization assignment that is closer to the real value,so as to reduce the subsequent local search space.In this paper,the graph representation of SAT problems is used,and the method based on graph neural network is used to predict the variable assignment probability and noise parameters of SAT problems.Variable assignment probabilities and random assignment methods allow the model to explore other solution spaces while using variable assignment probabilities.The experimental results on the 3SAT problem show that the initialization method proposed in this paper can reduce the number of flipped variables and the number of repeated flipped variables,thereby reducing the solution time and improving the solution rate.Secondly,this paper proposes a heuristic learning method based on graph attention network,which solves the difficult problem of heuristic design in random local search algorithm,and realizes a more stable and efficient learning method,which improves the solution accuracy of local search.In this paper,the attention mechanism is introduced in the graph neural network,so that the graph neural network can learn the data distribution characteristics of the SAT problem more accurately,and the variable selection process is modeled as a Markov decision process,using the more stable reinforcement learning method Advantage Actor Critic(A2C)for training.Experimental results on 3SAT,kcolor and kcover show that the proposed model achieves significant improvements in both solution rate and generalization performance compared to state-of-the-art learning-based local search solvers.