A Framework based on Genetic Algorithms for Distributed Constraint Optimization Problems

Abstract

Local search algorithms are widely applied in solving large-scale Distributed Constraint Optimization Problems(DCOPs). In local search algorithms, each agent makes its decision based on values of its neighbours. Thus, the search space of agents are bound up with those values. Fortunately, Genetic Algorithm(GA) can direct a search process to a more promising search space and help the search process break up the bound of local states, so we propose a GA-based framework (LSGA) to enhance local search algorithms. In LSGA, a novel fitness function is proposed to help agents evaluate the quality of value assignments. Moreover, we propose a method to decide crossover positions in term of agent-communication and the topological structure of DCOPs. Finally, we design a series of genetic operators for autonomous agents in DCOPs. The LSGA framework can be easily applied in any local search algorithm, and the experimental results demonstrate the superiority of the use of LSGA in the typical search algorithms over state-of-art local search algorithms.