next up previous
Next: GA Representation of DFA Up: GA Representation Previous: GA Representation

An Overview of GA

  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