Solving constraint satisfaction problems using hybrid evolutionary search
- 1 April 1998
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Evolutionary Computation
- Vol. 2 (1) , 23-33
- https://doi.org/10.1109/4235.728211
Abstract
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 CSPsKeywords
This publication has 16 references indexed in Scilit:
- Using the knowledge of the constraints network to design an evolutionary algorithm that solves CSPPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Self-adaptivity for constraint satisfaction: learning penalty functionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Solving small and large scale constraint satisfaction problems using a heuristic-based microgenetic algorithmPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Solving constraint satisfaction problems using genetic algorithmsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Evolutionary search guided by the constraint network to solve CSPPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Solving 3-SAT by GAs adapting constraint weightsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Solving randomly generated constraint satisfaction problems using a micro-evolutionary hybrid that evolves a population of hill-climbersPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Graph Coloring with Adaptive Evolutionary AlgorithmsJournal of Heuristics, 1998
- Locating the phase transition in binary constraint satisfaction problemsArtificial Intelligence, 1996
- Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problemsArtificial Intelligence, 1992