Search the FAQ Archives

3 - A - B - C - D - E - F - G - H - I - J - K - L - M
N - O - P - Q - R - S - T - U - V - W - X - Y - Z
faqs.org - Internet FAQ Archives

FAQ: comp.ai.genetic part 2/6 (A Guide to Frequently Asked Questions)
Section - Q1.1: What's a Genetic Algorithm (GA)?

( Part1 - Part2 - Part3 - Part4 - Part5 - Part6 - Single Page )
[ Usenet FAQs | Web FAQs | Documents | RFC Index | Houses ]


Top Document: FAQ: comp.ai.genetic part 2/6 (A Guide to Frequently Asked Questions)
Previous Document: Q1: What are Evolutionary Algorithms (EAs)?
Next Document: Q1.2: What's Evolutionary Programming (EP)?
See reader questions & answers on this topic! - Help others by sharing your knowledge
     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

	  // start with an initial time
	  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 its new fitness
	       evaluate P' (t);

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

User Contributions:

Comment about this article, ask questions, or add new information about this topic:

CAPTCHA




Top Document: FAQ: comp.ai.genetic part 2/6 (A Guide to Frequently Asked Questions)
Previous Document: Q1: What are Evolutionary Algorithms (EAs)?
Next Document: Q1.2: What's Evolutionary Programming (EP)?

Part1 - Part2 - Part3 - Part4 - Part5 - Part6 - Single Page

[ Usenet FAQs | Web FAQs | Documents | RFC Index ]

Send corrections/additions to the FAQ Maintainer:
David.Beasley@cs.cf.ac.uk (David Beasley)





Last Update March 27 2014 @ 02:11 PM