📂Optimization

What is crossover mixing in genetic algorithms?

Definition

In genetic algorithms, crossover denotes an operation that mixes features of multiple individuals to produce new solutions.

Description ^{1 2}

In a genetic algorithm, crossover—often shortened to recombination—is a method that mixes the traits of individuals selected by natural selection to generate the individuals of a new offspring generation. It is inspired by the mechanism of sexual reproduction in nature³, and aims to find better solutions through diverse trials even if that means foregoing an exhaustive search of the solution space.

On one hand, since parents that survive selection are likely to carry high-fitness features to pass on; on the other hand, if only elites dominate mating, population diversity can decrease, and crossover helps prevent getting stuck in wasteful computation.

Point crossover

A point crossover selects specific random point(s) in the chromosome that represents a solution and mixes parent traits at those cut points. Choosing a single point is much simpler to implement but can produce offspring biased toward one parent; selecting two points complicates implementation slightly but can yield offspring that are mixed more evenly.

Uniform crossover

In uniform crossover, each gene of the child is taken from the father with probability $p$ and from the mother with probability $1-p$. Typically one sets $p = 0.5$ so that the child inherits traits evenly from both parents. It is easy to implement, unbiased, and faithfully captures the intent of crossover, but it also increases the chance of producing nonsensical solutions.

Intermediate crossover

$$ \mathbf{x} \gets p \mathbf{x}_{a} + (1 - p) \mathbf{x}_{b} $$ If the solution space $X$ is a vector space, and the father and mother solutions are $\mathbf{x}_{a} , \mathbf{x}_{b} \in X$ respectively, one can create a child located roughly at the midpoint between the two solutions as shown above. This is called intermediate crossover.