GECCO 2003 - LNCS 2723

Implicit Parallelism

Alden H. Wright¹, Michael D. Vose², and Jonathan E. Rowe³

¹Dept. of Computer Science
University of Montana
Missoula, Montana 59812, USA
wright@cs.umt.edu

²Computer Science Department
University of Tennessee
Knoxville, TN 37996, USA
vose@cs.utk.edu

³School of Computer Science
University of Birmingham
Birmingham B15 2TT, Great Britain
J.E.Rowe@cs.bham.ac.uk

Abstract. 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 -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.

LNCS 2724, p. 1505 ff.

Full article in PDF