标题： GDBA 再探讨：释放引导局部搜索在分布式约束优化中的潜力 显示英文标题

标题： GDBA Revisited: Unleashing the Power of Guided Local Search for Distributed Constraint Optimization

摘要： 局部搜索是求解分布式约束优化问题（DCOPs）的重要不完全算法类别，但它常常收敛到较差的局部最优解。虽然GDBA提供了一套全面的规则来避免过早收敛，但在一般值问题上的实证效益仍然有限。在本工作中，我们系统地检查了GDBA，并识别出三个可能导致其性能不佳的因素，即过度激进的约束违反条件、无界的惩罚累积以及未协调的惩罚更新。为了解决这些问题，我们提出了分布式引导局部搜索（DGLS），这是一种新的GLS框架，用于DCOPs，它结合了自适应的违反条件，以选择性地惩罚高成本的约束，一种惩罚蒸发机制来控制惩罚的大小，并一种同步方案用于协调的惩罚更新。我们从理论上证明了惩罚值是有限的，而且在我们的DGLS中，代理参与了一个潜在博弈。我们在各种标准基准上的广泛实验结果表明，DGLS在性能上显著优于最先进的基线方法。特别是，与具有高阻尼因子的阻尼最大和算法（例如0.7或0.9）相比，我们的DGLS在一般值问题上表现出具有竞争力的性能，并且在任何时间结果方面，在结构化问题上以显著的差距超越它（\textbf{3.77\%--66.3\%}）。 显示英文摘要

摘要： Local search is an important class of incomplete algorithms for solving Distributed Constraint Optimization Problems (DCOPs) but it often converges to poor local optima. While GDBA provides a comprehensive rule set to escape premature convergence, its empirical benefits remain marginal on general-valued problems. In this work, we systematically examine GDBA and identify three factors that potentially lead to its inferior performance, i.e., over-aggressive constraint violation conditions, unbounded penalty accumulation, and uncoordinated penalty updates. To address these issues, we propose Distributed Guided Local Search (DGLS), a novel GLS framework for DCOPs that incorporates an adaptive violation condition to selectively penalize constraints with high cost, a penalty evaporation mechanism to control the magnitude of penalization, and a synchronization scheme for coordinated penalty updates. We theoretically show that the penalty values are bounded, and agents play a potential game in our DGLS. Our extensive empirical results on various standard benchmarks demonstrate the great superiority of DGLS over state-of-the-art baselines. Particularly, compared to Damped Max-sum with high damping factors (e.g., 0.7 or 0.9), our DGLS achieves competitive performance on general-valued problems, and outperforms it by significant margins (\textbf{3.77\%--66.3\%}) on structured problems in terms of anytime results.