随机可满足实例集上警示传播算法的收敛性

信息传播算法在求解随机kSAT问题时有惊人的效果,难解区域变窄.对于这种现象,至今缺少系统的理论解释.警示传播(warning propagation,简称WP)算法是一种基础的信息传播算法,为有效分析WP算法在随机kCNF公式上的收敛性,给出了随机kCNF公式因子图上圈存在的相变点.在随机kCNF公式产生模型G(n,k,p)中,取k=3,p=d/n2,因子图中圈存在的相变点为p=1/8n2.当d＜1/8时,因子图中开始出现圈,且每个连通分支至多有一个圈,因子图中含圈的连通分支的数目以及圈的长度均与n无关.因此,因子图是由森林和一些含有唯一圈的连通分支构成.证明了WP算法在这些实例集上高概率收敛,并且给出了算法的迭代步数为O(logn+s),其中,s为连通分支的大小.     

警示传播算法收敛的充分条件

信息传播算法求解可满足问题时有惊人的效果,难解区域变窄.然而,因子图带有环的实例,信息传播算法不总有效,常表现为不收敛.对于这种现象,至今缺少系统的理论解释.警示传播（warning propagation,简称WP）算法是一种基础的信息传播算法,对WP算法的收敛性研究是其他信息传播算法收敛性研究的重要基础.在WP算法中,将警示信息的取值从{0,1}松弛为[0,1],利用压缩函数的性质,给出了WP算法收敛的一个充分条件.选取了两组不同规模的随机3-SAT实例进行实验模拟,结果表明：当子句与变元的比值α<1.8时,该判定条件有效.     

命题逻辑可满足性问题的算法分析

1 引言可满足性问题(以下简称SAT)是问:对于一个命题逻辑公式,是否存在对其变元的一个真值赋值使之成立?这个问题在许多领域都有非常重要的意义,其快速求解算法的研究成为计算机科学的中心课题之一。例如在机器定理证明领域,某命题是否是一个和谐的公理集合的推论,这个问题归结为该命题的反面与该公理集合一起是否是不可满足的。通过量词消去技术和Herbrand定理的作用,谓词逻辑公式的不可满足性可以归结为命题逻辑公式的不可满足性。在知识库维护中,当知识以逻辑公式的形式表达时,知识库的一致性检查可以归结为命题逻辑公式的可满足性。在开放逻辑中,新事实是否与已有的知识矛盾,当遇到事实反驳时如何求得最大和谐的知识集,这些问题最后都要归结为命题逻辑公式的可满足性。1971年Cook首次证明了SAT是NP-完全的,从而大量的计算问题都可以归约到SAT。正是由于SAT的重要地位,各国学者对它进行了广泛而深入的研究。     

求解可满足问题的调查传播算法以及步长的影响规律

该文研究了求解可满足问题的调查传播算法．该算法利用合取范式因子图进行调查消息的迭代,并根据每一次迭代的收敛情况对部分布尔变量赋值以对问题进行简化,最后把简化的问题利用局部搜索算法来求解．文中所谓步长是指在每一次迭代收敛之后根据赋值倾向进行赋值的变量个数．该文根据模拟实验观察到步长对调查传播算法的影响规律,即随着步长的递增,算法的时间耗费以及算法的有效性都有近似单调递减的趋势．     

基于树宽的警示传播算法收敛性分析

警示传播算法作为一种基本的信息传播算法,其收敛时求解可满足性问题十分有效,但因子图结构较为复杂时,算法往往不收敛导致求解失败。为了对这种现象给予理论解释,同时对警示传播算法收敛性进行有效分析,利用树分解方法构造了命题公式对应因子图的树宽度量模型,计算可满足随机实例的树宽。建立树宽与警示传播算法收敛性之间的关系,给出了基于树宽的警示传播算法收敛性判定条件。通过实验分析,结果表明该方法有效,对于分析其他信息传播算法收敛性分析研究具有十分重要的意义。     

