"And just to make it interesting ..."
Principal Investigator
Peter Stadler
Abstract
Fitness landscapes are an important concept in molecular evolution. Many important examples of landscapes in physics and combinatorial optimization, which are widely used as model landscapes in simulations of molecular evolution and adaptation, are ``elementary'', i.e., they are (up to an additive constant) eigenfunctions of a graph Laplacian. The underlying graph itself is introduced in a natural way by a move set (mutation operator, search strategy) on the set of possible configurations or genes.
Using the Fourier decomposition determined by the graph it is possible to shown that elementary landscapes are characterized by their correlation functions. The correlation functions are in turn uniquely determined by the geometry of the underlying configuration space and the nearest neighbor correlation of the elementary landscape.
Eigenfunctions of Laplacian operators play an important role in the study if Riemannian manifolds in differential geometry. Indeed, fundamental results such as the maximum principle and Courant's Nodal Domain Theorem are valid for elementary landscapes on graphs. The search for further analogies is a promising avenue for future reseach on landscapes.
A similar approach, based again on algebraic graph theory, can be applied to recombination-like search, too. 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. This construction again allows a Fourier-decomposition of fitness landscapes into a superposition of ``elementary landscapes'' which are eigenfunctions of P-structure Laplacian. 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). It is likely that this approach will lead to a more profound understanding of the dynamics of schemata in genetic algorithms.