一种历史局部代价求解ADCOPs的算法  

Historical local cost based algorithm to solve ADCOPs

作　　者：石美凤 吴俊 陈媛[1] SHI Meifeng;WU Jun;CHEN Yuan(College of Computer Science and Engineering,Chongqing University of Technology,Chongqing 400054,China)

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

出　　处：《重庆理工大学学报（自然科学）》2022年第9期156-163,共8页Journal of Chongqing University of Technology：Natural Science

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

摘　　要：局部搜索算法是求解非对称分布式约束优化问题(asymmetric distributed constraint optimization problems,ADCOPs)的热点,然而此系列算法都未利用历史局部代价这一关键信息。提出了一种新的历史局部代价的算法(historical local cost,HLC),利用局部代价历史记录求解ADCOPs。HLC使用指数加权移动平均(exponential weighted moving average,EWMA)对局部代价进行模拟更新,并引入了种群机制对其充分模拟和搜索更广的解空间,从模拟局部代价的有效性和种群作用的优越性进行了理论分析。实验结果表明:HLC比最先进的ADCOPs非完备算法有更高质量的解。Since the local search algorithm for asymmetric distributed constrained optimization problems(ADCOPs)is proposed,the historical local cost which directly affects the global cost has not been considered.Therefore,this paper proposes a new algorithm HLC based on historical local cost,which uses local cost history to solve ADCOPs.HLC uses the exponential weighted moving average(EWMA)to simulate and update the local cost,and introduces the population mechanism to fully simulate and search it to solve ADCOPs.Moreover,the effectiveness of local cost simulation and the superiority of population action are analyzed theoretically.Finally,the experimental results show that HLC performs the greater superiorities over the state-of-the-art ADCOPs incomplete algorithms.

关 键 词：多智能体 分布式约束优化问题 非完备算法 局部搜索算法 

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