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

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