Parent document is top of "FAQ: part 2/6 (A Guide to Frequently Asked Questions)"
Previous document is "Introduction"
Next document is "Q1.1: What's a Genetic Algorithm (GA)?"

Q1: What are Evolutionary Algorithms (EAs)?

     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),
     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 it's 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.

     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.  As it  turns  out,  there  are  mathematical
     proofs  that  indicate  that  the  process  of  fitness proportionate
     reproduction is, in fact, near optimal in some senses.

     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 has 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

     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 it's new fitness
	       evaluate P' (t);

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

Parent document is top of "FAQ: part 2/6 (A Guide to Frequently Asked Questions)"
Previous document is "Introduction"
Next document is "Q1.1: What's a Genetic Algorithm (GA)?"