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

来源：计算机应用研究杂志2022年第8期北京时间：

作者：石美凤,杨海,陈媛,肖诗川,廖鑫,何颖,

单位：重庆理工大学计算机科学与工程学院,重庆400054；

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

关键词：分布式约束优化问题,多智能体系统,局部搜索算法,并行搜索优化,

基金资助：重庆市教育委员会科学技术研究计划青年项目资助项目(KJQN202001139)；重庆市基础研究与前沿探索项目(cstc2018jcyjAX0287)；重庆理工大学科研启动基金资助项目(2019ZD03)；重庆理工大学研究生创新项目(clgycx20202094)；；