Constraint-satisfaction problems
Á. E. Eiben, Zs. M. Ruttkay · 2000
In this section we discuss solving constraint satisfaction problems with evolutionary algorithms. We set up a formal framework by defining the notions free optimization problem, constrained optimization problem and constraint satisfaction problem. We note that constraint satisfaction problems (CSPs) lack an optimization component that is necessary for evolutionary problem solvers. Therefore we discuss different ways of solving CSPs in two stages: applying a suitable problem transformation and solving the transformed problem. C5.7.1 Introduction Applying evolutionary algorithms (EAs) for solving constraint satisfaction problems is interesting from two points of view. On the one hand, since a general CSP is known to be NP-complete (Mackworth 1977), one cannot expect that an effective classical deterministic search algorithm can be forged to solve CSPs. There has been a continuos effort to construct effective algorithms for specific CSPs, and to characterise the difficulty of problem cla...