Recombination (evolutionary algorithm)

In evolutionary algorithms, recombination is the generation of a new genome (also known as a branch genome ) from (usually) two parent genomes (parental genomes). A function that maps a permissible set of parental genomes to a set of subsidiary genomes is called a recombination function. A recombination function is a genetic operator .

The aim of recombination is to transfer the good qualities of two different parents to one child. Compared to algorithms that only use the mutation to change the genome, individuals with two good qualities A and B can possibly be found more quickly if there were previously only individuals who only had either A or B.

Good recombination functions are characterized by the fact that they at least retain the good properties of the parents and do not recombine in such a way that these properties are destroyed.

Different recombination types are differently suitable for different genome and problem types:

Recombination of binary numbers (bit strings)

When recombining binary numbers, the parental genomes are subdivided at one or more places and the subsidiary genome is assembled from these parts.

An example is the recombination of two parent genomes, which are divided in two places:

Procedure	example
Two binary numbers are given.	${\ displaystyle P_ {0} = \ left (0,1,1,0,0,1,0 \ right)}$ and ${\ displaystyle P_ {1} = \ left (1,0,0,0,1,0,0 \ right)}$
Now randomly choose two indices by which the genomes are divided.	${\ displaystyle s_ {1} = 3}$ , , ${\ displaystyle s_ {2} = 6}$
For the child genome, all positions between and are taken from, while all remaining positions are taken from. ${\ displaystyle P_ {1}}$ ${\ displaystyle s_ {1}}$ ${\ displaystyle s_ {2}}$ ${\ displaystyle P_ {0}}$	${\ displaystyle P_ {C} = \ left (0,1, {\ underline {0,0,1,0}}, 0 \ right)}$

Recombination of Permutations

The recombination of permutations is specially designed for genomes that are themselves permutations of a set .

An example of a recombination of permutations is the following procedure:

Procedure	example
Given 2 permutations of the same set	${\ displaystyle P_ {0} = \ left (A, B, C, D, E, F, G \ right)}$ and ${\ displaystyle P_ {1} = \ left (E, {\ underline {B}}, G, A, {\ underline {F}}, D, {\ underline {C}} \ right)}$
as well as a random selection of which places should be taken over directly from the first permutation.	${\ displaystyle S = \ left (1,0,0,1,1,0,1 \ right)}$
As a child permutation, a permutation is generated that is copied from wherever one has. ${\ displaystyle P_ {0}}$ ${\ displaystyle S}$ ${\ displaystyle 1}$	${\ displaystyle P_ {C} = \ left (A,?,?, D, E,?, G \ right)}$
The positions that were not taken over by are now also taken over, but in the order in which they appear in . ${\ displaystyle P_ {0}}$ ${\ displaystyle P_ {1}}$	${\ displaystyle P_ {not yet taken over} = \ left \ {B, C, F \ right \}}$ ${\ displaystyle P_ {in sequence of P_ {1}} = \ left (B, F, C \ right)}$
This results in the finished child genome.	${\ displaystyle P_ {C} = \ left (A, {\ underline {B}}, {\ underline {F}}, D, E, {\ underline {C}}, G \ right)}$

One can create a second (somewhat inverse) child in this way by inverting the list and applying the procedure again. ${\ displaystyle S}$

Edge recombination

Another variant of the recombination of permutations is the edge recombination, in which the neighborhood relationships between the elements of the parent genomes are preserved as well as possible. In Edge-2 recombination, preference is given to compounds that occur in both parent genomes. The Edge-3 and Edge-4 recombination also try, by inversion of the genomes, to exploit additional neighborhoods that were lost in the Edge-2 recombination. This method is particularly well suited for combinatorial optimization problems such as the traveling salesman problem .

Recombination of trees

The recombination of trees is specifically designed for genomes that are themselves trees .

An example of a recombination of trees is the following procedure:

Two parent trees (parent genomes) are given.
Select a subtree in each parent tree.
Swap these two subtrees.

The two newly created trees are now the two child genomes.

literature

Hartmut Pohlheim : Evolutionary Algorithms. Procedures, operators and tips for practice. Springer, Berlin 1999, ISBN 3540664130 .
Karsten Weicker : Evolutionary Algorithms. Teubner, Stuttgart 2002, ISBN 3519003627 .