A Self-Organization Based Divide and Conquer Algorithm for Distributed Constraint Optimization Problems

Distributed constraint optimization problem （DCOP） is a kind of optimization problem oriented to large-scale, open and dynamic network environments, which has been widely applied in many fields such as computational grid, multimedia networks, e-business, enterprise resource planning and so on. Besides the features such as non-linear and constraint-satisfaction which the traditional optimization problems have, DCOP has its distinct features including dynamic evolution, regional information, localized control and asynchronous updating of network states. It has become a challenge for computer scientists to find out a large-scale, parallel and intelligent solution for DCOP. So far, there have been a lot of methods for solving this problem. However, most of them are not completely decentralized and require prior knowledge such as the global structures of networks as their inputs. Unfortunately, for many applications the assumption that the global views of networks can not be obtained beforehand is not true due to their huge sizes, geographical distributions or decentralized controls. To solve this problem, a self-organizing behavior based divide and conquer algorithm is presented, in which multiple autonomous agents distributed in networks work together to solve the DCOP through a proposed self-organization mechanism. Compared with existing methods, this algorithm is completely decentralized and demonstrates good performance in both efficiency and effectiveness.