Max/min-sum distributed constraint optimization through value propagation on an alternating DAG
Max/min-sum distributed constraint optimization through value propagation on an alternating DAG
复制标题
通过交替 DAG 上的值传播进行最大/最小和分布式约束优化
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Hilla Peled
中科院分区：
文献类型：
--
作者：
R. Zivan;Hilla Peled
分布式约束优化问题(DCOP)是NP-Hard问题，因此越来越多的研究考虑不完全算法来解决这些问题。具体地说，最大和算法近年来引起了人们的关注，并在许多实际应用中得到了应用。不幸的是，在许多情况下，Max-sum并不能产生高质量的解决方案。更具体地说，当问题在执行Max-sum的因子图中包含各种大小的圈时，算法不收敛，并且它访问的状态质量较低。
在本文中，我们通过以下几个方面推进了对DCOP不完备算法的研究：(1)提出了一种基于交替有向无环图的Max-sum算法(Max-sum_AD)，该算法保证了线性时间内的收敛。(2)找出MAX-SUM和MAX-SUM_AD的主要弱点，这些弱点会导致不一致的成本/效用传播，并影响作业选择。(3)通过在Max-sum_AD中引入值传播来解决识别出的问题。我们的实证研究表明，与标准的最大和算法、有界的最大和算法以及无值传播的最大和算法相比，在求解包含循环的问题时，带值传播的Max-Sum_AD产生的解的质量有很大的改善。
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, when problems include cycles of various sizes in the factor graph upon which Max-sum performs, the algorithm does not converge and the states that it visits are of low quality.
In this paper we advance the research on 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) Identifying major weaknesses of Max-sum and Max-sum_AD that cause inconsistent costs/utilities to be propagated and affect the assignment selection. (3) Solving the identified problems by introducing value propagation to Max-sum_AD. Our empirical study reveals a large improvement in the quality of the solutions produced by Max-sum_AD with value propagation (VP), when solving problems which include cycles, compared with the solutions produced by the standard Max-sum algorithm, Bounded Max-sum and Max-sum_AD with no value propagation.