Crossover Invariant Subsets of the Search Space for Evolutionary Algorithms

Boris Mitavskiy

Research output: Contribution to journalArticle

10 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)19-46
Number of pages28
JournalEvolutionary Computation
Issue number1
Publication statusPublished - 1 Mar 2004


Dive into the research topics of 'Crossover Invariant Subsets of the Search Space for Evolutionary Algorithms'. Together they form a unique fingerprint.

Cite this