Page 143 - 《软件学报》2021年第5期

王晓峰 等:可满足性问题中信念传播算法的收敛性分析 1367

由压缩映射原理和引理 1 可知:如果 max a→ i b→ j τ a→ , i b→ ∑ j < 1 成立,则 BP 算法在 A ∞ -范数下收敛,且与初始
信息无关. □
2
3
为了书写方便,不妨设 f (x)=f (f (x)),f (x)=(f (f (x))),….有如下引理成立.
N
引理 2 [44] . 设函数 f :V→V,d 是 V 上的度量.对于某个 N∈`,假设 f 是关于 d 的压缩函数,那么 f 收敛到唯一
2
固定点 x ∞ ,也即对于任意的 x∈V,函数 f 的迭代序列 x,f (x),f (x),…收敛到 x ∞ .
设γ 1 ,γ 2 ,…,γ n 是方阵 M 的特征值,构成 M 的谱γ (M)={γ 1 ,γ 2 ,…,γ n },M 的谱半径为ρ (M)=sup{|γ i |:γ i ∈γ (M)}.
假设τ =max a→i,b→j {τ a→i,b→j },一个|D|×|D|的方阵 M 中的元素定义为 M a→i,b→j =1 V(j)\a (b)1 V(a)\i (j)τ .若 x∈X,则 1 X (x)=1;
若 x∉X,则 1 X (x)=0.
定理 3. 如果方阵 M 的谱半径ρ(M)<1,那么 BP 算法一定能达到收敛点,并且收敛过程不依赖于初始条件.
证明:文献[44]中的定理 4 表明:对于任意的 x∈\ |D| ,M 是一个不依赖于 x 的非负方阵,一个可微函数
|D|
|D|
|D|
f :\ →\ ,假设|f ′(x)|小于等于矩阵 M 中的对于元素.如果 M 的谱半径 1,那么对于任意的 x∈\ ,f 收敛到唯一
2
固定点 x ∞ ,也即 x,f (x),f (x),…,x ∞ .由前文中关于函数 f 的构造及情形 1 和情形 2 的推导可知,|f ′(x)|≤M.因
此,BP 算法能够有效收敛,收敛过程不依赖于初始条件. □
例 2:设命题公式为 F 1 ={(x 1 ∨x 2 ),(x 2 ∨x 3 ),(x 3 ∨x 4 ),…,(x n−1 ∨x n ),(x n ∨x 1 )},该公式的对应因子图中包含一个环路结
构.所以,由上文中所提构造方阵 M 的过程可知,方阵中任意行中除了一个值可能不是 0 的元素之外,所有元素的
值都是 0,将该可能值为非 0 的元素设为τ.通过圆盘定理可以知道:|λ |≤τ ,其中λ 为 M 的特征值.则利用上文中的
证明可知:|λ |≤τ<1.因此,有ρ (M)<1.又由定理 3 可得,在公式 F 1 中,BP 算法能够迭代至收敛状态.同理,在
F 2 ={(¬x 1 ∨¬x 2 ),(¬x 2 ∨¬x 3 ),(¬x 3 ∨¬x 4 ),…,(¬x n−1 ∨¬x n ),(¬x n ∨¬x 1 )}中,BP 算法同样能够到达收敛的状态.
注意到:定理 1 和定理 2 分别是针对范数||A|| 1 和||A|| ∞ 得出的结论,不同的范数对应的收敛条件不同.然而,目
前还不清楚是否存在一个最优范数,使得 BP 算法收敛的判定条件更加有效.

3 数值实验及分析

数值实验中用到的数据由模型 G(n,k,m)产生,n 表示变元个数,m 表示子句个数,k 表示每个子句的长度.实验
3
中,BP 算法的最大迭代次数 t max =10 ,ε=0.001.
当 k=3 时,G(n,k,m)模型被用于产生随机 3-SAT 实例.研究结果表明:对于随机 3-SAT 实例,存在可满足性相
[4]
变现象.如图 3(a)所示,当子句个数与变元个数的比值 m/n 小于 3.5 时,随机 3-SAT 实例高概率可满足 ;当子句
[5]
个数与变元个数的比值 m/n 大于 4.5 时,随机 3-SAT 实例高概率不可满足 ;对于子句个数与变元个数的比值
m/n 介于 3.5 与 4.5 之间的随机 3-SAT 实例,其可满足性不能从概率上给出较为确切的回答.同时,子句个数与变
元个数的比值 m/n 介于 3.5 与 4.5 之间的随机 3-SAT 实例,其求解难度也较大,大多数求解算法在该区域的实例
集上效果不明显,称该区域为随机 3-SAT 实例的难解区域,如图 3(b)所示.在α=4.27 附近,求解难度最大.因此,常
被国际竞赛用于构造难解实例来测试算法的性能.
在实验中,我们选取了两组规模不同的随机 3-SAT 实例,分别为 n=60 和 n=120,每次利用随机实例产生模型
生成 100 个随机实例作为一组数据,并统计每组数据的实验结果,作为图中的每个数据点.相关研究表明:随机实
例的难解程度与α的值密切相关.信息传播算法是基于消息迭代的近似算法,收敛性直接影响算法的性能.图
4(a)是 BP 算法在随机 3-SAT 实例集上的收敛情况,纵坐标是统计了所有实例中,收敛实例所占的比值,即实例能
够达到收敛状态的所占的概率;横坐标为α的变化情况.从图中可以看出:大约α<3.8 时,BP 算法高概率收敛;大
约α>3.8 时,BP 算法的收敛性开始下降;大约α>4.5 时,BP 算法高概率不收敛.这也表明 BP 算法主要用于求解可
满足性实例,在求解不可满足的实例时,算法常常会失效.图 4(b)是 BP 算法的运行时间随约束参数α的变化情
况,纵坐标表示运行时间(单位:s).当α>3.52 时,算法的运行时间急剧增大;随着α的增大,实例的因子图的结构变
得复杂,导致 BP 算法的计算时间增加.