置信传播和模拟退火相结合求解约束满足问题

Combining belief propagation and simulated annealing to solve random satisfaction problems

约束满足问题是人工智能领域的一个重要问题。针对一个具有精确相变现象和能产生大量难解实例的随机约束满足问题,提出了置信传播和模拟退火相结合的求解算法。这种算法先通过置信传播方程收敛后得到变量取值的边际概率分布,分别采用最大概率和最小分量熵的策略产生一组启发式的初始赋值,再用模拟退火对这组赋值进行修正。实验结果表明,该算法大大提高了初始赋值向最优解收敛的速度,表现出了显著优越于模拟退火算法的求解性能。

Constraint satisfaction problem is an important issue in the field of artificial intelligence. This paper proposed two algorithms combining belief propagation and simulated annealing to solve a random constraint satisfaction problem with exact phase transitions and large number of hard instances. The algorithms firstly obtained the marginal probability distribution of variable values after the convergence of the belief propagation equation, then used the strategy of maximum probability and minimum component entropy to generate a set of heuristic initial assignments, and then used simulated annealing to modify the assignments. The experimental results show that the algorithms greatly improve the convergence rate from the initial assignments toward the optimal solution, and shows a significant advantage over simulated annealing algorithm.