Recurrent distributed constraint satisfaction,virtual constraints,and meta-evolutionary protocols

Abstract

The distributed constraint satisfaction problem (DisCSP) can be viewed as a 4-tuple (X, D, C, A), where X is a set of n variables, D is a set of n domains (one domain for each of the n variables), C is a set of constraints that constrain the values that can be assigned to the n variables, and A is a set of agents for which the variables and constraints are distributed. The objective in solving a DisCSP is to allow the agents in A, through the use of an inter-agent communication protocol, to develop a consistent distributed solution by means of message passing. The constraints are typically considered private and are not allowed to be communicated to fellow agents. A recurrent DisCSP is one in which a subset of constraints ${\mathit{C}}_{\mathit{i}}\subseteq \mathit{C}$ is activated for a give occasion, i. The objective in solving recurrent DisCSPs is to discover solutions that remain valid when the constraints of ${\mathit{C}}_{\mathit{i}}$ are activated.

In this paper, 20 meta-evolutionary protocols are compared. These protocols are referred to as as evolutionary societies of hill-climbers (ESoHCs). The results show that those ESoHCs that use virtual constraints have superior performance to those that do not. The results also show that those ESoHCs which discover multiple solutions per occasion out perform those that discover fewer solutions per occasion.