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

Article type: Research Article

Authors: Dozier, Gerry

Affiliations: Department of Computer Science, and Software Engineering, Auburn University, Auburn AL 36849-5347, USA. E-mail: gvdozier@eng.auburn.edu

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 Ci⊆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 Ci 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.

DOI: 10.3233/KES-2005-9103

Journal: International Journal of Knowledge-based and Intelligent Engineering Systems, vol. 9, no. 1, pp. 21-31, 2005