Implicit Parallelism

posted 2/12/04

Michael D. Vose
Dept. of Computer Science 
University of Tennessee
203 Claxton Complex
1122 Volunteer Blvd.
Knoxville, TN  37996-3450

Alden H. Wright
Computer Science Dept.
Univ. of Montana
Missoula, MT 59812
(406) 243-4790

Jonathan E. Rowe
School of Computer Science
University of Birmingham
Birmingham B15 2TT
Great Britaink


This paper assumes a search space of fixed-length strings, where the size
of the alphabet can vary from position to position.  Structural crossover
is mask-based crossover, and thus includes $n$-point and uniform crossover.
Structural mutation is mutation that commutes with a group operation on
the search space.  This paper shows that structural crossover and mutation
project naturally onto competing families of schemata.  In other words,
the effect of crossover and mutation on a set of string positions can
be specified by considering only what happens at those positions and ignoring
other positions.  However, it is not possible to do this for proportional
selection except when fitness is constant on each schema of the family.
One can write down an equation which includes selection which generalizes
the Holland Schema theorem.  However, like the Schema theorem, this equation
cannot be applied over multiple time steps without keeping track of the
frequency of every string in the search space.