检索结果-内蒙古大学图书馆

Balancing exploration and exploitation in incomplete Min/Max-sum inference for distributed constraint optimization

AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS 2017年第5期31卷 1165-1207页

作者： Zivan, Roie Parash, Tomer Cohen, Liel Peled, Hilla Okamoto, Steven Ben Gurion Univ Negev Dept Ind Engn & Management Beer Sheva Israel

Distributed Constraint Optimization Problems (DCOPs) are NP-hard and therefore the number of studies that consider incomplete algorithms for solving them is growing. Specifically, the Max-sum algorithm has drawn attention in recent years and has been applied to a number of realistic applications. Unfortunately, in many cases Max-sum does not produce high-quality solutions. More specifically, Max-sum does not converge and explores solutions of low quality when run on problems whose constraint graph representation contains multiple cycles of different sizes. In this paper we advance the state-of-the-art in incomplete algorithms for DCOPs by: (1) proposing a version of the Max-sum algorithm that operates on an alternating directed acyclic graph (Max-sum_AD), which guarantees convergence in linear time;(2) solving a major weakness of Max-sum and Max-sum_AD that causes inconsistent costs/utilities to be propagated and affect the assignment selection, by introducing value propagation to Max-sum_AD (Max-sum_ADVP);and (3) proposing exploration heuristic methods that evidently improve the algorithms performance further. We prove that Max-sum_ADVP converges to monotonically improving states after each change of direction, and that it is guaranteed to converge in pseudo-polynomial time to a stable solution that does not change with further changes of direction. Our empirical study reveals a large improvement in the quality of the solutions produced by Max-sum_ADVP on various benchmarks, compared to the solutions produced by the standard Max-sum algorithm, Bounded Max-sum and Max-sum_AD with no value propagation. It is found to be the best guaranteed convergence inference algorithm for DCOPs. The exploration methods we propose for Max-sum_ADVP improve its performance further. However, anytime results demonstrate that their exploration level is not as efficient as a version of Max-sum, which uses Damping.

关键词： DCOP incomplete inference algorithms

来源：评论

学校读者我要写书评

暂无评论

Governing convergence of Max-sum on DCOPs through damping and splitting

引用

ARTIFICIAL INTELLIGENCE 2020年 279卷

作者： Cohen, Liel Galiki, Rotem Zivan, Roie Ben Gurion Univ Negev Dept Ind Engn & Management Beer Sheva Israel

Max-sum is a version of Belief Propagation, used for solving DCOPs. In tree-structured problems, Max-sum converges to the optimal solution in linear time. Unfortunately, when the constraint graph representing the problem includes multiple cycles (as in many standard DCOP benchmarks), Max-sum does not converge and explores low quality solutions. Recent attempts to address this limitation proposed versions of Max-sum that guarantee convergence, while ignoring some of the problem's constraints. Damping is a method that is often used for increasing the chances that Belief Propagation will converge. That being said, it has not been suggested for inclusion in the algorithms that propose Max-sum for solving DCOPs. In this paper we advance the research on incomplete-inference DCOP algorithms by: 1) investigating the effect of damping on Max-sum. We prove that, while damping slows down the propagation of information among agents, on tree-structured graphs, Max-sum with damping is guaranteed to converge to the optimal solution in weakly polynomial time;and 2) proposing 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 into two function nodes, we can control the level of asymmetry for each constraint. Our empirical results demonstrate a drastic improvement in the performance of Max-sum when using damping (referred to herein as Damped Max-sum, DMS). However, in contrast to the common assumption that Max-sum performs best when converging, we demonstrate that non converging versions perform efficient exploration, and produce high quality results, when implemented within an anytime framework. On most standard benchmarks, the best results were achieved using versions with a high damping factor, which outperformed existing incom

关键词： Distributed Constraint Optimization incomplete inference algorithms Max-sum

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：