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

来源：计算机应用研究杂志2019年第5期北京时间：

作者：吴拨荣,赵春艳,原志强,

单位：上海理工大学理学院,上海200093；

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

关键词：RB模型,相变现象,置信传播,模拟退火,算法效率,

基金资助：国家自然科学基金青年基金资助项目(11301339)；国家自然科学基金国际(地区)合作与交流项目(11491240108)；；