(c) Marek Obitko, 1998
As you can see from the genetic algorithm outline, the crossover and mutation are the most important parts 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.
A chromosome should in some way contain information about solution that
it represents. The most used way of encoding is a binary string. A chromosome
then could look like this:
| Chromosome 1 | 1101100100110110 |
| Chromosome 2 | 1101111000011110 |
Each chromosome is represented by a binary string. Each bit in the string can represent some characteristics of the solution. Another possibility is that 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. The encoding 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 proceed to crossover operation. Crossover operates on selected genes from parent chromosomes and creates new offspring. The simplest way how to do that is to choose randomly some crossover point and copy everything before this point from the first parent and then copy everything after the crossover point from the other parent.
Crossover can be illustrated as follows: ( | is the
crossover point):
| 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 quite complicated and depends mainly on the encoding of chromosomes. Specific crossover made for a specific problem can improve performance of the genetic algorithm.
After a crossover is performed, mutation takes place. Mutation is intended to prevent falling
of all solutions in the population into a local optimum of the solved problem. Mutation operation
randomly changes the offspring resulted from crossover. In case of binary encoding we can switch a few
randomly chosen bits from 1 to 0 or from 0 to 1. Mutation can be then illustrated as follows:
| Original offspring 1 | 1101111000011110 |
| Original offspring 2 | 1101100100110110 |
| Mutated offspring 1 | 1100111000011110 |
| Mutated offspring 2 | 1101101100110110 |
The technique of mutation (as well as crossover) depends mainly on the encoding of chromosomes. For example when we are encoding permutations, mutation could be performed as an exchange of two genes.