Algebraic theory of recombination spaces

Area of Science:

• Computational intelligence
• Mathematical optimization
• Evolutionary computation

Background:

• Understanding fitness landscapes is crucial for evolutionary algorithms.
• Existing analysis often focuses on mutation, with recombination less mathematically characterized.
• A unified framework for analyzing both mutation and recombination is needed.

Purpose of the Study:

• To introduce a novel mathematical representation, P-structure, for recombination.
• To analyze fitness landscapes using Fourier decomposition within this P-structure framework.
• To compare landscape properties induced by recombination with those induced by mutation.

Main Methods:

• Developed a P-structure mapping genotypes to recombinant sets.
• Applied Fourier decomposition to fitness landscapes on P-structures.
• Defined a Laplacian operator for P-structures and identified its eigenfunctions (elementary landscapes).
• Analyzed binary string recombination and compared with mutation spaces (hypercube).

Main Results:

• P-structure allows fitness landscape decomposition into elementary landscapes, analogous to mutation spaces.
• For binary strings, recombination elementary landscapes (p-spin/Walsh functions) match mutation elementary landscapes.
• Nearest neighbor correlations on elementary landscapes differ between mutation and recombination, and across recombination operators.
• One-point recombination shows higher correlations than uniform recombination, especially for tightly linked sites.

Conclusions:

• The algebraic approach effectively extends to recombination spaces.
• P-structure provides a powerful tool for analyzing fitness landscapes under recombination.
• This framework helps understand the relative difficulty of landscapes for specific recombination operators.