Genetic Algorithms, or GA
s implement efficient mechanisms to search what in mathematical terms are called a solution space
. This family of algorithms adopt several terms from biology, and hence the use of the term Genetic
. They are quite easy to understand and explain.
A typical GA will employ several distinct module
s to achieve it's goal
of searching a large - and possibly highly disparate
- solution space. They are presented
in roughly the sequential order of execution during a GA simulation.
. The purpose of this function is to consider all existing solutions, to determine if an optimal solution has been found within a precision programmed
by the GA creator. It also will determine if the function has failed to converge
, and abort
further processing if necessary.
If this is the case, a GA will present the best solution found to date in the simulation
. Sometimes referred to in the literature
as the God function
The Grim Reaper
: this function is responsbile for examining the existing solutions, and removing those which manifest the lowest score. The biological equivalent of survival of the fittest
. This function takes a subset of the existing solutions, and intermingles portions of their values into new solutions. This is probably best explained with an example.
Consider we have a function of three variables
, f(x,y,z). We also have two candidate
solutions, f(1,2,9) and f(-3,6,3). The breeder would construct a new candiate solution, for example, f(1,6,9), employing the DNA (continuing the use biological metaphors)
of each. This clearly a new solution that is a descendant
of the two parent
solutions. Keep in mind that both parent solutions were considered optimal, and therefore any child
solutions should be at least as good, and possbily better, than them (another biological metaphor)
The real strength of GA's lies in the next function: the mutant
function. This module takes a small subset of existing solutions, and random
ly changes their values (once again, DNA to use the biological metaphor)
). The purpose of the mutation function is to insure that the GA does NOT
get locked in a local region of the solution space.
In other words, the mutation function insures that a degree of randomness is introduced into the searching - and hence the possible solutions - evaluated by the GA.
Processing now continues at the first processing step, the evaluator.