The Study On Acceleration And Optimization To Incomplete Belief Propagation For Solving Distributed Constrained Optimization Problems

Distributed Constrained Optimization Problems(DCOP)is a fundamental framework for modeling multi-agent coordination in multi-agent systems(MAS)and has been applied in sensor networks,task scheduling,power networks and smart home etc.,with important academic research significance and practical value.The inference-based incomplete algorithms which use belief propagation can be directly used to solve n-ary DCOP.They have been successfully used in many real world applications and are an important method for DCOP solving,in which Max-Sum is typical representative.However,scalability is a huge challenge for incomplete belief propagation algorithms.Although some methods were proposed to overcome the issue,they suffer from either lacking generalization or requiring considerable computation in preprocess phase.Besides,due to there are utility ties,incomplete belief propagation algorithms have low solution quality.Against the above background,this paper devotes to accelerating incomplete belief propagation at a lower cost and improving the solution quality by reducing the affect of utility ties.The main research works are as follows:(1)The paper gives in-depth analysis about the impact of maximization operation on the scalability and the bottleneck of existing acceleration approaches,and presents a method to accelerate belief propagation,called Function Decomposing and State Pruning(FDSP).The method based on a branch-and-bound technique dynamically prunes the search space using the known lower bound and is generic,fast and easy-to-use.In this method,based dynamic programming the function decomposing technique was proposed to compute the upper bound of the function of each partial assignment by exploiting the fact that the assignment of the target variable is given,while state pruning technique based on depth-first was adopted to prune the search space.Then we prove that FDSP provides a monotonic non-increasing upper bound and do not change property of the incomplete belief propagation algorithms.Finally,our experiment results show that FDSP has generalization and powerful acceleration performance,and can effectively prune the solution space even under unfavorable conditions.(2)The paper providess in-depth researches about the effect of the abandoning local function optimality on the solution quality of the incomplete belief propagation algorithms,and presents a class of approaches based on local search strategies to accelerate and optimize the belief propagation,including stochastic strategy(SA-MS),maximum gain strategy(MGM-MS)and coordinate ascent strategy(CA-MS).This kind of approaches first accelerates belief propagation while taking into account the improvement of the solution quality,and innovatively combines local search and inference,then uses local search strategies to perform incomplete traversal of the solution space.In these approaches,the variables are randomly assigned initial value,and then according to different search strategies,the optimal value of the variables are found and replaced,and finally an assignment combination with the maximum utility is obtained.We then theoretically show that above algorithms' anytime property.Finally,the experimental results verify that SA-MS,MGM-MS and CA-MS can accelerate the incomplete belief propagation while improving algorithms' solution quality.