📂Optimization

What is the inbreeding prevention algorithm in genetic algorithms?

Terminology ¹

In the crossover mixing of genetic algorithms, the technique of measuring the distance or similarity between solutions and preventing overly similar solutions from mating, thereby increasing diversity, is called incest prevention.

Explanation

Allowing repeated crossover among similar solutions in a genetic algorithm is not merely analogous to increasing the probability of hereditary disease in nature; it is effectively the sin of repeatedly wasting computational resources on redundant calculations.

The strong term “incest” is easy to understand in practice: when running a genetic algorithm one can readily observe the emergence of an elite that dominates the entire population, and if that dominance is not checked, most individuals will come to resemble the initial ancestor and generations will pass with little diversity. Empirically, it is almost impossible for such highly similar solutions to obtain monopolistic status by mutation alone; this typically happens because relatives repeatedly mate with each other and the population collapses to a single point.

A canonical example of a prevention algorithm is, in a search space where chromosomes are represented as bits $\left\{ 0, 1 \right\}^{n}$, to allow crossover only when the two solutions are separated by at least a certain distance according to the Hamming distance. For example, suppose three solutions $\mathbf{x}_{1}$, $\mathbf{x}_{2}$, and $\mathbf{x}_{3}$ are given as follows. $$ \begin{align*} \mathbf{x}_{1} =& (0, 1, 0, 1, 1, 0, 0, 1) \\ \mathbf{x}_{2} =& (0, 1, 1, 1, 0, 0, 0, 1) \\ \mathbf{x}_{3} =& (1, 0, 1, 0, 1, 0, 1, 1) \end{align*} $$ If the threshold is 4, then the Hamming distance between $\mathbf{x}_{1}$ and $\mathbf{x}_{2}$ is 3 so their crossover is prohibited, whereas the Hamming distance between $\mathbf{x}_{1}$ and $\mathbf{x}_{3}$ is 5 so their crossover is allowed.