| As an important and efficient formulism to solve collaboration problem in multi-agent system, Distributed Constraint Optimization Problem(DCOP) has become an effective technique for distributed intelligent system modeling and multi-objective coordination optimization. Therefore, the study for DCOP has important research significance and practical value. Compared to the traditional centralized control, DCOP provides strong robustness and privacy, which is suitable to deal with large-scale and difficult combinatorial problems. So, DCOP has become a research hotspot in the field of distributed artificial intelligence. Meanwhile, the algorithms for solving DCOP are also studied extensively and are divided into complete and incomplete algorithms. Complete algorithms aim at traversing all combination spaces and guaranteeing to find the global optimal solution. Incomplete algorithms try to find a suboptimal solution in limited time. Nowadays, the search based strategies are the more typical solution strategy for complete and incomplete algorithms and have gained widespread concern. However, these search based strategies have still many limitations and cannot meet the needs of practical application. The main limitation for complete algorithms lacks the various search strategy; the main limitation for incomplete algorithms is that guiding the search based on individual local information is easy to fall into local optimum.Aiming at the above limitations, the paper mainly focuses the studies on complete and incomplete algorithms for solving DCOP from the two aspects: strategy integration and swarm intelligence based guidance. The detailed work is done as follows:(1) Provide an overview of DCOP algorithms and introduce the related definitions and commonly used communication structure of DCOP as well as its test benchmarks, evaluation metrics and experimental platform. The two complete algorithms based on Best-First search(BFS) and Depth-First search(DFS) strategies are described in detail and the knowledge of Ant Colony optimization(ACO) along with the ACO algorithm to solve Distributed Constraint Satisfaction problem(DCSP) are also presented. Moreover, the pros and cons of BFS and DFS strategies are deeply analyzed and the relationship between the two search strategies and the pseudo-tree of DCOP are explored, which provide a basis for the integration of BFS and DFS strategies.(2) A hybrid DCOP complete algorithm with DFS and BFS strategies is proposed. Based on the relationship between the two search strategies and the pseudo-tree of DCOP, the proposed algorithm adopts the layering boundary in the pseudo-tree to divide the agents with the different positions into DFS based agents and BFS based agents. A rule of layering boundary and a seamless joint scheme between the two strategies are given. The proposed algorithm not only makes full use of the advantages of the two strategies but also does not aggravate the original algorithm's complexity by maintaining the date structures and message types of the original algorithm. The completeness and effectiveness of the proposed algorithm are demonstrated by the theory and experiments, respectively.(3) A DCOP incomplete algorithm based on Ant Colony optimization(ACO) is proposed. By means of the swarm intelligence characteristics of ACO, the proposed algorithm guides the individuals to make the decision according to the global information generated by the cooperation among the individuals. After considering the differences between DCSP and DCOP, the pseudo-tree is adopted as the construction graph to improve the search concurrency; according to the characteristics of DCOP, the combination of logarithm and reciprocal operations are introduced into the pheromone update and guiding probability computation; the message processing scheme based on assembly line is proposed to enhance search efficiency. Finally, the experimental results demonstrate the superiority of the proposed algorithm over the other compared algorithms. |
PDF Full Text Request