by van Hemert, J
Abstract:
In 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.
Reference:
Evolutionary Computation and Constraint Satisfaction (van Hemert, J), Chapter in Handbook of Computational Intelligence (Kacpryk, J, Pedrycz, W, eds.), Springer, 2015.
Bibtex Entry:
@incollection{ComputationalIntelligence2015,
_day = {27},
abstract = {In 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.},
author = {van Hemert, J},
booktitle = {Handbook of Computational Intelligence},
chapter = {65},
doi = {10.1007/978-3-662-43505-2},
editor = {Kacpryk, J and Pedrycz, W},
isbn = {978030662043594-5},
keywords = {constraint satisfaction; evolutionary computation},
pages = {1271--84},
publisher = {Springer},
title = {Evolutionary Computation and Constraint Satisfaction},
year = {2015},
bdsk-url-1 = {http://dx.doi.org/10.1007/978-3-662-43505-2}}