Crossover invariant subsets of the search space for evolutionary algorithms

Area of Science:

• Evolutionary Computation
• Theoretical Computer Science

Background:

• Schemata and crossover operators are fundamental concepts in evolutionary computation.
• Understanding their relationship is crucial for analyzing algorithm behavior and performance.

Purpose of the Study:

• To establish a mathematical framework connecting schemata and crossover operators.
• To identify the largest family of crossover transformations corresponding to schemata.
• To unify existing notions of invariance in evolutionary computation.

Main Methods:

• Development of a general mathematical framework for reproduction transformations and invariant subsets.
• Proof of the correspondence between masked crossovers and Antonisse's schemata.
• Analysis of the dynastic span of subsets under crossover transformations.

Main Results:

• Masked crossovers are the largest transformation family corresponding to schemata.
• The full dynastic span is achieved in [log2n] iterations for n-dimensional search spaces.
• A generalized notion of invariance unifies Radcliffe's concepts.

Conclusions:

• The mathematical framework provides tools for theoretical analysis of evolutionary algorithms.
• The findings facilitate comparison of different evolutionary computation techniques.
• This work deepens the theoretical understanding of genetic representation and evolutionary processes.