A genetic algorithm based framework for local search algorithms for distributed constraint optimization problems

Abstract Local search algorithms are widely applied in solving large-scale Distributed constraint optimization problems (DCOPs) where each agent holds a value assignment to its variable and iteratively makes a decision on whether to replace its assignment according to its neighbor states. However, the value assignments of their neighbors confine their search to a small space so that agents in local search algorithms easily fall into local optima. Fortunately, Genetic Algorithms (GAs) can direct a search process to a more promising space and help the search process to break up the confine of local states. Accordingly, we propose a GA-based framework (LSGA) to enhance local search algorithms, where a series of genetic operators are redesigned for agents in distributed scenario to accommodate DCOPs. First, a fitness function is designed to evaluate the assignments for each agent, considering the balance of local benefits and global benefits. Then, a new method is provided to decide crossover positions in terms of agent-communication and topological structure of DCOPs. Besides, a self-adaptive crossover probability and a self-adaptive mutation probability are proposed to control the uses of crossover operator and mutation operator, respectively. And more importantly, the LSGA framework can be easily applied in any local search algorithm. The experimental results demonstrate the superiority of the use of LSGA in the typical search algorithms over state-of-the-art incomplete algorithms.

Authors

• Ziyu Chen
• Lizhen Liu
• Zhepeng Yu

Keywords

• Multi-agent system
• Distributed constraint optimization problem
• Incomplete algorithm
• Genetic algorithm
• Local search algorithm