The use of Solver as a basis for the implementation of genetic algorithms offers advantages over what may be considered a more virgin approach. Constraint programming enhances the creation of genetic algorithms in a variety of ways, including, but not limited to:
-
Guarantee of feasibility
In traditional GA systems, genetic operators such as mutation or combination are often quite blind to the constraints of the problem. This can lead to many generated solutions being illegal with respect to the problem constraints. This is normally circumvented in one of two ways. First, by using an
indirect representation. (This will be fully discussed in the next section.) Second, problem constraints are relaxed and their violation penalized.
In contrast to the second method, the use of constraint programming means that constraints have a central role to play and need not be avoided or softened; the constraint programming engine ensures that constraints will not be violated by new solutions that are produced.
-
Initial population generation
Generating an initial population of solutions is an essential part of genetic algorithms. Without constraint programming, often one has to begin with an entirely random population, perhaps softening important constraints in the process.
Using constraint programming, the generation of initial solutions can be performed by the execution of straight-forward constraint programming goals, just as in the standard Solver examples. Goals can be executed repeatedly, each time being differently randomized to result in a population which respects problem constraints. Quality can be traded for diversity by adjusting the amount of randomization applied to the goal. This topic will be more fully described later.
-
Flexibility
Constraint programming carries with it inherent flexibility in the type of operations that can be carried out. One example is that by simple addition of a constraint, it can be stipulated that any new solution generated must be better in quality than the worst member of the population. Such a constraint will be actively used in the genetic operator to restrict the set of solutions examined to those satisfying the aforementioned property. Another example of the flexibility fostered by constraint programming is the ability to mix what may be termed "pure" constraint programming (tree search) with genetic operators. For example, one might fill 3/4 of a new solution with information from parents, allowing the missing 1/4 to be supplied using a more standard tree search. Such techniques typically work well in practice.
PREVIOUS
NEXT