一种改进的警示传播算法求解Max-SAT问题

Max-SAT问题是SAT问题的优化版本，目标是在给定的子句集中找到一组变元赋值，使得满足子句数最多，该问题是典型的NP-hard问题。随着大数据和人工智能的深度发展，过去原有的算法已不再适用，设计新的求解算法或对已有的求解算法进行优化是目前研究的热点。针对警示传播算法求解随机Max-3-SAT问题的局限性，提出了一种基于变元权值计算的警示传播算法，结合随机游走算法，给出一种新型算法WWP+WalkSAT，通过改进求解的局限性，更好地得到一组有效的初始解，从而提高算法的局部搜索能力。利用2016年Max-SAT国际竞赛部分基准实例，将WWP+WalkSAT算法与八种局部搜索算法进行精度方面的对比实验。实验结果表明，WWP+WalkSAT算法有较好的性能。

Improved warning propagation algorithm for solving Max-SAT problem

The Max-SAT problem is an optimized version of the SAT problem. The goal is to find a set of variable assignments in a given set of clauses so that the maximum number of clauses is satisfied. This problem is a typical NP-hard problem. With the in-depth development of big data and artificial intelligence, the original algorithms in the past are no longer applicable. Designing a new solution algorithm or optimizing the existing solution algorithm is the current research hotspot. Aiming at the limitations of the information dissemination algorithm for solving the random Max-3-SAT problem, this paper proposed a warning dissemination algorithm based on the calculation of variable weights. Combined with the random walk algorithm, it formed a new algorithm WWP+WalkSAT, which was solved by improvement of the limitation, it was better to get a set of effective initial solutions, thereby improving the local search ability of the algorithm. Using some benchmark examples of the Max-SAT international competition in 2016, it used the WWP+WalkSAT algorithm and 8 local search algorithms for accuracy comparison experiments. The experimental results show that the WWP+WalkSAT algorithm has good performance.