Crossover Invariant Subsets of the Search Space for Evolutionary Algorithms

This paper addresses the relationship between schemata and crossover operators. In Appendix A a general mathematical framework is developed which reveals an interesting correspondence between the families of reproduction transformations and the corresponding collections of invariant subsets of the search space. On the basis of this mathematical apparatus it is proved that the family of masked crossovers is, for all practical purposes, the largest family of transformations whose corresponding collection of invariant subsets is the family of Antonisse's schemata. In the process, a number of other interesting facts are shown. It is proved that the full dynastic span of a given subset of the search space under either one of the traditional families of crossover transformations (one-point crossovers or masked crossovers) is obtained after [log2n] iterations where n is the dimension of the search space. The generalized notion of invariance introduced in the current paper unifies Radcliffe's notions of "respect" and "gene transmission". Besides providing basic tools for the theoretical analysis carried out in the current paper, the general facts established in Appendix A provide a way to extend Radcliffe's notion of "genetic representation function" to compare various evolutionary computation techniques via their representation.