论文标题
提高有界最大和算法的溶液质量以求解涉及硬和软约束的DCOP
Improving Solution Quality of Bounded Max-Sum Algorithm to Solve DCOPs involving Hard and Soft Constraints
论文作者
论文摘要
有界的最大-SUM（BMS）是一种消息通讯算法，它为特定形式的偏心协调问题提供了近似解决方案，即分布式约束优化问题（DCOPS）。特别是，BMS算法能够以较大的搜索空间解决这种类型的问题，但以低计算成本为代价。值得注意的是，传统的DCOP配方并不考虑必须满足的那些约束（也称为硬约束），而仅集中于软限制。因此，尽管在许多现实世界应用中都观察到两种约束的存在，但BMS算法并未积极利用硬性约束。为了解决这个问题，我们以一种可以处理具有两种类型约束的DCOP的方式来量身定制BMS。这样，我们的方法可以提高算法的解决方案质量。经验结果在大型DCOP的溶液质量方面表现出明显提高。
Bounded Max-Sum (BMS) is a message-passing algorithm that provides approximation solution to a specific form of de-centralized coordination problems, namely Distributed Constrained Optimization Problems (DCOPs). In particular, BMS algorithm is able to solve problems of this type having large search space at the expense of low computational cost. Notably, the traditional DCOP formulation does not consider those constraints that must be satisfied(also known as hard constraints), rather it concentrates only on soft constraints. Hence, although the presence of both types of constraints are observed in a number of real-world applications, the BMS algorithm does not actively capitalize on the hard constraints. To address this issue, we tailor BMS in such a way that can deal with DCOPs having both type constraints. In so doing, our approach improves the solution quality of the algorithm. The empirical results exhibit a marked improvement in the quality of the solutions of large DCOPs.
