Mutation

Mutation is where an object is randomly and blindly changed, and sent to the next generation.  One might think it blind luck if the mutation survives extinction, but some objects do.  Sometimes the mutations stimulate a population that moves toward the goal in leaps and bounds, other times, the mutation slow road in wrong direction.  Koza, et. al. suggest about 1% of each generation undergo mutation before being sent to the next.

This "1%" idea is one author's suggestion.  The mutation rate should depend on the target problem the GA is being used for.  Mutation rates can be anywhere between 1 in every 10 offspring, or 1 in every 100.  Oftentimes the rate is set to only 1 in 1000.

With each succeeding generation, populations are progressively improved by crossover, copying, mutation and extinction.  Koza, et. al. put it best: "The exploitation of small differences in fitness yields major improvements over many generations in much the same way that a small interest rate yields large growth when compounded over decades."

Demographic separation is a method in genetic programming used to speed up the process of natural selection.  The idea is to run genetic algorithms on separate computers with their own populations of objects.  As the generations of objects get closer to the goal, the separate populations can be mixed together in the same population (on the same computer) and further genetic algorithms can be run.  "Evolution in nature thrives when organisms are distributed in semi-isolated subpopulations..., [and later migrate and mix] so that each gets the benefit of the evolutionary improvement that has occurred elsewhere." 

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 mutation a little more tricky, but nevertheless, experimenters have created all kinds of methods to mutating chromosomes without duplicating genes.

 

Exchange Mutation

Suppose we have a chromosome:

5 3 2 1 7 4 0 6

We simply choose two genes at random (i.e.; 3 and 4) and swap them:

5 4 2 1 7 3 0 6

Easy.

 

Scramble Mutation

Choose two random points (i.e.; positions 4 and 7) and “scramble” the genes located between them:

0 1 2 3 4 5 6 7

becomes:

0 1 2 5 6 3 4 7

 

Displacement Mutation

Select two random points (i.e.; positions 4 and 6), grab the genes between them as a group, then reinsert the group at a random position displaced from the original.

0 1 2 3 4 5 6 7

becomes

0 3 4 5 1 2 6 7

 

Insertion Mutation

This is a very effective mutation and is almost the same as Displacement Mutation, except here only one gene (i.e.; 2) is selected to be displaced and inserted back into the chromosome. In tests, this mutation operator has been shown to be consistently better than any of the alternatives mentioned here.

0 1 2 3 4 5 6 7

Take the 2 out of the sequence,

0 1 3 4 5 6 7

and reinsert the 2 at a randomly chosen position:

0 1 3 4 5 2 6 7

 

Inversion Mutation

This is a very simple mutation operator. Select two random points (i.e.; positions 2 through 5) and reverse the genes between them.

0 1 2 3 4 5 6 7

becomes

0 4 3 2 1 5 6 7

 

Displaced Inversion Mutation

Select two random points (i.e.; positions 5 through 7), reverse the gene order between the two points, and then displace them somewhere along the length of the original chromosome (i.e.; position 2). This is similar to performing Inversion Mutation and then Displacement Mutation using the same start and end points.

0 1 2 3 4 5 6 7

becomes

0 6 5 4 1 2 3 7

 

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