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 Rk(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.