Balancing exploration and exploitation in incomplete Min/Max-sum inference for distributed constraint optimization
Balancing exploration and exploitation in incomplete Min/Max-sum inference for distributed constraint optimization
复制标题
平衡分布式约束优化的不完整最小/最大和推理中的探索和利用
DOI：
--
复制
发表时间：
2017
影响因子：
1.9
通讯作者：
Steven Okamoto
中科院分区：
文献类型：
--
作者：
R. Zivan;Tomer Parash;Liel Cohen;Hilla Peled;Steven Okamoto
分布式约束优化问题（dcop）是np困难的，因此考虑不完全算法来解决它们的研究数量正在增长。具体来说，最大和算法近年来引起了人们的关注，并被应用到许多实际应用中。不幸的是，在许多情况下，maxsum并不能产生高质量的解决方案。更具体地说，当运行在约束图表示包含多个不同大小的循环的问题上时，Max-sum不收敛，并且探索低质量的解。在本文中，我们提出了dcop的不完全算法的最新进展：(1)提出了一个在交替有向无环图（Max-sum_AD）上运行的最大和算法的版本，它保证了线性时间内的收敛性；(2)通过引入Max-sum_AD （Max-sum_ADVP）的价值传播，解决了Max-sum和Max-sum_AD导致不一致的成本/效用传播并影响分配选择的主要弱点；(3)提出了进一步提高算法性能的探索启发式方法。证明了Max-sum_ADVP在每次改变方向后收敛到单调改进状态，并保证在伪多项式时间内收敛到不随方向变化的稳定解。我们的实证研究表明，与没有值传播的标准Max-sum算法、Bounded Max-sum算法和Max-sum_AD算法相比，Max-sum_ADVP算法在各种基准上产生的解的质量有了很大的提高。结果表明，该算法是最能保证dcop收敛性的推理算法。我们提出的探索方法进一步提高了Max-sum_ADVP的性能。然而，任何时候的结果都表明，它们的勘探水平不如使用阻尼的Max-sum版本有效。
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.