Usenet 1994 January/usenetsourcesnewsgroupsinfomagicjanuary1994.iso/answers/ai-faq/genetic/part3

Internet Message Format | 1993-12-27 | 114.6 KB

Path: bloom-beacon.mit.edu!gatech!swrinde!cs.utexas.edu!uunet!Germany.EU.net!Informatik.Uni-Dortmund.DE!home!heitkoet
From: [e-mail] (Joerg Heitkoetter)
Newsgroups: comp.ai.genetic,comp.answers,news.answers
Subject: FAQ: comp.ai.genetic part 3/3 (A Guide to Frequently Asked Questions)
Supersedes: <[e-mail]>
Followup-To: comp.ai.genetic
Date: 27 Dec 1993 18:06:24 GMT
Organization: CS Department, University of Dortmund, Germany
Lines: 3115
Approved: [e-mail]
Expires: 9 Feb 1994 18:06:12 GMT
Message-ID: <[e-mail]>
References: <[e-mail]>
NNTP-Posting-Host: home.informatik.uni-dortmund.de
Summary: This is part 3 of a trilogy entitled "The Hitch-Hiker's Guide
     to Evolutionary Computation". A monthly published list of Frequently
     Asked Questions (and their answers) about Evolutionary Algorithms,
     Life and Everything. It should be read by anyone who whishes to post
     to the comp.ai.genetic newsgroup, preferably *before* posting.
Originator: [e-mail] (Joerg Heitkoetter)
Xref: bloom-beacon.mit.edu comp.ai.genetic:1999 comp.answers:3187 news.answers:13392

Archive-name:   ai-faq/genetic/part3
Last-Modified:  12/20/93
Issue:          1.10





FAQ(3/3)                          ANSWERS                         FAQ(3/3)



A20) Available EA software packages?
     [eds  note:  the following is a reformatted, alphabetised and updated
     version of a survey that, until June  '93,  was  maintained  by  Nici
     Schraudolph.  Nici and I agreed to incorporate the file into this FAQ
     and he no longer maintains the original version.]

     A copy of most of the packages  described  below  are  also  kept  at
     SAFIER, the SAnta Fe Instutute's Evolutionary computation Repository,
     that can be entered via anonymous FTP at sfi.santafe.edu:/pub/EC  (cf
     Q15.3) Check this out!

     You  should  also  be aware that most Genetic Programming software is
     archived by  Jim  McCoy  <[e-mail]>.   Available  via
     anonymous FTP to ftp.cc.utexas.edu:/pub/genetic-programming directory
     there are subdirectories containing papers related to GP, archives of
     the mailing list, as well as a suite of programs for implementing GP.
     These programs include the Lisp code from Koza's Genetic  Programming
     [KOZA92],  as  well  as  implementations in C and C++, as for example
     SGPC: Simple GENETIC PROGRAMMING in C by  Walter  Alden  Tackett  and
     Aviram Carmi <[e-mail]>.

     A  survey paper entitled "Genetic Algorithm Programming Environments"
     will be published  in  IEEE  Computer  in  the  february/1994  issue.
     Written  by  J.R. Filho, C. Alippi and P. Treleaven of the University
     College,    London,    UK,     it's     avail.     via     FTP     as
     bells.cs.ucl.ac.uk:/papagena/game/docs/gasurvey.ps


 PLEASE NOTE
     For  many  of these software packages, specific ordering instructions
     are given in the descriptions below.  Please  read  and  follow  them
     before  unnecessarily  bothering  the listed author or contact!  Also
     note that I haven't tested any of these programs (with the  exception
     the   one   I   administer),   so   I  can't  give  any  comments  or
     recommendations regarding their quality.

 Legend
     Type (this is a very ad-hoc classification)

      GE:  generational GA
      SS:  steady-state GA
      PA:  (pseudo) parallel GA
      ES:  evolution strategy
      OO:  object-oriented
      XP:  expert system
      ED:  educational/demo
      CF:  classifier system

     OS   Operating  System;  X11  implies  Unix;  "Win"  means  Microsoft
      Windows 3.x/NT (PC)




Issue 1.10               Posted: 20 December 1993                        1







FAQ(3/3)                          ANSWERS                         FAQ(3/3)



     Lang Programming  Language; in parentheses: source code not included;
      "TPas" = Think Pascal, "OPas" = MPW Object Pascal

     Price
      (1) free to government contractors, $221 otherwise (2) 69 pounds
      sterling  for educational use (3) educational discount available
      (4) available as addendum to a book (5) 995 pounds sterling  (6)
      single 3.500 DM, site license 10.000 DM (educational dicounts)

     Author or Contact
      given as Internet e-mail address if possible

           ES/GA/XP System Implementations:

     =========================================================================
      Name       Type OS       Lang  Price  Author/Contact
     =========================================================================

      BUGS        GE, X11,     C     free   Joshua Smith
          ED  Suntools             <[e-mail]>

      ESCaPaDE    ES  Unix     C     free   Frank Hoffmeister <hoffmeister@
                       ls11.informatik.uni-dortmund.de>

      Evolution   GE, DOS      C     free   Hans-Michael Voigt and
      Machine     ES                        Joachim Born
                       <[e-mail]>

      GAC,        GE  Unix    C      free   Bill Spears
      GAL         "   Lisp    "            <[e-mail]>

      GAGA        GE  Unix    C      free   Jon Crowcroft
                       <[e-mail]>

      GAucsd      GE  Unix    C      free   Nici Schraudolph
                       <[e-mail]>

      GA          GE, DOS     (C++)  free   Mark Hughes
      Workbench   ED                       <[e-mail]>

      Genesis     GE, Unix,   C      free   John Grefenstette
          ED  DOS                  <[e-mail]>

      GECO        GE, Unix,   Lisp   free   George P. W. Williams, Jr.
          ED  etc.                 <[e-mail]>

      GENEsYs     GE  Unix    C      free   Thomas Baeck <baeck@
                       ls11.informatik.uni-dortmund.de>

      GenET       GE, Unix,   C      free   Cezary Z. Janikow
          ED  etc.                 <[e-mail]>



Issue 1.10               Posted: 20 December 1993                        2







FAQ(3/3)                          ANSWERS                         FAQ(3/3)



      Genie       GE  Mac     TPas   free   Lance Chambers
                       <[e-mail]>

      Genitor     SS  Unix    C      free   Darrell Whitley
                       <[e-mail]>

      GENOCOP,    GE  Unix    C      free   Zbigniew Michalewicz
      Genetic-2/N                          <[e-mail]>

      GIGA        GE  Unix    C      free   Joe Culberson
                       <[e-mail]>

      LibGA       GE, Unix/DOS  C    free   Art Corcoran
           SS,ED  NeXT/Amiga           <[e-mail]>

      mGA1.0      GE  Unix    Lisp   free   Robert E. Smith
      SGA-C/Cube  "   nCube   C   "        <[e-mail]>

      PARAGENESIS GE  CM      C*     free   Michael van Lent
                       <[e-mail]>

      PeGAsuS     PA, Unix,   ANSI-C free   Dirk Schlierkamp-Voosen
          ED  etc.                 <dirk.schlierkamp-voosen.gmd.de>

      PGA         PA, Unix,   C      free   Peter Ross
          ED  etc.                 <[e-mail]>

      Splicer     GE  Mac,    C      (1)    Steve Bayer
              X11                  <[e-mail]>

      WOLF        SS  Mac,    C      $20/   David Rogers
              Unix           free  <[e-mail]>
     =========================================================================



          Classifier System Implementations:

     =========================================================================
      Name     Type  OS      Lang  Price Author/Contact
     =========================================================================

      CFS-C     CF,  Unix/DOS  C   free  Rick Riolo
        ED                      <[e-mail]>

      SCS-C     CF,  Unix/DOS  C   free  Joerg Heitkoetter
        ED   Atari TOS          <[e-mail]>
     ==========================================================================






Issue 1.10               Posted: 20 December 1993                        3







FAQ(3/3)                          ANSWERS                         FAQ(3/3)



             Commercial Packages:

     =========================================================================
      Name     Type  OS      Lang   Price  Author/Contact
     =========================================================================

      EnGENEer  OO,  X11      C       ?    George Robbins,
        GA                         Logica Cambridge Ltd.

      EvoFrame/ OO,  Mac,     C++/    (6)   Optimum Software
      REALizer  ES   Win      OPas         <[e-mail]>

      Evolver   GE   DOS,     (C,     $345  Phil Rybeck, Axcelis Inc.
             Mac      Pascal)

      GAME      OO,  X11      C++     (4)   Jose R. Filho
        GA                         <[e-mail]>

      MicroGA/  OO,  Mac,     C++     $249  Emergent Behavior, Inc.
      Galapagos GA   Win              (3)  <[e-mail]>

      Omega     ?    DOS      ?       ?     David Barrow, KiQ Ltd.

      OOGA/     OO,  Lisp             $60/  Lawrence Davis and
      GENESIS   GE   DOS      C       both  John Grefenstette
                       <[e-mail]>

      PC/Beagle XP   DOS      ?       (2)   Richard Forsyth

      XpertRule/XP   DOS     (TPas)   (5)   Attar Software
      GenAsys                              <[e-mail]>

      XYpe      SS   Mac     (C)      $725  Ed Swartz, Virtual Image Inc.
     =========================================================================



              Under Development:

     =========================================================================
      Name     Type OS      Lang   Price Author/Contact
     =========================================================================

      DGENESIS  GE  Unix     C     free  Erick Cantu
                    <[e-mail]>

      JAZZ-C    CF  Unix     C     free  Joerg Heitkoetter
                    <[e-mail]>
     =========================================================================





Issue 1.10               Posted: 20 December 1993                        4







FAQ(3/3)                          ANSWERS                         FAQ(3/3)



