  Distributed Constraint Optimization Problems (DCOPs) are a widely studied
class of optimization problems in which interaction between a set of
cooperative agents are modeled as a set of constraints. DCOPs are NP-hard and
significant effort has been devoted to developing methods for finding
incomplete solutions. In this paper, we study an emerging class of such
incomplete algorithms that are broadly termed as population-based algorithms.
The main characteristic of these algorithms is that they maintain a population
of candidate solutions of a given problem and use this population to cover a
large area of the search space and to avoid local-optima. In recent years, this
class of algorithms has gained significant attention due to their ability to
produce high-quality incomplete solutions. With the primary goal of further
improving the quality of solutions compared to the state-of-the-art incomplete
DCOP algorithms, we present two new population-based algorithms in this paper.
Our first approach, Anytime Evolutionary DCOP or AED, exploits evolutionary
optimization meta-heuristics to solve DCOPs. We also present a novel anytime
update mechanism that gives AED its anytime property. While in our second
contribution, we show that population-based approaches can be combined with
local search approaches. Specifically, we develop an algorithm called DPSA
based on the Simulated Annealing meta-heuristic. We empirically evaluate these
two algorithms to illustrate their respective effectiveness in different
settings against the state-of-the-art incomplete DCOP algorithms including all
existing population-based algorithms in a wide variety of benchmarks. Our
evaluation shows AED and DPSA markedly outperform the state-of-the-art and
produce up to 75% improved solutions.
