Crossover and mutation
Now, let's have a closer look of how the chromosome is manipulated by the GA to get our desired solution. In genetic algorithm, we have operators called crossover and mutation. The operators are acting upon the initial searching space which consists of all resulted solutions (a population) and each solution is represented by a chromosome. The best solution would have the highest fitness value (the fittest will survive from Darwin's theory). Initially, the population may not have the highest fitness member but its offspring are more likely to have one, after a series of operations done by the operators.
Let us assume that we operate on a chromosome which is a bit string data type. Operators are used to manipulate data so that a new offspring can be generated. There are two main types of operators which are explained below.
The first one is crossover. Crossover is a recombination process. There are 2 possible ways to do this, one is single-point crossover, the other one is multi-point crossover, as illustrated in the figure below. Single-point crossover is often used by the applications we have come across. Note that a high crossover rate compared to mutation rate is needed for good yield.1
(a)
(b)
This figure illustrates two examples of two methods for crossover,
(a) for one-piont crossover and (b) for muti-point crossover.
The second one is mutation. It is often done by randomly invert some bits on the string, the effect is that the variation of the genotype is larger hence increase the chance of finding the global maximum. A low mutation rate, which is normally 5 to 7 times less than crossover rate, is needed for good yield.2
some bits of a string are ‘mutated’ from 0s to 1s or vice versa.
flickr - colm.mcmullan
References
1 Santini, C.C., Zebulumi, R., Pacheco, M.A.C., Vellasco, M.R., Szwarcman, M.H.: Evolution of analog circuits on a programmable analog multiplexer array. Aerospace Conference, 2001, IEEE Proceedings (Volume 5) pp. 2301-2308 (2001)
2 Harman, M., Haddow, P. C.: Evolution of fault-tolerant and noise-robust digital designs. IEE Proceedings. Computers and Digital Techniques 151(4) pp. 287-294 (2004)