求解可满足性问题的信息传播算法研究综述

信息传播算法来自统计物理,被广泛应用于人工智能各个领域,特别是求解组合优化问题时,具有良好的有效性。通过对信息传播算法的相关文献进行分析,综述了信息传播算法以及其相关应用的发展史,根据信息传播算法的发展,介绍了求解可满足性问题的信息传播算法相关概念,主要涉及到警示传播算法、置信传播算法和调查传播算法,描述了三种算法发展中出现的收敛性、有效性研究,分别综述了各个算法在相关领域的应用情况,并总结了信息传播算法的研究路径和应用方向。     

求解多文字可满足SAT问题的置信传播算法

可满足(SAT)问题是指:是否存在一组布尔变元赋值,使得合取范式公式中每个子句至少有一个文字为真.多文字可满足SAT问题是指:是否存在一组布尔变元赋值,使得CNF公式中每个子句至少有两个文字为真.显然,此问题仍然是一个NP难问题.为了研究解决多文字可满足SAT问题的算法,引入随机实例产生模型,设计求解多文字可满足SAT问题的置信传播算法.最后,用实例模型产生了大量数据进行实验验证,结果表明:该算法求解多文字可满足SAT问题的性能优于其他启发式算法.     

规则实例集上警示传播算法的收敛性

信息传播算法求解随机3-SAT问题时非常有效,能使难解区域变窄.然而,对于因子图带有环的实例,信息传播算法并不总有效,常表现为不收敛.对于这种现象,至今缺少系统的理论解释.警示传播(Warning Propagation,WP)算法是一种基础的信息传播算法,对WP算法的收敛性研究是其它信息传播算法收敛性研究的重要基础.将一个3-SAT问题转换为具有规则结构的(3,4)-SAT问题,(3,4)-SAT问题是NP-完全的.基于(3,4)-SAT问题的规则结构性质,分析WP算法的收敛性.选取了3组不同规模的实例进行实验模拟,结果表明:在这种规则结构的可满足性实例集上,WP算法的收敛性有较大提高.     

基于结构熵的警示传播算法收敛性分析

收敛性是评价信息传播算法性能的重要指标,信息传播算法求解可满足性问题时,命题公式的结构特征影响算法的收敛性,具有复杂结构的命题公式,信息传播算法不总收敛。为了系统地对此现象给予理论解释,借助于结构熵的方法和技术,提出命题公式的结构熵模型及其度量方法,计算随机可满足性实例的结构熵。警示传播算法(WP)作为信息传播算法的基本模型,分析WP算法的收敛性对于研究其他信息传播算法的收敛性具有重要意义,分析了WP算法收敛性与结构熵之间的关系,给出WP算法收敛的判定条件。通过实验分析,该方法有效可行。     

求解可满足性问题的改进的模拟退火算法

该文为可满足性问题的高效近似求解提出了改进的模拟退火算法。数值实验表明,对于该文随机产生的测试问题例,改进的模拟退火算法完全胜过局部搜索算法、模拟退火算法以及目前国际上流行的WSAT算法。     

RB模型实例集上置信传播算法的收敛性

置信传播算法求解RB（k,n,α,r_c,p）模型实例时非常有效,几乎能够有效求解接近可满足性相变点的难解实例.然而,因子图带有回路的实例,置信传播算法不总有效,常表现为不收敛.对于这种现象,至今缺少系统的理论解释.置信传播算法是最为基础的信息传播算法,对置信传播算法的收敛性分析是其他信息传播算法收敛性分析的重要基础.在RB（k,n,α,r_c,p）模型中,取k=2,α>（1/k）,r_c>0均为常数,且满足ke^{-（α/（r_c））}≥1.证明了如果p∈（0,n^-2α）,则置信传播算法在RB（k,n,α,r_c,p）模型产生的随机实例集上高概率收敛.最后,在RB（k,n,α,r_c,p）模型上选取了几组不同的数据进行数值模拟,实验结果表明该结论有效.当问题规模n增大时,在RB（k,n,α,r_c,p）模型的可满足区域,实验收敛区间趋于一个固定范围,而理论收敛区间逐渐变窄.原因在于,RB（k,n,α,r_c,p）模型是一个具有增长定义域的随机CSP实例产生模型,不协调赋值的数目与参数p及问题规模n有关.     

