基于信息熵的局部搜索Max-SAT算法

摘要

可满足问题在众多的NP完全问题中被称为“种子”问题，是因为这个问题在实际生活中应用非常频繁，它在计算机领域一直备受专家学者关注，在人工智能、计算机视觉、组合优化方面有着诸多的应用。鉴于SAT问题的重要性，本文研究了Max-SAT问题。 Max-SAT 问题的解决方法分为完备算法和不完备算法，完备算法是在长时间求解问题后得到问题的最优解，而不完备算法是在短时间内得到问题的次优解。由于Max-SAT问题是NP难问题，范式难度和规模不一，采用不完备算法在短时间内解决这个问题是非常有必要的。本文通过对无权重的Max-SAT问题的研究，提出了一种高效的不完备算法。本算法的目的是找到一组变量赋值，这组变量赋值可以使给定的CNF范式中的可满足语句数量最多。本文的主要工作如下： 1、本文研究了国内外经典的不完备算法：GSAT算法、CCLS算法和基于交叉熵的可满足算法，分别比较了不同的不完备算法对范式的预处理工作。在对范式的求解过程中，预处理可以使后续搜索变量更快。范式中的变量在不同的子句中信息量是不同的。通过对信息熵的学习和研究发现信息熵可以很好地判别变量在当前范式中的重要程度，从而选择更为重要的变量放入变量池中作为候选变量。因此本文选取信息熵作为第一步预处理工作，并且信息熵在此之前没有被应用于解决此类问题。 2、本算法的目的是挑选对当前范式最优的变量，能够使最多的子句数目变为可满足状态。对预处理放入候选变量池中的变量，通过使用关联度方法进行局部搜索，进一步选出更优的变量。然后，通过剪枝方法对变量赋值，使得每次最大可能地减少子句数量。接着更新范式，执行下一次迭代运算。 3、最后为了验证本文算法的效果，选取基于交叉熵的不完备算法和2016年全球Max-SAT比赛中的算法作为对比实验。通过对实验结果的分析，本算法相对其它算法在搜索可满足语句数量上有所提高，同时还明显地提高了搜索可满足语句的速度。

目录

第一个书签之前