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

发布时间：2020-04-06 08:16

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

局部搜索,基本流程,不完备,相关理论

基于信息熵局部搜索 Max-SAT 算法的基排构安排如下：先对本文研究工作 Max-SAT 和 SAT了国内外相关工作与相关理论的研究构； Max-SAT 问题涉及到的相关理论及、熵的理论知识和基本常用的搜索算续准备对比的 Max-SAT 不完备算法的描述，通过对不完备算法的研究，T 局部搜索算法，同时，对算法从设

信源,概率,不确定性,信息熵

(P) = 1 = (2-1)但是在实际情况中，应用的并不是单一信源，，因而必须从全局出发，平均在各种情况下事件发生的不确定性，即得到真实的信息熵(InformationEntropy)。具体来讲，给定具有 N 种取值可能的信源，这些取值定义为X1, 2 ，相应的概率是P1, 2 ，由于各个信号彼此相互独立，则最终信源的不确定性是求对单个信号的不确定性也就是要求式（2-1）的所有和的平均值，也就是信息熵，定义为 E，我们把这个具体形式如下：H(X) = = 1 (2-2)一般运算中，式中对数一般取 2 为底，单位是比特，当然不是必须以 2 为底，也可以是其他数，只是单位不同，都可以换算成以 2 为底的公式。在这里可以举例最简单的二元信源为例，这样的信源为单符号信源，取值只能取 0 和 1，即二元信源。假设存在这样一个信源，它产生信号 0 的概率为 P，那么产生另一个信号 1 的概率就是 Q=1-P，由此可以得到如图 2-1 所示[34]。其中横坐标为概率，纵坐标为熵。
【学位授予单位】：电子科技大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP301.6

【相似文献】