Genetic Algorithm Techniques - The Theory, Continued
(Page 3 of 4 )
Mutation is interesting. It is required after each crossover recombination because it prevents the solutions from converging towards local optima/extreme. In a nutshell, mutation changes a few bits of the resulting binary strings (the offspring chromosome right after the crossover was applied). Check out the following example.
Child #1: 1101000
Child #2: 1010111
=========================
Mutated #1: 1001010
Mutated #2: 1011111
From the above you can see that mutation occurs randomly. You should be careful because mutation must occur (thus, its probability cannot be 0%) otherwise you'd fall towards the local extreme. But it cannot happen to all bits either, because that means each of the bits becomes inverted, thus no mutation in fact happens because practically inversion happens instead. Don't abuse mutation!
The final concepts we need to talk about are the fitness function and the selection function. The fitness assignment in short means that a scalar value will relate to the fitness of each chromosome from the population. The more fit a chromosome is, chances are the more it can contribute towards the best solution (better candidate). This is again problem-dependent. But the fitness function checks the quality of the chromosomes.
Selection can happen based on many theories. Often the so-called "Roulette wheel" is used but there are alternatives. It works like this: fitness of the entire population is represented on a "roulette wheel" (pie chart), and every chromosome gets a slice -- the more fit the chromosome, the bigger the slice it receives. Now the chromosomes are "picked" randomly by spinning the wheel. As you can see, the chances are you will pick from the bigger slices given to the fitter chromosomes.
Another selection technique that we must introduce is called elitism. It also derives from evolutionary biology. In short, it means that the best chromosome survives. Here's how this applies: we make at least one copy of the best chromosome(s) and do our best to propagate them towards further population generations.
The importance of elitism is explained in the following: convergence is guaranteed. Why? Well, let's assume a global optimum is found. This will be yielded from the best individuals (candidates), meaning that thanks to elitism, further solutions will also converge to the aforementioned optimum. But be careful! The probability of conversion to any local optima is also higher due to the exact same characteristics.
Nonetheless, there are many more selection schemes. Let's name a few others: rank selection (each chromosome receives a rank based on its fitness), tournament selection (within each sub-set of candidates each chromosome "races" other chromosomes, but only one can win, meaning it earns selection), hierarchical selection, stochastic remainder sampling, generation selection, scaling selection, and so forth. Each has its benefits.
As an implementation example please check out the pseudo code algorithm below.
Procedure Genetic_algorithm()
Initialize_population P;
Fitness_evaluate P;
While NOT solution do
P' = Selection P;
Crossover P';
Mutate P';
Fitness_evaluate P';
P = Selection between P and P';
End while
End procedure
Next: Concluding Thoughts >>
More Development Cycles Articles
More By Barzan "Tony" Antal
