一个约束可满足性问题的演化算法求解

约束可满足性问题是一大类常出现于现实应用中的复杂问题,因其繁多的约束条件而出名。本文针对一个经典的约束可满足性问题——斑马属谁问题,基于演化算法的框架进行求解。我们采用矩阵的表示方式,并设计了相应的杂交和变异算子。实验表明,演化算法能高效地解决该问题。

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

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