Next: GA Representation of DFA
Up: GA Representation
Previous: GA Representation
A genetic algorithm GA is a search algorithm that is based on the
natural selection mechanism: namely, survival of the fittest. GA
combines randomized techniques with a guided search strategy. The main
knowledge structures of a GA are strings, that play the role of chromosomes
of nature. Such a string (also called chromosome) constitutes of
several substrings each of which corresponds to a feature of the problem
and occupies a certain place in the string. These substrings are called
genes due to their similarity with the natural counterpart.
The value domain of a certain gene is called the allele of the gene.
In a GA application a population (mostly of fixed size) of chromosomes
is accommodated and until a termination criteria is satisfied iteratively
this population is acted on with the following operators [3].
A genetic algorithm employs three operators that acts on chromosomes:
- A reproduction operator
- copies individual strings to live in the
next generation according
to their objective function values. The objective function is based on
a biological measure of fitness, which is to be maximized. This is how the
natural selection is simulated [1].
- A crossover operator
- uses the population of chromosomes at the current
generation as a `mating pool' from which to select a random pair
of chromosomes and randomly exchange corresponding genes to form
new chromosome(s). This process is exhaustively carried out all over
the pool of chromosomes [5].
- A mutation operator
- is then used to perform a stochastic alternation
of a randomly chosen gene's value. In GA this operator has a low
probability of alternation [2].
Meltem TURHAN
Tue Oct 29 22:25:58 EET 1996