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

• 作者: 原志强 吴拨荣 赵春艳
• 来源期刊: 计算机应用研究
• 关键词: RB模型 相变现象 置信传播 模拟退火 算法效率
• 年，卷（期）: 2019,（5）
• 所属期刊栏目: 算法研究探讨
• 页码范围: 1297-1301
• 页数: 5页
• 分类号: TP301.6
• 语种: 中文
• DOI: 10.19734/j.issn.1001-3695.2017.11.0790

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	原志强	上海理工大学理学院	2	17	1.0	2.0
2	赵春艳	上海理工大学理学院	6	17	1.0	4.0
3	吴拨荣	上海理工大学理学院	1	1	1.0	1.0