Distributed constraint satisfaction, restricted recombination, and genetic protocols

In this paper, we present four genetic protocols for solving randomly generated distributed constraint satisfaction problems. These genetic protocols are based on an evolutionary paradigm known as a society of hill-climbers (SoHC) and are thus referred to as genetic SoHCs (GSoHCs). The difference between the SoHC and the GSoHCs is that each of the GSoHCs use a distributed restricted recombination operator. We compare the SoHC and GSoHC protocols on a test suite of 400 randomly generated distributed constraint satisfaction problems (DisCSPs) that are composed of asymmetric constraints (referred to as DisACSPs). In a second experiment, we compare the best performing GSoHC and the SoHC on an additional 1100 randomly generated DisACSPs in order to compare their performances across the phase transition. Our results show that all of the GSoHCs dramatically outperform the SoHC protocol even at the phase transition where, on average, the most difficult DisACSPs reside.