Recombination

Recombination is the process of constructing new chromosomes from specific segments of two selected parent chromosomes.  There are a wide variety of methods used, all of which depend on the problem which you're trying to solve.

The most common type of recombination involves making two new chromosomes from the sequences of two selected parents.  This is done by choosing a point in the two parent sequences, copying each gene up to the point, then swapping all the remaining genes.  For instance, if the chosen point splits the parents in half, then the first half of Parent A is joined to the latter half of Parent B, while the first half of Parent B is joined to the latter half of Parent A.  This creates two new offspring with the varying features of both parents.

Figure 1.  A point is chosen in the two parent chromosomes above (between the 7th and 8th genes), and copied for the offspring.  After the chosen point, the remaining genes of the parents are swapped and joined to the opposite offspring.

Although not quite as common, recombination can also be used to create only one offspring:

In some genetic algorithms, chromosomes are made of sequences which cannot have duplicate digits.  For example, a chromosome cannot have multiple 3's, or multiple 7's, or duplicate instances of any number.  This makes recombination a little more tricky, but nevertheless, experimenters have created all kinds of methods to recombining chromosomes without duplicating genes.

 

Crossover

Crossover is like sexual reproduction, mating surviving objects to creating new objects for the next generation.  Not every combination is successful in surviving in the successive generations, but many do.   Typically, the greatest numbers of combinations to go extinct occur in the beginning when the program is first run.

The genetic algorithm would select those offspring that are closer to matching the goal for the next generation, and leave the rest for extinction.

Some authors suggest that any two chromosomes selected for crossover should only be allowed a 70% chance of successfully doing so.  That means the odds are 7 in 10 that any two parents will create offspring for the next generation.

The underlying idea to explain crossover performance is that the good fitness of the parents is somehow due to precise parts of their genetic material (termed building blocks), and the recombining of those building blocks will result in an increase in fitness.

Nevertheless, there are numerous other ways to perform crossover. For instance, crossing over two vectors of floating-points values can be done by linear combination (with uniformly drawn weights) of the parents values. The idea is that information pertaining to the problem at hand should be somehow exchanged.

 

Partially-Mapped Crossover

Suppose we've selected two parent chromosomes:

Parent1: 2 5 0 3 61 4 7

Parent2: 3 4 0 7 25 1 6

In this example, we're saying that the 3 in Parent1 is mapped to the 7 in Parent2 (in red).  The 6 in Parent1 is mapped to the 2 in Parent2 (in blue).  The 1 in Parent1 is mapped to 5 in Parent2 (in pink).  Then, in three steps, we can create new offspring:

Step 1 [swap 3 and 7]

Child1: 2 5 0 7 6 1 4 3

Child2: 7 4 0 3 2 5 1 6

Step 2 [swap 6 and 2]

Child1: 6 5 0 7 2 1 4 3

Child2: 7 4 0 3 6 5 1 2

Step 3 [swap 1 and 5]

Child1: 6 1 0 7 2 5 4 3

Child2: 7 4 0 3 6 1 5 2

This creates two new chromosomes from the two parents:

Parent1: 2 5 0 3 6 1 4 7

Parent2: 3 4 0 7 2 5 1 6

Child1: 6 1 0 7 2 5 4 3

Child2: 7 4 0 3 6 1 5 2

 

Order-Based Crossover

To perform order-based crossover, several genes are chosen at random from one parent and then the order of those genes is imposed on the respective genes in the other parent.  For example:

Parent1: 2 5 0 3 6 1 4 7

The genes in bold red are the genes which have been chosen at random. Now, impose the order--5, 0, then 1--on the same genes in Parent2 to give Offspring1 like so:

Parent2: 3 4 0 7 2 5 1 6

Offspring1: 3 4 5 7 2 0 1 6

The gene numbered "1" stayed in the same place because it was already positioned in the correct order.

Now the same sequence of actions is performed on the other parent. Using the same random positions as the first,

Parent2: 3 4 0 7 2 5 1 6

Impose the order--4, 0, and 5--on the same genes in Parent1 to give Offspring2 like so:

Parent1: 2 5 0 3 6 1 4 7

Offspring2: 24 0 3 6 1 5 7

This time, the gene numbered "0" stayed in the same place because it was already positioned in the correct order.

 

Position-Based Crossover

This is similar to Order-Based Crossover, but instead of imposing the order of the genes, this operator imposes the position. So, using the same example parents and random positions, here's how to do it.

Parent1: 2 5 0 3 6 1 4 7

Parent2: 3 4 0 7 2 5 1 6

First, swap over the selected genes from Parent1 to Offspring1, keeping them in the same position.

OffSpring1: _ 5 0 _ _ 1 _ _

Now, from left to right, iterate through Parent2's genes and fill in the blanks if that gene number has not already appeared. In this example, filling in the blanks results in:

Offspring1: 3 5 0 4 7 1 2 6

Then we work on Offspring2:

Offspring2: _ 4 0 _ _ 5 _ _

This time, from left to right, iterate through Parent1’s genes and fill in the blanks if that gene number has not already appeared.

Offspring2: 2 4 0 3 6 5 1 7

 

public void footer() {
About | Contact | Privacy Policy | Terms of Service | Site Map
Copyright© 2009-2012 John McCullock. All Rights Reserved.
}