Just think of an OPTIMIZATION problem as a black box.  A large  black
     box.  As  large as, for example, a Coca-Cola vending machine. Now, we
     don't know anything about the inner workings of this  box,  but  see,
     that  there  are some regulators to play with, and of course we know,
     that we want to have a bottle of the real thing...

     Putting this everyday problem into a mathematical model,  we  proceed
     as follows:

     (1) we  label all the regulators with x and a number starting from 1;
	 the result is a vector x, i.e.  (x_1,...,x_n),  where  n  is  the
	 number of visible regulators.

     (2) we must find an objective function, in this case it's obvious, we
	 want to get k bottles of the real thing, where k is equal  to  1.
	 [some  might  want  a  "greater or equal" here, but we restricted
	 ourselves to the visible regulators (we all know that sometimes a
	 "kick  in  the  right  place" gets use more than 1, but I have no
	 idea how to put this mathematically...)]

     (3) thus, in the language some mathematicians  prefer  to  speak  in:
	 f(x)  =  k  =  1. So, what we have here is a maximization problem
	 presented in a form we know from some  boring  calculus  lessons,
	 and   we   also   know  that  there  at  least  a  dozen  utterly
	 uninteresting techniques to solve problems presented this  way...

 What can we do in order to solve this problem?
     We  can  either try to gain more knowledge or exploit what we already
     know about the interior of the black box. If the  objective  function
     turns  out  to  be smooth and differentiable, analytical methods will
     produce the exact solution.

     If this turns out to be impossible, we  might  resort  to  the  brute
     force  method  of  enumerating the entire SEARCH SPACE.  But with the
     number of possibilities growing exponentially in  n,  the  number  of
     dimensions  (inputs),  this  method  becomes infeasible even for low-
     dimensional spaces.

     Consequently, mathematicians  have  developed  theories  for  certain
     kinds  of  problems  leading  to specialized OPTIMIZATION procedures.
     These  algorithms  perform  well  if  the  black  box  fulfils  their
     respective  prerequisites.   For example, Dantzig's simplex algorithm
     (Dantzig 66) probably  represents  the  best  known  multidimensional
     method capable of efficiently finding the global optimum of a linear,
     hence convex, objective function in a search space limited by  linear
     constraints.   (A  USENET  FAQ on linear programming is maintained by
     Professor   Robert   Fourer   <4er@iems.nwu.edu>   (and   "nonlinear-
     programming-faq")  that  is  posted monthly to sci.op-research and is
     mostly interesting to read.  It is also  available  from  http://www-
     unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.html )

     Gradient  strategies  are  no longer tied to these linear worlds, but
     they smooth their world by exploiting the objective function's  first
     partial  derivatives  one  has to supply in advance. Therefore, these
     algorithms rely on a locally linear internal model of the black  box.

     Newton   strategies   additionally   require   the   second   partial
     derivatives, thus building a quadratic internal model.  Quasi-Newton,
     conjugate  gradient  and  variable metric strategies approximate this
     information during the search.

     The deterministic  strategies  mentioned  so  far  cannot  cope  with
     deteriorations,  so  the search will stop if anticipated improvements
     no longer occur. In a multimodal ENVIRONMENT  these  algorithms  move
     "uphill"  from their respective starting points. Hence, they can only
     converge to the next local optimum.

     Newton-Raphson-methods might even diverge if  a  discrepancy  between
     their  internal assumptions and reality occurs.  But of course, these
     methods turn out to  be  superior  if  a  given  task  matches  their
     requirements.  Not relying on derivatives, polyeder strategy, pattern
     search and rotating coordinate search should also be  mentioned  here
     because  they  represent  robust  non-linear  optimization algorithms
     (Schwefel 81).

     Dealing with technical optimization problems, one will rarely be able
     to write down the objective function in a closed form.  We often need
     a SIMULATION model in order to grasp reality.  In general, one cannot
     even   expect   these   models   to  behave  smoothly.  Consequently,
     derivatives do not exist. That is why  optimization  algorithms  that
     can  successfully  deal  with  black  box-type  situations  have been
     developed. The increasing applicability is of course paid  for  by  a
     loss  of  "convergence  velocity,"  compared  to algorithms specially
     designed for the given problem.  Furthermore, the guarantee  to  find
     the global optimum no longer exists!

 But why turn to nature when looking for more powerful algorithms?
     In  the  attempt  to  create  tools for various purposes, mankind has
     copied, more often instinctively than geniously,  solutions  invented
     by  nature.  Nowadays, one can prove in some cases that certain forms
     or structures are not only well adapted to their ENVIRONMENT but have
     even reached the optimum (Rosen 67). This is due to the fact that the
     laws of nature have remained  stable  during  the  last  3.5  billion
     years.  For  instance,  at branching points the measured ratio of the
     diameters in a system of blood-vessels comes close to the theoretical
     optimum  provided  by  the laws of fluid dynamics (2^-1/3).  This, of
     course, only represents a  limited,  engineering  point  of  view  on
     nature. In general, nature performs adaptation, not optimization.

     The idea to imitate basic principles of natural processes for optimum
     seeking procedures emerged more than three decades  ago  (cf  Q10.3).
     Although  these  algorithms  have  proven  to  be  robust  and direct
     OPTIMIZATION tools, it is only in the last five years that they  have
     caught  the researchers' attention. This is due to the fact that many
     people still look at organic EVOLUTION as a giantsized game of  dice,
     thus  ignoring  the  fact  that  this  model of evolution cannot have
     worked: a human germ-cell comprises approximately 50,000 GENEs,  each
     of  which  consists  of about 300 triplets of nucleic bases. Although
     the four  existing  bases  only  encode  20  different  amino  acids,
     20^15,000,000,  ie  circa 10^19,500,000 different GENOTYPEs had to be
     tested in only circa 10^17 seconds, the age of our planet. So, simply
     rolling  the  dice  could  not have produced the diversity of today's
     complex living systems.

     Accordingly,  taking  random  samples   from   the   high-dimensional
     parameter  space  of an objective function in order to hit the global
     optimum must fail (Monte-Carlo search). But  by  looking  at  organic
     evolution  as  a  cumulative,  highly  parallel  sieving process, the
     results of which pass on slightly modified into the next  sieve,  the
     amazing   diversity   and  efficiency  on  earth  no  longer  appears
     miraculous. When building a model, the point is to isolate  the  main
     mechanisms  which  have  led  to  today's  world  and which have been
     subjected to evolution themselves.  Inevitably, nature  has  come  up
     with  a  mechanism  allowing  INDIVIDUALs  of one SPECIES to exchange
     parts of their genetic information (RECOMBINATION or CROSSOVER), thus
     being able to meet changing environmental conditions in a better way.

     Dantzig, G.B.  (1966)  "Lineare  Programmierung  und  Erweiterungen",
     Berlin: Springer. (Linear programming and extensions)

     Kursawe,  F.  (1994) " Evolution strategies: Simple models of natural
     processes?", Revue Internationale de Systemique, France (to  appear).

     Rosen,   R.  (1967)  "Optimality  Principles  in  Biologie",  London:
     Butterworth.

     Schwefel, H.-P. (1981) "Numerical Optimization of  Computer  Models",
     Chichester: Wiley.

------------------------------

     Copyright  (c) 1993-2000 by J. Heitkoetter and D. Beasley, all rights
     reserved.

     This FAQ may be posted to any USENET newsgroup, on-line  service,  or
     BBS  as  long  as  it  is  posted  in  its entirety and includes this
     copyright statement.  This FAQ may not be distributed  for  financial
     gain.   This  FAQ  may  not  be included in commercial collections or
     compilations without express permission from the author.

End of ai-faq/genetic/part3
***************************

--