Genetic Algorithms
               By
     Tersia Gowases an Lukasa Rakozzy
 

Contents
-	History
-	General Idea
-	Operations of Genetic Algoithms
-	Observations
-	Working examples
-	Genetic algorithms and expert systems
-	References



                                                     History:


Genetic algorithms orginated from the studies of cellular automata
conducted by John Holland and his collegues at the University of
Michigan in the mid 1970s

Genetic algorithms research remained mostly theortical until the mid
1980s, but interest grew with an increase in desktop computation

In 1989 John Markoff wrote the Evolver, the first commercially
avaliable desktop genetic algorithim




                                                   General Idea:


Genetic algorithms are an evolutionary technique that use cross-over
and mutation operations to solve optimization problems using the
survival of the fittest principle

In nature the fittest individuals are more likely to survive and mate;
therefore the next generation should be fitter and healthier because
they were bred form healthy parents

The same idea is applied to a concept by first guessing solutions and
then combining the fittest solutions to create a new generations of
solutions which should be better than the previous generation

Therefore one can define genetic algorithms as a programming technique
that mimics biological evolution as a problem ~V solving strategy

                                       

                                           Operations of Genetic Algorithms:


The genetic algorithm process consists of the following steps:
-	Encoding
-	Evaluation
-	Crossover
-	Mutation

Example: Maximize the following: f  = - 2x2 + 4x ~V 5  
Over the integers {0,1,2,~E,15}; maximized when x=1




1. Encoding

Encoding involves finding the most suitable representation for each
unique solution

There are various methods of encoding:
-	Binary encoding
-	Pre-mutational encoding
-	Value encoding
-	Tree encoding

Example: 12   =  1100  |   7   =  0111



2. Evaluation

A metric called the fitness function is used to quantitatively
evaluate each encoded solution

There are various methods of evaluation:

-    Elitist selection
-    Generation selection
-    Tournament selection
-    Fitness proportionate selection
-    Roulette wheel selection
-    Hierarchal selection

Example: f  = - 2x2 + 4x ~V 5 ; is our evaluating function
f(7) = -71     |    f(12) = -241



3. Crossover

Crossover is where two individuals are selected and segments of there
code are swapped in order to produce an artificial offspring, that are
combinations of their parents

Example:
V1 =   12=   1100    à   11 | 00
V2 =     7=   0111    à   01 | 11
V1~R     =       1111
V2~R     =       0100



4. Mutation

Mutation in living organinism is acheived by changing one gene

Simularly, mutation in genetic algorithms is acheived by making small
alterations in an individual~Rs code

Example:
V2 =   7 =   0111    
V2~R        =   0101



                                              Observations:


Proper fitness function prevents finding local optima instead of global optima
GAs can rapidly locate good solutions
GAs are not the best solution for all optimization problems
      -    Other solutions are faster or more optimal
      -    GAs can not be used if there is no way to define fitness function


 

                                           GA and Exert systems

-    Acoustics
-    Aerospace Engineering
-    Astronomy and astrophysics
-    Chemistry
-    Electrical engineering
-    Game playing
-    Geophysics
-    Materials Engineering
-    Mathematics and algorithmic
-    Military and law enforcement
-    Molecular biology
-    Pattern recognition and data mining
-    Robotics
-    Routing and scheduling 
-    Systems engineering



                                                References:

-	http://www.talkorigins.org/faqs/genalg/genalg.html
-	http://www.estec.esa.nl/outreach/gatutor/contents.htm
-       http://www.math.hmc.edu/seniorthesis/archives/2001/kbryant/
kbryant-2001-thesis.pdf
-	http://mcld.co.uk/evolutionarysound/
-	http://mzlabs.com/gart/g4.html