The Study On Local Search Algorithms For Distributed Constraint Optimization Problems

As an important abstraction for collaboration problem in multi-agent system,Distributed Constraint Optimization Problems(DCOP)have become an effective technique for modeling distributed intelligent system and multi-objective coordination optimization problems with the characteristics of privacy,information locality,decentralized control,etc.Therefore,the algorithms for solving DCOP have become a hot research area in this field.The local search algorithm has made broad attention as an important banch of incomplete algorithm for solving DCOP,since the simple logical structure and flexible optimization method.This paper provides the overview of algorithms for DCOP and introduces the advantages and weaknesses of different algorithms.Aiming at the limitations of local search algorithms,this paper mainly focus the studies on the two aspects: the weakness of local search algorithms and intelligence based guidance.The detailed work is done as follows:(1)This paper provides a partial decision scheme(PDS)for local search algorithms according to the dependency of the value assignments between agents.By ignoring some value assignments of neighbors to break the dependency,agents gain more decision space and make better decisions,so that the solution quality of local search algorithms can be improved effectively with a small overhead.PDS comprises two partial decision processes: trigger partial decision and recursive partial decision.The former is performed by agents who cannot enhance their local benefits unilaterally to break out of potential local optima that caused by the dependency of the value assignments.The latter is recursively performed by neglected agents to improve global benefits.Besides,the trigger conditions along with a self-adaptive probability are introduced to control the use of PDS.Besides,the scheme can be applied to any synchronous local search algorithms,which peovides universal application.Moreover,we prove the feasibility and convergence of PDS,while the experimental results also demonstrate the effectiveness of PDS.(2)This paper presents a local-search-based genetic algorithm(LS-GA)which combines the intelligence of genetic algorithm and the flexibility of local search as a new try of incomplete algorithms for solving DCOP.This paper presents mALS framework by improving ALS framework,so the best individual can be record in distributed environment.According to the characteristics of DCOP,we modify the method of gene coding and use the block area as gene segment of individual.Then two crossover operators based on random strategy and competition strategy repectively,and the selection operator based on mALS framework and a predetermination stragety are presented,so that the consistency can be guaranteed when operating individuals by different agents.The experimental results demonstrate the effectiveness of the proposed algorithm by comparing with different algorithms.