V. Operators of GA
As you can see from the genetic algorithm outline, the crossover and mutation are the most important part of the genetic algorithm. The performance is influenced mainly by these two operators. Before we can explain more about crossover and mutation, some information about chromosomes will be given.
Encoding of a Chromosome
The chromosome should in some way contain information about solution which
it represents. The most used way of encoding is a binary string. The chromosome
then could look like this:
Each chromosome has one binary string. Each bit in this string can represent some characteristic of the solution. Or the whole string can represent a number - this has been used in the basic GA applet.
Of course, there are many other ways of encoding. This depends mainly on the solved problem. For example, one can encode directly integer or real numbers, sometimes it is useful to encode some permutations and so on.
After we have decided what encoding we will use, we can make a step to crossover. Crossover selects genes from parent chromosomes and creates a new offspring. The simplest way how to do this is to choose randomly some crossover point and everything before this point point copy from a first parent and then everything after a crossover point copy from the second parent.
Crossover can then look like this ( | is the
|Chromosome 1||11011 | 00100110110|
|Chromosome 2||11011 | 11000011110|
|Offspring 1||11011 | 11000011110|
|Offspring 2||11011 | 00100110110|
There are other ways how to make crossover, for example we can choose more crossover points. Crossover can be rather complicated and very depends on encoding of the encoding of chromosome. Specific crossover made for a specific problem can improve performance of the genetic algorithm.
After a crossover is performed, mutation take place. This is to prevent falling
all solutions in population into a local optimum of solved problem. Mutation
changes randomly the new offspring. For binary encoding we can switch a few
randomly chosen bits from 1 to 0 or from 0 to 1. Mutation can then be
|Original offspring 1||1101111000011110|
|Original offspring 2||1101100100110110|
|Mutated offspring 1||1100111000011110|
|Mutated offspring 2||1101101100110110|
The mutation depends on the encoding as well as the crossover. For example when we are encoding permutations, mutation could be exchanging two genes.