• 世界杯来了!谈谈中国足球怎么搞(原创) 2019-08-24
  • 世界杯“男模天团”闪亮登场 2019-08-23
  • 端午假期国内游客超8900万人次 全域旅游见成效 2019-08-21
  • 张佳宁杂志玩转新娘风 甜系女生展俏皮魅力 2019-08-21
  • 高清:里约奥运会官方海报在当地博物馆展出 2019-08-18
  • 乌鲁木齐水磨沟区开建两座立体停车库 2019-08-18
  • 督导组进驻河北6市!扫黑除恶可电话举报 2019-08-17
  • 媒体述评:中国在半岛事务中扮演重要角色 2019-08-17
  • 国内外顶尖规划建筑设计专家建言三亚总部经济区建设 ——凤凰网房产北京 2019-08-12
  • 美国已经获得了,美国期望的金融开放,其他的美国已经不在乎了。本人早就断定,中美合作奢谈共赢。美国需要的是进入和控制中国,中国需要的是出口创汇。 2019-08-12
  • 文体 —频道 春城壹网 七彩云南 一网天下 2019-07-28
  • 足协杯-张稀哲造点索9破门 国安主场2-1上港占先机 2019-07-28
  • 中纪委驻农业部纪检组到滇调研云南省省脱贫攻坚工作 2019-07-21
  • 日战犯笠实自供饿死150名平民 烧死14名村民 2019-07-21
  • 阿根廷努力振兴乡村经济(国外乡村见闻(三)) 2019-07-18
  • b超测孕周公式:香港内部资料三中三

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

    Combining belief propagation and simulated annealing to solve random satisfaction problems

    免费全文下载 (已被下载 次)  
    获取PDF全文
    作者 吴拨荣,赵春艳,原志强
    机构 上海理工大学 理学院,上海 200093
    统计 摘要被查看 次,已被下载
    文章编号 1001-3695(2019)05-004-1297-05
    DOI 10.19734/j.issn.1001-3695.2017.11.0790
    摘要 约束满足问题是人工智能领域的一个重要问题。针对一个具有精确相变现象和能产生大量难解实例的随机约束满足问题,提出了置信传播和模拟退火相结合的求解算法。这种算法先通过置信传播方程收敛后得到变量取值的边际概率分布,分别采用最大概率和最小分量熵的策略产生一组启发式的初始赋值,再用模拟退火对这组赋值进行修正。实验结果表明,该算法大大提高了初始赋值向最优解收敛的速度,表现出了显著优越于模拟退火算法的求解性能。
    关键词 RB模型; 相变现象; 置信传播; 模拟退火; 算法效率
    基金项目 国家自然科学基金青年基金资助项目(11301339)
    国家自然科学基金国际(地区)合作与交流项目(11491240108)
    本文URL //www.eoqksu.shop/article/01-2019-05-004.html
    英文标题 Combining belief propagation and simulated annealing to solve random satisfaction problems
    作者英文名 Wu Borong, Zhao Chunyan, Yuan Zhiqiang
    机构英文名 College of Science,University of Shanghai for Science & Technology,Shanghai 200093,China
    英文摘要 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.
    英文关键词 RB model; phase transition; belief propagation; simulated annealing; algorithm efficiency
    参考文献 查看稿件参考文献
     
    收稿日期 2017/11/29
    修回日期 2018/1/16
    页码 1297-1301
    中图分类号 TP301.6
    文献标志码 A
  • 世界杯来了!谈谈中国足球怎么搞(原创) 2019-08-24
  • 世界杯“男模天团”闪亮登场 2019-08-23
  • 端午假期国内游客超8900万人次 全域旅游见成效 2019-08-21
  • 张佳宁杂志玩转新娘风 甜系女生展俏皮魅力 2019-08-21
  • 高清:里约奥运会官方海报在当地博物馆展出 2019-08-18
  • 乌鲁木齐水磨沟区开建两座立体停车库 2019-08-18
  • 督导组进驻河北6市!扫黑除恶可电话举报 2019-08-17
  • 媒体述评:中国在半岛事务中扮演重要角色 2019-08-17
  • 国内外顶尖规划建筑设计专家建言三亚总部经济区建设 ——凤凰网房产北京 2019-08-12
  • 美国已经获得了,美国期望的金融开放,其他的美国已经不在乎了。本人早就断定,中美合作奢谈共赢。美国需要的是进入和控制中国,中国需要的是出口创汇。 2019-08-12
  • 文体 —频道 春城壹网 七彩云南 一网天下 2019-07-28
  • 足协杯-张稀哲造点索9破门 国安主场2-1上港占先机 2019-07-28
  • 中纪委驻农业部纪检组到滇调研云南省省脱贫攻坚工作 2019-07-21
  • 日战犯笠实自供饿死150名平民 烧死14名村民 2019-07-21
  • 阿根廷努力振兴乡村经济(国外乡村见闻(三)) 2019-07-18