可满足性问题的一种DNA表面计算模型

可满足性问题的一种DNA表面计算模型是一种特殊的DNA计算方法,该模型是采用荧光标记的策略和荧光猝灭技术,通过观察荧光灭光情况排除非解,从而有效的解决可满足性问题(SAT).该模型方法具有错误率低、编码简单、读取方便等很好的性能,能够大大减少实验过程中的错差.     

Convergence Rate Analysis of Gaussian Belief Propagation for Markov Networks

Gaussian belief propagation algorithm (GaBP) is one of the most important distributed algorithms in signal processing and statistical learning involving Markov networks. It is well known that the algorithm correctly computes marginal density functions from a high dimensional joint density function over a Markov network in a finite number of iterations when the underlying Gaussian graph is acyclic. It is also known more recently that the algorithm produces correct marginal means asymptotically for cyclic Gaussian graphs under the condition of walk summability (or generalised diagonal dominance). This paper extends this convergence result further by showing that the convergence is exponential under the generalised diagonal dominance condition, and provides a simple bound for the convergence rate. Our results are derived by combining the known walk summability approach for asymptotic convergence analysis with the control systems approach for stability analysis.      

求解QBF 问题的启发式调查传播算法

提出了一种启发式调查传播算法,并基于该算法设计了一种QBF(quantified Boolean formulae)求解器——HSPQBF(heuristic survey propagation algorithm for solving QBF)系统.它将Survey Propagation信息传递方法应用到QBF求解问题中.利用Survey Propagation作为启发式引导DPLL(Davis,Putnam,Logemann and Loveland)算法,选择合适的变量进行分支,从而可以减小搜索空间,并减少算法回退的次数.在分支处理过程中,HSPQBF系统结合了单元传播、冲突学习和满足蕴涵学习等一些优秀的QBF求解技术,从而能够提高QBF问题的求解效率.实验结果表明,HSPQBF无论在随机问题上还是在QBF标准测试问题上都有很好的表现,验证了调查传播技术在QBF问题求解中的实际价值.     

递推信度传播算法——-按良序的信度传播

针对循环信度传播算法在多环的贝叶斯网中迭代次数较多且不一定收敛的问题, 提出了递推信度传播算法. 它与循环信度传播及其推广算法的区别就在于按某一特定顺序(良序)进行信度传播. 该算法经过一轮信度传播便达到不动点, 显著降低了计算量. 按这种顺序传播信度等价于去掉网络中某些边而解除了网络中的环, 从而使信度不再出现环流. 此算法得到的不动点与循环信度传播算法在收敛时得到的不动点是一致的, 也就是网络的Bethe自由能的最小值点. 最后, 实验验证本文所提的算法在实际应用中能有效地降低推理的复杂度.     

An Algorithm for Approximating the Satisfiability Problem of High-level Conditions

The satisfiability problem is the fundamental problem in proving the conflict-freeness of specifications, or in finding a counterexample for an invalid statement. In this paper, we present a non-deterministic, monotone algorithm for this undecidable problem on graphical conditions that is both correct and complete, but in general not guaranteed to terminate. For a fragment of high-level conditions, the algorithm terminates, hence it is able to decide. Instead of enumerating all possible objects of a category to approach the problem, the algorithm uses the input condition in a constructive way to progress towards a solution. To this aim, programs over transformation rules with external interfaces are considered. We use the framework of weak adhesive HLR categories. Consequently, the algorithm is applicable to a number of replacement capable structures, such as Petri-Nets, graphs or hypergraphs.