01935nas a2200181 4500008004100000022002200041245005700063210005700120260001300177300001600190520140400206653002801610653002901638100001401667700001601681700001601697856004001713 2015 eng d a978030662043594-500aEvolutionary Computation and Constraint Satisfaction0 aEvolutionary Computation and Constraint Satisfaction bSpringer a1271–12843 aIn this chapter we will focus on the combination of evolutionary computation techniques and constraint satisfaction problems. Constraint Programming (CP) is another approach to deal with constraint satisfaction problems. In fact, it is an important prelude to the work covered here as it advocates itself as an alternative approach to programming (Apt). The first step is to formulate a problem as a CSP such that techniques from CP, EC, combinations of the two (c.f., Hybrid) or other approaches can be deployed to solve the problem. The formulation of a problem has an impact on its complexity in terms of effort required to either find a solution or proof no solution exists. It is therefore vital to spend time on getting this right.
Main differences between CP and EC. CP defines search as iterative steps over a search tree where nodes are partial solutions to the problem where not all variables are assigned values. The search then maintain a partial solution that satisfies all variables assigned values. Instead, in EC most often solver sample a space of candidate solutions where variables are all assigned values. None of these candidate solutions will satisfy all constraints in the problem until a solution is found. Another major difference is that many constraint solvers from CP are sound whereas EC solvers are not. A solver is sound if it always finds a solution if it exists.10aconstraint satisfaction10aevolutionary computation1 aHemert, J1 aKacpryk, J.1 aPedrycz, W. uhttp://research.nesc.ac.uk/node/998