A genetic algorithm based framework for local search algorithms for distributed constraint optimization problems
- PDF / 4,663,681 Bytes
- 31 Pages / 439.37 x 666.142 pts Page_size
- 94 Downloads / 186 Views
(2020) 34:41
A genetic algorithm based framework for local search algorithms for distributed constraint optimization problems Ziyu Chen1 · Lizhen Liu1 · Jingyuan He1 · Zhepeng Yu1
© Springer Science+Business Media, LLC, part of Springer Nature 2020
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. Keywords Multi-agent system · Distributed constraint optimization problem · Incomplete algorithm · Genetic algorithm · Local search algorithm
1 Introduction Distributed constraint optimization problems (DCOPs) are a fundamental framework for multi-agent systems (MAS) [1] where agents coordinate their decisions to optimize a global objective. They have been widely deployed in many real applications [2] such as meeting and task scheduling [3–5], sensor network problems [6, 7], smart grid problems * Ziyu Chen [email protected] * Lizhen Liu [email protected] 1
College of Computer Science, Chongqing University, Chongqing, China
13
Vol.:(0123456789)
41
Page 2 of 31
Autonomous Agents and Multi-Agent Systems
(2020) 34:41
[8, 9], etc. A DCOP consists of a set of agents, each choosing values for its own variables under some constraints. Then, the agents coordinate their decisions of value assignments so that the sum of all constraints is optimized. For solving DCOPs, plenty of algorithms have been proposed and they can generally be grouped into two categories, i.e., incomplete and complete. Complete algorithms can guarantee to find the optimal solution and be broadly divided into search-based algorithms [10–15] and inference-based [16–19] algorithms which systematically explore t
Data Loading...
