基于局部并行搜索的分布式约束优化算法框架

针对当前局部搜索算法在求解大规模、高密度的分布式约束优化问题（DCOP）时，求解困难且难以跳出局部最优取得进一步优化等问题，提出一种基于局部并行搜索的分布式约束优化算法框架（LPOS），算法中agent通过自身的取值并行地搜索局部所有邻居取值来进一步扩大对解空间的搜索，从而避免算法过早陷入局部最优。为了保证算法的收敛性与稳定性，设计了一种自适应平衡因子K来平衡算法对解的开发和继承能力，并在理论层面证明了并行搜索优化算法可以扩大对解空间的搜索，自适应平衡因子K可以实现平衡目的。综合实验结果表明，基于该算法框架的算法在求解低密度和高密度DCOP时性能都优于目前最新的算法。特别是在求解高密度DCOP中有显著的提升。

Local parallel search framework for distributed constraint optimization problems

In order to solve the problem that it is difficult to get out of the local optimum to achieve further optimization in large-scale dense distributed constraint optimization problems(DCOP), this paper proposed a local parallel search framework(LPOS) for solving algorithms of DCOP. In LPOS, the agent searched all the value assignments of its local neighbors in parallel according to its current value assignment to further expand the search of solution space, so as to avoid the algorithm falling into local optimum prematurely. In order to ensure the convergence of the algorithm, this paper designed an adaptive equilibrium factor K to balance the exploration and exploitation ability of the DCOP solving algorithms. At the theoretical analysis, it proved that the LPOS could expand the search of solution space and the K could achieve the balance. The experimental results demonstrate that the performance of the proposed LPOS is better than the-state-of-the-art algorithms in both low density and high density. Specifically, LPOS significantly superior to the competitors when solving high density DCOP.