We combine the concept of evolutionary search with the systematic search concepts of arc revision and hill climbing to form a hybrid system that quickly finds solutions to static and dynamic constraint satisfaction problems (CSPs). Furthermore, we present the results of two experiments. In the first experiment, we show that our evolutionary hybrid outperforms a well-known hill climber, the iterative descent method (IDM), on a test suite of 750 randomly generated static CSPs. These results show the existence of a "mushy region" which contains a phase transition between CSPs that are based on constraint networks that have one or more solutions and those based on networks that have no solution. In the second experiment, we use a test suite of 250 additional randomly generated CSPs to compare two approaches for solving CSPs. In the first method, all the constraints of a CSP are known by the hybrid at run-time. We refer to this method as the static method for solving CSPs. In the second method, only half of the constraints of a CSPs are known at run-time. Each time that our hybrid system discovers a solution that satisfies all of the constraints of the current network, one additional constraint is added. This process of incrementally adding constraints is continued until all the constraints of a CSP are known by the algorithm or until the maximum number of individuals has been created. We refer to this second method as the dynamic method for solving CSPs. Our results show hybrid evolutionary search performs exceptionally well in the presence of dynamic (incremental) constraints, then also illuminate a potential hazard with solving dynamic CSPs.
展开▼
