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

Improved warning propagation algorithm for solving Max-SAT problem

作　　者：吴宇翔 王晓峰[1,2] 丁红胜[1] 于卓 Wu Yuxiang;Wang Xiaofeng;Ding Hongsheng;Yu Zhuo(School of Computer Science&Engineering,North Minzu University,Yinchuan 750021,China;Key Laboratory of Images&Graphics Intelligent Processing of State Ethnic Affairs Commission,North Minzu University,Yinchuan 750021,China)

机构地区：[1]北方民族大学计算机科学与工程学院,银川750021 [2]北方民族大学图像图形智能处理国家民委重点实验室,银川750021

出　　处：《计算机应用研究》2022年第8期2290-2294,共5页Application Research of Computers

基　　金：国家自然科学基金资助项目(62062001);宁夏自然科学基金资助项目(2020AAC03214);北方民族大学研究生创新项目(YCX21086)。

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

关 键 词：可满足性问题 最大可满足性问题 警示传播算法 局部搜索算法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]