求解分布式约束优化问题的邻居忽略策略局部搜索算法  

Series of neighbor ignoring strategies for local search algorithms for distributed constraint optimization problems

作　　者：石美凤 贾国艳 Shi Meifeng;Jia Guoyan(Dept.of Computer Science&Engineering,Chongqing University of Technology,Chongqing 400054,China)

机构地区：[1]重庆理工大学计算机科学与工程学院,重庆400054

出　　处：《计算机应用研究》2025年第3期788-794,共7页Application Research of Computers

基　　金：重庆市教委科学技术研究项目(KJQN202401101);重庆理工大学研究生创新工程项目(gzlcx20232058)。

摘　　要：针对现有基于局部搜索思想的分布式约束优化问题求解算法存在容易陷入局部最优的问题,提出了一系列用于求解分布式约束优化问题(DCOP)的基于邻居忽略策略(NI)的局部搜索算法,以扩大对解空间的搜索,避免陷入局部最优。为了研究智能体之间约束关系的可变性和随机性对局部搜索的影响和极值对于局部搜索的影响,分别设计了单个随机邻居忽略策略和极值邻居忽略策略。同时,基于单个邻居随机忽略策略和极值邻居忽略策略,设计了用于平衡算法探索和开发能力的混合策略。此外,还设计了多个邻居随机忽略策略,以探讨求解DCOP时同时随机忽略多个邻居的可行性,并在理论上证明了随机邻居忽略策略对智能体之间的约束关系没有影响。将提出的一系列基于邻居忽略策略的局部搜索算法与十种先进的非完备算法在三类基准问题上的寻优结果进行了实验对比,结果表明所提一系列用于求解DCOP的基于邻居忽略策略的局部搜索算法显著优于目前先进的非完备算法。The local search algorithm for solving DCOP has the advantages of high flexibility,high efficiency,and high fault tolerance,but also easy to fall into the local optimum as the incomplete algorithm.Considering this,this paper designed a series of neighbor ignoring strategies to expand the search for solution spaces.Specifically,the single random neighbor ignoring strategy delved into the impact of variability and randomness in the constraint relationships among agents on the local search.In contrast,extreme neighbor ignoring focused on discussing the influence of extreme values on the local search algorithm.Furthermore,the hybrid strategy denoted as single random and extreme neighbor ignoring integrated the previous two to strike a more optimal balance between exploration and exploitation.In addition,the multiple random neighbor ignoring strategy offers a way to investigate the feasibility and implications of ignoring multiple neighbors simultaneously when solving DCOP.Theoretical ana-lysis reveals that the proposed neighbor ignoring strategy has no discernible impact on the constraints between agents.The extensive experimental results on three benchmark problems demonstrate the superiority of utilizing the neighbor ignoring strategy within the local search framework over the current state-of-the-art incomplete algorithms.

关 键 词：分布式约束优化问题 邻居忽略 解空间扩大搜索 局部搜索算法 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]