A SIMD Environment for Genetic Algorithms with Interconnected Subpopulations

Abstract

The algorithmic form of GAs conforms well to SIMD computing
environments with relatively minor adjustments to the operators.
In this paper we consider in detail a GA implementation
on a MasPar machine.
The question of the degree to which control parameters affecting
intercommunication impact performance is addressed using ANOVA
methods.
The purpose is to supplant anecdotal experience with statistical
evidence.
A set of control parameters—topology, migration operator, migration
radius, and migration probability—were chosen together with four
representative levels of each.
Metrics for three response variables—efficiency, diversity, and
schema propagation—were developed that allowed insight into the behavior under
the various parametric conditions.
These were incorporated into three 4×4×4×4 randomized factorial experiment designs.
Among other things, it was determined that the interconnection
topology is not in itself a significant factor but the extent of
connectivity and frequency of communication are.
An important outcome of this study is that, while the individual
factors are significant, the factors do not interact in unexpected
ways.