The University of Sussex

The SAGA cross: the mechanics of recombination for species with variable length genotypes

Inman Harvey

Genetic Algorithms (GAs) usually use genotypes of a predetermined fixed length. For these, a recombination operator can trivially select the same crossover point on each parent genotype. In the SAGA (Species Adaptation Genetic Algorithms) paradigm, however, where open-ended evolution allows genotype lengths to increase indefinitely, given a crossover point on one parent it is not immediately obvious where on the other parent the corresponding crossover should be. It is argued that this second crossover should be chosen so as to maximise the similarities between the exchanged segments to the left of the crossover, and also to the right of the crossover. These similarities will in general be close in the genetically converged species characteristic of SAGA. An unambiguous measure can be made of these similarities defined syntactically on the symbols on the genotype, without reference to their interpretation. An efficient algorithm is presented that (given the crossover on one parent) can specify the optimal crossover point or group of points on the second parent.

Download compressed postscript file