The Study On Ant Conlony Optimization For Distributed Constraint Optimization Problems

Distributed Constraint Optimization Problems(DCOP)and Asymmetric Distributed Constraint Optimization Problems(ADCOP)are fundamental frameworks for coordination problems in Multi-agent Systems(MAS).Whereas,many existing DCOP algorithms derive from centralized single-solution optimization approaches.The study on ADCOP is still in its infancy,with few research achievements and feasible algorithm framework.As an important population-based algorithm,ant colony optimization(ACO)has been successfully applied into combinatorial optimization problems,but is rarely used in distributed constraint inference problems.Since DCOP and ADCOP can be seen distributed combinatorial optimization problems,this paper presents two algorithms that take the power of ants to solve DCOP and ADCOP.The main work is as follows:? This paper presents an ant-based algorithm to solve DCOP,called ACO_DCOP.In this paper,based on the characteristic of DCOP,the construction graph,the probability and the updating of pheromone in ACO are studied to apply ACO to solve DCOP.Specifically,ACO_DCOP constructs the construction graph according to a BFS pseudo-tree.And the calculation of a pheromone factor in an agent considers the assignments of the other agents to remove irrelevant pheromone trails.In order to evaluate the local benefits reasonably,a new mechanism that captures local benefits is proposed to compute heuristic factors.And a new method is proposed to compute pheromone deltas appropriately,which uses the mean of the solution costs as the criterion for evaluating the quality of solutions.Moreover,pipelining technique is introduced to improve the solving efficiency.In our theoretical analysis,we prove thatACO_DCOP is an anytime algorithm.Our empirical evaluation indicates that ACO_DCOP is able to find solutions of equal or significantly higher quality than state-of-the-art DCOP algorithms.? This paper presents an ant-based algorithm to solve ADCOP,called ACO_ADCOP.This paper reaches the calculation of the total cost in an ADCOP,the privacy loss,the construction graph and the probability for applying ACO into solving ADCOP.To compute the total cost in an ADCOP,this paper introduces the DFS tree-based back-checking mechanism.And the extent of privacy loss is limited by making messages only related to the accumulated cost.Moreover,this paper also proposes a new method to compute the heuristic factor,which evaluates the local benefit using an estimation of costs for neighbors.Finally,the experiment results indicate that ACO_ADCOP performs better than the existing ADCOP incomplete algorithms.