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: What are Evolutionary Algorithms (EAs)?

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


Top Document: FAQ: comp.ai.genetic part 2/6 (A Guide to Frequently Asked Questions)
Previous Document: News Headers
Next Document: Q1.1: What's a Genetic Algorithm (GA)?
See reader questions & answers on this topic! - Help others by sharing your knowledge
     Evolutionary algorithm is an umbrella term used to describe computer-
     based problem solving systems which use computational models of  some
     of  the known mechanisms of EVOLUTION as key elements in their design
     and implementation. A variety of EVOLUTIONARY  ALGORITHMs  have  been
     proposed.   The  major  ones  are:  GENETIC  ALGORITHMs  (see  Q1.1),
     EVOLUTIONARY PROGRAMMING (see Q1.2), EVOLUTION STRATEGIEs (see Q1.3),
     CLASSIFIER  SYSTEMs  (see  Q1.4), and GENETIC PROGRAMMING (see Q1.5).
     They all share a common conceptual base of simulating  the  evolution
     of  INDIVIDUAL  structures  via processes of SELECTION, MUTATION, and
     REPRODUCTION.  The processes depend on the perceived  PERFORMANCE  of
     the individual structures as defined by an ENVIRONMENT.

     More  precisely, EAs maintain a POPULATION of structures, that evolve
     according to  rules  of  selection  and  other  operators,  that  are
     referred  to  as  "search operators", (or GENETIC OPERATORs), such as
     RECOMBINATION  and  mutation.  Each  individual  in  the   population
     receives  a  measure  of its FITNESS in the environment. Reproduction
     focuses attention on high fitness individuals, thus  exploiting  (cf.
     EXPLOITATION)  the  available fitness information.  Recombination and
     mutation perturb those individuals, providing general heuristics  for
     EXPLORATION.  Although simplistic from a biologist's viewpoint, these
     algorithms are sufficiently complex to provide  robust  and  powerful
     adaptive search mechanisms.

     --- "An Overview of Evolutionary Computation" [ECML93], 442-459.

 BIOLOGICAL BASIS
     To  understand  EAs, it is necessary to have some appreciation of the
     biological processes on which they are based.

     Firstly, we should note that EVOLUTION (in nature or  anywhere  else)
     is  not  a  purposive  or  directed  process.   That  is, there is no
     evidence to support the assertion that the goal of  evolution  is  to
     produce Mankind. Indeed, the processes of nature seem to boil down to
     a haphazard GENERATION of biologically diverse  organisms.   Some  of
     evolution is determined by natural SELECTION or different INDIVIDUALs
     competing for resources in the ENVIRONMENT.   Some  are  better  than
     others.  Those  that  are  better  are  more  likely  to  survive and
     propagate their genetic material.

     In nature, we see that the encoding for genetic information  (GENOME)
     is   done  in  a  way  that  admits  asexual  REPRODUCTION.   Asexual
     reproduction typically results  in  OFFSPRING  that  are  genetically
     identical  to  the  PARENT.   (Large  numbers  of organisms reproduce
     asexually; this includes most bacteria which some biologists hold  to
     be the most successful SPECIES known.)

     Sexual  reproduction  allows  some shuffing of CHROMOSOMEs, producing
     offspring that contain a combination of information from each parent.
     At  the  molecular level what occurs (wild oversimplification alert!)
     is that a pair of almost identical chromosomes bump into one another,
     exchange  chunks  of genetic information and drift apart. This is the
     RECOMBINATION operation, which is  often  referred  to  as  CROSSOVER
     because   of  the  way  that  biologists  have  observed  strands  of
     chromosomes crossing over during the exchange.

     Recombination happens in an environment where the  selection  of  who
     gets  to mate is largely a function of the FITNESS of the individual,
     i.e. how good the individual is at competing in its environment. Some
     "luck" (random effect) is usually involved too. Some EAs use a simple
     function   of   the   fitness   measure   to    select    individuals
     (probabilistically)  to  undergo genetic operations such as crossover
     or  asexual  reproduction  (the  propagation  of   genetic   material
     unaltered).    This   is   fitness-proportionate   selection.   Other
     implementations use  a  model  in  which  certain  randomly  selected
     individuals  in  a subgroup compete and the fittest is selected. This
     is called tournament selection and is the form of selection we see in
     nature  when stags rut to vie for the privilege of mating with a herd
     of hinds.

     Much EA research  has  assumed  that  the  two  processes  that  most
     contribute   to   evolution   are   crossover   and   fitness   based
     selection/reproduction.    Evolution,   by   definition,   absolutely
     requires  diversity in order to work.  In nature, an important source
     of diversity is MUTATION.  In an EA, a large amount of  diversity  is
     usually  introduced at the start of the algorithm, by randomising the
     GENEs  in  the  POPULATION.   The  importance  of   mutation,   which
     introduces   further   diversity  while  the  algorithm  is  running,
     therefore continues to be a matter of debate. Some refer to it  as  a
     background  operator, simply replacing some of the original diversity
     which may have been  lost,  while  others  view  it  as  playing  the
     dominant role in the evolutionary process.

     It cannot be stressed too strongly that an EVOLUTIONARY ALGORITHM (as
     a SIMULATION of a genetic process) is  not  a  random  search  for  a
     solution  to  a  problem (highly fit individual).  EAs use stochastic
     processes, but the  result  is  distinctly  non-random  (better  than
     random).

 PSEUDO CODE
     Algorithm EA is

	  // start with an initial time
	  t := 0;

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

	  // evaluate fitness of all initial individuals in population
	  evaluate P (t);

	  // test for termination criterion (time, fitness, etc.)
	  while not done do

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

	       // select 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 EA.

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: News Headers
Next Document: Q1.1: What's a Genetic Algorithm (GA)?

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