A Study On Several Issues Of Distributed Constraint Optimization Algorithm

In real life, many problems can be abstracted into multi-agent model to solve. Distributed constraint optimization algorithm (DCOP) is the main algorithm to solve multi-agent problem in recent years. The solution of multi-agent problem is NP hard. How to get the best and completed solution is significant for increasing of productivity and development of society. Firstly, although there are lots of DCOP algorithms, most of them are suitable for solution of specific problems. And because of the different quality of algorithms, when there is a new practical problem abstracted into multi-agent model, the algorithm just has constraints on the choice. Secondly, there is a research about combination of main DCOP algorithms and set up a frame of distributed constraint optimization (FRODO),but it is more suitable for algorithm performance analyzing and has shortage of algorithm selection in practical problem. At the same time, because the framework had been presented early, the efficiency and performance of the algorithm also need to be improved.To solve these problems, this paper analyzes the shortage of the FRODO framework in solving the practical problems. And according to the result, we promote the framework in expansibility and strategy of adaptability. This paper classifies the typical algorithms and set up the adaptive strategy matching algorithm basis on characteristics of constraint graph. At last, this paper designs and realizes the adaptive plant of distributed optimization (APLODO) and improves the MULBS algorithm which founded in process of testing plant.This paper analyzes the process of practical problems solved in the FRODO framework first. It shows that a completed framework of distributed optimization must have a better expansibility and strategy of adaptability. On the one hand, this paper divides the implementation of DCOP algorithms into many modules and explains the implementation of the algorithm in this mode with MULBS algorithm. On the other hand, this paper selects five classical algorithms from the aspect of the strategy of search, the completeness of solution, synchronism and timeliness. Then we analyze and classify algorithms based on performance with three different features of constraint graph under the perfect evaluation index system. The features include density of graph, the number of agents and the domain size of value. After that, this paper gives adaptive strategy matching algorithm based on problem target and algorithm classification. The main idea of the algorithm is score mechanism. Based on FRODO, this paper designs and completes APLODO. At last, we find out that the MULBS algorithm has shortage in solving conflict or run in parallel. This paper gives a better algorithm named MULBS+, the experiment shows that except increasing a few messages, the new algorithm is better than the old one in all aspects.