Parent document is top of "FAQ: comp.ai.genetic part 2/6 (A Guide to Frequently Asked Questions)"
Previous document is "Q1: What are Evolutionary Algorithms (EAs)?"
Next document is "Q1.2: What's Evolutionary Programming (EP)?"

# Q1.1: What's a Genetic Algorithm (GA)?

```     The GENETIC ALGORITHM is a model of machine  learning  which  derives
its  behavior  from a metaphor of some of the mechanisms of EVOLUTION
in nature. This is done  by  the  creation  within  a  machine  of  a
POPULATION  of  INDIVIDUALs  represented by CHROMOSOMEs, in essence a
set of character strings that are analogous to the base-4 chromosomes
that  we  see in our own DNA.  The individuals in the population then
go through a process of simulated "evolution".

Genetic algorithms are used for a  number  of  different  application
areas.  An  example  of  this  would be multidimensional OPTIMIZATION
problems in which the character string of the chromosome can be  used
to encode the values for the different parameters being optimized.

In  practice,  therefore,  we  can  implement  this  genetic model of
computation by having arrays of bits or characters to  represent  the
chromosomes.   Simple   bit   manipulation   operations   allow   the
implementation of CROSSOVER, MUTATION and other operations.  Although
a  substantial  amount  of  research  has been performed on variable-
length strings and  other  structures,  the  majority  of  work  with
genetic  algorithms is focussed on fixed-length character strings. We
should focus on both this aspect of fixed-lengthness and the need  to
encode the representation of the solution being sought as a character
string, since these are  crucial  aspects  that  distinguish  GENETIC
PROGRAMMING,  which  does  not have a fixed length representation and
there is typically no encoding of the problem.

When the genetic algorithm is implemented it is  usually  done  in  a
manner  that  involves  the following cycle:  Evaluate the FITNESS of
all of the individuals in the population.  Create a new population by
performing   operations   such  as  crossover,  fitness-proportionate
REPRODUCTION and mutation on the individuals whose fitness  has  just
been  measured.  Discard the old population and iterate using the new
population.

One iteration of this loop is referred to as a GENERATION.  There  is
no  theoretical  reason for this as an implementation model.  Indeed,
we do not see this punctuated behavior in populations in nature as  a
whole, but it is a convenient implementation model.

The  first  generation  (generation  0) of this process operates on a
population of randomly generated individuals.   From  there  on,  the
genetic  operations,  in concert with the fitness measure, operate to
improve the population.

PSEUDO CODE
Algorithm GA is

t := 0;

// initialize a usually random population of individuals
initpopulation P (t);

// evaluate fitness of all initial individuals of population
evaluate P (t);
// test for termination criterion (time, fitness, etc.)
while not done do

// increase the time counter
t := t + 1;

// select a sub-population for offspring production
P' := selectparents P (t);

// recombine the "genes" of selected parents
recombine P' (t);

// perturb the mated population stochastically
mutate P' (t);

// evaluate it's new fitness
evaluate P' (t);

// select the survivors from actual fitness
P := survive P,P' (t);
od
end GA.
```

Parent document is top of "FAQ: comp.ai.genetic part 2/6 (A Guide to Frequently Asked Questions)"
Previous document is "Q1: What are Evolutionary Algorithms (EAs)?"
Next document is "Q1.2: What's Evolutionary Programming (EP)?"