A novel approach for the integration of evolution programs and constraint
solving techniques over finite domains is presented.
This integration provides a problem-independent optimization strategy
for large-scale constrained optimization problems over finite domains.
In this approach, genetic operators are based on an arc-consistency
algorithm, and chromosomes are arc-consistent portions of the search
space of the problem. The paper describes the main issues arising in this
integration: chromosome representation and evaluation, selection and
replacement strategies, and the design of genetic operators.
We also present a parallel execution model for a distributed memory
architecture of the previous integration. We have adopted a global
parallelization approach that preserves the properties, behavior, and
fundamentals of the sequential algorithm. Linear speedup is achieved
since genetic operators are coarse-grained, as they perform a search
in a discrete space carrying out arc-consistency.
The implementation has been tested on a CRAY T3E multiprocessor
using a complex constrained optimization problem.