home *** CD-ROM | disk | FTP | other *** search
/ Nebula 1994 June / NEBULA_SE.ISO / Documents / FAQ / AI-faq / genetic / part1 < prev    next >
Encoding:
Internet Message Format  |  1993-08-21  |  67.5 KB
  1. Path: senator-bedfellow.mit.edu!bloom-beacon.mit.edu!gatech!howland.reston.ans.net!europa.eng.gtefsd.com!uunet!mcsun!Germany.EU.net!Informatik.Uni-Dortmund.DE!lusty!heitkoet
  2. From: joke@ls11.informatik.uni-dortmund.de (Joerg Heitkoetter)
  3. Newsgroups: comp.ai.genetic,comp.answers,news.answers
  4. Subject: FAQ: comp.ai.genetic part 1/3 (A Guide to Frequently Asked Questions)
  5. Supersedes: <part1_743188477@lusty.informatik.uni-dortmund.de>
  6. Followup-To: comp.ai.genetic
  7. Date: 20 Aug 1993 13:57:14 GMT
  8. Organization: CS Department, University of Dortmund, Germany
  9. Lines: 1786
  10. Approved: news-answers-request@MIT.Edu
  11. Expires: 3 Oct 1993 13:57:09 GMT
  12. Message-ID: <part1_745855029@lusty.informatik.uni-dortmund.de>
  13. References: <NEWS_745855029@lusty.informatik.uni-dortmund.de>
  14. NNTP-Posting-Host: lusty.informatik.uni-dortmund.de
  15. Summary: This is part 1 of a trilogy entitled "The Hitch-Hiker's Guide
  16.      to Evolutionary Computation". A monthly published list of Frequently
  17.      Asked Questions (and their answers) about Evolutionary Algorithms,
  18.      Life and Everything. It should be read by anyone who whishes to post
  19.      to the comp.ai.genetic newsgroup, preferably *before* posting.
  20. Originator: joke@ls11.informatik.uni-dortmund.de (Joerg Heitkoetter)
  21. Xref: senator-bedfellow.mit.edu comp.ai.genetic:1182 comp.answers:1671 news.answers:11622
  22.  
  23. Archive-name:    ai-faq/genetic/part1
  24. Last-Modified:    08/20/93
  25. Version:    0.6
  26.  
  27.  
  28.  
  29.  
  30.  
  31. FAQ(1/3)                      COMP.AI.GENETIC                     FAQ(1/3)
  32.  
  33.  
  34.  
  35.      [eds  note:  This  is a preliminary version, ie. a "proposal", of the
  36.      forthcoming FAQ to comp.ai.genetic. If you  want  to  contribute  new
  37.      items,  make  corrections, or want to fill in a "[..]" template, drop
  38.      me a mail.]
  39.  
  40.  
  41.  
  42.  
  43.  
  44.  
  45.  
  46.  
  47.                       The
  48.                  Hitch-Hiker's
  49.                    Guide to
  50.                Evolutionary Computation
  51.                (FAQ in comp.ai.genetic)
  52.  
  53.                    edited by
  54.  
  55.                    Joerg Heitkoetter
  56.              Systems Analysis Research Group, LSXI
  57.             Department of Computer Science
  58.                 University of Dortmund
  59.                D-44221 Dortmund, Germany
  60.             <joke@ls11.informatik.uni-dortmund.de>
  61.  
  62.            (Usually FAQ means "Frequently Asked Questions,"
  63.              though it's sometimes referred to as
  64.                "Familiar Awkward Questions" ;-)
  65.  
  66.                PLEASE, SEARCH THIS POSTING FIRST
  67.                 IF YOU HAVE A QUESTION
  68.                       and
  69.               DON'T POST ANSWERS TO FAQs:
  70.             POINT THE ASKER TO THIS POSTING
  71.                       and
  72.                   DON'T PANIC
  73.  
  74.      FAQ  /F-A-Q/ or /fak/ [USENET] n.  1. A  Frequently  Asked  Question.
  75.       2.  A  compendium  of  accumulated  lore, posted periodically to
  76.       high-volume  newsgroups  in  an  attempt   to   forestall   such
  77.       questions.   Some  people  prefer  the term `FAQ list' or `FAQL'
  78.       /fa'kl/, reserving `FAQ' for sense 1.
  79.  
  80.      FAQ list
  81.       /F-A-Q list/ or /fak list/ [USENET] n.  Syn FAQ, sense 2.
  82.  
  83.      FAQL /fa'kl/ n. Syn. FAQ list.
  84.  
  85.      RTFAQ
  86.  
  87.  
  88.  
  89. Version 0.6               Posted: 20 August 1993                         1
  90.  
  91.  
  92.  
  93.  
  94.  
  95.  
  96.  
  97. FAQ(1/3)                          PREFACE                         FAQ(1/3)
  98.  
  99.  
  100.  
  101.       /R-T-F-A-Q/ [USENET: primarily written, by  analogy  with  RTFM]
  102.       imp. Abbrev. for `Read the FAQ!', an exhortation that the person
  103.       addressed ought to read the newsgroup's FAQ list before  posting
  104.       questions.   RTFM  /R-T-F-M/  [UNIX]  imp. Acronym for `Read The
  105.       Fucking Manual'.  1. Used by gurus to brush off  questions  they
  106.       consider  trivial or annoying.  Compare Don't do that, then!  2.
  107.       Used when reporting a problem to indicate that you  aren't  just
  108.       asking  out  of  randomness.   "No,  I  can't  figure out how to
  109.       interface UNIX to my toaster, and yes,  I  have  RTFM."   Unlike
  110.       sense  1,  this  use  is considered polite.  See also FM, RTFAQ,
  111.       RTFB, RTFS, RTM, all of which mutated  from  RTFM,  and  compare
  112.       UTSL.
  113.  
  114.            --- "The on-line hacker Jargon File, version 2.9.12, 10 May
  115.           1993",      available via anon. ftp to ftp.gnu.ai.mit.edu in
  116.                                 "/pub/gnu"
  117.  
  118. PREFACE
  119.      This  posting  is  intended  to  help, provide basic information, and
  120.      serve as a "first straw" for  individuals,  ie.   uninitiated  hitch-
  121.      hikers, who are stranded in the mindboggling universe of Evolutionary
  122.      Computation (EC); that in turn is only a small footpath  to  an  even
  123.      more  mindboggling  scientific  universe,  that,  incorporating Fuzzy
  124.      Systems, and Artificial Neural Networks, is sometimes referred to  as
  125.      Computational Intelligence (CI); that in turn is only part of an even
  126.      more advanced scientific universe of mindparalysing complexity,  that
  127.      incorporating  Artificial  Life,  Fractal Geometry, and other Complex
  128.      Systems Sciences might someday be referred to as Natural  Computation
  129.      (NC).
  130.  
  131.      Over  the  course  of  the past years, GLOBAL OPTIMIZATION ALGORITHMS
  132.      imitating certain principles of nature have proved  their  usefulness
  133.      in  various  domains of applications. Especially those principles are
  134.      worth copying where nature has found "stable islands" in a "turbulent
  135.      ocean"  of  solution  possibilities.  Such  phenomena can be found in
  136.      annealing processes, central nervous systems and biological evolution
  137.      which  in  turn  have  lead  to  the  following optimization methods:
  138.      Simulated Annealing (SA), Artificial Neural Networks (ANNs)  and  the
  139.      field of Evolutionary Computation (EC).
  140.  
  141.      EC  may currently be characterized by the following pathways: Genetic
  142.      Algorithms (GA), Evolutionary Programming (EP), Evolution  Strategies
  143.      (ES), Classifier Systems (CFS), Genetic Programming (GP), and several
  144.      other problem solving strategies,  that  are  based  upon  biological
  145.      observations,  that  date back to CHARLES DARWIN's discoveries in the
  146.      19th century: the means of natural selection and the survival of  the
  147.      fittest,  ie.  the "theory of evolution." The inspired algorithms are
  148.      thus termed Evolutionary Algorithms (EA).
  149.  
  150.      Moreover, is this posting intended to introduce and help  those,  who
  151.      are just beginning to read this newsgroup, and those who are new "on"
  152.  
  153.  
  154.  
  155. Version 0.6               Posted: 20 August 1993                         2
  156.  
  157.  
  158.  
  159.  
  160.  
  161.  
  162.  
  163. FAQ(1/3)                          PREFACE                         FAQ(1/3)
  164.  
  165.  
  166.  
  167.      USENET.  It shall help to avoid lengthy discussions of questions that
  168.      usually  arise for beginners of one or the other kind, and are boring
  169.      to read again and again by comp.ai.genetic "old-timers."
  170.  
  171.      You will see this  posting  popping  up  each  month  in  the  USENET
  172.      newsgroup  comp.ai.genetic (including comp.answers, and news.answers,
  173.      where it should be locatable at ANY time).
  174.  
  175.  
  176. CONTRIBUTIONS
  177.      Contributions are always welcome. Send e-mail to the  current  editor
  178.      of  this  posting,  as  stated somewhere above, if it is relevant, it
  179.      will be incorporated. (Please format your contribution  appropriately
  180.      so  it  can  just  be  dropped in. Unformatted contributions however,
  181.      won't be rejected.)
  182.  
  183.  
  184. ARCHIVE SERVICE
  185.      This posting (like all other FAQs, ie. the essence of  the  knowledge
  186.      floating   through   USENET)   is   available   between  postings  on
  187.      rtfm.mit.edu in the directory "/pub/usenet/news.answers" as the files
  188.      ai-faq/genetic/part?.  The  FAQ  may also be retrieved by e-mail from
  189.      <mail-server@rtfm.mit.edu>. Send a message to  the  mail-server  with
  190.      "help"   and   "index"  in  the  body  on  separate  lines  for  more
  191.      information.
  192.  
  193.  
  194. DISCLAIMER
  195.      This monthly posting is not meant to discuss any topic  exhaustively,
  196.      but  should  be  thought of as a list of reference pointers, instead.
  197.      This posting is provided on an "as is" basis, NO WARRANTY  whatsoever
  198.      is expressed or implied, especially, NO WARRANTY that the information
  199.      contained herein is correct or useful in any way,  although  both  is
  200.      intended.  However, please note that the opinions expressed herein do
  201.      not necessarily reflect those of the Systems Analysis Research Group,
  202.      neither as a whole, nor in part, they are just mine.
  203.  
  204.  
  205. HITCH-HIKING THE FAQNIVERSE
  206.      This  guide  is  big.  Really big. You just won't believe how hugely,
  207.      vastly, mindbogglingly big it is. That's why it has been split into a
  208.      trilogy,   ie.   it   can   be   pieced   together  from  files  "ai-
  209.      faq/genetic/part1",      "ai-faq/genetic/part2",       and       "ai-
  210.      faq/genetic/part3".
  211.  
  212.  Searching for answers
  213.      To  find  the answer of question number x, just search for the string
  214.      "Ax)" (so the answer to question "Q42:" is at "A42)")
  215.  
  216.  What does, eg. [ICGA85] mean?
  217.  
  218.  
  219.  
  220.  
  221. Version 0.6               Posted: 20 August 1993                         3
  222.  
  223.  
  224.  
  225.  
  226.  
  227.  
  228.  
  229. FAQ(1/3)                          PREFACE                         FAQ(1/3)
  230.  
  231.  
  232.  
  233.      Some books would be referenced again and again, that's why  they  got
  234.      this  kind  of "tag", that an experienced hitch-hiker will search for
  235.      to dissolve the riddle.
  236.  
  237.  Why all this UPPERCASING in running text?
  238.      Some words are written in all uppercase letters, eg.  EVOLUTION,  you
  239.      will find these reappearing in the Glossary (cf A99).
  240.  
  241.  Referencing this Guide
  242.      If  you  want  to  reference this guide (although I have currently no
  243.      idea, why you should want to do this), I'd be insanely  proud  if  it
  244.      looks like:
  245.  
  246.      Heitkoetter,   Joerg,   ed.    (1993)  "The  Hitch-Hiker's  Guide  to
  247.      Evolutionary  Computation:  A  list  of  Frequently  Asked  Questions
  248.      (FAQ)",  Usenet:  comp.ai.genetic.   Available via anonymous ftp from
  249.      rtfm.mit.edu  in  pub/usenet/news.answers/ai-faq/genetic/part?.   ~60
  250.      pages.   Or simply call it "the Guide", or "HHGEC" for acronymaniacs.
  251.  
  252.  Obtaining a PostScript version
  253.      For innumerable reasons this guide is written using an ancient,  good
  254.      old-fashioned  UNIX  text formatting utility, namely troff(1); better
  255.      to say the GNU version groff(1) and a hacked macro package  based  on
  256.      "tmac.an";  it's  thus  easy to generate ASCII (posted), TeX DVI (not
  257.      posted), and PostScript (ftpable) versions from a unique source.  The
  258.      latter,  looks really crisp (using boldface, italics, etc.), and thus
  259.      is available for those who prefer offline  reading.   Look  for  file
  260.      "/pub/EA/docs/hhgec.ps.Z"       on      the      SyS      ftp-server:
  261.      lumpi.informatik.uni-dortmund.de (129.217.36.140).
  262.  
  263.  The ZEN Puzzle
  264.      For some weird reason this guide contains some puzzles which can only
  265.      be  solved  by  cautious  readers  who have (1) a certain amount of a
  266.      certain kind of humor, (2) a certain amount of patience and time, (3)
  267.      a  certain  amount of experience in ZEN navigation, and (4) a certain
  268.      amount of books of a certain author.
  269.  
  270.      Usually, puzzles search either for certain answers (more  often,  ONE
  271.      answer)  to  a  question;  or,  for the real smartasses, sometimes an
  272.      answer is presented, and a certain question  is  searched  for.   ZEN
  273.      puzzles are even more challenging: you have to come up with an answer
  274.      to a question, both of which are not  explicitly,  rather  implicitly
  275.      stated  somewhere  in  this  FAQ.  Thus,  you are expected to give an
  276.      answer AND a question!
  277.  
  278.      To give an impression what this is all about, consider the following,
  279.      submitted  by  Craig  W.  Reynolds.  The correct question is: "Why is
  280.      Fisher's `improbability quote' (cf EPILOGUE) included in this  FAQ?",
  281.      Craig's correct answer is: `This is a GREAT quotation, it sounds like
  282.      something directly out of  a  turn  of  the  century  Douglas  Adams:
  283.      Natural  selection:  the original "Infinite Improbability Drive"' Got
  284.  
  285.  
  286.  
  287. Version 0.6               Posted: 20 August 1993                         4
  288.  
  289.  
  290.  
  291.  
  292.  
  293.  
  294.  
  295. FAQ(1/3)                          PREFACE                         FAQ(1/3)
  296.  
  297.  
  298.  
  299.      the message? Well, this was easy and very obvious. The other  puzzles
  300.      are more challenging...
  301.  
  302.      However,  all  this is just for fun (mine and hopefully yours), there
  303.      is nothing like the $100 price, some big shots in  computer  science,
  304.      eg.  Don Knuth usually offer; all there is but a honorable mentioning
  305.      of the ZEN navigator, including the puzzle  s/he  solved.  It's  thus
  306.      like  in  real life: don't expect to make money from the time being a
  307.      scientist, it's all just for the fun of it...
  308.  
  309.      Welcome aboard. Enjoy the trip!
  310.  
  311.  
  312.  
  313.  
  314.  
  315.  
  316.  
  317.  
  318.  
  319.  
  320.  
  321.  
  322.  
  323.  
  324.  
  325.  
  326.  
  327.  
  328.  
  329.  
  330.  
  331.  
  332.  
  333.  
  334.  
  335.  
  336.  
  337.  
  338.  
  339.  
  340.  
  341.  
  342.  
  343.  
  344.  
  345.  
  346.  
  347.  
  348.  
  349.  
  350.  
  351.  
  352.  
  353. Version 0.6               Posted: 20 August 1993                         5
  354.  
  355.  
  356.  
  357.  
  358.  
  359.  
  360.  
  361. FAQ(1/3)                     TABLE OF CONTENTS                    FAQ(1/3)
  362.  
  363.  
  364.  
  365. TABLE OF CONTENTS
  366.  ai-faq/genetic/part1
  367.      Q0:    What is this newsgroup for? How shall it be used?
  368.  
  369.      Q1:    What are Evolutionary Algorithms (EAs)?
  370.  
  371.      Q1.1:  What's a Genetic Algorithm (GA)?
  372.  
  373.      Q1.2:  What's Evolutionary Programming (EP)?
  374.  
  375.      Q1.3:  What's an Evolution Strategy (ES)?
  376.  
  377.      Q1.4:  What's a Classifier System (CFS)?
  378.  
  379.      Q1.5:  What's Genetic Programming (GP)?
  380.  
  381.      Q2:    What can you do with EAs? What can't you do with them?
  382.  
  383.      Q3:    Who is or should be concerned with EAs?
  384.  
  385.      Q4:    How many Evolutionary Algorithms exist? Which?
  386.  
  387.      Q4.1:  What about Tierra, VENUS, PolyWorld, etc.?
  388.  
  389.  ai-faq/genetic/part2
  390.      Q5:    What about all this Optimization stuff?
  391.  
  392.      Q10:   Good introductory material about EAs?
  393.  
  394.      Q11:   Any journals and magazines about EAs?
  395.  
  396.      Q12:   The most important conferences concerned with EAs?
  397.  
  398.      Q13:   Evolutionary Computation Associations?
  399.  
  400.      Q14:   Where do I get technical reports on EAs from?
  401.  
  402.      Q15:   Other sources of information about EAs?
  403.  
  404.      Q15.1: Electronic Digests?
  405.  
  406.      Q15.2: Electronic Mailing Lists?
  407.  
  408.      Q15.3: Electronic Access to Research Institutes?
  409.  
  410.      Q15.4: Relevant Electronic News and FAQs?
  411.  
  412.      Q15.5: What about all these Internet Services?
  413.  
  414.  ai-faq/genetic/part3
  415.  
  416.  
  417.  
  418.  
  419. Version 0.6               Posted: 20 August 1993                         6
  420.  
  421.  
  422.  
  423.  
  424.  
  425.  
  426.  
  427. FAQ(1/3)                     TABLE OF CONTENTS                    FAQ(1/3)
  428.  
  429.  
  430.  
  431.      Q20:   Available EA software packages? FTP sites?
  432.  
  433.      Q20.1: Free EA software packages?
  434.  
  435.      Q20.2: Commercial EA software packages?
  436.  
  437.      Q20.3: Software from current research projects?
  438.  
  439.      Q42:   What is life all about?
  440.  
  441.      Q42b:  Is there a FAQ to this group?
  442.  
  443.      Q98:   What about Patents on EAs?
  444.  
  445.      Q99:   I don't get the message. What about a Glossary on EAs?
  446.  
  447.  
  448.  
  449.  
  450.  
  451.  
  452.  
  453.  
  454.  
  455.  
  456.  
  457.  
  458.  
  459.  
  460.  
  461.  
  462.  
  463.  
  464.  
  465.  
  466.  
  467.  
  468.  
  469.  
  470.  
  471.  
  472.  
  473.  
  474.  
  475.  
  476.  
  477.  
  478.  
  479.  
  480.  
  481.  
  482.  
  483.  
  484.  
  485. Version 0.6               Posted: 20 August 1993                         7
  486.  
  487.  
  488.  
  489.  
  490.  
  491.  
  492.  
  493. FAQ(1/3)                          ANSWERS                         FAQ(1/3)
  494.  
  495.  
  496.  
  497. A0) What is this newsgroup for?
  498.      The newsgroup comp.ai.genetic is intended as a forum for  people  who
  499.      want  to  use or explore the capabilities of Genetic Algorithms (GA),
  500.      Evolutionary Programming (EP), Evolution Strategies (ES),  Classifier
  501.      Systems  (CFS),  Genetic Programming (GP), and some other, less well-
  502.      known problem solving  algorithms  that  are  more  or  less  loosely
  503.      coupled to the field of Evolutionary Computation (EC).
  504.  
  505.      The following guidelines present the essentials of the USENET on-line
  506.      documentation, that is posted each month to news.announce.newusers.
  507.  
  508.      If you are already familiar with "netiquette" you don't want to  read
  509.      any  further;  if  you  don't  know  what the hell this is all about,
  510.      proceed as follows: (1) carefully read the following paragraphs,  (2)
  511.      read  all  the documents in news.announce.newusers before posting any
  512.      article to USENET.  At least you should give the introductory stuff a
  513.      try,  ie.  files  "news-answers/introduction" and "news-answers/news-
  514.      newusers-intro". Both are survey articles, that provide a  short  and
  515.      easy  way  to get an overview of the interesting parts of the on-line
  516.      docs, and thus can help to prevent you from drowning in the megabytes
  517.      to  read. Both can be received either by subscribing to news.answers,
  518.      or sending the following message to <mail-server@rtfm.mit.edu>
  519.  
  520.       send usenet/news.answers/introduction
  521.       send usenet/news.answers/news-newusers-intro
  522.  
  523.      Thanx in advance for your patience!
  524.  
  525.      You will probably find  the  following  types  of  articles  in  this
  526.      newsgroup:
  527.  
  528.  1. Requests
  529.      Requests  are  articles  of  the form "I am looking for X" where X is
  530.      something public like a book, an article, a piece of software.
  531.  
  532.      If multiple different answers can be expected, the person making  the
  533.      request  should  prepare  to make a summary of the answers he/she got
  534.      and announce to do  so  with  a  phrase  like  "Please  e-mail,  I'll
  535.      summarize" at the end of the posting.
  536.  
  537.      The  Subject  line  of  the  posting  should  then  be something like
  538.      "Request: X"
  539.  
  540.  2. Questions
  541.      As opposed to requests, questions are  concerned  with  something  so
  542.      specific  that  general  interest  cannot readily be assumed.  If the
  543.      poster thinks that the topic is  of  some  general  interest,  he/she
  544.      should announce a summary (see above).
  545.  
  546.      The  Subject  line of the posting should be something like "Question:
  547.      this-and-that" (Q: this-and-that) or have  the  form  of  a  question
  548.  
  549.  
  550.  
  551. Version 0.6               Posted: 20 August 1993                         8
  552.  
  553.  
  554.  
  555.  
  556.  
  557.  
  558.  
  559. FAQ(1/3)                          ANSWERS                         FAQ(1/3)
  560.  
  561.  
  562.  
  563.      (ie., end with a question mark)
  564.  
  565.  3. Answers
  566.      These  are  reactions  to  questions or requests.  As a rule of thumb
  567.      articles of type "answer" should be rare.   Ideally,  in  most  cases
  568.      either  the  answer  is  too  specific to be of general interest (and
  569.      should thus be e-mailed to the poster) or  a  summary  was  announced
  570.      with  the question or request (and answers should thus be e-mailed to
  571.      the poster).
  572.  
  573.      The subject lines of answers are automatically adjusted by  the  news
  574.      software.
  575.  
  576.  4. Summaries
  577.      In  all  cases  of requests or questions the answers for which can be
  578.      assumed to be of some general interest, the poster of the request  or
  579.      question shall summarize the answers he/she received.  Such a summary
  580.      should be announced in  the  original  posting  of  the  question  or
  581.      request with a phrase like "Please answer by e-mail, I'll summarize"
  582.  
  583.      In  such  a  case  answers  should NOT be posted to the newsgroup but
  584.      instead be mailed to the poster who collects and reviews them.  After
  585.      about 10 to 20 days from the original posting, its poster should make
  586.      the summary of answers and post it to the net.
  587.  
  588.      Some care should be invested into a summary:
  589.  
  590.      a) simple concatenation of all  the  answers  might  not  be  enough;
  591.     instead  redundancies, irrelevances, verbosities and errors should
  592.     be filtered out (as good as possible),
  593.  
  594.      b) the answers shall be separated clearly
  595.  
  596.      c) the contributors of the individual answers shall  be  identifiable
  597.     unless  they  requested  to  remain anonymous [eds note: yes, that
  598.     happens])
  599.  
  600.      d) the summary shall start with the "quintessence" of the answers, as
  601.     seen by the original poster
  602.  
  603.      e) A  summary  should, when posted, clearly be indicated to be one by
  604.     giving it a Subject line starting with "Summary:"
  605.  
  606.      Note that a good summary is pure gold for the rest of  the  newsgroup
  607.      community,  so  summary  work  will be most appreciated by all of us.
  608.      (Good summaries are more valuable than any moderator!)
  609.  
  610.  5. Announcements
  611.      Some articles never need  any  public  reaction.   These  are  called
  612.      announcements  (for  instance  for  a  workshop,  conference  or  the
  613.      availability of some technical report or software system).
  614.  
  615.  
  616.  
  617. Version 0.6               Posted: 20 August 1993                         9
  618.  
  619.  
  620.  
  621.  
  622.  
  623.  
  624.  
  625. FAQ(1/3)                          ANSWERS                         FAQ(1/3)
  626.  
  627.  
  628.  
  629.      Announcements should be clearly indicated to be such by giving them a
  630.      subject line of the form "Announcement: this-and-that"
  631.  
  632.      Due  to  common  practice,  conference  announcements usually carry a
  633.      "CFP:" in their subject line, ie. "call for papers"  (or:  "call  for
  634.      participation").
  635.  
  636.  6. Reports
  637.      Sometimes  people  spontaneously  want  to  report  something  to the
  638.      newsgroup. This might be  special  experiences  with  some  software,
  639.      results   of  own  experiments  or  conceptual  work,  or  especially
  640.      interesting information from somewhere else.
  641.  
  642.      Reports should be clearly indicated to  be  such  by  giving  them  a
  643.      subject line of the form "Report: this-and-that"
  644.  
  645.  7. Discussions
  646.      An  especially  valuable  possibility  of USENET is of course that of
  647.      discussing a certain topic with hundreds of  potential  participants.
  648.      All  traffic  in  the newsgroup that can not be subsumed under one of
  649.      the above categories should belong to a discussion.
  650.  
  651.      If somebody explicitly wants to start a discussion, he/she can do  so
  652.      by  giving  the posting a subject line of the form "Start discussion:
  653.      this-and-that" (People who react on this, please  remove  the  "Start
  654.      discussion: " label from the subject line of your replies)
  655.  
  656.      It  is quite difficult to keep a discussion from drifting into chaos,
  657.      but, unfortunately, as many other newsgroups show there seems  to  be
  658.      no  secure way to avoid this.  On the other hand, comp.ai.genetic has
  659.      not had many problems with this effect, yet, so  let's  just  go  and
  660.      hope...
  661.  
  662.  
  663. A1) What are Evolutionary Algorithms (EAs)?
  664.      Evolutionary  algorithms  use  computational  models  of evolutionary
  665.      processes as  key  elements  in  the  design  and  implementation  of
  666.      computer-based  problem  solving  systems.  A variety of evolutionary
  667.      computational  models  have  been  proposed.  They  share  a   common
  668.      conceptual  base of simulating the evolution of individual structures
  669.      via  processes  of  SELECTION,  MUTATION,  and   REPRODUCTION.    The
  670.      processes  depend  on  the  perceived  PERFORMANCE  of the individual
  671.      structures as defined by an ENVIRONMENT.
  672.  
  673.      More precisely, EAs maintain a POPULATION of structures, that  evolve
  674.      according  to  rules  of  selection  and  other  operators,  that are
  675.      referred  to  as  SEARCH  OPERATORS,  (GENETIC  OPERATORS)  such   as
  676.      RECOMBINATION  and  MUTATION.   Each  individual  in  the  population
  677.      receives a measure of it's fitness in the  environment.  Reproduction
  678.      focuses  attention  on  high fitness individuals, thus EXPLOITING the
  679.      available fitness information.  Recombination  and  mutation  perturb
  680.  
  681.  
  682.  
  683. Version 0.6               Posted: 20 August 1993                        10
  684.  
  685.  
  686.  
  687.  
  688.  
  689.  
  690.  
  691. FAQ(1/3)                          ANSWERS                         FAQ(1/3)
  692.  
  693.  
  694.  
  695.      those  individuals,  providing  general  heuristics  for EXPLORATION.
  696.      Although simplistic from a biologist's  viewpoint,  these  algorithms
  697.      are  sufficiently  complex  to  provide  robust and powerful ADAPTIVE
  698.      SEARCH mechanisms.
  699.  
  700.      ---  from:  "An  Overview  of  Evolutionary  Computation"   [ECML93],
  701.      442-459.
  702.  
  703.  PSEUDO CODE
  704.      The pseudo code of a typical EA looks like:
  705.      Algorithm EA is
  706.  
  707.       // start with an initial time
  708.       t := 0;
  709.  
  710.       // initialize a usually random population of individuals
  711.       initpopulation P (t);
  712.  
  713.       // evaluate fitness of all initial individuals in population
  714.       evaluate P (t);
  715.  
  716.       // test for termination criterion (time, fitness, etc.)
  717.       while not done do
  718.  
  719.            // increase the time counter
  720.            t := t + 1;
  721.  
  722.            // select sub-population for offspring production
  723.            P' := selectparents P (t);
  724.  
  725.            // recombine the "genes" of selected parents
  726.            recombine P' (t);
  727.  
  728.            // perturb the mated population stochastically
  729.            mutate P' (t);
  730.  
  731.            // evaluate it's new fitness
  732.            evaluate P' (t);
  733.  
  734.            // select the survivors from actual fitness
  735.            P := survive P,P' (t);
  736.       od
  737.      end EA.
  738.  
  739. A1.1) What's a Genetic Algorithm (GA)?
  740.      The  Genetic  Algorithm  is a model of MACHINE LEARNING which derives
  741.      its behavior from a metaphor of the processes of evolution in nature.
  742.      This  is  done  by  the  creation within a machine of a POPULATION of
  743.      individuals represented by chromosomes, in essence a set of character
  744.      strings  that  are analogous to the base-4 chromosomes that we see in
  745.      our own DNA.  The individuals in the population  then  go  through  a
  746.  
  747.  
  748.  
  749. Version 0.6               Posted: 20 August 1993                        11
  750.  
  751.  
  752.  
  753.  
  754.  
  755.  
  756.  
  757. FAQ(1/3)                          ANSWERS                         FAQ(1/3)
  758.  
  759.  
  760.  
  761.      process of evolution.
  762.  
  763.      We  should  note that EVOLUTION (in nature or anywhere else) is not a
  764.      purposive or directed process. That  is,  there  is  no  evidence  to
  765.      support  the  assertion  that  the  goal  of  evolution is to produce
  766.      Mankind. Indeed, the  processes  of  nature  seem  to  boil  down  to
  767.      different  individuals  competing  for  resources in the environment.
  768.      Some are better than others. Those that are better are more likely to
  769.      survive and propagate their genetic material.
  770.  
  771.      In  nature,  we  see  that  the  encoding for our genetic information
  772.      (genome) is done in a way that admits sexual  reproduction.   ASEXUAL
  773.      REPRODUCTION (such as by budding) typically results in offspring that
  774.      are genetically identical to the parent.  SEXUAL REPRODUCTION  allows
  775.      the  creation  of  genetically radically different offspring that are
  776.      still of the same general flavor (species).
  777.  
  778.      At the molecular level what occurs (wild  oversimplification  alert!)
  779.      is  that a pair of chromosomes bump into one another, exchange chunks
  780.      of genetic information and drift apart.  This  is  the  RECOMBINATION
  781.      operation,  which GA/GPers generally refer to as CROSSOVER because of
  782.      the way that genetic material crosses over  from  one  chromosome  to
  783.      another.
  784.  
  785.      The crossover operation happens in an environment where the selection
  786.      of who gets to mate is a function of the FITNESS of  the  individual,
  787.      ie. how good the individual is at competing in its environment.  Some
  788.      genetic algorithms use a simple function of the  fitness  measure  to
  789.      select  individuals (probabilistically) to undergo genetic operations
  790.      such  as  crossover  or  REPRODUCTION  (the  propagation  of  genetic
  791.      material unaltered).  This is fitness-proportionate SELECTION.  Other
  792.      implementations use  a  model  in  which  certain  randomly  selected
  793.      individuals  in  a subgroup compete and the fittest is selected. This
  794.      is called tournament selection and is the form of selection we see in
  795.      nature  when stags rut to vie for the privilege of mating with a herd
  796.      of hinds. The two processes that most  contribute  to  evolution  are
  797.      crossover and fitness based selection/reproduction.
  798.  
  799.      As it turns out, there are mathematical proofs that indicate that the
  800.      process of fitness  proportionate  reproduction  is,  in  fact,  near
  801.      optimal in some senses.
  802.  
  803.      Mutation  also  plays  a  role  in this process, though it is not the
  804.      dominant role that  is  popularly  believed  to  be  the  process  of
  805.      evolution, ie. random mutation and survival of the fittest. It cannot
  806.      be stressed too strongly that the genetic algorithm (as a  simulation
  807.      of  a  genetic  process) is not a "random search" for a solution to a
  808.      problem  (highly  fit  individual).  The   genetic   algorithm   uses
  809.      stochastic processes, but the result is distinctly non-random (better
  810.      than random).
  811.  
  812.  
  813.  
  814.  
  815. Version 0.6               Posted: 20 August 1993                        12
  816.  
  817.  
  818.  
  819.  
  820.  
  821.  
  822.  
  823. FAQ(1/3)                          ANSWERS                         FAQ(1/3)
  824.  
  825.  
  826.  
  827.      Genetic algorithms are used for a  number  of  different  application
  828.      areas.  An  example  of  this  would be multidimensional optimization
  829.      problems in which the character string of the chromosome can be  used
  830.      to encode the values for the different parameters being optimized.
  831.  
  832.      In  practice,  therefore,  we  can  implement  this  genetic model of
  833.      computation by having arrays of bits or characters to  represent  the
  834.      chromosomes.   Simple   bit   manipulation   operations   allow   the
  835.      implementation of crossover, mutation and other operations.  Although
  836.      a  substantial  amount  of  research  has been performed on variable-
  837.      length strings and  other  structures,  the  majority  of  work  with
  838.      genetic  algorithms is focussed on fixed-length character strings. We
  839.      should focus on both this aspect of fixed-lengthness and the need  to
  840.      encode the representation of the solution being sought as a character
  841.      string, since these are  crucial  aspects  that  distinguish  Genetic
  842.      Programming,  which  does  not have a fixed length representation and
  843.      there is typically no encoding of the problem.
  844.  
  845.      When the genetic algorithm is implemented it is  usually  done  in  a
  846.      manner that involves the following cycle: Evaluate the fitness of all
  847.      of the individuals in the population.  Create  a  new  population  by
  848.      performing   operations   such  as  crossover,  fitness-proportionate
  849.      reproduction and mutation on the individuals whose fitness  has  just
  850.      been  measured.  Discard the old population and iterate using the new
  851.      population.
  852.  
  853.      One iteration of this loop is referred to as a GENERATION.  There  is
  854.      no theoretical reason for this as an implementation model. Indeed, we
  855.      do not see this punctuated behavior in populations  in  nature  as  a
  856.      whole, but it is a convenient implementation model.
  857.  
  858.      The  first  generation  (generation  0) of this process operates on a
  859.      population of randomly generated  individuals.  From  there  on,  the
  860.      genetic  operations,  in concert with the fitness measure, operate to
  861.      improve the population.
  862.  
  863.  PSEUDO CODE
  864.      The pseudo code of a standard GA looks like:
  865.      Algorithm GA is
  866.  
  867.       // start with an initial time
  868.       t := 0;
  869.  
  870.       // initialize a usually random population of individuals
  871.       initpopulation P (t);
  872.  
  873.       // evaluate fitness of all initial individuals of population
  874.       evaluate P (t);
  875.  
  876.       // test for termination criterion (time, fitness, etc.)
  877.       while not done do
  878.  
  879.  
  880.  
  881. Version 0.6               Posted: 20 August 1993                        13
  882.  
  883.  
  884.  
  885.  
  886.  
  887.  
  888.  
  889. FAQ(1/3)                          ANSWERS                         FAQ(1/3)
  890.  
  891.  
  892.  
  893.            // increase the time counter
  894.            t := t + 1;
  895.  
  896.            // select a sub-population for offspring production
  897.            P' := selectparents P (t);
  898.  
  899.            // recombine the "genes" of selected parents
  900.            recombine P' (t);
  901.  
  902.            // perturb the mated population stochastically
  903.            mutate P' (t);
  904.  
  905.            // evaluate it's new fitness
  906.            evaluate P' (t);
  907.  
  908.            // select the survivors from actual fitness
  909.            P := survive P,P' (t);
  910.       od
  911.      end GA.
  912.  
  913. A1.2) What's Evolutionary Programming (EP)?
  914.      [..]
  915.  
  916.  PSEUDO CODE
  917.      The pseudo code of an Evolutionary Programming algorithm looks like:
  918.      Algorithm EP is
  919.  
  920.       // start with an initial time
  921.       t := 0;
  922.  
  923.       // initialize a usually random population of individuals
  924.       initpopulation P (t);
  925.  
  926.       // evaluate fitness of all initial individuals of population
  927.       evaluate P (t);
  928.  
  929.       // test for termination criterion (time, fitness, etc.)
  930.       while not done do
  931.  
  932.            // increase the time counter
  933.            t := t + 1;
  934.  
  935.            // perturb the whole population stochastically
  936.            P' := mutate P (t);
  937.  
  938.            // evaluate it's new fitness
  939.            evaluate P' (t);
  940.  
  941.            // select the survivors from actual fitness
  942.            P := survive P,P' (t);
  943.       od
  944.  
  945.  
  946.  
  947. Version 0.6               Posted: 20 August 1993                        14
  948.  
  949.  
  950.  
  951.  
  952.  
  953.  
  954.  
  955. FAQ(1/3)                          ANSWERS                         FAQ(1/3)
  956.  
  957.  
  958.  
  959.      end EP.
  960.  
  961.      It should be pointed out that EP does not  use  any  CROSSOVER  as  a
  962.      GENETIC OPERATOR.
  963.  
  964. A1.3) What's an Evolution Strategy (ES)? [preliminary]
  965.      In  1963 two students at the Technical University of Berlin (TUB) met
  966.      and were soon to collaborate  on  experiments  which  used  the  wind
  967.      tunnel  of  the Institute of Flow Engineering.  During the search for
  968.      the optimal shapes of bodies in a flow, which was then  a  matter  of
  969.      laborious  intuitive  experimentation,  the  idea  was  conceived  of
  970.      proceeding strategically.  However, attempts with the coordinate  and
  971.      simple  gradient  strategies  (cf Q5) were unsuccessful.  Then one of
  972.      the  students,  Ingo  Rechenberg,  now  Professor  of   Bionics   and
  973.      Evolutionary  Engineering, hit upon the idea of trying random changes
  974.      in the parameters  defining  the  shape,  following  the  example  of
  975.      natural  mutations.   The  EVOLUTION  STRATEGY  was  born.   A  third
  976.      student, Peter Bienert, joined them and started the  construction  of
  977.      an  automatic  experimenter, which would work according to the simple
  978.      rules of mutation  and  selection.   The  second  student,  Hans-Paul
  979.      Schwefel,  set  about  testing the efficiency of the new methods with
  980.      the help of a Zuse Z23 computer; for there were plenty of  objections
  981.      to these "random strategies."
  982.  
  983.      In spite of an occasional lack of financial support, the Evolutionary
  984.      Engineering Group which had been formed held  firmly  together.  Ingo
  985.      Rechenberg  received  his  doctorate  in  1970  (Rechenberg  73).  It
  986.      contains the theory of the two  membered  evolution  strategy  and  a
  987.      first proposal for a multimembered strategy which in the nomenclature
  988.      introduced here is of the (m+1) type.   In the  same  year  financial
  989.      support  from  the  Deutsche  Forschungsgemeinschaft  (DFG, Germany's
  990.      National Science Foundation) enabled the work, that was concluded, at
  991.      least  temporarily,  in 1974 with the thesis "Evolutionsstrategie und
  992.      numerische Optimierung" (Schwefel 77).
  993.  
  994.      Thus,  EVOLUTION  STRATEGIES  were  invented   to   solve   technical
  995.      optimization problems (TOPs) like eg. contructing an optimal flashing
  996.      nozzle, and until recently ES were only known  to  civil  engineering
  997.      folks,  as  an  alternative to standard solutions.  Usually no closed
  998.      form analytical objective function is available for TOPs  and  hence,
  999.      no   applicable   optimization  method  exists,  but  the  engineer's
  1000.      INTUITION.
  1001.  
  1002.      The first attempts to imitate principles of organic  evolution  on  a
  1003.      computer  still  resembled those iterative optimization methods known
  1004.      up to that time: In a two-membered or (1+1) ES, one parent  generates
  1005.      one   offspring  per  generation  by  applying  NORMALLY  DISTRIBUTED
  1006.      mutations, ie. smaller steps occur more likely than big ones, until a
  1007.      child  performs better than its ancestor and takes its place. Because
  1008.      of this simple structure, theoretical results  for  stepsize  control
  1009.      and   CONVERGENCE  VELOCITY  could  be  derived.  The  ratio  between
  1010.  
  1011.  
  1012.  
  1013. Version 0.6               Posted: 20 August 1993                        15
  1014.  
  1015.  
  1016.  
  1017.  
  1018.  
  1019.  
  1020.  
  1021. FAQ(1/3)                          ANSWERS                         FAQ(1/3)
  1022.  
  1023.  
  1024.  
  1025.      successful and all mutations should come to 1/5:  the  so-called  1/5
  1026.      SUCCESS  RULE  was  discovered.  This first algorithm, using mutation
  1027.      only, has then been enhanced to a (m+1) strategy  which  incorporated
  1028.      RECOMBINATION  due  to  several,  ie.  m parents being available. The
  1029.      mutation scheme and the exogenous stepsize control were taken  across
  1030.      unchanged from  (1+1) ESs.
  1031.  
  1032.      Schwefel  later  generalized these strategies to the multimembered ES
  1033.      now denoted by (m+l) and (m,l) which  imitates  the  following  basic
  1034.      principles  of  organic  evolution:  a  POPULATION,  leading  to  the
  1035.      possibility  of  RECOMBINATION  with  random  mating,  MUTATION   and
  1036.      SELECTION.   These  strategies  are  termed  PLUS  STRATEGY and COMMA
  1037.      STRATEGY, respectively: in the plus case, the parental generation  is
  1038.      taken into account during selection, while in the comma case only the
  1039.      offspring undergoes selection, and the parents die off. m (usually  a
  1040.      lowercase my, denotes the population size, and l, usually a lowercase
  1041.      lambda denotes the number of offspring generated per generation).  Or
  1042.      to  put  it  in  an  utterly  insignificant  and  hopelessly outdated
  1043.      language:
  1044.  
  1045.       (define (Evolution-strategy population)
  1046.         (if (terminate? population)
  1047.           population
  1048.           (evolution-strategy
  1049.         (select
  1050.           (cond (plus-strategy?
  1051.               (union (mutate
  1052.                    (recombine population))
  1053.                  population))
  1054.             (comma-strategy?
  1055.               (mutate
  1056.                 (recombine population))))))))
  1057.  
  1058.      However, dealing with ES is sometimes seen as "strong  tobacco,"  for
  1059.      it takes a decent amount of PROBABILITY THEORY and applied STATISTICS
  1060.      to understand the inner workings of an ES, while it navigates through
  1061.      the  hyperspace  of  the  usually  n-dimensional  problem  space,  by
  1062.      throwing hyperelipses into the deep...
  1063.  
  1064.      Luckily, this medium doesn't allow for  much  mathematical  ballyhoo;
  1065.      the  author  therefore  has  to come up with a simple but brilliantly
  1066.      intriguing explanation to save the reader from falling asleep  during
  1067.      the rest of this section, so here we go:
  1068.  
  1069.      Imagine a black box. A large black box. As large as, say for example,
  1070.      a Coka-Cola vending machine. Now, ... (to be continued)
  1071.  
  1072.      [..]
  1073.  
  1074.      A single individual of the ES' population consists of  the  following
  1075.      GENOTYPE representing a point in the SEARCH SPACE:
  1076.  
  1077.  
  1078.  
  1079. Version 0.6               Posted: 20 August 1993                        16
  1080.  
  1081.  
  1082.  
  1083.  
  1084.  
  1085.  
  1086.  
  1087. FAQ(1/3)                          ANSWERS                         FAQ(1/3)
  1088.  
  1089.  
  1090.  
  1091.      OBJECT VARIABLES
  1092.       Real-valued  x_i  have to be tuned by recombination and mutation
  1093.       such that an objective  function  reaches  its  global  optimum.
  1094.       Referring   to   the  metaphor  mentioned  previously,  the  x_i
  1095.       represent the regulators of the alien Coka-Cola vending machine.
  1096.  
  1097.      STRATEGY VARIABLES
  1098.       Real-valued  s_i  (usually denoted by a lowercase sigma) or mean
  1099.       STEPSIZES determine the mutability of the  x_i.  They  represent
  1100.       the STANDARD DEVIATION of a  (0, s_i) GAUSSIAN DISTRIBUTION (GD)
  1101.       being added to each x_i  as  an  undirected  mutation.  With  an
  1102.       EXPECTANCY  VALUE  of  0  the  parents  will  produce offsprings
  1103.       similar to themselves on average. In order to  make  a  doubling
  1104.       and  a  halving  of  a stepsize equally probable, the s_i mutate
  1105.       LOG-NORMALLY,  distributed,  ie.  exp(GD),  from  generation  to
  1106.       generation.    These  stepsizes  hide  the  INTERNAL  MODEL  the
  1107.       population has made of its environment, ie. a SELF-ADAPTATION of
  1108.       the  stepsizes  has  replaced the exogenous control of the (1+1)
  1109.       ES.
  1110.  
  1111.      This concept works because selection sooner or  later  prefers  those
  1112.      individuals having built a good model of the objective function, thus
  1113.      producing better  offspring.  Hence,  LEARNING  takes  place  on  two
  1114.      levels:  (1)  at  the genotypic, ie. the object and strategy variable
  1115.      level and (2) at the phenotypic level, ie. the fitness level.
  1116.  
  1117.      Depending on an individual's x_i, the  resulting  objective  function
  1118.      value f(x), where x denotes the vector of objective variables, serves
  1119.      as the PHENOTYPE (fitness) in the selection step. In a plus strategy,
  1120.      the  m best of all (m+l) individuals survive to become the parents of
  1121.      the next generation. Using the comma variant, selection  takes  place
  1122.      only  among  the l offspring. The second scheme is more realistic and
  1123.      therefore more successful, because no individual may survive forever,
  1124.      which  could  at  least  theoretically  occur using the plus variant.
  1125.      Untypical for conventional  optimization  algorithms  and  lavish  at
  1126.      first  sight,  a  comma  strategy allowing intermediate deterioration
  1127.      performs  better!  Only  by  FORGETTING  highly  fit  individuals   a
  1128.      permanent  adaptation  of the stepsizes can take place and avoid long
  1129.      stagnation phases due to misadapted s_i's.   This  means  that  these
  1130.      individuals   have   built  an  internal  model  that  is  no  longer
  1131.      appropriate  for  further  progress,  and  thus  should   better   be
  1132.      discarded.
  1133.  
  1134.      By  choosing  a  certain ratio m/l, one can determine the convergence
  1135.      property of the evolution strategy: If one wants a  fast,  but  local
  1136.      convergence,  one  should  choose  a small HARD SELECTION, ratio, eg.
  1137.      (5,100), but looking for the global  optimum,  one  should  favour  a
  1138.      SOFTer SELECTION (15,100).
  1139.  
  1140.      Self-adaptation  within ESs depends on the following AGENTS (Schwefel
  1141.      87):
  1142.  
  1143.  
  1144.  
  1145. Version 0.6               Posted: 20 August 1993                        17
  1146.  
  1147.  
  1148.  
  1149.  
  1150.  
  1151.  
  1152.  
  1153. FAQ(1/3)                          ANSWERS                         FAQ(1/3)
  1154.  
  1155.  
  1156.  
  1157.      RANDOMNESS:
  1158.       One cannot model mutation as a pure random process.  This  would
  1159.       mean that a child is completely independent of its parents.
  1160.  
  1161.      POPULATION SIZE:
  1162.       The  population  has  to  be  sufficiently  large.  Not only the
  1163.       current best should be allowed to reproduce, but a set  of  good
  1164.       individuals.  Biologists  have coined the term REQUISITE VARIETY
  1165.       being necessary to prevent a species from  becoming  poorer  and
  1166.       poorer genetically and eventually dying out.
  1167.  
  1168.      COOPERATION:
  1169.       In  order  to  exploit  the effects of a population (m > 1), the
  1170.       individuals should recombine their knowledge with that of others
  1171.       (cooperate)   because   one   cannot  expect  the  knowledge  to
  1172.       accumulate in the best individual only.
  1173.  
  1174.      DETERIORATION:
  1175.       In order to allow better internal models (stepsizes) to  provide
  1176.       better  progress  in the future, one should accept deterioration
  1177.       from one generation to the next. A limited life-span  in  nature
  1178.       is not a sign of failure, but an important means of preventing a
  1179.       species from freezing genetically.
  1180.  
  1181.      ESs prove to be successful when compared to other  iterative  methods
  1182.      on a large number of test problems (Schwefel 77).  They are adaptable
  1183.      to nearly all sorts of problems in optimization,  because  they  need
  1184.      very little information about the problem, esp. no derivatives of the
  1185.      objective function. For a list of some 300 applications of  EAs,  see
  1186.      the  Sys-2/92  report  (cf  Q14).   ESs  are  capable of solving high
  1187.      dimensional, multimodal, nonlinear problems subject to linear  and/or
  1188.      nonlinear  constraints.  The  objective function can also, eg. be the
  1189.      result of a SIMULATION, it does not have to  be  given  in  a  closed
  1190.      form.   This  also  holds for the constraints which may represent the
  1191.      outcome of, eg. a finite elements method (FEM). ESs have been adapted
  1192.      to VECTOR OPTIMIZATION problems (Kursawe 92), and they can also serve
  1193.      as a  heuristic  for  NP-complete  combinatorial  problems  like  the
  1194.      TRAVELLING  SALESMAN  problem  or  problems  with a noisy or changing
  1195.      response surface.
  1196.  
  1197.      References
  1198.  
  1199.      (Kursawe  92)   F.   Kursawe   "Evolution   strategies   for   vector
  1200.      optimization", Taipei, National Chiao Tung University, 187-193.
  1201.  
  1202.      (Kursawe  94)  F.  Kursawe  "Evolution  strategies:  Simple models of
  1203.      natural processes?", Revue Internationale de Systemique,  France  (to
  1204.      appear).
  1205.  
  1206.      (Rechenberg   73)  I.  Rechenberg  "Evolutionsstrategie:  Optimierung
  1207.      technischer Systeme  nach  Prinzipien  der  biologischen  Evolution",
  1208.  
  1209.  
  1210.  
  1211. Version 0.6               Posted: 20 August 1993                        18
  1212.  
  1213.  
  1214.  
  1215.  
  1216.  
  1217.  
  1218.  
  1219. FAQ(1/3)                          ANSWERS                         FAQ(1/3)
  1220.  
  1221.  
  1222.  
  1223.      Stuttgart: Fromman-Holzboog.
  1224.  
  1225.      (Schwefel    77)   H.-P.   Schwefel   "Numerische   Optimierung   von
  1226.      Computermodellen mittels der Evolutionsstrategie", Basel: Birhaeuser.
  1227.  
  1228.      (Schwefel  87)  H.-P. Schwefel "Collective Phaenomena in Evolutionary
  1229.      Systems", 31st Annu. Meet. Inter'l Soc. for General System  Research,
  1230.      Budapest, 1025-1033.
  1231.  
  1232. A1.4) What's a Classifier System (CFS)?
  1233.      [..]
  1234.  
  1235. A1.5) What's Genetic Programming (GP)?
  1236.      Genetic Programming is the extension of the genetic model of learning
  1237.      into the space of programs. That is, the objects that constitute  the
  1238.      population   are  not  fixed-length  character  strings  that  encode
  1239.      possible solutions to the problem at hand, they  are  programs  that,
  1240.      when  executed,  "are"  the candidate solutions to the problem. These
  1241.      programs are expressed in genetic programming as parse trees,  rather
  1242.      than  as lines of code.  Thus, for example, the simple program "a + b
  1243.      * c" would be represented as:
  1244.  
  1245.          +
  1246.         / \
  1247.         a  *
  1248.          / \
  1249.          b  c
  1250.  
  1251.      or, to be precise, as suitable data  structures  linked  together  to
  1252.      achieve this effect. Because this is a very simple thing to do in the
  1253.      programming language Lisp, many GPers tend to use Lisp. However, this
  1254.      is simply an implementation detail. There are straightforward methods
  1255.      to implement GP using a non-Lisp programming environment.
  1256.  
  1257.      The programs in the population are  composed  of  elements  from  the
  1258.      FUNCTION  SET and the TERMINAL SET, which are typically fixed sets of
  1259.      symbols selected to be appropriate to the solution of problems in the
  1260.      domain of interest.
  1261.  
  1262.      In  GP  the  crossover  operation  is  implemented by taking randomly
  1263.      selected subtrees in the individuals (selected according to  fitness)
  1264.      and exchanging them.
  1265.  
  1266.      It should be pointed out that GP usually does not use any MUTATION as
  1267.      a GENETIC OPERATOR.
  1268.  
  1269.  
  1270. A2) What can EAs do for you? What can't they do?
  1271.      In  principle,  EAs  can  compute  any   computable   function,   ie.
  1272.      everything a normal digital computer can do.
  1273.  
  1274.  
  1275.  
  1276.  
  1277. Version 0.6               Posted: 20 August 1993                        19
  1278.  
  1279.  
  1280.  
  1281.  
  1282.  
  1283.  
  1284.  
  1285. FAQ(1/3)                          ANSWERS                         FAQ(1/3)
  1286.  
  1287.  
  1288.  
  1289.      EAs are especially bad suited for problems that are already known how
  1290.      to solve, unless these problems are intended to  serve  as  BENCHMARK
  1291.      PROGRAMS.   Special  purpose  algorithms,  ie. algorithms that have a
  1292.      certain amount of PROBLEM DOMAIN KNOWLEDGE hard coded in  them,  will
  1293.      usually outperform EAs, so there is no BLACK MAGIC in EC.  EAs should
  1294.      be used when there is no other known problem  solving  strategy,  and
  1295.      the  problem domain is NP-complete.  That's where EAs come into play:
  1296.      heuristically finding solutions where all else fails.
  1297.  
  1298.      Following  is  an  incomplete   (sic!)    list   of   successful   EA
  1299.      applications:
  1300.  
  1301.  TIMETABLING
  1302.      Another  thing that has been addressed quite successfully with GAs is
  1303.      timetabling. A very common manifestation of this kind of  problem  is
  1304.      the  timetabling  of  exams  or  classes in Universities, etc. At the
  1305.      Department  of  Artificial  Intelligence,  University  of  Edinburgh,
  1306.      timetabling  the  MSc  exams is now done using a GA (Corne et al. 93,
  1307.      Fang 92). An example of the use of GAs  for  timetabling  classes  is
  1308.      (Abramson & Abela 1991).
  1309.  
  1310.      In  the  exam  timetabling  case,  the  fitness function for a genome
  1311.      representing a timetable involves computing degrees of punishment for
  1312.      various  problems  with  the timetable, such as clashes, instances of
  1313.      students having to take  consecutive  exams,  instances  of  students
  1314.      having  (eg)  three  or  more  exams  in one day, the degree to which
  1315.      heavily-subscribed exams occur late in  the  timetable  (which  makes
  1316.      marking harder), overall length of timetable, etc. The modular nature
  1317.      of the fitness function has the key to the main potential strength of
  1318.      using  GAs  for  this  sort of thing as opposed to using conventional
  1319.      search and/or constraint programming methods. The  power  of  the  GA
  1320.      approach  is  the  ease  with  which it can handle arbitrary kinds of
  1321.      constraints and  objectives;  all  such  things  can  be  handled  as
  1322.      weighted  components of the fitness function, making it easy to adapt
  1323.      the GA to the  particular  requirements  of  a  very  wide  range  of
  1324.      possible overall objectives . Very few other timetabling methods, for
  1325.      example, deal with such objectives at all, which shows how  difficult
  1326.      it  is  (without  GAs)  to  graft  the  capacity  to handle arbitrary
  1327.      objectives onto the basic "find shortest- length  timetable  with  no
  1328.      clashes"  requirement.  The  proper  way  to  weight/handle different
  1329.      objectives in the fitness function in  relation  to  the  general  GA
  1330.      dynamics remains, however, an important research problem!
  1331.  
  1332.      GAs thus offer a combination of simplicity, flexibility & speed which
  1333.      competes very favorably with other approaches, but  are  unlikely  to
  1334.      outperform   knowledge-based  (etc)  methods  if  the  best  possible
  1335.      solution is required at any cost. Even then,  however,  hybridisation
  1336.      may yield the best of both worlds; also, the ease (if the hardware is
  1337.      available!) of implementing GAs in parallel enhances the  possibility
  1338.      of  using  them for good, fast solutions to very hard timetabling and
  1339.      similar problems.
  1340.  
  1341.  
  1342.  
  1343. Version 0.6               Posted: 20 August 1993                        20
  1344.  
  1345.  
  1346.  
  1347.  
  1348.  
  1349.  
  1350.  
  1351. FAQ(1/3)                          ANSWERS                         FAQ(1/3)
  1352.  
  1353.  
  1354.  
  1355.      References
  1356.  
  1357.      (Corne et al. 93) D. Corne,  H.-L.  Fang,  C.  Mellish  "Solving  the
  1358.      Modular  Exam  Scheduling Problem with Genetic Algorithms".  Proc. of
  1359.      6th  Int'l  Conf.  on  Industrial  and  Engineering  Applications  of
  1360.      Artificial Intelligence & Expert Systems, ISAI, (to appear).
  1361.  
  1362.      (Fang   92)  H.-L.  Fang  "Investigating  GAs  for  scheduling",  MSc
  1363.      Dissertation,   University   of   Edinburgh   Dept.   of   Artificial
  1364.      Intelligence, Edinburgh, UK.
  1365.  
  1366.      (Abramson  & Abela 91) Abramson & Abela "A Parallel Genetic Algorithm
  1367.      for Solving  the  School  Timetabling  Problem'',  Technical  Report,
  1368.      Division of I.T., C.S.I.R.O, April 1991.
  1369.  
  1370.  JOB-SHOP SCHEDULING
  1371.      The  Job-Shop  Scheduling  Problem  (JSSP)  is  a  very difficult NP-
  1372.      complete problem which, so far, seems best addressed by sophisticated
  1373.      branch  and  bound  search  techniques.  GA researchers, however, are
  1374.      continuing to make  progress  on  it.   (Davis  85)  started  off  GA
  1375.      research  on  the  JSSP,  (Whitley  89)  reports  on  using  the edge
  1376.      recombination operator (designed initially for the TSP) on JSSPs too.
  1377.      More  recent work includes (Nakano 91),(Yamada & Nakano 92), (Fang et
  1378.      al. 93).  The latter three  report  increasingly  better  results  on
  1379.      using  GAs on fairly large benchmark JSSPs (from Muth & Thompson 63);
  1380.      neither consistently outperform branch & bound search yet,  but  seem
  1381.      well  on  the  way.  A  crucial  aspect  of such work (as with any GA
  1382.      application) is the method used to  encode  schedules.  An  important
  1383.      aspect of some of the recent work on this is that better results have
  1384.      been obtained by rejecting the conventional wisdom  of  using  binary
  1385.      representations   (as  in  (Nakano  91))  in  favor  of  more  direct
  1386.      encodings. In (Yamada & Nakano 92), for example,  a  genome  directly
  1387.      encodes operation completion times, while in (Fang et al. 93) genomes
  1388.      represent implicit instructions for building a schedule. The  success
  1389.      of  these  latter techniques, especially since their applications are
  1390.      very important in industry, should eventually spawn  advances  in  GA
  1391.      theory.
  1392.  
  1393.      Concerning  the point of using GAs at all on hard job-shop scheduling
  1394.      problems, the same goes here as suggested  above  for  `Timetabling':
  1395.      The   GA   approach  enables  relatively  arbitrary  constraints  and
  1396.      objectives to be incorporated painlessly into a  single  optimization
  1397.      method.   It   is  unlikely  that  GAs  will  outperform  specialized
  1398.      knowledge-based  and/or  conventional  OR-based  approaches  to  such
  1399.      problems  in  terms  of  raw solution quality, however GAs offer much
  1400.      greater simplicity and flexibility, and so, for example, may  be  the
  1401.      best method for quick high-quality solutions, rather than finding the
  1402.      best possible solution at any cost. Also, of course,  hybrid  methods
  1403.      will  have a lot to offer, and GAs are far easier to parallelize than
  1404.      typical knowledge-based/OR methods.
  1405.  
  1406.  
  1407.  
  1408.  
  1409. Version 0.6               Posted: 20 August 1993                        21
  1410.  
  1411.  
  1412.  
  1413.  
  1414.  
  1415.  
  1416.  
  1417. FAQ(1/3)                          ANSWERS                         FAQ(1/3)
  1418.  
  1419.  
  1420.  
  1421.      Similar to the JSSP is  the  Open  Shop  Scheduling  Problem  (OSSP).
  1422.      (Fang  et  al.  93) reports an initial attempt at using GAs for this.
  1423.      Ongoing results from the same source shows  reliable  achievement  of
  1424.      results  within  less than 0.23% of optimal on moderately large OSSPs
  1425.      (so far, up to 20x20), including an  improvement  on  the  previously
  1426.      best known solution for a benchmark 10x10 OSSP. A simpler form of job
  1427.      shop problem is the Flow-Shop Sequencing problem;  recent  successful
  1428.      work on applying GAs to this includes (Reeves 93)."
  1429.  
  1430.      References
  1431.  
  1432.      (Davis  85)  L.  Davis "Job-Shop Scheduling with Genetic Algorithms",
  1433.      [ICGA85], 136-140.
  1434.  
  1435.      (Muth  &  Thompson  63)  J.F.  Muth  &   GL.   Thompson   "Industrial
  1436.      Scheduling". Prentice Hall, Englewood Cliffs, NJ, 1963.
  1437.  
  1438.      (Nakano  91)  R. Nakano "Conventional Genetic Algorithms for Job-Shop
  1439.      Problems", [ICGA91], 474-479.
  1440.  
  1441.      (Reeves  93)  C.R.  Reeves  "A   Genetic   Algorithm   for   Flowshop
  1442.      Sequencing", Coventry Polytechnic Working Paper, Coventry, UK.
  1443.  
  1444.      (Whitley  et  al.  89)  D.  Whitley,  T.  Starkweather,  D'Ann Fuquay
  1445.      "Scheduling  Problems  and  Traveling  Salesmen:  The  Genetic   Edge
  1446.      Recombination Operator", [ICGA89], 133-140.
  1447.  
  1448.      (Fang  et  al. 93) H.-L. Fang, P. Ross, D. Corne "A Promising Genetic
  1449.      Algorithm Approach to Job - Shop Scheduling, Rescheduling & Open-Shop
  1450.      Scheduling Problems", [ICGA93], 375-382.
  1451.  
  1452.      (Yamada  &  Nakano  92)  T.  Yamada  & R. Nakano "A Genetic Algorithm
  1453.      Applicable to Large-Scale Job-Shop Problems", [PPSN92], 281-290.
  1454.  
  1455.  MANAGEMENT SCIENCES
  1456.      "Applications of EA in management science and closely related  fields
  1457.      like organizational ecology is a domain that has been covered by some
  1458.      EA researchers - with considerable bias towards scheduling  problems.
  1459.      Since  I believe that EA have considerable potential for applications
  1460.      outside  the  rather  narrow  domain  of   scheduling   and   related
  1461.      combinatorial  problems,  I  started  collecting references about the
  1462.      status quo of EA-applications in  management  science.   This  report
  1463.      intends  to  make  available  my findings to other researchers in the
  1464.      field. It is a short  overview  and  lists  some  230  references  to
  1465.      current as well as finished research projects.  [..]
  1466.  
  1467.      At  the  end of the paper, a questionnaire has been incorporated that
  1468.      may be used for this purpose. Other comments are also appreciated."
  1469.  
  1470.      --- from the Introduction of (Nissen 93)
  1471.  
  1472.  
  1473.  
  1474.  
  1475. Version 0.6               Posted: 20 August 1993                        22
  1476.  
  1477.  
  1478.  
  1479.  
  1480.  
  1481.  
  1482.  
  1483. FAQ(1/3)                          ANSWERS                         FAQ(1/3)
  1484.  
  1485.  
  1486.  
  1487.      References
  1488.  
  1489.      (Nissen 93) V. Nissen "Evolutionary Algorithms in Management Science:
  1490.      An  Overview  and  List  of  References",  Papers  on  Economics  and
  1491.      Evolution, edited  by  the  European  Study  Group  for  Evolutionary
  1492.      Economics.    This   report   is   also   avail.  via  anon.  ftp  to
  1493.      gwdu03.gwdg.de in directory "pub/msdos/reports/wi", file "earef.eps".
  1494.  
  1495.      (Boulding  91)  K.E.  Boulding  "What  is  evolutionary  economics?",
  1496.      Journal of Evolutionary Economics, 1, 9-17.
  1497.  
  1498.  FURTHER APPLICATION(S)
  1499.      [..]
  1500.  
  1501.      References
  1502.  
  1503.      [..]
  1504.  
  1505.  
  1506. A3) Who is concerned with EAs?
  1507.      Evolutionary Computation attracts researchers  and  people  of  quite
  1508.      dissimilar disciplines, ie. EC is a interdisciplinary research field:
  1509.  
  1510.  Computer scientists
  1511.      Want to find out about the  properties  of  sub-symbolic  information
  1512.      processing  with  EAs  and  about  learning, ie.  adaptive systems in
  1513.      general.
  1514.  
  1515.      They  also  build  the  hardware  necessary  to  enable  future   EAs
  1516.      (precursors  are  already  beginning  to  emerge)  to huge real world
  1517.      problems, ie. the term "massively parallel  computation"  [HILLIS92],
  1518.      springs to mind.
  1519.  
  1520.  Engineers
  1521.      Of  many  kinds want to exploit the capabilities of EAs on many areas
  1522.      to solve their application, esp. optimization problems.
  1523.  
  1524.  Roboticists
  1525.      Want to build MOBOTs (MOBile RobOTs, ie.  R2D2's  and  #5's  cousins)
  1526.      that  navigate through UNCERTAIN environments, without using built-in
  1527.      "maps".  The MOBOTS thus have to adapt  to  their  surroundings,  and
  1528.      learn what they can do "move-through-door" and what they can't "move-
  1529.      through-wall" on their own by "trial-and-error".
  1530.  
  1531.  Cognitive scientists
  1532.      Might view CFS as a possible apparatus to describe models of thinking
  1533.      and cognitive systems.
  1534.  
  1535.  Physicists
  1536.      Use  EC  hardware,  eg. Hillis' (Thinking Machine Corp.'s) Connection
  1537.      Machine to model real  world  problems  which  include  thousands  of
  1538.  
  1539.  
  1540.  
  1541. Version 0.6               Posted: 20 August 1993                        23
  1542.  
  1543.  
  1544.  
  1545.  
  1546.  
  1547.  
  1548.  
  1549. FAQ(1/3)                          ANSWERS                         FAQ(1/3)
  1550.  
  1551.  
  1552.  
  1553.      variables, that run "naturally" in parallel, and thus can be modelled
  1554.      more easily and esp.  "faster" on  a  parallel  machine,  than  on  a
  1555.      serial "PC" one.
  1556.  
  1557.  Biologists
  1558.      In  fact  many  working  biologists  are  hostile to modeling, but an
  1559.      entire  community   of   Population   Biologists   arose   with   the
  1560.      'evolutionary  synthesis' of the 1930's created by the polymaths R.A.
  1561.      Fisher, J.B.S. Haldane, and S. Wright.  Wright's  'shifting  balance'
  1562.      theory  (balancing  drift  and selection in small POPULATIONS thereby
  1563.      avoiding local optima) is of current interest to both biologists  and
  1564.      ECers -- populations are naturally parallel.
  1565.  
  1566.      A  good  exposition  of  current  Population  Biology  modeling is J.
  1567.      Maynard Smith's text Evolutionary Genetics.  Richard Dawkin's Selfish
  1568.      Gene and Extended Phenotype are unparalleled (sic!) prose expositions
  1569.      of  evolutionary  processes.   Rob  Collins'  papers  are   excellent
  1570.      parallel GA models of evolutionary processes (available in ICGA91 and
  1571.      by ftp from ftp.cognet.ucla.edu "/pub/alife/papers").
  1572.  
  1573.      As fundamental motivation, consider Fisher's comment:  "No  practical
  1574.      biologist  interested  in  [e.g.] sexual reproduction would be led to
  1575.      work out the detailed consequences experienced  by  organisms  having
  1576.      three  or more sexes; yet what else should [s/]he do if [s/]he wishes
  1577.      to understand why the sexes are, in fact, always two?"  (Three  sexes
  1578.      would make for even weirder grammar, [s/]he said...)
  1579.  
  1580.  Philosophers
  1581.      and some other really curious people may also be interested in EC for
  1582.      various reasons.
  1583.  
  1584.  
  1585. A4) How many EAs exist? Which?
  1586.  The All Stars
  1587.      There  are  currently  3  main  paradigms  in  EA  research:  Genetic
  1588.      Algorithms,   Evolutionary  Programming,  and  Evolution  Strategies.
  1589.      Classifier Systems and Genetic Programming are offspring  of  the  GA
  1590.      community.   Besides  this  leading  crop,  there  are numerous other
  1591.      different approaches, alongside  to  hybrid  experiments,  ie.  there
  1592.      exist  pieces  of  software that reside in some researchers computer,
  1593.      that have been described in papers of proceedings  volumes,  and  may
  1594.      someday  prove  useful  on  a  certain  task. To stay in EA slang, we
  1595.      should think of these evolving strands as building blocks, that  when
  1596.      recombined  someday, will produce new offspring and give birth to new
  1597.      EA paradigm(s).
  1598.  
  1599.  Promising Rookies
  1600.      As far as "solving complex function  and  combinatorial  optimization
  1601.      tasks"  is  concerned,  Davis work on real-valued representations and
  1602.      adaptive operators should be mentioned (Davis 89). Moreover Whitley's
  1603.      GENITOR  system  incorporating  ranking  and "steady state" mechanism
  1604.  
  1605.  
  1606.  
  1607. Version 0.6               Posted: 20 August 1993                        24
  1608.  
  1609.  
  1610.  
  1611.  
  1612.  
  1613.  
  1614.  
  1615. FAQ(1/3)                          ANSWERS                         FAQ(1/3)
  1616.  
  1617.  
  1618.  
  1619.      (Whitley   89),   Goldberg's   "messy   GAs",    involves    adaptive
  1620.      representations (Goldberg 91), and Eshelman's CHC algorithm (Eshelman
  1621.      91).
  1622.  
  1623.      For  "the  design  of  robust  learning  systems",  ie.   the   field
  1624.      characterized  by  CFS, Holland's (1986) classifier system, with it's
  1625.      state-of-the-art implementation CFS-C  (Riolo  88),  we  should  note
  1626.      recent  developments  in  SAMUEL  (Grefenstette 89), GABIL (De Jong &
  1627.      Spears 91), and GIL (Janikow 91).
  1628.  
  1629.      References
  1630.  
  1631.      (Davis 89) Davis, L.  "Adapting  operator  probabilities  in  genetic
  1632.      algorithms", [ICGA89], 60-69.
  1633.  
  1634.      (Whitley  89) Whitley, D. et al. "The GENITOR algorithm and selection
  1635.      pressure: why rank-based allocation of reproductive trials is  best",
  1636.      [ICGA89], 116-121.
  1637.  
  1638.      (Goldberg  91) Goldberg, D. et al. "Don't worry, be messy", [ICGA91],
  1639.      24-30.
  1640.  
  1641.      (Eshelman 91) Eshelman, L.J. et al. "Preventing premature convergence
  1642.      in genetic algorithms by preventing incest", [ICGA91], 115-122.
  1643.  
  1644.      (Holland  86)  Holland, J.H. "Escaping brittleness: The possibilities
  1645.      of general-purpose learning algorithms applied to parallel rule-based
  1646.      systems".   In R. Michalski, J. Carbonell, T. Mitchell (eds), Machine
  1647.      Learning: An artificial  Intelligence  Approach.  Los  Altos:  Morgan
  1648.      Kaufmann.
  1649.  
  1650.      (Riolo  88)  Riolo,  R.L.  "CFS-C:  A  package  of domain independent
  1651.      subroutines for implementing classifier systems in  arbitrary,  user-
  1652.      defined   environments".   Logic  of  computers  group,  Division  of
  1653.      computer science and engineering, University of Michigan.
  1654.  
  1655.      (Grefenstette 89) Grefenstette, J.J. "A system for  learning  control
  1656.      strategies with genetic algorithms", [ICGA89], 183-190.
  1657.  
  1658.      (De  Jong  &  Spears  91)  De  Jong KA. & Spears W. "Learning concept
  1659.      classification rules using genetic  algorithms".  Proc.  12th  IJCAI,
  1660.      651-656, Sydney, Australia: Morgan Kaufmann.
  1661.  
  1662.      (Janikow  91)  Janikow  C. "Inductive learning of decision rules from
  1663.      attribute-based examples:  A  knowledge-intensive  genetic  algorithm
  1664.      approach". TR91-030, The University of North Carolina at Chapel Hill,
  1665.      Dept. of Computer Science, Chapel Hill, NC.
  1666.  
  1667. A4.1) What about Tierra, VENUS, etc.?
  1668.      None of these are Evolutionary Algorithms, but all of  them  use  the
  1669.      evolutionary methaphora as their "playground". [..]
  1670.  
  1671.  
  1672.  
  1673. Version 0.6               Posted: 20 August 1993                        25
  1674.  
  1675.  
  1676.  
  1677.  
  1678.  
  1679.  
  1680.  
  1681. FAQ(1/3)                          ANSWERS                         FAQ(1/3)
  1682.  
  1683.  
  1684.  
  1685.  Tierra
  1686.      "This  project  involves inoculating the process of evolution into an
  1687.      artificial   medium.   Self-replicating   machine   code   algorithms
  1688.      (``creatures'')  are run on computers in which mutations occur in the
  1689.      form of bit flips. The result is evolution by natural selection.  The
  1690.      project encompasses both biological and computational goals: To study
  1691.      the PROCESS of evolution in detail, through analysis of sequences  of
  1692.      events  and genetic changes. To observe the envelopes of evolutionary
  1693.      possibilities, both under identical and very different conditions. To
  1694.      understand  what  factors affect the shapes of phylogenetic trees. To
  1695.      understand  what  are  the  elements  of  evolvability   in   genetic
  1696.      languages.  To  understand what elements are required for an evolving
  1697.      system to spontaneously increase in diversity and complexity,  as  in
  1698.      the   transition  from  single  celled  to  multi-cellular  life.  To
  1699.      experiment with the control of evolution of machine code  algorithms,
  1700.      for  the  purpose  of  breeding programs to do useful work. This work
  1701.      will lead to a greater understanding of the process of evolution, and
  1702.      to  the possible forms that life may take on throughout the universe.
  1703.      In addition, it may provide a means (through evolution) of developing
  1704.      the  software  of  the  future,  particularly  software for massively
  1705.      parallel computers."
  1706.  
  1707.      --- from: "A Proposal: Evolution of Digital Organisms" by  Thomas  S.
  1708.      Ray (1992)
  1709.  
  1710.   Tierra by snail mail?
  1711.      Send a check for $65 US (drawn on an American bank), to:
  1712.       Virtual Life
  1713.       P.O. Box 625
  1714.       Newark, Delaware, 19715, USA
  1715.       (specify 3.5" or 5.25" disks)
  1716.  
  1717.  VENUS
  1718.      Steen  Rasmussen's  (et  al.) VENUS I+II "coreworlds" as described in
  1719.      [ALIFEII] and [LEVY92], are inspired  by  A.K.  Dewdney's  well-known
  1720.      article  (Dewdney  1984). Dewdney proposed a game called "Core Wars",
  1721.      in which hackers create computer programs that battle for control  of
  1722.      a  computer's  "core"  memory.   Since  computer  programs  are  just
  1723.      patterns of information, a successful program in  core  wars  is  one
  1724.      that  replicates  its  pattern  within the memory, so that eventually
  1725.      most of the memory contains its  pattern  rather  than  that  of  the
  1726.      competing program.
  1727.  
  1728.      VENUS  is  a modification of Core Wars in which the Computer programs
  1729.      can mutate, thus the pseudo assembler code creatures of VENUS  evolve
  1730.      steadily.   Furthermore   each   memory   location  is  endowed  with
  1731.      "resources" which, like sunshine are added  at  a  steady  state.   A
  1732.      program  must  have  sufficient resources in the regions of memory it
  1733.      occupies in order to execute.   The  input  of  resources  determines
  1734.      whether  the  VENUS ecosystem is a "jungle" or a "desert."  In jungle
  1735.      environments, Rasmussen et al. observe the spontaneous  emergence  of
  1736.  
  1737.  
  1738.  
  1739. Version 0.6               Posted: 20 August 1993                        26
  1740.  
  1741.  
  1742.  
  1743.  
  1744.  
  1745.  
  1746.  
  1747. FAQ(1/3)                          ANSWERS                         FAQ(1/3)
  1748.  
  1749.  
  1750.  
  1751.      primitive  "copy/split"  organisms  starting from (structured) random
  1752.      initial conditions.
  1753.  
  1754.      --- stripped from (Farmer & Belin 92), p.821
  1755.  
  1756.      (Dewdney 84) "Computer Recreations:  In  the  Game  called  Core  War
  1757.      Hostile  Programs  Engage  in  a  Battle of Bits", Sci. Amer. 250(5),
  1758.      14-22.
  1759.  
  1760.      (Farmer  &  Belin  92)  "Artificial  Life:  The  Coming   Evolution",
  1761.      [ALIFEII], 815-840.
  1762.  
  1763.      (Rasmussen,  et  al.  90)  "The Coreworld: Emergence and Evolution of
  1764.      Cooperative Structures in a  Computational  Chemistry",  [FORREST90],
  1765.      111-134.
  1766.  
  1767.      (Rasmussen,  et al. 92) "Dynamics of Programmable Matter", [ALIFEII],
  1768.      211-254.
  1769.  
  1770.  PolyWorld
  1771.      Larry Yaeger's PolyWorld as described in [ALIFEIII] and  [LEVY92]  is
  1772.      available   via   anonymous   ftp  from  ftp.apple.com  in  directory
  1773.      "/pub/polyworld".
  1774.  
  1775.      "The subdirectories in this "polyworld" area contain the source  code
  1776.      for the PolyWorld ecological simulator, designed and written by Larry
  1777.      Yaeger, and Copyright 1990, 1991, 1992 by Apple Computer.
  1778.  
  1779.      PostScript versions of my Artificial Life III  technical  paper  have
  1780.      now  been added to the directory.  These should be directly printable
  1781.      from most machines.  Because some unix systems' "lpr" commands cannot
  1782.      handle  very large files (ours at least), I have split the paper into
  1783.      Yaeger.ALife3.1.ps and Yaeger.ALife3.2.ps.  These files can be ftp-ed
  1784.      in  "ascii"  mode.   For  unix  users I have also included compressed
  1785.      versions of both these files (indicated by the .Z suffix),  but  have
  1786.      left the uncompressed versions around for people connecting from non-
  1787.      unix systems.  I  have  not  generated  PostScript  versions  of  the
  1788.      images,  because  they are color and the resulting files are much too
  1789.      large to store, retrieve,  or  print.   Accordingly,  though  I  have
  1790.      removed  a  Word-formatted  version  of the textual body of the paper
  1791.      that used to be here, I have left a  Word-formatted  version  of  the
  1792.      color  images.   If  you wish to acquire it, you will need to use the
  1793.      binary transfer mode to move it to first your unix host and then to a
  1794.      Macintosh  (unless  Word on a PC can read it - I don't know), and you
  1795.      may need to do something nasty like use ResEdit to set the file  type
  1796.      and  creator to match those of a standard Word document (Type = WDBN,
  1797.      Creator = MSWD).  [..]"
  1798.  
  1799.      --- from the README by Larry Yaeger <larryy@apple.com>
  1800.  
  1801.  
  1802.  
  1803.  
  1804.  
  1805. Version 0.6               Posted: 20 August 1993                        27
  1806.  
  1807.  
  1808.  
  1809.