• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International conference on principles and practice of constraint programming >Balancing Asymmetry in Max-sum Using Split Constraint Factor Graphs
【24h】

Balancing Asymmetry in Max-sum Using Split Constraint Factor Graphs

机译：使用分裂约束因子图的最大和平衡不对称

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Max-sum is a version of Belief Propagation, used for solving DCOPs. On tree-structured problems, Max-sum converges to the optimal solution in linear time. When the constraint graph representing the problem includes multiple cycles, Max-sum might not converge and explore low quality solutions. Damping is a method that increases the chances that Max-sum will converge. Damped Max-sum (DMS) was recently found to produce high quality solutions for DCOP when combined with an anytime framework. We propose a novel method for adjusting the level of asymmetry in the factor graph, in order to achieve a balance between exploitation and exploration, when using Max-sum for solving DCOPs. By converting a standard factor graph to an equivalent split constraint factor graph (SCFG), in which each function-node is split to two function-nodes, we can control the level of asymmetry for each constraint. Our empirical results demonstrate that by applying DMS to SCFGs with a minor level of asymmetry we can find high quality solutions in a small number of iterations, even without using an anytime framework. As part of our investigation of this success, we prove that for a factor-graph with a single constraint, if this constraint is split symmetrically, Max-sum applied to the resulting cycle is guaranteed to converge to the optimal solution and demonstrate that for an asymmetric split, convergence is not guaranteed.
机译：Max-sum是“信念传播”的一个版本，用于解决DCOP。在树结构问题上，最大和在线性时间内收敛到最优解。当表示问题的约束图包括多个周期时，最大和可能不会收敛并探索低质量的解决方案。阻尼是增加最大和收敛的机会的一种方法。最近发现，与任何时间框架结合使用，阻尼最大和（DMS）可以为DCOP提供高质量的解决方案。我们提出了一种新的方法来调整因子图中的不对称程度，以便在使用Max-sum解决DCOP时实现开发与勘探之间的平衡。通过将标准因子图转换为等效拆分约束因子图（SCFG）（其中每个功能节点均被拆分为两个功能节点），我们可以控制每个约束的不对称程度。我们的经验结果表明，通过将DMS应用于不对称程度较小的SCFG，即使不使用任何时间框架，也可以通过少量迭代找到高质量的解决方案。作为对该成功研究的一部分，我们证明对于具有单个约束的因子图，如果对称地分解该约束，则可以保证应用于结果循环的Max-sum收敛到最优解，并证明不对称拆分，无法保证收敛。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号