Parallel Evolutionary Optimization with Constraint Propagation.

A. Ruiz-Andino, L. Araujo, J. J. Ruz, F. Sáez.

This paper describes a parallel model for a distributed memory architecture

of a non traditional evolutionary computation method, which integrates

constraint propagation and evolution programs. This integration provides

a problem-independent optimisation strategy for large scale constrained

combinatorial problems over finite integer domains. We have adopted
a global

parallelisation approach which preserves the advantages of larger populations,

as well as properties, behaviour, and theoretical studies of the sequential

algorithm. Moreover, high speedup is achieved since genetic operators
are

coarse-grained, as they perform a search in a discrete space carrying
out

constraint propagation. A global parallelisation implies a single population

but, as we focus on distributed memory architectures, the single virtual

population is physically distributed among the processors. Selection
and

mating consider all the individuals in the population, but the application

of genetic operators is performed in parallel. The implementation of
the

model has been tested on a CRAY T3E multiprocessor using two complex
constrained

optimisation problems. Experiments have proved the efficiency of this
approach

since linear speedups have been obtained.