Transit sets of two-point crossover

Abstract

Genetic Algorithms typically invoke crossover operators to produce offsprings that are a “mixture” of two parents x and y. On strings, k-point crossover breaks parental genotypes at at most k corresponding positions and concatenates alternating fragments for the two parents. The transit set R_k(x, y) comprises all offsprings of this form. It forms the tope set of an uniform oriented matroid with Vapnik-Chervonenkis dimension k + 1. The Topological Representation Theorem for oriented matroids thus implies a representation in terms of pseudosphere arrangements. This makes it possible to study 2-point crossover in detail and to characterize the partial cubes defined by the transit sets of two-point crossover.