Genetic Algorithms for Dynamic Variable Ordering in Constraint Satisfaction Problems
Hugo Terashima‐Marín, R. de la Calleja Manzanedo, Manuel Valenzuela Rendón · Research in Computing Science · 2005
A Constraint Satisfaction Problem (CSP) can be stated as follows: we are given a set of variables, a finite and discrete domain for each variable, and a set of constraints defined over the values that each variable can simultaneously take. The objective is to find a consistent assignment of values to variables in such a way that all constraints are satisfied. To do this, a deterministic algorithm can be used. However, the order in which the variables are considered in the search process has a direct impact in the efficiency of the algorithm. Various heuristics have been proposed to determine a convenient order, which are usually divided in two types: static and dynamic. This investigation in particular uses Genetic Algorithms as a heuristic to determine the dynamic variable ordering during the search. The GA is coupled with a conventional CSP solving method. Results show that the approach is efficient when tested with a wide range of randomly generated problems