96-07-01
The Algebraic Theory of Recombination Spaces
Peter F. Stadler and Guenter P. Wagner
A new mathematical representation is proposed for the
configuration space structure induced by recombination which we
called ``P-structure''. It consists of a mapping of pairs
of objects to the power set of all objects in the search space. The
mapping assigns to each pair of parental ``genotypes'' the set of all
recombinant genotypes obtainable from the parental ones. It is shown that
this construction allows a Fourier-decomposition of fitness landscapes
into a superposition of ``elementary landscapes''. This decomposition is
analogous to the Fourier decomposition of fitness landscapes on mutation
spaces. The elementary landscapes are obtained as eigenfunctions of a
Laplacian operator defined for P-structures. For binary string
recombination the elementary landscapes are exactly the $p$-spin
functions (Walsh functions), i.e. the same as the elementary landscapes
of the string point mutation spaces (i.e. the hypercube). This supports
the notion of a strong homomorphisms between string mutation and
recombination spaces. However, the effective nearest neighbor
correlations on these elementary landscapes differ between mutation and
recombination and among different recombination operators. On average,
the nearest neighbor correlation is higher for one-point recombination
than for uniform recombination. For one-point recombination the
correlations are higher for elementary landscapes with fewer interacting
sites as well as for sites which have closer linkage, confirming the
qualitative predictions of the Schema-Theorem. We conclude that the
algebraic approach to fitness landscape analysis can be extended to
recombination spaces and provides an effective way to analyze the
relative hardness of a landscape for a given recombination operator.
Return to 1996 working papers list.