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

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