A20.1) Free software packages?
 BUGS:
     BUGS  (Better  to  Use Genetic Systems) is an interactive program for
     demonstrating the GENETIC ALGORITHM and is written in the  spirit  of
     Richard  Dawkins'  celebrated Blind Watchmaker software. The user can
     play god (or `GA FITNESS  function,'  more  accurately)  and  try  to
     evolve  lifelike organisms (curves). Playing with BUGS is an easy way
     to get an understanding of how and why the GA works. In  addition  to
     demonstrating  the basic genetic operators (selection, CROSSOVER, and
     MUTATION), it allows users to easily  see  and  understand  phenomena
     such as GENETIC DRIFT and premature convergence. BUGS is written in C
     and runs under Suntools and X Windows.

     BUGS was written by Joshua Smith at Williams College and is available
     via  anonymous  ftp from santafe.edu, directory "pub/misc/BUGS". Note
     that   it   is   unsupported   software,   copyrighted   but   freely
     distributable.

      Joshua R. Smith
      Room E15-492
      MIT Media Lab
      20 Ames Street
      Cambridge, MA 02139

      Net: <[e-mail]>

 ESCaPaDE:
     ESCaPaDE  is  a sophisticated software ENVIRONMENT to run experiments
     with Evolutionary Algorithms, such as  e.g.  an  EVOLUTION  Strategy.
     Future versions of the software will provide a well-defined interface
     to  any  kind  of  Evolutionary  Algorithm,  for   instance   GENETIC
     ALGORITHMs.   The  main  support for experimental work is provided by
     two internal tables:

     o  a table of objective functions and

     o  a table of so-called data monitors,

     which allow easy implementation of functions for monitoring all types
     of information inside the Evolutionary Algorithm under experiment.

     ESCaPaDE  1.2  comes  with  the  KORR implementation of the EVOLUTION
     Strategy  by  H.-P.  Schwefel  which  offers  simple  and  correlated
     MUTATIONs.   KORR  is  provided  as  a FORTRAN 77 subroutine, and its
     cross-compiled C version is used internally by ESCaPaDE.

     ESCaPaDE 1.2 will be available by e-mail request in  order  to  track
     the  spread  of  the software as this is its first public release. An
     extended version of the package was used for  several  investigations
     so  far  and  has  proven  to  be very reliable. The software and its
     documentation is fully copyrighted although it may be freely used for



Issue 1.10               Posted: 20 December 1993                        5







FAQ(3/3)                          ANSWERS                         FAQ(3/3)



     scientific work; it requires 5-6 MB of disk space.

     In  order  to obtain ESCaPaDE via mail request, please send a message
     to the e-mail address below.

     The SUBJECT line should contain the request 'help' or 'get ESCaPaDE'.
     (If the subject line does not match a predefined set of mail requests
     the mail handler will NOT recognize your request!)

     For more information contact:

      Frank Hoffmeister
      Systems Analysis Research Group, LSXI
      Department of Computer Science
      University of Dortmund
      D-44221 Dortmund, Germany

      Net: <[e-mail]>
      Fax: [phone]

 Evolution Machine:
     The "Evolution Machine"  (EM)  was  created  by  Hans-Michael  Voigt,
     Joachim  Born  and  Jens Treptow. The authors developed the EM at the
     Institute for Informatics and Computing  Techniques  of  Berlin.   At
     present,  Hans-Michael  Voigt  and  Joachim Born are at the Technical
     University of Berlin.

     The Evolution Machine (EM) is universally  applicable  to  continuous
     (real-coded) optimization problems.

     In  the  EM,   we  have  coded   fundamental  evolutionary algorithms
     (Genetic Algorithms and Evolution Strategies),  and added some of our
     approaches to evolutionary search.

     The EM includes extensive menu techniques with:

     o  Default parameter setting for unexperienced users.

     o  Well-defined  entries  for   EM-control  by freaks of the EM,  who
    want  to leave  the standard  process control.

     o  Data processing for repeated runs (with or without change  of  the
    strategy parameters).

     o  Graphical  presentation  of  results:  online  presentation of the
    evolution  progress,  one-,  two-  and  three-dimensional  graphic
    output  to analyse the fitness function and the evolution process.

     o  Integration of calling MS--DOS utilities (Turbo C).





Issue 1.10               Posted: 20 December 1993                        6







FAQ(3/3)                          ANSWERS                         FAQ(3/3)



     We provide  the EM-software in object code,  which can be run on PC's
     with  MS--DOS  and Turbo C, v2.0,  resp. Turbo C++,v1.01.  The Manual
     to the EM is included in the distribution kit.

     The  EM  software  is  available   by   anonymous   ftp   from   ftp-
     bionik.fb10.tu-berlin.de        (130.149.192.50)        in        the
     "pub/software/Evolution-Machine"  directory,   which   contains   the
     compressed files em_tc.exe (EM for Turbo C), em_tcp.exe (EM for Turbo
     C++) and em_man.exe (the manual). Additionally, it  exists  the  file
     em-man.ps.Z  (PostScript  file  of  the  manual,  generated  with the
     standard Unix compress(1) program).

     If you do not have ftp access, please send us either 5 1/4 or  3  1/2
     MS-DOS  compatible  disks.  We  will  return them with the compressed
     files (834 kB).

     We welcome bug  reports,  comments  and  sugestions,  but  have  only
     limited  manpower  for  providing help, patches and new releases.  We
     are making EM available in order to encourage the experimental use of
     evolutionary  algorithms, and to get feedback as to its strengths and
     weaknesses.

     Official contact information:

      Hans-Michael Voigt or Joachim Born
      Technical University Berlin
      Bionics and Evolution Techniques Laboratory
      Bio- and Neuroinformatics Research Group
      Ackerstrasse 71-76 (ACK1)
      D-13355 Berlin, Germany

      Net: <{voigt,born}@fb10.tu-berlin.de>
      Tel: [phone]

 GAC, GAL:
     For those of you interested in obtaining some free GA  software,  I'm
     providing  the  packages I've been using for a few years. GAC is a GA
     written in C. GAL is my Common Lisp  version.  They  are  similar  in
     spirit  to  John  Grefenstette's Genesis, but they don't have all the
     nice  bells  and  whistles.  Both  versions  currently  run  on   Sun
     workstations.  If  you  have  something  else, you might need to do a
     little modification. [Alan Schultz informs  me  that  GAL  is  easily
     ported to the Mac - although his version is no longer available.]

     In  the  spirit  of "freeware", I am willing to e-mail either version
     (or both) to anyone who wants it. All I ask is  that  I  be  credited
     when  it  is  appropriate.  Also,  I  would  appreciate hearing about
     improvements! This software is the property of the Department of  the
     Navy.





Issue 1.10               Posted: 20 December 1993                        7







FAQ(3/3)                          ANSWERS                         FAQ(3/3)



     The  code  will  be  in a "shar" format that will be easy to install.
     This  code  is  "as  is",  however.  There  is  a  README  and   some
     documentation in the code. There is NO user's guide, though (nor am I
     planning on writing one at this time). I  am  interested  in  hearing
     about  bugs,  but  I  may  not get around to fixing them for a while.
     Also, I will be unable to answer many questions about  the  code,  or
     about  GAs in general. This is not due to a lack of interest, but due
     to a lack of free time!  --- Bill Spears <[e-mail]>

     p.s.:   We   have   also   set   up   an    anonymous    FTP    site:
     ftp.aic.nrl.navy.mil.   GAC,  GAL,  and  PostScript  versions of some
     papers are under "pub/spears".  Feel free to browse.

 GAGA:
     GAGA (GA for General Application)  is  a  self-contained,  re-entrant
     procedure  which is suitable for the minimization of many "difficult"
     cost functions.  Originally written in Pascal by Ian  Poole,  it  was
     rewritten in C by Jon Crowcroft. GAGA can be obtained by request from
     the author; given sufficient interest it will be made  available  via
     anonymous ftp.

      Jon Crowcroft
      Univeristy College London
      Gower Street
      London WCIE 6BT, UK

      Net: <[e-mail]>

 GAucsd:
     GAucsd is a GENESIS-based GA package incorporating numerous bug fixes
     and user interface improvements. Major additions  include  a  wrapper
     that  simplifies  the  writing of evaluation functions, a facility to
     distribute  experiments  over  networks  of  machines,  and   Dynamic
     Parameter  Encoding,  a  technique  that  improves  GA PERFORMANCE in
     continuous  SEARCH  SPACEs  by  adaptively   refining   the   genomic
     representation of real-valued parameters.

     GAucsd  was  written in C for Unix systems, but the central GA engine
     is easily ported to other platforms. The entire package can be ported
     to  systems where implementations of the Unix utilities "make", "awk"
     and "sh" are available.

     GAucsd  can  be  obtained  via   anonymous   ftp   from   cs.ucsd.edu
     (132.239.51.3), file "pub/GAucsd/GAucsd14.sh.Z", or via mail server -
     send an EMPTY message with the subject line containing  "send  GAucsd
     source"  to  <[e-mail]>.   Requests  to be added to a mailing
     list for dissemination of GAucsd bug  reports,  patches  and  updates
     should be directed to the same address.

      Nicol N. Schraudolph
      The SALK Institute



Issue 1.10               Posted: 20 December 1993                        8







FAQ(3/3)                          ANSWERS                         FAQ(3/3)



      San Diego, La Jolla, CA, USA

      Net: <[e-mail]>

 GA Workbench:
     A  mouse-driven  interactive GA demonstration program aimed at people
     wishing to show GAs in action on simple FUNCTION OPTIMIZATIONs and to
     help   newcomers   understand  how  GAs  operate.  Features:  problem
     functions  drawn  on  screen  using  mouse,  run-time  plots  of   GA
     POPULATION distribution, peak and average FITNESS.  Useful population
     statistics displayed numerically, GA configuration (population  size,
     GENERATION   gap   etc.)    performed   interactively   with   mouse.
     Requirements: MS-DOS PC, mouse, EGA/VGA display.

     Available by ftp from the simtel20  archive  mirrors,  as  the  WSMR-
     SIMTEL20.Army.Mil  site  was  closed  down  in  October 93.  Look for
     "gaw110.zip" or free on 5.25'' disk by request from:

      Mark Hughes
      Cambridge Consultants Ltd.
      The Science Park, Milton Road
      Cambridge CB4 4DW, UK

      Net: <[e-mail]>

 GECO:
     Genetic Evolution through Combination of Objects (GECO), version 2.0.

     GECO  is  an  extensible,  object-oriented  framework for prototyping
     genetic algorithms in Common Lisp. GECO makes extensive use of  CLOS,
     the  Common  Lisp  Object System, to implement its functionality. The
     abstractions provided by the classes have been chosen with the intent
     both  of  being  easily  understandable  to  anyone familiar with the
     paradigm of  genetic  algorithms,  and  of  providing  the  algorithm
     developer with the ability to customize all aspects of its operation.
     It  comes  with  extensive  documentation,   in   the   form   of   a
     PostScript(tm)  file,  and  some simple examples are also provided to
     illustrate its intended use.

     GECO  Version  2.00  is  now  available  via   anonymous   ftp   from
     ftp.aic.nrl.navy.mil,  in  files "/pub/galist/src/ga/GECO-v2.0.tar.Z"
     (Unix) or "/pub/galist/src/ga/GECO-v2.0.cpt.hqx" (Macintosh).

      George P. W. Williams, Jr.
      1334 Columbus City Rd.
      Scottsboro, AL 35768

      Net: <[e-mail]>
      Tel: [phone]
      Fax: [phone]




Issue 1.10               Posted: 20 December 1993                        9







FAQ(3/3)                          ANSWERS                         FAQ(3/3)



 GENEsYs:
     GENEsYs  is  a  GENESIS-based  GA   implementation   which   includes
     extensions  and  new  features  for  experimental  purposes,  such as
     selection   schemes   like   linear    ranking,    Boltzmann,    (mu,
     lambda)-selection,   and   general   extinctive  selection  variants,
     CROSSOVER operators like n-point and uniform  crossover  as  well  as
     discrete and intermediate RECOMBINATION.  Self-adaptation of MUTATION
     rates is also possible.

     A set  of  objective  functions  is  provided,  including  De  Jong's
     functions,  complicated  continuous  functions, a TSP-problem, binary
     functions, and a fractal function. There are  also  additional  data-
     monitoring facilities such as recording average, variance and skew of
     object variables and MUTATION rates, or creating bitmap-dumps of  the
     POPULATION.

     GENEsYs   1.0   is   available  via  ftp  from  lumpi.informatik.uni-
     dortmund.de (129.217.36.140). Log on with user name  "ftp"  and  give
     your  full  e-mail address as password. The file GENEsYs-1.0.tar.Z in
     directory "pub/GA/src" contains the complete  software  distribution;
     the  documentation alone is available as GENEsYs-1.0-doc.tar.Z in the
     same location.

     For more information contact:

      Thomas Baeck
      Systems Analysis Research Group, LSXI
      Department of Computer Science
      University of Dortmund
      D-44221 Dortmund, Germany

      Net: <[e-mail]>
      Fax: [phone]

 GenET:
     GenET  Version  1.00  is  now  available  via  anonymous   ftp   from
     radom.umsl.edu,  as  "/var/ftp/GenET.tar.Z".   To learn more, you may
     get  the  User's  Manual,  available  in  compressed  postscript   in
     "/var/ftp/userMan.ps.Z".  It  also  comes  bundled  with the complete
     package.

     GenET is a "generic" GA package. It is  not  generic  in  the  normal
     sense,  which  usually  implies some standard (binary) representation
     and its operators.  It is generic  in  the  sense  that  all  problem
     independent   mechanisms  have  been  implemented  and  can  be  used
     regardless of application  domain.   Using  the  package  forces  (or
     allows,  however  you  look  at it) concentration on the problem: you
     have to suggest the best representation, and the best  operators  for
     such  space that utilize your problem-specific knowledge.  You do not
     have to think about possible GA models or their implementation.  This
     speeds   up   problem-specific  GA  applications  by  about  95%  for



Issue 1.10               Posted: 20 December 1993                       10







FAQ(3/3)                          ANSWERS                         FAQ(3/3)



     researchers w/o extensive GA libraries and about 50% for  those  with
     complete  good  libraries.  The  package  provides  some libraries of
     representations  and  operators.  The  user  can  either  create  new
     rep/opers,  use  the  existing, or implement rep/operators along with
     the  problem.   Problem  is  implemented  by  specifying   only   the
     evaluation   and  initialization.   Representations  are  defined  by
     functions to allocate storage and display CHROMOSOMEs.  etc. All such
     interfaces have standard definitions.

     The  package,  in  addition  to  allowing  for fast implementation of
     applications and being a natural tool for comparing different  models
     and strategies, is intended to become a depository of representations
     and operators.  Currently, only FP representation is  implemented  in
     the library with few operators.

     The  algorithm  provides a wide selection of models and choices.  For
     example,  POPULATION  models  range  from  generational  GA,  through
     steady-state,  to  (n,m)-EP  and  (n,n+m)-EP  models  (for  arbitrary
     problems, not just parameter optimization).  (Some are  not  finished
     at  the  moment).   Choices  include automatic adaptation of operator
     probabilities and a dynamic ranking mechanism, etc.

     Even though the implementation is  far  from  optimal,  it  is  quite
     efficient  -  implemented  in ATT's C++ (3.0) (functional design) and
     also tested on  gcc.   Along  with  the  package  you  will  get  two
     examples.   They   illustrate   how   to   implement   problems  with
     heterogeneous and homogeneous structures, with explicit rep/opers and
     how  to  use the existing library (FP).  Very soon I will place there
     another example - our  GENOCOP  operators  for  linearly  constrained
     optimization.  This  example  nicely  illustrates  the  power  of the
     generic mechanism for adapting the operators, which nicely  allocates
     the  resources (high probabilities) to those operators that currently
     show the best promise.  One more example soon to  appear  illustrates
     how  to  deal  with  complex structures and non-stationary problems -
     this is a fuzzy rule-based controller optimized using the package and
     some specific rep/operators.

     If   you   start  using  the  package,  please  send  me  evaluations
     (especially bugs) and suggestions for future versions.  Have fun.

      Cezary Z. Janikow
      Department of Math and CS, CCB319
      St. Louis, MO 63121

      Net: <[e-mail]>
      Tel: [phone]
      Fax: [phone]

 Genie:
     Genie is a GA-based modeling/forecasting  system  that  is  used  for
     long-term  planning.  One can construct a model of an ENVIRONMENT and



Issue 1.10               Posted: 20 December 1993                       11







FAQ(3/3)                          ANSWERS                         FAQ(3/3)



     then view the forecasts of how that environment will evolve into  the
     future.  It  is  then  possible  to  alter  the future picture of the
     environment so as to construct a picture of a desired future (I  will
     not  enter  into  arguments  of  who  is or should be responsible for
     designing a desired or better future). The GA  is  then  employed  to
     suggest  changes  to  the  existing  environment  so  as to cause the
     desired future to come about.

     Genie is available free of charge via e-mail or on 3.5'' disk from:

      Lance Chambers
      Department of Transport
      136 Stirling Hwy
      Nedlands
      West Australia 6007

      Net: <[e-mail]>

 Genitor:
     "Genitor is a modular GA package containing  examples  for  floating-
     point, integer, and binary representations. Its features include many
     sequencing operators as well as subpopulation modeling.

     The Genitor Package  has  code  for  several  order  based  CROSSOVER
     operators,  as  well  as  example  code  for doing some small TSPs to
     optimality.

     We are planning to release a new and improved  Genitor  Package  this
     summer,  but  it will mainly be additions to the current package that
     will include parallel island  models,  cellular  GAs,  delta  coding,
     perhaps  CHC (depending on the legal issues) and some other things we
     have found useful.

     Thank  you  for  your  interest  and  good  luck  in  searching  your
     hyperspace."

     To  receive  GENITOR via anonymous ftp from Colorado State University
     Computer Science Department follow these steps:

      1. % mkdir Genitor
      2. % cd Genitor
      3. % ftp 129.82.102.183
      4. <login:> anonymous
      5. <password:> {your e-mail address for our information}
      6. ftp> cd pub
      7. ftp> binary
      8. ftp> get GENITOR.tar
      9. ftp> bye

     The GENITOR.tar file is in tar format and  can  be  restored  in  the
     current directory using the following commands.



Issue 1.10               Posted: 20 December 1993                       12







FAQ(3/3)                          ANSWERS                         FAQ(3/3)



      10. % tar -xvf GENITOR.tar .

     Note  to  SPARC-2  users: There is something strange about unix on on
     sparc-2s.  REMOVE the  libraries  /Genitor/lib/ga/libcsu***.a  before
     attempting  to  rebuild  them for your machine.  Somehow, the file is
     not  completely  overwitten  on  this  operating   system.    --   T.
     Starkweather

     Please      direct      all     comments     and     questions     to
     <[e-mail]>.  If these fail to work, contact:

      L. Darrell Whitley
      Dept. of Computer Science
      Colorado State University
      Fort Collins, CO 80523, USA

      Net: <[e-mail]>

 GENOCOP, Genetic-2, Genetic-2N:
     These three genetic optimization packages are available as compressed
     tar  files  via  anonymous  ftp from unccsun.uncc.edu (152.15.10.88),
     directory  "coe/evol".  They  have   been   developed   by   Zbigniew
     Michalewicz  and  are described in detail in his recent book "Genetic
     Algorithms + Data Structures = Evolution Programs" (Springer  Verlag,
     August 1992).

     GENOCOP (GENETIC ALGORITHM for Numerical Optimization for COnstrained
     Problems) optimizes a function with any number of linear  constraints
     (equalities  and  inequalities). Genetic-2 is an optimization package
     for the linear transportation problem; Genetic-2N for  the  nonlinear
     one.

      Zbigniew Michalewicz
      Dept. of Computer Science
      University of North Carolina
      Chappel-Hill, NC, USA

      Net: <[e-mail]>

 GIGA:
     GIGA is designed to propogate information through a POPULATION, using
     CROSSOVER as  its  operator.   A  discussion  of  how  it  propogates
     BUILDING  BLOCKs,  similar  to those found in Royal Road functions by
     John Holland, is given in the DECEPTION section of [1].

     References

     [1] Genetic Invariance: A New Paradigm for GENETIC  ALGORITHM  Design
     University of Alberta Technical Report TR92-02, June 1992





Issue 1.10               Posted: 20 December 1993                       13







FAQ(3/3)                          ANSWERS                         FAQ(3/3)



     [2]  GIGA  Program  Description  and  Operation University of Alberta
     Computing Science Technical Report TR92-06, June 1992

     These can be obtained, along with  the  program,  via  anon.  ftp  to
     ftp.cs.ualberta.ca in "pub/TechReports" in the subdirectories TR92-02
     and TR92-06.

     Alternatively, if you have gopher, try:

      gopher gopher.cs.ualberta.ca

     And follow the links to University of Alberta Technical Reports.

      Joe Culberson
      Department of Computer Science
      University of Alberta, CA

      Net: <[e-mail]>
      Tel: [phone]

 LibGA:
     LibGA  Version  1.00  is  now  available  via  anonymous   ftp   from
     ftp.aic.nrl.navy.mil, in the file "/pub/galist/src/ga/libga100.tar.Z"
     or by email request to its author.

     LibGA is a library of routines written in C  for  developing  GENETIC
     ALGORITHMs.   It  is  fairly  simple to use, with many knobs to turn.
     Most GA parameters can be set or changed via configuration file, with
     no  need to recompile.  (E.g., operators, pool size and even the data
     type used in the CHROMOSOME  can  be  changed  in  the  configuration
     file.)  Function pointers are used for the genetic operators, so they
     can easily be manipulated on the fly.  Several genetic operators  are
     supplied   and   it  is  easy  to  add  more.   LibGA  runs  on  many
     systems/architectures.  These include Unix, DOS, NeXT, and Amiga.

     I realize this is "yet another GA", but I hope it proves useful.

      Art Corcoran
      Net: <[e-mail]>

 mGA1.0, SGA-C, SGA-Cube:
     mGA1.0 is a Common Lisp implementation of a messy GA as described  in
     TCGA  report  No.  90004.  Messy  GAs overcome the linkage problem of
     simple GENETIC ALGORITHMs by combining variable-length strings,  GENE
     expression,   messy   operators,  and  a  nonhomogeneous  phasing  of
     evolutionary processing.  Results on a number of difficult  deceptive
     test functions have been encouraging with the messy GA always finding
     global optima in a polynomial number of function evaluations.

     See TCGA reports 89003, 90005, 90006, and 91004 for more  information
     on  messy  GAs;  they  can be obtained from the address below. Please



Issue 1.10               Posted: 20 December 1993                       14







FAQ(3/3)                          ANSWERS                         FAQ(3/3)



     note that 91004 is a dissertation and requires a pre-payment of $9.00
     US  ($12.00  US  to  ship  overseas)  to  offset the cost of copying,
     binding and shipping.

     SGA-C is a C-language  translation  and  extension  of  the  original
     Pascal  SGA  code presented in Goldberg's book "Genetic Algorithms in
     Search, Optimization & Machine Learning" (Addison  Wesley  1989).  It
     has  some  additional  features, but its operation is essentially the
     same as that of the Pascal version. SGA-C is described in TCGA report
     No.  91002,  which  is  included  in the distribution as a PostScript
     file.

     SGA-Cube is a C-language translation  of  Goldberg's  SGA  code  with
     modifications  to  allow  execution on the nCUBE 2 Hypercube Parallel
     Computer.  When run on the nCUBE 2, SGA-Cube can  take  advantage  of
     the   hypercube  architecture,  and  is  scalable  to  any  hypercube
     dimension. The hypercube  implementation  is  modular,  so  that  the
     algorithm  for exploiting parallel processors can be easily modified.

     In addition to its parallel capabilities, SGA-Cube can be compiled on
     various  serial  computers  via  compile-time  options. In fact, when
     compiled on a serial computer, SGA-Cube is essentially  identical  to
     SGA-C.  SGA-Cube has been nominally tested on a Sun 4/70 workstation,
     a VAX Ultrix system, a Cray X-MP/24 running UNICOS 5.1, and the nCUBE
     2. It is described in TCGA report No. 91005, which is included in the
     distribution as a PostScript file.

     Each of these programs is distributed in form of a  Unix  shar  file,
     available via e-mail or on various formatted media by request from:

      Robert Elliott Smith
      Department of Engineering of Mechanics
      Room 210 Hardaway Hall
      The University of Alabama
      P.O. Box 870278
      Tuscaloosa, Alabama 35487, USA

      Net: <[e-mail]>
      Tel: [phone]
      Fax: [phone]

     SGA-C  and  SGA-Cube  are  also  available in compressed tar form via
     anonymous ftp from the GA-List  archive  server  ftp.aic.nrl.navy.mil
     (192.26.18.56) in the "pub/galist/source-code/ga-source" directory.

 PARAGENESIS:
     "I  spent this past summer at the Naval Research Lab working with Ken
     De Jong  and  John  Grefenstette  to  implement  John  Grefenstette's
     GENESIS  on  the  CM-200  in  C*. The result, which I've been calling
     PARAGENESIS, is an attempt to improve PERFORMANCE as much as possible
     without  changing  the behavior of the GENETIC ALGORITHM.  Unlike the



Issue 1.10               Posted: 20 December 1993                       15







FAQ(3/3)                          ANSWERS                         FAQ(3/3)



     punctuated equilibria and local selection models PARAGENESIS  doesn't
     modify  the  genetic  algorithm  to  be  more parallelizable as these
     modifications can drastically alter the behavior  of  the  algorithm.
     Instead  each  member  is  placed  on  a  separate processor allowing
     initialization, evaluation and MUTATION to  be  completely  parallel.
     The  costs  of  global  control  and  communication  in selection and
     CROSSOVER are present but minimized as much as possible.  In  general
     PARAGENESIS  on  an  8k  CM-200 seems to run 10-100 times faster than
     GENESIS on a Sparc 2 and finds equivalent  solutions.  The  solutions
     are  not  identical only because the parallel random number generator
     gives a different stream of numbers.

     PARAGENESIS includes all the features of  serial  GENESIS  plus  some
     additions.  The  additions  include  the  ability  to  collect timing
     statistics, probabilistic selection(as opposed to Baker's  stochastic
     universal  sampling),  uniform  CROSSOVER  and  local or neighborhood
     selection. Anyone familiar with the serial implementation of  GENESIS
     and C* should have little problem using PARAGENESIS.

     PARAGENESIS  is  available via anonymous ftp from the GA-List archive
     at ftp.aic.nrl.navy.mil (192.26.18.74).  The  compressed  and  tar-ed
     code is found in the file /pub/galist/src/ga/paragenesis.tar.Z.

     DISCLAIMER:  PARAGENESIS  is  fairly  untested  at this point and may
     contain some bugs. I will try to fix any reported bugs as my schedule
     and my access to the CM allows."

      Michael van Lent
      Computer Science Dept.
      University of Tennessee
      Knoxville TN 37996-1301, USA

      Net: <[e-mail]>

 PeGAsuS:
     PeGAsuS   is   a   Programming   Environment  for  Parallel   Genetic
     Algorithms developed at  the  German  National  Research  Center  for
     Computer  Science.  In fact, it is a tool kit which can be  used  The
     environment   is   written  in  ANSI-C  and  is  available  for  many
     different  UNIX-based  machines.   It runs on MIMD parallel machines,
     such as transputers, and  distributed  systems.

     The User Interface  consists  of  three  parts:  the  PeGAsuS  script
     language, a graphical interface and a user library.  The user library
     has the same functionality of the PeGAsuS GA library.  It allows  the
     user  to   define   application   specific  functions  that  are  not
     provided  by  the system library.  The script  language  is  used  to
     specify  the  experiment.   The  user   can  use   it   to define the
     application  dependent  data  structures,   attaches   the    genetic
     operators   to  them   and   specifies   the input/output  interface.
     Whereas  the script language specifies the  construction  of  a  sub-



Issue 1.10               Posted: 20 December 1993                       16







FAQ(3/3)                          ANSWERS                         FAQ(3/3)



     population,  The  the  execution  order   of the  genetic  operators,
     manage   communication  between  different  processes   and   provide
     input/output   facilities.    They    build    general   frames   for
     simulating GAs, and can be considered as autonomous processes.

     They  interpret  the  PeGAsuS   script,   create   appropriate   data
     structures, and describe the order of the frame functions.  A "frame"
     function controls the execution a base function.   They  prepare  the
     data   representing   the  genetic   material,  and apply the genetic
     operators to it, according to the script specification.  The  Library
     contains   genetic  operators,   a  collection  of fitness functions,
     and input/output and control procedures.  It provides the  user  with
     a   number   of  validated  modules  for  Currently,  PeGAsuS  can be
     compiled with the GNU C, RS/6000 C, ACE-C, and  Alliant's  FX/2800  C
     compilers.   It runs on SUN s and RS/6000 workstations, as well as on
     the Alliant FX/28.

     For more information contact:

      Dirk Schlierkamp-Voosen
      Research Group for Adative Systems
      German National Research Center for
      Computer Science
      53731 Sankt Augustin, Germany

      Net: <[e-mail]>
      Tel: [phone]

 PGA:
     PGA is a simple testbed for basic EXPLORATIONs in GENETIC ALGORITHMs.
     Command  line  arguments  control  a range of parameters, there are a
     number of built-in problems for the GA  to  solve.  The  current  set
     consists of:

     o  maximize the number of bits set in a CHROMOSOME

     o  De Jong's functions DJ1, DJ2, DJ3, DJ5

     o  binary F6, used by Schaffer et al

     o  a  crude  1-d  knapsack problem; you specify a target and a set of
    numbers in an external file, GA tries to find a subset  that  sums
    as closely as possible to the target

     o  the `royal road' function(s); a CHROMOSOME is regarded as a set of
    consecutive blocks of size K, and scores K for each block entirely
    filled with 1s

     and  it's easy to add your own problems (see below).  CHROMOSOMEs are
     represented as character arrays, so you are not  (quite)  stuck  with
     bit-string problem encodings.



Issue 1.10               Posted: 20 December 1993                       17







FAQ(3/3)                          ANSWERS                         FAQ(3/3)



     PGA  has  been  used  for teaching for a couple of years now, and has
     been used as a starting point by a fair number of  people  for  their
     own projects. So it's reasonably reliable. However, if you find bugs,
     or have useful contributions to make, Tell Me!

      Peter Ross
      Department of AI
      University of Edinburgh
      80 South Bridge
      Edinburgh EH1 1HN, UK

      Net: <[e-mail]>

 Splicer:
     Splicer is a GENETIC ALGORITHM tool that can be used to solve  search
     and  optimization problems, created by the Software Technology Branch
     (STB) of the Information Systems Directorate  at  NASA/Johnson  Space
     Center  with  support from the MITRE Corporation. Splicer was written
     in C on an Apple Macintosh, then ported to Unix workstations  running
     X11;  it  has  a  modular  architecture  with well-defined interfaces
     between a GA kernel, representation libraries, FITNESS  modules,  and
     user interface libraries.

     The   representation   libraries   contain  functions  for  defining,
     creating, and decoding genetic strings, as well as multiple CROSSOVER
     and  MUTATION  operators.  Libraries  supporting  binary  strings and
     permutations are provided, others can be created by the user.

     FITNESS modules are typically written  by  the  user,  although  some
     sample  applications  are provided. The modules may contain a fitness
     function, initial  values  for  various  control  parameters,  and  a
     function which graphically displays the best solutions.

     Splicer  provides  event-driven  graphic user interface libraries for
     the Macintosh and the X11 window system (using the HP widget set);  a
     menu-driven  ASCII  interface  is  also  available  though  not fully
     supported.  The extensive documentation includes a  reference  manual
     and  a  user's  manual;  an  architecture  manual  and  the  advanced
     programmer's manual are currently being written.

     An  electronic  bulletin  board  (300/1200/2400   baud,   8N1)   with
     information  regarding  Splicer  can  be reached at [phone] or
     (713)  280-3892.   Splicer  is  available  free  to  NASA   and   its
     contractors  for  use  on government projects by calling the STB Help
     Desk weekdays 9am-4pm CST at [phone].  Government  contractors
     should have their contract monitor call the STB Help Desk; others may
     purchase Splicer for $221 (incl. documentation) from:

      COSMIC
      382 E. Broad St.
      Athens, GA 30602, USA



Issue 1.10               Posted: 20 December 1993                       18







FAQ(3/3)                          ANSWERS                         FAQ(3/3)



      Net: <[e-mail]>
      Tel: [phone]
      Fax: [phone]

 WOLF:
     This is  a  simulator  for  the  G/SPLINES  (genetic  spline  models)
     algorithm which builds spline-based functional models of experimental
     data, using CROSSOVER and MUTATION to evolve a POPULATION  towards  a
     better  fit.  It is derived from Friedman's MARS models. The original
     work  was  presented  at  ICGA-4,  and  further   results   including
     additional basis function types such as B-splines have been presented
     at the NIPS-91 meeting.

     Available at no cost via anonymous FTP by contacting the author; runs
     on  SUN (and possibly any SYSV) UNIX box. Macintosh version available
     on floppy disk for a $20 fee. Both versions can be redistributed  for
     noncommercial use. Simulator includes executable and C source code; a
     technical report (RIACS tech report 91.10) is also available.

      David Rogers
      MS Ellis, NASA Ames Research Center
      Moffett Field, CA 94035, USA

      Net: <[e-mail]>

 CFS-C:
     CFS-C 1.0 is a domain independent  collection  of  classifier  system
     routines written by Rick L. Riolo as part of his PhD dissertation.  A
     completely rewritten CFS-C++ is  planned  for  1994;  the  CFS-C  2.0
     mentioned  in  [SAB90] (e.g. "latent learning") will not be released;
     instead an ANSIfied version of 1.0 (CFS-C 1.98j)  is  available  from
     SAFIER and the SyS ftp server.

     CFS-C        is        available        from        SAFIER        as:
     sfi.santafe.edu:/pub/EC/CFS/src/cfsc-1.98j.tar.gz  and  includes  the
     original  1.02  CFS-C  in it's "cfsc/orig" folder after unpacking. On
     the     SyS     ftp      server      it's:      lumpi.informatik.uni-
     dortmund.de:/pub/CFS/src/cfsc-1.98j.tar.gz

     References

     Rick  L.  Riolo  (1988)  "CFS-C:  A  package  of  domain  independent
     subroutines for implementing classifier systems in  arbitrary,  user-
     defined environments", Logic of computers group, Division of computer
     science and engineering, University of Michigan.

     Rick  L.  Riolo  (1988)  "LETSEQ:  An  implementation  of  the  CFS-C
     classifier-system  in a task-domain that involves learning to predict
     letter sequences", Logic of computers  group,  Division  of  computer
     science and engineering, University of Michigan.




Issue 1.10               Posted: 20 December 1993                       19







FAQ(3/3)                          ANSWERS                         FAQ(3/3)



     Rick  L.  Riolo  (1988)  "CFS-C/FSW1:  An implementation of the CFS-C
     classifier system in a task domain that involves learning to traverse
     a finite state world", Logic of computers group, Division of computer
     science and engineering, University of Michigan.

 SCS-C:
     SCS-C is a (`mostly ANSI') C language translation  and  extension  of
     Goldberg's  Simple  Classifier  System, as presented in Appendix D in
     his seminal book "Genetic Algorithms  in  Search,  Optimization,  and
     Machine Learning", Addison-Wesley, Reading, MA, 1989.

     SCS-C  has been developed in parallel on a Sun 10/40 and an ATARI ST,
     and thus should be quite portable; it's distributed  free  of  charge
     and  the other terms of the GPL, i.e. the GNU General Public License.

     SCS-C   v0.99j   will   be    made    available    via    ftp    from
     lumpi.informatik.uni-dortmund.de  (129.217.36.140).  Log on with user
     name "ftp" and give your full e-mail address as  password.  The  file
     scs-c-0.99j.tar.gz  in  directory "pub/LCS/src" contains the complete
     software distribution; the documentation alone is available as scs-c-
     doc.tar.gz in directory "pub/LCS/docs".

     For more information contact:

      Joerg Heitkoetter
      Systems Analysis Research Group, LSXI
      Department of Computer Science
      University of Dortmund
      D-44221 Dortmund, Germany

      Net: <[e-mail]>
      Fax: [phone]


A20.2) Commercial software packages?
 EnGENEer:
     Logica  Cambridge  Ltd.  developed  EnGENEer  as  an in-house GENETIC
     ALGORITHM ENVIRONMENT to assist the development of GA applications on
     a wide range of domains. The software was written in C and runs under
     Unix as part of a consultancy and systems package. It  supports  both
     interactive  (X-Windows) and batch (command-line) modes of operation.

     EnGENEer provides a number of flexible  mechanisms  which  allow  the
     developer  to  rapidly  bring the power of GAs to bear on new problem
     domains.  Starting  with  the  Genetic  Description   Language,   the
     developer can describe, at high level, the structure of the ``genetic
     material'' used. The  language  supports  discrete  GENEs  with  user
     defined   cardinality   and   includes   features  such  as  multiple
     CHROMOSOMEs models, multiple SPECIES models and non-evolvable parsing
     symbols which can be used for decoding complex genetic material.




Issue 1.10               Posted: 20 December 1993                       20







FAQ(3/3)                          ANSWERS                         FAQ(3/3)



     The  user  also  has available a descriptive high level language, the
     Evolutionary Model Language. It allows the description of the GA type
     used  in  terms  of  configurable options including: population size,
     POPULATION structure and  source,  selection  method,  CROSSOVER  and
     MUTATION  type  and  probability,  INVERSION,  dispersal  method, and
     number of offspring per GENERATION.

     Both the Genetic Description  Language  and  the  Evolutionary  Model
     Language   are  fully  supported  within  the  interactive  interface
     (including online help system) and can be defined either "on the fly"
     or  loaded  from audit files which are automatically created during a
     GA run.

     Monitoring of GA progress is provided via both  graphical  tools  and
     automatic storage of results (at user defined intervals). This allows
     the user to restart EnGENEer from any point in a run, by loading both
     the POPULATION at that time and the evolutionary model that was being
     used.

     Connecting EnGENEer to  different  problem  domains  is  achieved  by
     specifying  the  name  of  the  program  used to evaluate the problem
     specific FITNESS function and constructing a simple  parsing  routine
     to   interpret   the   genetic   material.   A  library  of  standard
     interpretation  routines  are  also  provided   for   commonly   used
     representation  schemes  such  as gray-coding, permutations, etc. The
     fitness evaluation can then be run as either a slave process  to  the
     GA  or  via  a standard handshaking routines. Better still, it can be
     run on either the machine hosting the EnGENEer or on  any  sequential
     or parallel hardware capable of connecting to a Unix machine.

     For more information, contact:

      George Robbins
      Systems Intelligence Division
      Logica Cambridge Ltd.
      Betjeman House
      104 Hills Road
      Cambridge CB2 1LQ, UK

      Tel: [phone]
      Fax: [phone]

 EvoFrame:
     EvoFrame  is  to  Evolution  Strategies  what  MicroGA  is to Genetic
     Algorithms, a toolkit for application development  incorporating  ESs
     as the optimization engine.

     EvoFrame  is  an  object  oriented  implemented  programming tool for
     Evolution  Strategies   (Rechenberg/Schwefel,   Germany)   for   easy
     implementation and solution of numerical and combinatorical problems.
     EvoFrame  gives  you  freedom  of  implementing  every  byte  of  the



Issue 1.10               Posted: 20 December 1993                       21







FAQ(3/3)                          ANSWERS                         FAQ(3/3)



     optimization  principle  and its user interface. You can focus on the
     optimization problem and forget about all the rest.

     EvoFrame is available as Version 2.0 in Borland-Pascal 7.0 and Turbo-
     Vision  for  PC's and as Version 1.0 in C++ for Apple Macintosh using
     MPW   and   MacApp.    Both   implementations   allow   full    typed
     implementation,  i.e.   no  more  translation  from  problem specific
     format to an optimization  specific  one.   A  prototyping  tool  (cf
     REALizer) exists for both platforms too.

     EvoFrame  allows pseudoparallel optimization of many problems at once
     and you can switch optimization parameters and internal methods (i.e.
     quality  function etc.) during runtime and during optimization cycle.
     Both tools can  be  modified  or  extended  by  overloading  existing
     methods  for  experimental  use.  They  are  developed continously in
     correlation to new research results.

     The  PC  version  is  prepared  for  experimental  use   due   to   a
     comprehensive  protocolling  mechanism of optimzation cycles and user
     data. It also allows compilation of executable files  with  different
     complexity  by  setting conditional compilation flags. It can be used
     with 3 levels of stacked populations.

     The Mac version is the more complex  (recursive)  implementation.  It
     allows stacking of any number of populations for modelling of complex
     systems. Theory stops at multipopulation level at the time.  EvoFrame
     for  Mac  is  ready for the future, allowing any number of population
     levels.

     Ask for porting the Mac version (C++) to any other platform,  i.e.  X
     Windows.

 REALizer:
     REALizer  is  a  tool for rapid prototyping of EvoFrame applications.
     It's an override of the corresponding framework which is prepared  to
     optimize  using  a  vector  of real numbers. All methods for standard
     evolution  and  file  handling,  etc.  are  ready  implemented.   The
     remaining  work  for the user is to define a constant for the problem
     size, fill  in  the  quality  function  and  start  the  optimization
     process.
      .PP For further information, current prices and orders, contact:

      Wolfram Stebel
      Optimum Software
      Braunfelser Str. 26
      35578 Wetzlar, Germany

      Net: <[e-mail]>
      Tel: [phone]
      Fax: [phone]




Issue 1.10               Posted: 20 December 1993                       22







FAQ(3/3)                          ANSWERS                         FAQ(3/3)



 Evolver:
     Evolver   is  a  spreadsheet  add-in  which  incorporates  the  first
     commercially available GENETIC ALGORITHM  to  search  for  solutions.
     Evolver  can  be  customized  through  the  macro  language,  and  is
     available for $345 on 3.5'' or 5.25'' floppies for the  Excel,  WingZ
     and  Resolve  spreadsheets  on  the Mac and PC computers. For further
     information, contact:

      Axcelis, Inc.
      4668 Eastern Avenue North
      Seattle, WA 98103-6932, USA

      Tel: [phone]

     To order Evolver, contact:

      Spreadware Distributors
      P.O. Box 4552
      Palm Desert, CA 92261, USA

      Tel: [phone]
      Fax: [phone]

 GAME:
     GAME  (GA  Manipulation   Environment)   aims   to   demonstrate   GA
     applications and build a suitable programming environment.

     GAME  is  being  developed  as  part  of  the PAPAGENA project of the
     European Community's Esprit III initiative.

     GAME is available as an addendum to a  book  on  PGAs  (cf  PAPAGENA,
     Q20.3).  And from the project's FTP server bells.cs.ucl.ac.uk see the
     directories under "papagena", e.g. "papagena/game/docs" contains  all
     the  papers  that  have  been  produced  over  the course of the GAME
     project, e.g. you'll find a little bit outdated  draft  of  the  GAME
     DESIGN  NOTES  document,  which  explains  some of the details of the
     implementation. There are some other  technical  reports  also.   The
     sources  can also be obtained by ftp see "papagena/game/version2.01".

     GAME is now in version 2.01 (the version distributed  with  the  book
     was  1.0). This version is still able to run only sequential GAs, but
     version 3.0 is coming soon and will handle parallel GAs as well.

     Unfortunately, The project  yet  only  produced  a  Borland  C++  3.x
     version, so far.  It is intended to distribute a version for UNIX/GNU
     C++  as  well,  when  some  compatibility   issues   concerning   C++
     "standards"  have  been  resolved.  Afterward  a UNIX version will be
     released, but this will be  only  happen  after  the  release  of  PC
     version 3.0.





Issue 1.10               Posted: 20 December 1993                       23







FAQ(3/3)                          ANSWERS                         FAQ(3/3)



     Please, feel free to use and distribute the software.

     For more information contact:

      Jose Luiz Ribeiro Filho
      Department of Computer Science
      University College London
      Gower Street
      London WC1E 6BT, UK

      Net: <[e-mail]>
      Tel: [phone] x 3701
      Fax: [phone]

 MicroGA:
     MicroGA  is a powerful and flexible new tool which allows programmers
     to integrate GAs into their software quickly and  easily.  It  is  an
     object-oriented  C++  framework  that comes with full source code and
     documentation as well as three sample applications. Also included  is
     the  Galapagos  code  generator which allows users to create complete
     applications interactively without writing any C++ code, and a sample
     MacApp interface.

     MicroGA  is  available  for Macintosh II or higher with MPW and a C++
     compiler, and also in a Microsoft Windows version for PC compatibles.
     Compiled  applications  made with MicroGA can be sold without license
     fee. MicroGA is priced at $249.

 Galapagos:
     Galapagos is a tool for use with Emergent Behavior's MicroGA Toolkit.
     It  allows  a  user to define a function and set of constraints for a
     problem that the user wants to solve using the  GA.   Galapagos  then
     generates a complete C++ program using the information supplied. Then
     all the user has to do  is  to  compile  these  files,  using  either
     Turbo/Borland   C++  (PC,  MS  Windows),  or  MPW  and  C++  compiler
     (Macintosh), and link the resulting code to the MicroGA library. Then
     just  run  the  program.  Galapagos  comes  free  with  every copy of
     MicroGA.

     For further information and orders, contact:

      Steve Wilson
      Emergent Behavior
      635 Wellsbury Way
      Palo Alto, CA 94306, USA

      Net: <[e-mail]>
      Tel: [phone]

     MicroGA is distributed in Germany by Optimum Software (cf EvoFrame  &
     REALizer entries).



Issue 1.10               Posted: 20 December 1993                       24







FAQ(3/3)                          ANSWERS                         FAQ(3/3)



 Omega:
     The  Omega  Predictive Modeling System, marketed by KiQ Limited, is a
     powerful  approach  to  developing  predictive  models.  It  exploits
     advanced GA techniques to create a tool which is "flexible, powerful,
     informative and straightforward to  use".  Omega  is  geared  to  the
     financial  domain,  with applications in Direct Marketing, Insurance,
     Investigations  and  Credit  Management.   The   ENVIRONMENT   offers
     facilities  for  automatic handling of data; business, statistical or
     custom measures of PERFORMANCE, simple and complex  profit  modeling,
     validation   sample  tests,  advanced  confidence  tests,  real  time
     graphics, and optional control over the internal GA.

     For further information, contact:

      KiQ
      Business Modeling Systems Ltd.
      Easton Hall, Great Easton
      Essex CM6 2HD, UK

      Tel: [phone]

 OOGA, GENESIS:
     OOGA  (Object-Oriented  GA)  is  a  GENETIC  ALGORITHM  designed  for
     industrial  use.   It  includes examples accompanying the tutorial in
     the companion "Handbook of Genetic Algorithms". OOGA is designed such
     that each of the techniques employed by a GA is an object that may be
     modified, displayed or replaced in object-oriented fashion.  OOGA  is
     especially well-suited for INDIVIDUALs wishing to modify the basic GA
     techniques or tailor them to new domains.

     The buyer of OOGA also receives GENESIS,  a  generational  GA  system
     written  by  John  Grefenstette.  As  the  first  widely available GA
     program GENESIS has been very influential in stimulating the  use  of
     GAs,  and  several  other  GA  packages are based on it. This release
     sports an improved user interface.  OOGA and  GENESIS  are  available
     together  on  3.5''  or  5.25''  disk  for  $60  ($52.50 inside North
     America) by order from:

      The Software Partnership (T.S.P.)
      P.O. Box 991
      Melrose, MA 02176, USA

      Tel: [phone]

 PC-Beagle:
     PC-Beagle is a rule-finder program for PCs which examines a  database
     of  examples  and uses machine-learning techniques to create a set of
     decision rules for classifying those examples, thus turning data into
     knowledge.   The  system  contains six major components, one of which
     (HERB - the "Heuristic Evolutionary Rule Breeder") uses GA techniques
     to generate rules by natural selection.



Issue 1.10               Posted: 20 December 1993                       25







FAQ(3/3)                          ANSWERS                         FAQ(3/3)



     PC-Beagle  is  available to educational users for 69 pounds sterling.
     Orders, payment or requests for information should be addressed to:

      Richard Forsyth
      Pathway Research Ltd.
      59 Cranbrook Rd.
      Bristol BS6 7BS, UK

      Tel: [phone]

 XpertRule GenAsys:
     XpertRule GenAsys is an expert system  shell  with  embedded  GENETIC
     ALGORITHM  marketed  by  Attar Software. Targeted to solve scheduling
     and design applications, this system combines the  power  of  genetic
     algorithms  in  evolving  solutions  with  the  power  of  rule-based
     programming in analyzing the effectiveness of  solutions.  Rule-based
     programming  can  also be used to generate the initial POPULATION for
     the  genetic  algorithm  and  for  post-optimization  planning.  Some
     examples  of  design  and  scheduling problems which can be solved by
     this system include: optimization of design parameters in  electronic
     and  avionic  industries,  route  optimization  in  the  distribution
     sector, production scheduling in manufacturing, etc.

     For further information, contact:

      Attar Software
      Newlands Road
      Leigh, Lancashire, UK

      Net: <[e-mail]>
      Tel: [phone]
      Fax: [phone]

 XYpe:
     XYpe (The GA Engine) is a commercial GA application  and  development
     package  for  the Apple Macintosh. Its standard user interface allows
     you to design CHROMOSOMEs, set attributes of the genetic  engine  and
     graphically  display its progress. The development package provides a
     set of Think C libraries and include files for the design of  new  GA
     applications. XYpe supports adaptive operator weights and mixtures of
     alpha, binary, gray, ordering and real number codings.

     The price of $725 (in  Massachusetts  add  5%  sales  tax)  plus  $15
     shipping   and   handling   includes   technical  support  and  three
     documentation manuals.  XYpe requires a Macintosh SE  or  newer  with
     2MB  RAM  running  OS  V6.0.4  or  greater,  and Think C if using the
     development package.

     Currently the GA engine  is  working;  the  user  interface  will  be
     completed on demand. Interested parties should contact:




Issue 1.10               Posted: 20 December 1993                       26







FAQ(3/3)                          ANSWERS                         FAQ(3/3)



      Ed Swartz
      Virtual Image, Inc.
      75 Sandy Pond Road #11
      Ayer, MA 01432, USA

      Tel: [phone]


A20.3) Current research projects?
 PAPAGENA:
     The  European  ESPRIT III project PAPAGENA is pleased to announce the
     availability of the following book and software:

     Parallel Genetic Algorithms: Theory  and  Applications  was  recently
     published by IOS press. The book, edited by Joachim Stender, provides
     an overview  of  the  theoretical,  as  well  as  practical,  aspects
     involved   in  the  study  and  implementation  of  parallel  GENETIC
     ALGORITHMs (PGAs).

     The book comes with a floppy disk version of GAME (Genetic  Algorithm
     Manipulation Environment).  The disk contains the C++ source code for
     the sequential version the the GAME Virtual Machine. Also two  simple
     demonstration  examples  are  included  (an analytical function and a
     TSP) to illustrate the use of the VM.  Code is provided for both UNIX
     and MS-DOS.

     GAME  provides  a  general  purpose  toolkit  for the programming and
     simulation of a wide range of GA and PGA algorithms and applications.
     The   GAME   Environment  is  being  upgraded  to  include  graphical
     monitoring tools, and to allow for arbitrary levels of addressing for
     GA  manipulation (i.e., POPULATIONs can be broken down into arbitrary
     substructures  beyond  INDIVIDUALs,  CHROMOSOMEs,  and  GENEs,   with
     biological operators acting at all levels).

     For    more    information   contact:   Jose   Luiz   Ribeiro   Filho
     <[e-mail]> (please refer to the  section  on  GAME  above,
     that also lists the full affiliation/address).

 DGENESIS:
     Based on GENESIS 5.0, this project at ITAM (Mexico) aims to implement
     a distributed GA on a network of workstations.  For more information,
     contact Erick Cantu <[e-mail]>.


A21)  What  are  Gray codes, why to use them, how to efficiently implement
     them?
     The correct spelling is "Gray"---not  "gray",  "Grey",  or  "grey"---
     since Gray codes are named after the Frank Gray  who  patented  their
     use for shaft encoders in 1953  [1].   Gray  codes  actually  have  a
     longer history, and the inquisitive reader may want to  look  up  the
     August, 1972,  issue  of  Scientific  American,  which  contains  two



Issue 1.10               Posted: 20 December 1993                       27







FAQ(3/3)                          ANSWERS                         FAQ(3/3)



     articles of interest: one on the origin  of  binary  codes  [2],  and
     another by Martin  Gardner  on  some  entertaining  aspects  of  Gray
     codes [3].  Other references containing descriptions  of  Gray  codes
     and more modern, non-GA, applications include the second  edition  of
     Numerical  Recipes  [4],  Horowitz  and  Hill  [5],  Kozen  [6],  and
     Reingold [7].

     A Gray code represents  each  number  in  the  sequence  of  integers
     {0...2^N-1} as a binary string of length N  in  an  order  such  that
     adjacent integers have Gray code representations that differ in  only
     one bit position.  Marching through the  integer  sequence  therefore
     requires flipping just one bit at a time.  Some  call  this  defining
     property of Gray codes the "adjacency property" [8].

     Example (N=3):  The binary coding of {0...7} is {000, 001, 010,  011,
     100, 101, 110, 111}, while one Gray coding is {000,  001,  011,  010,
     110, 111, 101, 100}.  In essence, a Gray code takes a binary sequence
     and shuffles  it  to  form  some  new  sequence  with  the  adjacency
     property.  There exist,  therefore,  multiple  Gray  codings  or  any
     given N.  The example shown here belongs to a  class  of  Gray  codes
     that goes by the fancy name "binary-reflected Gray codes".  These are
     the most  commonly  seen  Gray  codes,  and  one  simple  scheme  for
     generationg such a Gray code sequence says, "start with all bits zero
     and successively flip the right-most bit that produces a new string."

     Hollstien [9] investigated the use of GAs for optimizing functions of
     two variables and claimed that  a  Gray  code  representation  worked
     slightly better than the binary representation.  He attrributed  this
     difference to the adjacency property of Gray codes.   Notice  in  the
     above example that the step from three to four requires the  flipping
     of all the bits in the binary representation.  In  general,  adjacent
     integers in the binary representaion often lie many bit flips  apart.
     This fact makes it less likely that a mutation  operator  can  effect
     small changes for a binary-coded individual.

     A Gray code representation seems to  improve  a  mutation  operator's
     chances of making incremental improvements, and a  close  examination
     suggests why.  In  a  binary-coded  string  of  length  N,  a  single
     mutation in the most significant  bit  (MSB)  alters  the  number  by
     2^(N-1).  In a Gray-coded string, fewer mutations lead  to  a  change
     this large.  The user of Gray codes does, however, pay  a  price  for
     this feature: those "fewer mutations" lead to  much  larger  changes.
     In the Gray code illustrated above, for example, a single mutation of
     the left-most bit changes a zero to a seven and vice-versa, while the
     largest change a single mutation can make to a corresponding  binary-
     coded individual is always four.  One might still view this aspect of
     Gray codes with some favor:  most  mutations  will  make  only  small
     changes, while the occasional  mutation  that  effects  a  truly  big
     change may initiate exploration of an  entirely  new  region  in  the
     space of chromosomes.




Issue 1.10               Posted: 20 December 1993                       28







FAQ(3/3)                          ANSWERS                         FAQ(3/3)



     The algorithm for converting between the binary-reflected  Gray  code
     described above  and  the  standard  binary  code  turns  out  to  be
     surprisingly simple to state.  First label the bits of a binary-coded
     string B[i], where larger i's represent more  significant  bits,  and
     similarly label the corresponding Gray-coded string G[i].  We convert
     one to the other as follows:  Copy the most  significant  bit.   Then
     for each smaller i  do  either  G[i] = XOR(B[i+1], B[i])---to convert
     binary to  Gray---or B[i] = XOR(B[i+1], G[i])---to  convert  Gray  to
     binary.

     One may easily implement the above algorithm in C.   Imagine  you  do
     something like

      typedef unsigned short      allele;

     and then use type "allele" for each bit in your chromosome, then  the
     following two functions will convert between  binary  and  Gray  code
     representations.  You must pass them the address  of  the  high-order
     bits for each of the two strings  as  well  as  the  length  of  each
     string.  (See  the  comment  statements  for  examples.)   NB:  These
     functions assume a chromosome arranged  as  shown  in  the  following
     illustration.

     index:    C[9]                                                    C[0]
           *-----------------------------------------------------------*
     Char C:   |  1  |  1  |  0  |  0  |  1  |  0  |  1  |  0  |  0  |  0  |
           *-----------------------------------------------------------*
           ^^^^^                                                 ^^^^^
           high-order bit                                  low-order bit

 C CODE
     /* Gray <==> binary conversion routines */
     /* written by Dan T. Abell, 7 October 1993 */
     /* please send any comments or suggestions */
     /* to [e-mail] */

     void gray_to_binary (Cg, Cb, n)
     /* convert chromosome of length n from */
     /* Gray code to binary representation */
     allele    *Cg,*Cb;
     int  n;
     {
      int j;

      *Cb = *Cg;               /* copy the high-order bit */
      for (j = 0; j < n; j++) {
           Cb--; Cg--;         /* for the remaining bits */
           *Cb= *(Cb+1)^*Cg;   /* do the appropriate XOR */
      }
     }




Issue 1.10               Posted: 20 December 1993                       29







FAQ(3/3)                          ANSWERS                         FAQ(3/3)



     void binary_to_gray(Cb, Cg, n)
     /* convert chromosome of length n from */
     /* binary to Gray code representation */
     allele    *Cb, *Cg;
     int  n;
     {
      int j;

      *Cg = *Cb;               /* copy the high-order bit */
      for (j = 0; j < n; j++) {
           Cg--; Cb--;         /* for the remaining bits */
           *Cg= *(Cb+1)^*Cb;   /* do the appropriate XOR */
      }
     }

     References

     [1] F. Gray, "Pulse Code Communication", U.  S.  Patent  2  632  058,
     March 17, 1953.

     [2]  F.  G.  Heath, "Origins of the Binary Code", Scientific American
     v.227,n.2 (August, 1972) p.76.

     [3]  Martin  Gardner,  "Mathematical  Games",   Scientific   American
     v.227,n.2 (August, 1972) p.106.

     [4]  William H. Press, et al., Numerical Recipes in C, Second Edition
     (Cambridge University Press, 1992).

     [5] Paul Horowitz and Winfield Hill, The Art of  Electronics,  Second
     Edition (Cambridge University Press, 1989).

     [6]  Dexter  Kozen,  The Design and Analysis of Algorithms (Springer-
     Verlag, New York, NY, 1992).

     [7] Edward M. Reingold, et al.,  Combinatorial  Algorithms  (Prentice
     Hall, Englewood Cliffs, NJ, 1977).

     [8]  David  E.  Goldberg, Genetic Algorithms in Search, Optimization,
     and Machine Learning (Addison-Wesley, Reading, MA, 1989).

     [9] R.  B.  Hollstien,  Artificial  Genetic  Adaptation  in  Computer
     Control Systems (PhD thesis, University of Michigan, 1971).


A42) What is Life all about?
     42

     References





Issue 1.10               Posted: 20 December 1993                       30







FAQ(3/3)                          ANSWERS                         FAQ(3/3)



     Adams, D. (1979) "The Hitch Hiker's Guide to the Galaxy", London: Pan
     Books.

     Adams, D. (1980) "The Restaurant at the End of the Universe", London:
     Pan Books.

     Adams,  D.  (1982)  "Life,  the Universe and Everything", London: Pan
     Books.

     Adams, D. (1984) "So long, and thanks for all the Fish", London:  Pan
     Books.

     Adams, D. (1992) "Mostly Harmless", London: Heinemann.


A42b) Is there a FAQ to this group?
     Yes.


A98) Any Patents on EAs?
     Process  patents  have  been  issued  both  for  the  Bucket  Brigade
     Algorithm (BBA) in classifier systems: U.S.  patent  #[..]  (to  John
     Holland) and for GP: U.S. patent #4,935,877 (to John Koza).

     This  FAQ  does  not attempt to provide legal advice. However, use of
     the Lisp code in the book [KOZA92] is freely  licensed  for  academic
     use.  Although  those  wishing  to make commercial use of any process
     should obviously consult any patent holders in question, it is pretty
     clear  that  it's  not  in  anyone's  best  interests to stifle GA/GP
     research and/or development. Commercial licenses much like those used
     for  CAD  software  can  presumably  be obtained for the use of these
     processes where necessary.

     There are currently no known patents  for  other  EA  paradigms;  but
     there  is  a  periodic  posting  on  comp.ai.neural-nets  by  Gregory
     Aharonian <[e-mail]> about patents on Artificial  Neural
     Networks (ANNs).


A99) A Glossary on EAs?
 A
     ADAPTIVE BEHAVIOUR:
      "...underlying  mechanisms  that allow animals, and potentially,
      ROBOTs to adapt and survive in uncertain environments" --- Meyer
      & Wilson (1991), [SAB90]

     AI:  See ARTIFICIAL INTELLIGENCE.

     ALIFE:
      See ARTIFICIAL LIFE.




Issue 1.10               Posted: 20 December 1993                       31







FAQ(3/3)                         GLOSSARY                         FAQ(3/3)



     ALLELE:
      (biol) Each GENE is able to occupy only a particular region of a
      CHROMOSOME, it's locus. At any given locus there may  exist,  in
      the POPULATION, alternative forms of the gene. These alternative
      are called alleles of one another.

      (EC) The value of a GENE.  Hence, for a  binary  representation,
      each gene may have an ALLELE of 0 or 1.

     ARTIFICIAL INTELLIGENCE:
      "...the  study  of  how to make computers do things at which, at
      the moment, people are better" --- Elaine  Rich (1988)

     ARTIFICIAL LIFE:
      Term coined by Christopher G.  Langton  for  his  1987  [ALIFEI]
      conference.  In  the preface of the proceedings he defines ALIFE
      as "...the study of simple computer generated hypothetical  life
      forms, i.e.  life-as-it-could-be."

 B
     BUILDING BLOCK:
      (EC)  A  small,  tightly clustered group of GENEs which have co-
      evolved  in  such  a  way  that  their  introduction  into   any
      CHROMOSOME  will  be  likely  to  give increased FITNESS to that
      chromosome.

      The "building block hypothesis"  [GOLDBERG89]  states  that  GAs
      find  solutions  by  first  finding  as  many BUILDING BLOCKs as
      possible, and then combining them together to give  the  highest
      FITNESS.

 C
     CENTRAL DOGMA:
      (biol)  The  dogma  that  nucleic acids act as templates for the
      synthesis of proteins, but never the  reverse.  More  generally,
      the dogma that GENEs exert an influence over the form of a body,
      but the form of a body is never  translated  back  into  genetic
      code: acquired characteristics are not inherited. cf LAMARCKISM.

      (GA) The dogma that the  behaviour  of  the  algorithm  must  be
      analysed using the SCHEMA THEOREM.

      (life in general) The dogma that this all is useful in a way.

      "You  guys  have  a dogma. A certain irrational set of believes.
      Well, here's  my  irrational  set  of  beliefs.  Something  that
      works."

      --- Rodney A. Brooks, [LEVY92]

     CHROMOSOME:



Issue 1.10               Posted: 20 December 1993                       32







FAQ(3/3)                         GLOSSARY                         FAQ(3/3)



      (biol)  One  of  the  chains of DNA found in cells.  CHROMOSOMEs
      contain GENEs, each encoded as a subsection of  the  DNA  chain.
      Chromosomes  are  usually  present  in all cells in an organism,
      even though only a minority of them will be active  in  any  one
      cell.

      (EC)  A datastructure which holds a `string' of task parameters,
      or GENEs.  This may be stored, for example,  as  a  binary  bit-
      string, or an array of integers.

     COMBINATORIAL OPTIMIZATION:
      Some tasks involve combining a set of entities in a specific way
      (e.g.  the task of building a house).  A  general  combinatorial
      task  involves deciding (a) the specifications of those entities
      (e.g. what size, shape, material to make the bricks  from),  and
      (b)  the  way in which those entities are brought together (e.g.
      the number of bricks, and  their  relative  positions).  If  the
      resulting  combination  of  entities  can in some way be given a
      FITNESS score, then COMBINATORIAL OPTIMIZATION is  the  task  of
      designing  a  set  of  entities,  and  deciding how they must be
      configured, so  as  to  give  maximum  fitness.  cf  ORDER-BASED
      PROBLEM.

     CROSSOVER:
      (EC)  A  REPRODUCTION  OPERATOR  which forms a new CHROMOSOME by
      combining parts  of  each  of  two  `parent'  chromosomes.   The
      simplest  form  is single-point CROSSOVER, in which an arbitrary
      point in the chromosome is  picked.  All  the  information  from
      parent  A  is  copied  from the start up to the crossover point,
      then all the information  from  parent  B  is  copied  from  the
      crossover point to the end of the chromosome. The new chromosome
      thus gets the head of one parent's chromosome combined with  the
      tail  of  the  other.   Variations exist which use more than one
      crossover point, or combine information from  parents  in  other
      ways.

      (biol)  A   complicated   process   whereby  CHROMOSOMEs,  while
      engaged in the  production  of  GAMETEs,  exchange  portions  of
      genetic material.  The result is that an almost infinite variety
      of  gametes  may  be  produced.   Subsequently,  during   sexual
      REPRODUCTION,  male and female gametes (i.e. sperm and ova) fuse
      to  produce  a  new  cell  with  a  complete  set   of   DIPLOID
      CHROMOSOMEs.

      In  [HOLLAND92]  the sentence "When sperm and ova fuse, matching
      CHROMOSOMEs line up with one another and then cross over partway
      along  their  length,  thus  swapping  genetic material" is thus
      wrong, since these two activities occur in  different  parts  of
      the  life  cycle.  [eds note:  If sexual REPRODUCTION (the  Real
      Thing) worked like in GAs, then Holland would be right,  but  as
      we  all  know,   it's   not   the  case.   We just encountered a



Issue 1.10               Posted: 20 December 1993                       33







FAQ(3/3)                         GLOSSARY                         FAQ(3/3)



      Freudian  slip  of  a  Grandmaster.  BTW:    even   the   German
      translation  of   this  article  has  this  "bug", although it's
      well-hidden by the translator.]

 D
     DARWINISM:
      (biol) Theory of EVOLUTION, proposed by Darwin,  that  evolution
      comes    about    through    random   variation   of   heritable
      characteristics, coupled with natural selection (survival of the
      fittest).  A  physical mechanism for this, in terms of GENEs and
      CHROMOSOMEs, was discovered many years later. cf LAMARCKISM.

      (EC) Theory which inspired all branches of EC.

     DECEPTION:
      The condition where the  combination  of  good  BUILDING  BLOCKs
      leads   to  reduced  FITNESS,  rather  than  increased  fitness.
      Proposed by [GOLDBERG89] as a reason for the failure of  GAs  on
      many tasks.

     DIPLOID CHROMOSOME:
      (biol)  A  CHROMOSOME  which  consists  of  a pair of homologous
      chromosomes, i.e. two chromosomes containing the same  GENEs  in
      the  same  sequence.  In sexually reproducing SPECIES, the genes
      in one of the chromosomes will  have  been  inherited  from  the
      father's GAMETE (sperm), while the genes in the other chromosome
      are from the mother's gamete (ovum).

     DNA: (biol) Deoxyribonucleic Acid, a double stranded macromolecule of
      helical  structure  (comparable  to  a  spiral  staircase). Both
      single strands are linear,  unbranched  nucleic  acid  molecules
      build  up  from  alternating  deoxyribose  (sugar) and phosphate
      molecules. Each deoxyribose part  is  coupled  to  a  nucleotide
      base,  which  is  responsible for establishing the connection to
      the other strand of the DNA.  The  4  nucleotide  bases  Adenine
      (A),  Thymine (T), Cytosine (C) and Guanine (G) are the alphabet
      of the genetic information. The sequences of these bases in  the
      DNA  molecule determines the building plan of any organism. [eds
      note: suggested reading: James  D.  Watson  (1968)  "The  Double
      Helix", London: Weidenfeld and Nicholson]

      (literature)  Douglas  Noel  Adams, contemporary Science Fiction
      comedy writer. Published "The Hitch-Hiker's Guide to the Galaxy"
      when  he  was  25 years old, which made him one of the currently
      most  successful  British  authors.   [eds  note:  interestingly
      Watson  was  also 25 years old, when he discovered the DNA; both
      events are probably not interconnected; you might also  want  to
      look  at:  Neil  Gaiman's  (1987)  "DON'T  PANIC -- The Official
      Hitch-Hiker's Guide to the Galaxy companion", and of course  get
      your  hands  on  the  wholly  remarkable FAQ in alt.fan.douglas-
      adams]



Issue 1.10               Posted: 20 December 1993                       34







FAQ(3/3)                         GLOSSARY                         FAQ(3/3)



     DNS: (biol) Desoxyribonukleinsaeure, German for DNA.

      (comp) The Domain Name System, a distributed database system for
      translating    computer    names   (e.g.   lumpi.informatik.uni-
      dortmund.de)   into   numeric   Internet,   i.e.    IP-addresses
      (129.217.36.140)  and  vice-versa.   DNS allows you to hook into
      the net without remembering long lists  of  numeric  references,
      unless  your  system  administrator  has incorrectly set-up your
      site's system.

 E
     EC:  See EVOLUTIONARY COMPUTATION.

     ENVIRONMENT:
      (biol) That which  surrounds  an  organism.  Can  be  'physical'
      (abiotic),  or  biotic.   In both, the organism occupies a NICHE
      which influences its FITNESS within the  total  ENVIRONMENT.   A
      biotic  environment  may  present   frequency-dependent  fitness
      functions within a  POPULATION,  that  is,  the  fitness  of  an
      organism's  behaviour  may  depend upon how many others are also
      doing it.  Over several  GENERATIONs,  biotic  environments  may
      foster   co-evolution,  in  which  fitness  is  determined  with
      selection partly by other SPECIES.

     EPISTASIS:
      (biol) A "masking" or "switching" effect among GENEs.  A biology
      textbook says: "A gene is said to be epistatic when its presence
      suppresses the effect of a gene  at  another  locus.   Epistatic
      genes  are  sometimes  called  inhibiting genes because of their
      effect on other genes which are described as hypostatic."

      (EC) When EC  researchers  use  the  term  EPISTASIS,  they  are
      generally  referring  to  any  kind  of strong interaction among
      GENEs, not just masking effects. A possible definition is:

      EPISTASIS is  the  interaction  between  different  GENEs  in  a
      CHROMOSOME.   It  is  the  extent  to  which the contribution to
      FITNESS of one gene depends on the values of other genes.

      Problems with little  or  no  EPISTASIS  are  trivial  to  solve
      (hillclimbing  is sufficient). But highly epistatic problems are
      difficult to solve, even for GAs.   High  epistasis  means  that
      BUILDING BLOCKs cannot form, and there will be DECEPTION.

     ESS: See EVOLUTIONARILY STABLE STRATEGY.

     EVOLUTION:
      That  process  of  change  which is assured given a reproductive
      POPULATION in which there are (1) varieties of INDIVIDUALs, with
      some  varieties being (2) heritable, of which some varieties (3)
      differ in FITNESS (reproductive success).



Issue 1.10               Posted: 20 December 1993                       35







FAQ(3/3)                         GLOSSARY                         FAQ(3/3)



      "Don't assume that all people who accept EVOLUTION are atheists"

      --- Talk.origin FAQ

     EVOLUTIONARILY STABLE STRATEGY:
      A  strategy that does well in a POPULATION dominated by the same
      strategy.  (cf Maynard Smith, 1974)

     EVOLUTIONARY COMPUTATION:
      Encompasses methods of simulating EVOLUTION on a computer.   The
      term  is  relatively new and represents an effort bring together
      researchers who have been working in closely related fields  but
      following  different  paradigms.   The  field  is  now  seen  as
      including research in GENETIC ALGORITHMs, evolution  strategies,
      evolutionary  programming, ARTIFICIAL LIFE, and so forth.  For a
      good overview see the editorial introduction to Vol. 1, No. 1 of
      "Evolutionary  Computation" (MIT Press, 1993).  That, along with
      the papers in  the  issue,  should  give  you  a  good  idea  of
      representative research.

     EXPLOITATION:
      When  traversing  a SEARCH SPACE, EXPLOITATION is the process of
      using information gathered from previously visited points in the
      search  space  to  determine which places might be profitable to
      visit next.  An  example  is  hillclimbing,  which  investigates
      adjacent  points in the search space, and moves in the direction
      giving  the  greatest   increase   in   FITNESS.    Exploitation
      techniques are good at finding local maxima.

     EXPLORATION:
      The  process of visiting entirely new regions of a SEARCH SPACE,
      to  see  if  anything  promising  may  be  found  there.  Unlike
      EXPLOITATION,  EXPLORATION  involves  leaps  into  the  unknown.
      Problems which have many local  maxima  can  sometimes  only  be
      solved by this sort of random search.

 F
     FITNESS:
      (biol)  Loosely:  adaptedness.  Often measured as, and sometimes
      equated to, relative reproductive success.  Also proportional to
      expected  time  to extinction.  "The fit are those who fit their
      existing ENVIRONMENTs and  whose  descendants  will  fit  future
      environments."   (J.  Thoday,  "A  Century  of  Darwin",  1959).
      Accidents of history are relevant.

      (EC) A value assigned to an INDIVIDUAL which reflects  how  well
      the  INDIVIDUAL solves the task in hand. A "fitness function" is
      used to map a CHROMOSOME to a FITNESS value.

     FUNCTION OPTIMIZATION:
      For a function which takes a set  of  N  input  parameters,  and



Issue 1.10               Posted: 20 December 1993                       36







FAQ(3/3)                         GLOSSARY                         FAQ(3/3)



      returns  a  single output value, F, FUNCTION OPTIMIZATION is the
      task of finding the  set(s)  of  parameters  which  produce  the
      maximum (or minimum) value of F. Function optimization is a type
      of VALUE-BASED PROBLEM.

     FUNCTION SET:
      (GP) The set of operators used in GP. These functions label  the
      internal (non-leaf) points of the parse trees that represent the
      programs in the POPULATION.  An example FUNCTION  SET  might  be
      {+, -, *}.

 G
     GA:  See GENETIC ALGORITHM.

     GAME THEORY:
      A  mathematical theory originally developed for human games, and
      generalized to human economics and  military  strategy,  and  to
      EVOLUTION in the theory of EVOLUTIONARILY STABLE STRATEGY.  GAME
      THEORY comes into it's own wherever the optimum  policy  is  not
      fixed,  but  depends upon the policy which is statistically most
      likely to be adopted by opponents.

     GAMETE:
      (biol) Cells which carry genetic information from their  parents
      for  the  purposes  of  sexual  REPRODUCTION.   In animals, male
      GAMETEs are called sperm, female gametes are called ova. Gametes
      have HAPLOID CHROMOSOMEs.

     GENE:
      (EC)  A  subsection  of a CHROMOSOME which (usually) encodes the
      value of a single parameter.

      (biol) A unit of heredity. May be defined in different ways  for
      different  purposes.  Molecular biologists sometimes use it in a
      more  abstract  sense.  Following  Williams  (cf   Q10.7)   `any
      hereditary  information  for  which  there  is  a  favorable  or
      unfavorable selection bias equal to several or  many  times  its
      rate of endogenous change.' cf CHROMOSOME.

     GENE-POOL:
      The  whole  set of GENEs in a breeding POPULATION.  The metaphor
      on which the term is based  de-emphasizes  the  undeniable  fact
      that  genes actually go about in discrete bodies, and emphasizes
      the idea of genes flowing about the world like a liquid.

      "Everybody out of the GENE-POOL, now!"

      --- Author prefers to be anonymous

     GENERATION:
      (EC) An iteration of the measurement of FITNESS and the creation



Issue 1.10               Posted: 20 December 1993                       37







FAQ(3/3)                         GLOSSARY                         FAQ(3/3)



      of a new POPULATION by means of REPRODUCTION OPERATORs.

     GENETIC ALGORITHM:
      A  type  of  EVOLUTIONARY  COMPUTATION  devised  by John Holland
      [HOLLAND92].   A  model  of  machine  learning   that   uses   a
      genetic/evolutionary  metaphor.  Implementations  typically  use
      fixed-length  character  strings  to  represent  their   genetic
      information.

     GENETIC DRIFT:
      Changes  in  gene/allele  frequencies  in a POPULATION over many
      GENERATIONs, resulting from chance rather than selection. Occurs
      most  rapidly  in  small  populations.  Can lead to some ALLELEs
      becoming `extinct', thus reducing the genetic variability in the
      population.

     GENETIC PROGRAMMING:
      GENETIC  ALGORITHMs applied to programs.  GENETIC PROGRAMMING is
      more expressive than fixed-length character string  GAs,  though
      GAs  are  likely  to  be  more  efficient  for  some  classes of
      problems.

     GENOME:
      The entire collection of GENEs (and hence CHROMOSOMEs) possessed
      by an organism.

     GP:  See GENETIC PROGRAMMING.

 H
     HAPLOID CHROMOSOME:
      (biol)  A  CHROMOSOME  consisting of a single sequence of GENEs.
      These are found in GAMETEs.  cf DIPLOID CHROMOSOME.

      In EC, it is usual for CHROMOSOMEs to be haploid.


 I
     INDIVIDUAL:
      A single  member  of  a  POPULATION.   In  EC,  each  INDIVIDUAL
      contains  a  CHROMOSOME  which represents a possible solution to
      the task being tackled, i.e. a single point in the SEARCH SPACE.
      Other  information is usually also stored in an each individual,
      e.g. its FITNESS.

     INVERSION:
      (EC) A REORDERING operator which  works  by  selecting  two  cut
      points in a CHROMOSOME, and reversing the order of all the GENEs
      between those two points.

 L
     LAMARCKISM:



Issue 1.10               Posted: 20 December 1993                       38







FAQ(3/3)                         GLOSSARY                         FAQ(3/3)



      Theory of EVOLUTION which preceded  Darwin's.  Lamarck  believed
      that  evolution  came  about through the inheritance of acquired
      characteristics. That is, the skills or physical features  which
      an  INDIVIDUAL  acquires during its lifetime can be passed on to
      its offspring.  Although Lamarckian inheritance  does  not  take
      place  in  nature, the idea has been usefully applied by some in
      EC.  cf DARWINISM.

 M
     MIGRATION:
      The transfer of (the GENEs  of)  an  INDIVIDUAL  from  one  SUB-
      POPULATION to another.

     MOBOT:
      MOBile ROBOT.  cf ROBOT.

     MUTATION:
      (EC)  a  REPRODUCTION  OPERATOR  which forms a new CHROMOSOME by
      making (usually small) alterations to the values of GENEs  in  a
      copy of a single, parent chromosome.

 N
     NICHE:
      (biol)  In  natural ecosystems, there are many different ways in
      which animals may survive (grazing, hunting, on the  ground,  in
      trees,   etc.),   and   each  survival  strategy  is  called  an
      "ecological niche."  SPECIES which occupy different NICHEs (e.g.
      one eating plants, the other eating insects) may coexist side by
      side without competition, in a stable way. But  if  two  species
      occupying  the  same niche are brought into the same area, there
      will be competition,  and  eventually  the  weaker  of  the  two
      species  will  be  made  (locally)  extinct.  Hence diversity of
      species depends on them occupying a diversity of niches  (or  on
      geographical separation).

      (EC)  In  EC,  we  often  want  to  maintain  diversity  in  the
      POPULATION.  Sometimes a FITNESS function may  be  known  to  be
      multimodal, and we want to locate all the peaks. We may consider
      each peak in the fitness function as analogous to a  NICHE.   By
      applying   techniques   such  as  fitness  sharing  (Goldberg  &
      Richardson, [ICGA87]), the  population  can  be  prevented  from
      converging  on a single peak, and instead stable SUB-POPULATIONs
      form at each  peak.  This  is  analogous  to  different  SPECIES
      occupying different niches. See also SPECIES, SPECIATION.

 O
     ORDER-BASED PROBLEM:
      A  problem  where  the solution must be specified in terms of an
      arrangement (e.g. a linear ordering)  of  specific  items,  e.g.
      TRAVELLING   SALESMAN   PROBLEM,  computer  process  scheduling.
      ORDER-BASED PROBLEMs are a class of  COMBINATORIAL  OPTIMIZATION



Issue 1.10               Posted: 20 December 1993                       39







FAQ(3/3)                         GLOSSARY                         FAQ(3/3)



      problems  in  which  the  entities  to  be  combined are already
      determined. cf VALUE-BASED PROBLEM.

     ONTOGENESIS:
      Refers to a single organism, and  means  the  life  span  of  an
      organism from it's birth to death.  cf PHYLOGENESIS.

 P
     PANMICTIC POPULATION:
      (EC,  biol)  A  mixed  POPULATION.   A  population  in which any
      INDIVIDUAL may  be  mated  with  any  other  individual  with  a
      probability  which  depends  only on FITNESS.  Most conventional
      evolutionary algorithms have PANMICTIC POPULATIONs.

      The opposite is a POPULATION divided into groups known  as  SUB-
      POPULATIONs,  where INDIVIDUALs may only mate with others in the
      same sub-population. cf SPECIATION.

     PERFORMANCE:
      cf FITNESS.

     PHYLOGENESIS:
      Refers to  a  POPULATION  of  organisms.  The  life  span  of  a
      POPULATION  of organisms from pre-historic times until today. cf
      ONTOGENESIS.

     POPULATION:
      A group of INDIVIDUALs which may interact together, for  example
      by mating, producing offspring, etc. Typical POPULATION sizes in
      EC range from 1  (for  certain  EVOLUTION  strategies)  to  many
      thousands (for GENETIC PROGRAMMING).  cf SUB-POPULATION.

 R
     RECOMBINATION:
      cf CROSSOVER.

     REORDERING:
      (EC)  A  REORDERING  operator  is  a REPRODUCTION OPERATOR which
      changes the order of GENEs in a CHROMOSOME,  with  the  hope  of
      bringing related genes closer together, thereby facilitating the
      production of BUILDING BLOCKs.  cf INVERSION.

     REPRODUCTION:
      (biol, EC) The creation of a new  INDIVIDUAL  from  two  parents
      (sexual  REPRODUCTION).  Asexual reproduction is the creation of
      a new individual from a single parent.

     REPRODUCTION OPERATOR:
      (EC) A mechanism which  influences  the  way  in  which  genetic
      information  is  passed  on  from  parent(s) to offspring during
      REPRODUCTION.  REPRODUCTION  OPERATORs  fall  into  three  broad



Issue 1.10               Posted: 20 December 1993                       40







FAQ(3/3)                         GLOSSARY                         FAQ(3/3)



      categories: CROSSOVER, MUTATION and REORDERING operators.

     ROBOT:
      "The  Encyclopedia  Galactica  defines  a  ROBOT as a mechanical
      apparatus designed to do the work of man. The marketing division
      of  the  Sirius Cybernetics Corporation defines a robot as `Your
      Plastic Pal Who's Fun To Be With'."

      --- Douglas Adams (1979)

 S
     SCHEMA:
      A pattern of GENE values in  a  CHROMOSOME,  which  may  include
      `dont  care'  states.  Thus  in a binary chromosome, each SCHEMA
      (plural schemata) can be specified  by  a  string  of  the  same
      length  as the chromosome, with each character one of {0, 1, #}.
      A particular chromosome is said to `contain' a particular schema
      if  it  matches the schema (e.g. chromosome 01101 matches schema
      #1#0#).

      The `order' of a SCHEMA is the number of non-dont-care positions
      specified,  while  the `defining length' is the distance between
      the furthest two non-dont-care positions. Thus #1#0# is of order
      2 and defining length 3.

     SCHEMA THEOREM:
      Theorem  devised by Holland [HOLLAND92] to explain the behaviour
      of GAs.  In essence, it  says  that  a  GA  gives  exponentially
      increasing   reproductive  trials  to  above  average  schemata.
      Because each CHROMOSOME contains a great many schemata, the rate
      of  SCHEMA processing in the POPULATION is very high, leading to
      a phenomenon known as implicit parallelism. This gives a GA with
      a  population  of  size  N  a  speedup  by  a factor of N cubed,
      compared to a random search.

     SEARCH SPACE:
      If the solution to a task can be represented by a set of N real-
      valued  parameters, then the job of finding this solution can be
      thought of as a  search  in  an  N-dimensional  space.  This  is
      referred  to simply as the SEARCH SPACE.  More generally, if the
      solution to a task can be  represented  using  a  representation
      scheme,  R,  then  the  search  space is the set of all possible
      configurations which may be represented in R.

     SPECIATION:
      (biol) The process whereby a new SPECIES comes about.  The  most
      common cause of SPECIATION is that of geographical isolation. If
      a SUB-POPULATION of a single species is separated geographically
      from  the  main  POPULATION  for a sufficiently long time, their
      GENEs will diverge  (either  due  to  differences  in  selection
      pressures  in  different  locations,  or  simply  due to GENETIC



Issue 1.10               Posted: 20 December 1993                       41







FAQ(3/3)                         GLOSSARY                         FAQ(3/3)



      DRIFT).  Eventually, genetic differences will be so  great  that
      members of the sub-population must be considered as belonging to
      a different (and new) species.

      SPECIATION is very important in evolutionary biology. Small SUB-
      POPULATIONs can evolve much more rapidly than a large POPULATION
      (because genetic changes don't take long to become fixed in  the
      population).  Sometimes,  this  EVOLUTION  will produce superior
      INDIVIDUALs which can outcompete,  and  eventually  replace  the
      SPECIES of the original, main population.

      (EC)  Techniques analogous to geographical isolation are used in
      a number of GAs.  Typically, the POPULATION is divided into SUB-
      POPULATIONs,  and  INDIVIDUALs  are  only  allowed  to mate with
      others in the same sub-population. (A small amount of  MIGRATION
      is performed.)

      This   produces  many  SUB-POPULATIONs  which  differ  in  their
      characteristics, and may be referred to as different  "species".
      This technique can be useful for finding multiple solutions to a
      problem, or simply maintaining diversity in the SEARCH SPACE.

      Most   biology/genetics   textbooks   contain   information   on
      SPECIATION.   A more detailed account can be found in "Genetics,
      Speciation and  the  Founder  Principle",  L.V.  Giddings,  K.Y.
      Kaneshiro  and  W.W.  Anderson  (Eds.),  Oxford University Press
      1989.

     SPECIES:
      (biol) There is  no  universally-agreed  firm  definition  of  a
      SPECIES.   A  species  may be roughly defined as a collection of
      living creatures,  having  similar  characteristics,  which  can
      breed  together  to  produce  viable  offspring similar to their
      parents. Members of  one  species  occupy  the  same  ecological
      NICHE.   (Members  of  different species may occupy the same, or
      different niches.)

      (EC) In EC the definition of  "species"  is  less  clear,  since
      generally  it is always possible for a pair INDIVIDUALs to breed
      together.  It is probably safest to use this term  only  in  the
      context   of   algorithms   which   employ  explicit  SPECIATION
      mechanisms.

      (biol) The  existence  of  different  SPECIES  allows  different
      ecological NICHEs to be exploited. Furthermore, the existence of
      a variety of different species itself creates new  niches,  thus
      allowing room for further species. Thus nature bootstraps itself
      into almost limitless complexity and diversity.

      Conversely, the domination of one, or a small number of  SPECIES
      reduces  the  number  of  viable  NICHEs,  leads to a decline in



Issue 1.10               Posted: 20 December 1993                       42







FAQ(3/3)                         GLOSSARY                         FAQ(3/3)



      diversity, and a reduction in  the  ability  to  cope  with  new
      situations.

      "Give any one SPECIES too much rope, and they'll fuck it up"

      --- Roger Waters, "Amused to Death", 1992

     SUB-POPULATION:
      A  POPULATION  may  be  sub-divided  into  groups, known as SUB-
      POPULATIONs, where INDIVIDUALs may only mate with others in  the
      same  group.  (This  technique  might  be  chosen  for  parallel
      processors).  Such  sub-divisions  may  markedly  influence  the
      evolutionary  dynamics of a population (e.g.  Wright's 'shifting
      balance' model).  Sub-populations  may  be  defined  by  various
      MIGRATION constraints: islands with limited arbitrary migration;
      stepping-stones   with   migration   to   neighboring   islands;
      isolation-by-distance  in  which each individual mates only with
      near neighbors. cf PANMICTIC POPULATION, SPECIATION.

     SUMMERSCHOOL:
      (USA) One of the most interesting things in the  US  educational
      system: class work during the summer break.

 T
     TERMINAL SET:
      (GP)  The  set  of  terminal  (leaf)  nodes  in  the parse trees
      representing the programs in the POPULATION.  A  terminal  might
      be a variable, such as X, a constant value, such as 42, (cf Q42)
      or a function taking no arguments, such as (move-north).

     TRAVELLING SALESMAN PROBLEM:
      The travelling salesperson has the task of visiting a number  of
      clients,  located  in different cities. The problem to solve is:
      in what order should the cities be visited in order to  minimise
      the total distance travelled (including returning home)? This is
      a classical example of an ORDER-BASED PROBLEM.

     TSP: See TRAVELLING SALESMAN PROBLEM.

 U
     USENET:
      "Usenet is like a herd of performing elephants with diarrhea  --
      massive, difficult to redirect, awe-inspiring, entertaining, and
      a source of mind-boggling amounts of excrement  when  you  least
      expect it."

      --- Gene Spafford (1992)

 V
     VALUE-BASED PROBLEM:
      A problem where the solution must be specified in terms of a set



Issue 1.10               Posted: 20 December 1993                       43







FAQ(3/3)                         GLOSSARY                         FAQ(3/3)



      of real-valued parameters.  FUNCTION OPTIMIZATION  problems  are
      of this type.  cf SEARCH SPACE, ORDER-BASED PROBLEM.

 Z
     ZEN NAVIGATION:
      A  methodology  with  tremendous propensity to get lost during a
      hike from A to B.  ZEN NAVIGATION  simply  consists  in  finding
      something  that  looks  as  if  it knew where it is going to and
      follow  it.   The  results  are  more  often   surprising   than
      successful, but it's usually being worth for the sake of the few
      occasions when it is both.

      Sometimes ZEN NAVIGATION is referred  to  as  "doing  scientific
      research,"  where  A is a state of mind being considered as pre-
      PhD, and B (usually a different) state of mind, known  as  post-
      PhD. While your time spent in state C, somewhere inbetween A and
      B, is usually referred to as "being a nobody."


ACKNOWLEDGMENTS
     Finally, credit where credit is due. I'd like to thank all the people
     who  helped  in  assembling  this  guide,  and their patience with my
     "variations on English  grammar".  In  the  order  I  received  their
     contributions, thanks to:

 Contributors,
     Lutz  Prechelt  (University  of  Karlsruhe)  the  comp.ai.neural-nets
     FAQmeister, for letting  me  strip  several  ideas  from  "his"  FAQ.
     Ritesh  "peace"  Bansal  (CMU)  for  lots of comments and references.
     David  Beasley  (University  of  Wales)  for  a  valuable   list   of
     publications  (Q12),  and many further additions.  David Corne, Peter
     Ross,  and  Hsiao-Lan  Fang  (University  of  Edinburgh)  for   their
     TIMETABLING  and  JSSP  entries.   Mark  Kantrowitz (CMU) for mocking
     about this-and-that, and being a "mostly valuable" source  concerning
     FAQ  maintenance;  parts  of  A11  have  been stripped from "his" ai-
     faq/part4 FAQ; Mark also contributed the less verbose ARCHIVE  SERVER
     infos.   The  texts  of  Q1.1,  Q1.5, Q98 and some entries of Q99 are
     courtesy by James  Rice  (Stanford  University),  stripped  from  his
     genetic-programming  FAQ  (Q15).   Jonathan  I. Kamens (MIT) provided
     infos on how-to-hook-into the USENET FAQ  system.   Una  Smith  (Yale
     University)  contributed  the  better parts of the Internet resources
     guide  (Q15.5).   Daniel   Polani   (Gutenberg   University,   Mainz)
     "contributed"  the  Alife  II  Video  proceedings  info.   Jim  McCoy
     (University of Texas) reminded me of  the  GP  archive  he  maintains
     (Q20).   Ron Goldthwaite (UC Davis) added definitions of Environment,
     Evolution, Fitness, and Population to the glossary, and some thoughts
     why   Biologists  should  take  note  of  EC  (Q3).   Joachim  Geidel
     (University of Karlsruhe) sent a diff of the  current  "navy  server"
     contents  and the software survey, pointing to "missing links" (Q20).
     Richard Dawkins "Glossary" section of "The extended phenotype" served
     for many new entries, too numerous to mention here (Q99).  Mark Davis



Issue 1.10               Posted: 20 December 1993                       44







FAQ(3/3)                         GLOSSARY                         FAQ(3/3)



     (New  Mexico  State  University)  wrote  the  part  on   Evolutionary
     Programming  (Q1.2).   Dan Abell (University of Maryland) contributed
     the section on efficient greycoding (Q21).  Walter Harms  (University
     of  Oldenburg)  commented  on introductory EC literature.  Lieutenant
     Colonel J.S. Robertson (USMA, West Point), for providing a  home  for
     this      subversive      posting     on     their     FTP     server
     euler.math.usma.edu:/pub/misc/GA.  Rosie O'Neill for  suggesting  the
     PhD thesis entry (Q10.11).  Charlie Pearce (University of Nottingham)
     for critical remarks concerning "tables"; well, here  they  are!   J.
     Ribeiro Filho (University College London) for the pointer to the IEEE
     Computer GA  Software  Survey;  the  PeGAsuS  description  (Q20)  was
     stripped from it.

 Reviewers,
     Robert  Elliott  Smith  (The University of Alabama) reviewed the TCGA
     infos (Q14), and Nici Schraudolph (UCSD) first  unconsciously,  later
     consciously, provided about 97% of Q20* answers.  Nicheal Lynn Cramer
     (BBN) adjusted my historic view of GP genesis.  David Fogel (ORINCON)
     commented and helped on this-and-that (where this-and-that is closely
     related to EP).  Kazuhiro M. Saito (MIT) and Mark  D.  Smucker  (Iowa
     State)  caught  my favorite typo(s).  Craig W. Reynolds was the first
     who solved one of the well-hidden puzzles in the FAQ, and also  added
     some  valuable stuff.  Joachim Born (TU Berlin) updated the Evolution
     Machine (EM) entry and provided the pointer to the Bionics  technical
     report  ftp  site  (Q14).   Pattie  Maes (MIT Media Lab) reviewed the
     ALIFE IV additions to the list of conferences (Q12).  Scott D. Yelich
     (Santa Fe Institute) reviewed the SFI connectivity entry (Q15).  Rick
     Riolo (MERIT) reviewed the CFS-C entry (Q20).  And  Davika  Seunarine
     (Acadia Univ.)  for smoothing out this and that.

 and Everybody...
     Last  not  least  I'd like to thank Hans-Paul Schwefel, Thomas Baeck,
     Frank Kursawe, Guenter Rudolph for  their  respective  contributions,
     and  the  rest  of  the  Systems  Analysis  Research Group for wholly
     remarkable patience and almost incredible  unflappability  during  my
     various  extravangances and ego-trips during my time (1990-1993) with
     this group.

     It was a tremendously worthwhile experience.  Thanks!







       "And all our yesterdays have lighted fools; the way to dusty death;
    out, out brief candle; life's but a walking shadow; a poor player;
      that struts and gets his hour upon the stage; and then is heared
       no more; it is a tale; told by an idiot, full of sound an fury,
                              signifying nothing."



Issue 1.10               Posted: 20 December 1993                       45







FAQ(3/3)                         GLOSSARY                         FAQ(3/3)



                          --- Shakespeare, Macbeth


                                 EPILOGUE
              "Natural selection is a mechanism for generating
                 an exceedingly high degree of improbability."

                  --- Sir Ronald Aylmer Fisher (1890-1962)


     This is a GREAT quotation, it sounds like something directly out of a
    turn of the century Douglas Adams: Natural selection: the original
                        "Infinite Improbability Drive"

             --- Craig Reynolds, on reading the previous quote

     "`The  Babel  fish,'  said  The  Hitch  Hiker's  Guide  to the Galaxy
     quietly, `is small, yellow and leech-like, and  probably  the  oddest
     thing  in  the  Universe.   It feeds on brainwave energy received not
     from his own carrier  but  from  those  around  it.  It  absorbs  all
     unconscious  mental frequencies from this brainwave energy to nourish
     itself with.  It then  excretes  into  the  mind  of  its  carrier  a
     telepathic   matrix   formed   by  combining  the  conscious  thought
     frequencies with nerve signals picked up from the speech  centers  of
     the  brain which has supplied them.  The practical upshot of all this
     is that if you stick a Babel fish  in  your  ear  you  can  instantly
     understand  anything  said to you in any form of language. The speech
     patterns you actually hear decode the brainwave matrix which has been
     fed  into  your mind by your Babel fish.  `Now it is such a bizarrely
     improbable coincidence than anything so mindbogglingly  useful  could
     have  evolved  purely by chance that some thinkers have chosen to see
     it as a final and clinching proof of the non-existence of God.   `The
     argument  goes  something  like  this:  ``I  refuse  to  prove that I
     exist,'' says God, ``for proof denies faith, and without faith  I  am
     nothing.''   ``But,''  says  Man, ``The Babel fish is a dead giveaway
     isn't it?  It could not have evolved by chance. It proves you  exist,
     and  so  therefore,  by  your  own arguments, you don't. QED.''  ``Oh
     dear,'' says God, ``I hadn't thought of that,'' and promptly vanishes
     in  a  puff  of  logic.   ``Oh, that was easy,'' says Man, and for an
     encore goes on to prove that black is white and gets  himself  killed
     on the next zebra crossing."

                          --- Douglas Adams (1979)

     "Well, people; I really wish this thingie to turn into a paper babel-
     fish for all those young ape-descended organic  life  forms  on  this
     crazy  planet,  who don't have any clue about what's going on in this
     exciting  "new"  research  field,  called  Evolutionary  Computation.
     However,  this  is  just  a  start,  I need your help to increase the
     usefulness of this guide, especially  its  readability  for  natively
     English  speaking  folks;  whatever  it  is:  I'd  like  to hear from



Issue 1.10               Posted: 20 December 1993                       46







FAQ(3/3)                         EPILOGUE                         FAQ(3/3)



     you...!"

                                --- The Editor

           "Parents of young organic life forms should be warned, that
       paper babel-fishes can be harmful, if stuck too deep into the ear."

                        --- Encyclopedia Galactica














































Issue 1.10               Posted: 20 December 1993                       47



--

    -joke

--
Joerg Heitkoetter
Systems Analysis Group                     "Why was I born with such
University of Dortmund, Germany             contemporaries?"
<[e-mail]>                -- Oscar Wilde