置信传播和模拟退火相结合求解约束满足问题
Combining belief propagation and simulated annealing to solve random satisfaction problems作者机构：上海理工大学理学院上海200093
出 版 物：《计算机应用研究》 (Application Research of Computers)
年 卷 期：2019年第36卷第5期
页 面：1297-1301页
学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 081202[工学-计算机软件与理论]
基 金：国家自然科学基金青年基金资助项目(11301339) 国家自然科学基金国际(地区)合作与交流项目(11491240108)
摘 要：约束满足问题是人工智能领域的一个重要问题。针对一个具有精确相变现象和能产生大量难解实例的随机约束满足问题,提出了置信传播和模拟退火相结合的求解算法。这种算法先通过置信传播方程收敛后得到变量取值的边际概率分布,分别采用最大概率和最小分量熵的策略产生一组启发式的初始赋值,再用模拟退火对这组赋值进行修正。实验结果表明,该算法大大提高了初始赋值向最优解收敛的速度,表现出了显著优越于模拟退火算法的求解性能。
维普期刊数据库
同方期刊数据库