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

Historical local cost based algorithm to solve ADCOPs

局部搜索算法是求解非对称分布式约束优化问题(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.