Genetic Algorithms: Crossover
Crossover is a genetic
operator that combines (mates) two chromosomes (parents)
to produce a new chromosome (offspring). The idea behind
crossover is that the new chromosome may be better than
both of the parents if it takes the best characteristics
from each of the parents. Crossover occurs during
evolution according to a user-definable crossover
probability.
Genetic
Server and Genetic Library
include the following types of crossover:
One Point
A crossover operator that randomly selects a crossover
point within a chromosome then interchanges the two
parent chromosomes at this point to produce two new
offspring.
Consider the following 2 parents which have been selected
for crossover. The “|” symbol indicates the
randomly chosen crossover point.
Parent 1: 11001|010
Parent 2: 00100|111
After interchanging the parent chromosomes at the
crossover point, the following offspring are produced:
Offspring1: 11001|111
Offspring2: 00100|010
Two Point
A crossover operator that randomly selects two crossover
points within a chromosome then interchanges the two
parent chromosomes between these points to produce two
new offspring.
Consider the following 2 parents which have been selected
for crossover. The “|” symbols indicate the
randomly chosen crossover points.
Parent 1: 110|010|10
Parent 2: 001|001|11
After interchanging the parent chromosomes between the
crossover points, the following offspring are produced:
Offspring1: 110|001|10
Offspring2: 001|010|11
Uniform
A crossover operator that decides (with some probability
– know as the mixing ratio) which parent will
contribute each of the gene values in the offspring
chromosomes. This allows the parent chromosomes to be
mixed at the gene level rather than the segment level (as
with one and two point crossover). For some problems,
this additional flexibility outweighs the disadvantage of
destroying building blocks.
Consider the following 2 parents which have been selected
for crossover:
Parent 1: 11001010
Parent 2: 00100111
If the mixing ratio is 0.5, approximately half of the
genes in the offspring will come from parent 1 and the
other half will come from parent 2. Below is a possible
set of offspring after uniform crossover:
Offspring1:
Offspring2: |
 |
Note: The subscripts indicate which
parent the gene came from.
Arithmetic
A crossover operator that linearly combines two parent
chromosome vectors to produce two new offspring according
to the following equations:
Offspring1 = a * Parent1 + (1- a) * Parent2
Offspring2 = (1 – a) * Parent1 + a
* Parent2
where a is a random weighting factor (chosen before each
crossover operation).
Consider the following 2 parents (each consisting of 4
float genes) which have been selected for crossover:
Parent 1: (0.3)(1.4)(0.2)(7.4)
Parent 2: (0.5)(4.5)(0.1)(5.6)
If a = 0.7, the following two offspring would be
produced:
Offspring1: (0.36)(2.33)(0.17)(6.86)
Offspring2: (0.402)(2.981)(0.149)(6.842)
Heuristic
A crossover operator that uses the fitness
values of the two parent chromosomes to determine the
direction of the search. The offspring are created
according to the following equations:
Offspring1 = BestParent + r * (BestParent
– WorstParent)
Offspring2 = BestParent
where r is a random number between 0 and 1.
It is possible that Offspring1 will not be feasible. This
can happen if r is chosen such that one or more of its
genes fall outside of the allowable upper or lower
bounds. For this reason, heuristic crossover has a user
settable parameter (n) for the number of times to try and
find an r that results in a feasible chromosome. If a
feasible chromosome is not produced after n tries, the
WorstParent is returned as Offspring1.
