Usenet 1994 January

home *** CD-ROM | disk | FTP | other *** search

/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / answers / ai-faq / genetic / part1 next >

Wrap

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

Path: bloom-beacon.mit.edu!usc.edu!cs.utexas.edu!uunet!Germany.EU.net!Informatik.Uni-Dortmund.DE!home!heitkoet From: joke@ls11.informatik.uni-dortmund.de (Joerg Heitkoetter) Newsgroups: comp.ai.genetic,comp.answers,news.answers Subject: FAQ: comp.ai.genetic part 1/3 (A Guide to Frequently Asked Questions) Supersedes: <part1_753815849@lusty.informatik.uni-dortmund.de> Followup-To: comp.ai.genetic Date: 27 Dec 1993 18:06:17 GMT Organization: CS Department, University of Dortmund, Germany Lines: 2917 Approved: news-answers-request@MIT.Edu Expires: 9 Feb 1994 18:06:12 GMT Message-ID: <part1_757015572@lusty.informatik.uni-dortmund.de> References: <NEWS_757015572@lusty.informatik.uni-dortmund.de> NNTP-Posting-Host: home.informatik.uni-dortmund.de Summary: This is part 1 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: joke@ls11.informatik.uni-dortmund.de (Joerg Heitkoetter) Xref: bloom-beacon.mit.edu comp.ai.genetic:1997 comp.answers:3185 news.answers:13390 Archive-name: ai-faq/genetic/part1 Last-Modified: 12/20/93 Issue: 1.10 FAQ(1/3) COMP.AI.GENETIC FAQ(1/3) The Hitch-Hiker's Guide to Evolutionary Computation (FAQ in comp.ai.genetic) edited by Joerg Heitkoetter c/o Systems Analysis Research Group, LSXI Department of Computer Science University of Dortmund D-44221 Dortmund, Germany <joke@ls11.informatik.uni-dortmund.de> or <joke@santafe.edu> (Usually FAQ means "Frequently Asked Questions," though it's sometimes referred to as "Familiar Awkward Questions" ;-) PLEASE, SEARCH THIS POSTING FIRST IF YOU HAVE A QUESTION and DON'T POST ANSWERS TO FAQs: POINT THE ASKER TO THIS POSTING and DON'T PANIC Issue 1.10 Posted: 20 December 1993 1 FAQ(1/3) PREFACE FAQ(1/3) FAQ /F-A-Q/ or /fak/ [USENET] n. 1. A Frequently Asked Question. 2. A compendium of accumulated lore, posted periodically to high-volume newsgroups in an attempt to forestall such questions. Some people prefer the term `FAQ list' or `FAQL' /fa'kl/, reserving `FAQ' for sense 1. FAQ list /F-A-Q list/ or /fak list/ [USENET] n. Syn FAQ, sense 2. FAQL /fa'kl/ n. Syn. FAQ list. RTFAQ /R-T-F-A-Q/ [USENET: primarily written, by analogy with RTFM] imp. Abbrev. for `Read the FAQ!', an exhortation that the person addressed ought to read the newsgroup's FAQ list before posting questions. RTFM /R-T-F-M/ [UNIX] imp. Acronym for `Read The Fucking Manual'. 1. Used by gurus to brush off questions they consider trivial or annoying. Compare Don't do that, then! 2. Used when reporting a problem to indicate that you aren't just asking out of randomness. "No, I can't figure out how to interface UNIX to my toaster, and yes, I have RTFM." Unlike sense 1, this use is considered polite. See also FM, RTFAQ, RTFB, RTFS, RTM, all of which mutated from RTFM, and compare UTSL. --- "The on-line hacker Jargon File, version 3.0, 29 July 1993", available via anon. ftp to ftp.gnu.ai.mit.edu as "/pub/gnu/jarg300.txt.gz" PREFACE This posting is intended to help, provide basic information, and serve as a "first straw" for individuals, i.e. uninitiated hitch- hikers, who are stranded in the mindboggling universe of Evolutionary Computation (EC); that in turn is only a small footpath to an even more mindboggling scientific universe, that, incorporating Fuzzy Systems, and Artificial Neural Networks, is sometimes referred to as Computational Intelligence (CI); that in turn is only part of an even more advanced scientific universe of mindparalysing complexity, that incorporating Artificial Life, Fractal Geometry, and other Complex Systems Sciences might someday be referred to as Natural Computation (NC). Over the course of the past years, GLOBAL OPTIMIZATION algorithms imitating certain principles of nature have proved their usefulness in various domains of applications. Especially those principles are worth copying where nature has found "stable islands" in a "turbulent ocean" of solution possibilities. Such phenomena can be found in annealing processes, central nervous systems and biological evolution which in turn have lead to the following optimization methods: Simulated Annealing (SA), Artificial Neural Networks (ANNs) and the field of Evolutionary Computation (EC). Issue 1.10 Posted: 20 December 1993 2 FAQ(1/3) PREFACE FAQ(1/3) EC may currently be characterized by the following pathways: Genetic Algorithms (GA), Evolutionary Programming (EP), Evolution Strategies (ES), Classifier Systems (CFS), Genetic Programming (GP), and several other problem solving strategies, that are based upon biological observations, that date back to CHARLES DARWIN's discoveries in the 19th century: the means of natural selection and the survival of the fittest, i.e. the "theory of evolution." The inspired algorithms are thus termed Evolutionary Algorithms (EA). Moreover, is this posting intended to introduce and help those, who are just beginning to read this newsgroup, and those who are new "on" USENET. It shall help to avoid lengthy discussions of questions that usually arise for beginners of one or the other kind, and are boring to read again and again by comp.ai.genetic "old-timers." You will see this posting popping up each month in the USENET newsgroup comp.ai.genetic (including comp.answers, and news.answers, where it should be locatable at any time). CONTRIBUTIONS Contributions, additions, corrections, cash, etc. are always welcome. Send e-mail to the address above, if it is relevant, it will be incorporated; if it is irrelevant it has even more chances to make in into the next issue... (Please format your contribution appropriately so it can just be dropped in. Unformatted contributions however, won't be rejected.) ARCHIVE SERVICE This posting (like all other FAQs, i.e. the essence of the knowledge floating through USENET) is available between postings on rtfm.mit.edu in the directory "/pub/usenet/news.answers" as the files ai-faq/genetic/part?. The FAQ may also be retrieved by e-mail from <mail-server@rtfm.mit.edu>. Send a message to the mail-server with "help" and "index" in the body on separate lines for more information. DISCLAIMER This quarterly posting (i.e., 4 issues per year) is not meant to discuss any topic exhaustively, but should be thought of as a list of reference pointers, instead. This posting is provided on an "as is" basis, NO WARRANTY whatsoever is expressed or implied, especially, NO WARRANTY that the information contained herein is up-to-date, correct or useful in any way, although all this is intended. Moreover, please note that the opinions expressed herein do not necessarily reflect those of the Systems Analysis Research Group, neither as a whole, nor in part, they are just the editor's very own collection of ideas, emerged over the past 28 years. Issue 1.10 Posted: 20 December 1993 3 FAQ(1/3) PREFACE FAQ(1/3) NOTE: some portions of this else rather dry guide are intended to be satirical. If you do not recognize it as such, consult your local doctor or a professional comedian. HITCH-HIKING THE FAQNIVERSE This guide is big. Really big. You just won't believe how hugely, vastly, mindbogglingly big it is. That's why it has been split into a trilogy, i.e. it can be pieced together from files "ai- faq/genetic/part1", "ai-faq/genetic/part2", and "ai- faq/genetic/part3". Searching for answers To find the answer of question number x, just search for the string "Ax)" (so the answer to question "Q42:" is at "A42)") What does, e.g. [ICGA85] mean? Some books would be referenced again and again, that's why they got this kind of "tag", that an experienced hitch-hiker will search for to dissolve the riddle. Why all this UPPERCASING in running text? Some words are written in all uppercase letters, e.g. EVOLUTION, you will find these reappearing in the Glossary (cf A99), with a ":" sign appended, thus if you run on, say EC you can search for the string "EC:" in the Glossary. Other typographical conventions A certain file on a certain FTP server will be specified in a certain way: <ftp-site-name>:<the-complete-filename>, as e.g. in ftp.certain.site:/pub/foo/bar.tar.gz Referencing this Guide If you want to reference this guide (although I have currently no idea, why you should want to do this), I'd be insanely proud if it looks like: Heitkoetter, Joerg, ed. (1993) "The Hitch-Hiker's Guide to Evolutionary Computation: A list of Frequently Asked Questions (FAQ)", Usenet: comp.ai.genetic. Available via anonymous ftp from rtfm.mit.edu in pub/usenet/news.answers/ai-faq/genetic/part?. ~90 pages. PostScript repositories: lumpi.informatik.uni- dortmund.de:/pub/EA/docs/hhgtec-*.ps.gz,and sfi.santafe.edu:/pub/EC/FAQ/hhgtec-*.ps.gz Or simply call it "the Guide", or "HHGTEC" for acronymaniacs. Obtaining a PostScript version For innumerable reasons this guide is written using an ancient, good old-fashioned UNIX text formatting utility, namely troff(1); better Issue 1.10 Posted: 20 December 1993 4 FAQ(1/3) PREFACE FAQ(1/3) to say the GNU version groff(1) and a hacked macro package based on "tmac.an"; it's thus easy to generate ASCII (posted), TeX DVI (not posted), and PostScript (ftpable) versions from a unique source. The latter, looks really crisp (using boldface, italics, etc.), and thus is available for those who prefer offline reading. Get file "/pub/EA/docs/hhgtec-*.ps.gz" from the SyS ftp-server: lumpi.informatik.uni-dortmund.de (129.217.36.140); or from within the US you might try: ftp.santafe.edu and get file "/pub/EC/FAQ/hhgtec-*.ps.gz". "As a net is made up of a series of ties, so everything in this world is connected by a series of ties. If anyone thinks that the mesh of a net is an independent, isolated thing, he is mistaken. It is called a net because it is made up of a series of interconnected meshes, and each mesh has its place and responsibility in relation to other meshes." --- Buddha The ZEN Puzzle For some weird reason this guide contains some puzzles which can only be solved by cautious readers who have (1) a certain amount of a certain kind of humor, (2) a certain amount of patience and time, (3) a certain amount of experience in ZEN navigation, and (4) a certain amount of books of a certain author. Usually, puzzles search either for certain answers (more often, ONE answer) to a question; or, for the real smartasses, sometimes an answer is presented, and a certain question is searched for. ZEN puzzles are even more challenging: you have to come up with an answer to a question, both of which are not explicitly, rather implicitly stated somewhere in this FAQ. Thus, you are expected to give an answer AND a question! To give an impression what this is all about, consider the following, submitted by Craig W. Reynolds. The correct question is: "Why is Fisher's `improbability quote' (cf EPILOGUE) included in this FAQ?", Craig's correct answer is: `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"' Got the message? Well, this was easy and very obvious. The other puzzles are more challenging... However, all this is just for fun (mine and hopefully yours), there is nothing like the $100 price, some big shots in computer science, e.g. Don Knuth usually offer; all there is but a honorable mentioning of the ZEN navigator, including the puzzle s/he solved. It's thus like in real life: don't expect to make money from the time being a scientist, it's all just for the fun of it... Issue 1.10 Posted: 20 December 1993 5 FAQ(1/3) PREFACE FAQ(1/3) Enjoy the trip! Issue 1.10 Posted: 20 December 1993 6 FAQ(1/3) TABLE OF CONTENTS FAQ(1/3) TABLE OF CONTENTS ai-faq/genetic/part1 Q0: Hey, what about an Introduction to all this? Q0.1 What's the precise of comp.ai.genetic? Q0.2 How do I get started? What about Usenet documentation? Q0.3 Blaah! Don't you have something more funny? Q1: What are Evolutionary Algorithms (EAs)? Q1.1: What's a Genetic Algorithm (GA)? Q1.2: What's Evolutionary Programming (EP)? Q1.3: What's an Evolution Strategy (ES)? Q1.4: What's a Classifier System (CFS)? Q1.5: What's Genetic Programming (GP)? Q2: What can you do with EAs? What can't you do with them? Q3: Who is or should be concerned with EAs? Q4: How many Evolutionary Algorithms exist? Which? Q4.1: What about Tierra, VENUS, PolyWorld, etc.? ai-faq/genetic/part2 Q5: What about all this Optimization stuff? Q10: Good introductory material about EAs? Q10.1: Books for absolute beginners? Q10.2: Textbooks? Q10.3: The Classics? Q10.4: Introductory Journal Articles? Q10.5: Introductory Technical Reports? Issue 1.10 Posted: 20 December 1993 7 FAQ(1/3) TABLE OF CONTENTS FAQ(1/3) Q10.6: Not-quite-so-introductory Literature? Q10.7: Biological Background Readings? Q10.8: Electronic Bibliography Collections? Q10.9: Videos? Q10.10:CD-ROMs? Q10.11:How do I get a copy of a dissertation? Q11: Any journals and magazines about EAs? Q12: The most important conferences concerned with EAs? Q13: Evolutionary Computation Associations? Q14: Where do I get technical reports on EAs from? Q15: Other sources of information about EAs? Q15.1: Electronic Digests? Q15.2: Electronic Mailing Lists? Q15.3: Electronic Access to Research Institutes? Q15.4: Relevant Electronic News and FAQs? Q15.5: What about all these Internet Services? ai-faq/genetic/part3 Q20: Available EA software packages? FTP sites? Q20.1: Free EA software packages? Q20.2: Commercial EA software packages? Q20.3: Software from current research projects? Q21: What are Gray codes, why might I want to use them, and how do I efficiently implement them? C Code, please? Issue 1.10 Posted: 20 December 1993 8 FAQ(1/3) TABLE OF CONTENTS FAQ(1/3) Q42: What is life all about? Q42b: Is there a FAQ to this group? Q98: What about Patents on EAs? Q99: I don't get the message. What about a Glossary on EAs? Issue 1.10 Posted: 20 December 1993 9 FAQ(1/3) ANSWERS FAQ(1/3) A0) Hey, what about an Introduction to all this? A0.1) What's the precise of comp.ai.genetic? The newsgroup comp.ai.genetic is intended as a forum for people who want to use or explore the capabilities of Genetic Algorithms (GA), Evolutionary Programming (EP), Evolution Strategies (ES), Classifier Systems (CFS), Genetic Programming (GP), and some other, less well- known problem solving algorithms that are more or less loosely coupled to the field of Evolutionary Computation (EC). A0.2) How do I get started? What about USENET documentation? The following guidelines present the essentials of the USENET online documentation, that is posted each month to news.announce.newusers. If you are already familiar with "netiquette" you don't want to read any further; if you don't know what the hell this is all about, proceed as follows: (1) carefully read the following paragraphs, (2) read all the documents in news.announce.newusers before posting any article to USENET. At least you should give the introductory stuff a try, i.e. files "news-answers/introduction" and "news-answers/news- newusers-intro". Both are survey articles, that provide a short and easy way to get an overview of the interesting parts of the online docs, and thus can help to prevent you from drowning in the megabytes to read. Both can be received either by subscribing to news.answers, or sending the following message to <mail-server@rtfm.mit.edu>: send usenet/news.answers/introduction send usenet/news.answers/news-newusers-intro quit Netiquette "Usenet is a convention, in every sense of the word." Although USENET is usually characterized as "an anarchy, with no laws and no one in charge" there have "emerged" several rules over the past years that shall facilitate life within newsgroups. Thus, you will probably find the following types of articles: 1. Requests Requests are articles of the form "I am looking for X" where X is something public like a book, an article, a piece of software. If multiple different answers can be expected, the person making the request should prepare to make a summary of the answers he/she got and announce to do so with a phrase like "Please e-mail, I'll summarize" at the end of the posting. The Subject line of the posting should then be something like "Request: X" Issue 1.10 Posted: 20 December 1993 10 FAQ(1/3) ANSWERS FAQ(1/3) 2. Questions As opposed to requests, questions are concerned with something so specific that general interest cannot readily be assumed. If the poster thinks that the topic is of some general interest, he/she should announce a summary (see above). The Subject line of the posting should be something like "Question: this-and-that" (Q: this-and-that) or have the form of a question (i.e., end with a question mark) 3. Answers These are reactions to questions or requests. As a rule of thumb articles of type "answer" should be rare. Ideally, in most cases either the answer is too specific to be of general interest (and should thus be e-mailed to the poster) or a summary was announced with the question or request (and answers should thus be e-mailed to the poster). The subject lines of answers are automatically adjusted by the news software. 4. Summaries In all cases of requests or questions the answers for which can be assumed to be of some general interest, the poster of the request or question shall summarize the answers he/she received. Such a summary should be announced in the original posting of the question or request with a phrase like "Please answer by e-mail, I'll summarize" In such a case answers should NOT be posted to the newsgroup but instead be mailed to the poster who collects and reviews them. After about 10 to 20 days from the original posting, its poster should make the summary of answers and post it to the net. Some care should be invested into a summary: a) simple concatenation of all the answers might not be enough; instead redundancies, irrelevances, verbosities and errors should be filtered out (as good as possible), b) the answers shall be separated clearly c) the contributors of the INDIVIDUAL answers shall be identifiable unless they requested to remain anonymous [eds note: yes, that happens]) d) the summary shall start with the "quintessence" of the answers, as seen by the original poster e) A summary should, when posted, clearly be indicated to be one by giving it a Subject line starting with "Summary:" Issue 1.10 Posted: 20 December 1993 11 FAQ(1/3) ANSWERS FAQ(1/3) Note that a good summary is pure gold for the rest of the newsgroup community, so summary work will be most appreciated by all of us. (Good summaries are more valuable than any moderator!) 5. Announcements Some articles never need any public reaction. These are called announcements (for instance for a workshop, conference or the availability of some technical report or software system). Announcements should be clearly indicated to be such by giving them a subject line of the form "Announcement: this-and-that", or "ust "A: this-and-that". Due to common practice, conference announcements usually carry a "CFP:" in their subject line, i.e. "call for papers" (or: "call for participation"). 6. Reports Sometimes people spontaneously want to report something to the newsgroup. This might be special experiences with some software, results of own experiments or conceptual work, or especially interesting information from somewhere else. Reports should be clearly indicated to be such by giving them a subject line of the form "Report: this-and-that" 7. Discussions An especially valuable possibility of USENET is of course that of discussing a certain topic with hundreds of potential participants. All traffic in the newsgroup that can not be subsumed under one of the above categories should belong to a discussion. If somebody explicitly wants to start a discussion, he/she can do so by giving the posting a subject line of the form "Start discussion: this-and-that" (People who react on this, please remove the "Start discussion: " label from the subject line of your replies) It is quite difficult to keep a discussion from drifting into chaos, but, unfortunately, as many other newsgroups show there seems to be no secure way to avoid this. On the other hand, comp.ai.genetic has not had many problems with this effect, yet, so let's just go and hope... Thanx in advance for your patience! A0.3) Blaah! Don't you have something more funny? Yes. Let's face it. All these files are written by USENET afficionados, and thus might offend beginners for some reasons, but there is an alternative way: The EFF recently announced the following in "EFFector Online Volume 5 No. 15, 8/20/1993" (A Publication of the Electronic Frontier Foundation, ISSN 1062-9424), available via Issue 1.10 Posted: 20 December 1993 12 FAQ(1/3) ANSWERS FAQ(1/3) comp.org.eff.news: Big Dummy's Guide to the Internet "EFF is proud to announce that the Big Dummy's Guide to the Internet is now available for free download from our ftp site. The Big Dummy's Guide is a user guide for novices on all the Internet has to offer. The genesis of the Big Dummy's Guide was a few informal conversations, which included Mitch Kapor of the Electronic Frontier Foundation (EFF) and Steve Cisler of Apple Computers, in June of 1991. With the support of Apple Computers, EFF hired a writer (Adam Gaffin) and actually took on the project in September of 1991. The idea was to write a guide to the Internet for folks who had little or no experience with network communications. The Guide is currently posted to "the 'net" in ASCII and Hypercard (Mac) formats. We have been giving it away on disk at conferences, and we hope to have a print edition available for a nominal charge soon. We're hoping to update this Guide on a regular basis, so please feel free to send us your comments and corrections. Enjoy!" The (original) Big Dummy's Guide to the Internet can be downloaded by anonymous ftp from ftp.eff.org. The ASCII version is located at /pub/Net_info/Big_Dummy/big-dummys-guide.txt . The Hypercard stack is located at /pub/Net_info/Big_Dummy/big-dummys-guide.sea.hqx . The Texinfo version (PostScript, TeXX DVI, HTML, GNU Info, ASCII) is avail. at /pub/Net_info/Big_Dummy/Big_Dummys_Guide_Texi/* (cf References of Q15) A1) What are Evolutionary Algorithms (EAs)? Evolutionary algorithms use computational models of evolutionary processes as key elements in the design and implementation of computer-based problem solving systems. A variety of evolutionary computational models have been proposed. They share a common conceptual base of simulating the EVOLUTION of INDIVIDUAL structures via processes of SELECTION, MUTATION, and REPRODUCTION. The processes depend on the perceived PERFORMANCE of the individual structures as defined by an ENVIRONMENT. More precisely, EAs maintain a POPULATION of structures, that evolve according to rules of selection and other operators, that are referred to as SEARCH OPERATORS, (GENETIC OPERATORS) such as RECOMBINATION and MUTATION. Each INDIVIDUAL in the population receives a measure of it's FITNESS in the ENVIRONMENT. REPRODUCTION focuses attention on high fitness individuals, thus EXPLOITING the available fitness information. Recombination and mutation perturb those individuals, providing general heuristics for EXPLORATION. Although simplistic from a biologist's viewpoint, these algorithms Issue 1.10 Posted: 20 December 1993 13 FAQ(1/3) ANSWERS FAQ(1/3) are sufficiently complex to provide robust and powerful ADAPTIVE SEARCH mechanisms. --- "An Overview of Evolutionary Computation" [ECML93], 442-459. PSEUDO CODE Algorithm EA is // start with an initial time t := 0; // initialize a usually random population of individuals initpopulation P (t); // evaluate fitness of all initial individuals in population evaluate P (t); // test for termination criterion (time, fitness, etc.) while not done do // increase the time counter t := t + 1; // select sub-population for offspring production P' := selectparents P (t); // recombine the "genes" of selected parents recombine P' (t); // perturb the mated population stochastically mutate P' (t); // evaluate it's new fitness evaluate P' (t); // select the survivors from actual fitness P := survive P,P' (t); od end EA. A1.1) What's a Genetic Algorithm (GA)? The GENETIC ALGORITHM is a model of MACHINE LEARNING which derives its behavior from a metaphor of the processes of EVOLUTION in nature. This is done by the creation within a machine of a POPULATION of INDIVIDUALs represented by CHROMOSOMEs, in essence a set of character strings that are analogous to the base-4 chromosomes that we see in our own DNA. The individuals in the population then go through a process of evolution. We should note that EVOLUTION (in nature or anywhere else) is not a purposive or directed process. That is, there is no evidence to Issue 1.10 Posted: 20 December 1993 14 FAQ(1/3) ANSWERS FAQ(1/3) support the assertion that the goal of evolution is to produce Mankind. Indeed, the processes of nature seem to boil down to different INDIVIDUALs competing for resources in the ENVIRONMENT. Some are better than others. Those that are better are more likely to survive and propagate their genetic material. In nature, we see that the encoding for our genetic information (GENOME) is done in a way that admits sexual REPRODUCTION (such as by budding) typically results in offspring that are genetically identical to the parent. SEXUAL REPRODUCTION allows the creation of genetically radically different offspring that are still of the same general flavor (SPECIES). At the molecular level what occurs (wild oversimplification alert!) is that a pair of CHROMOSOMEs bump into one another, exchange chunks of genetic information and drift apart. This is the RECOMBINATION operation, which GA/GPers generally refer to as CROSSOVER because of the way that genetic material crosses over from one chromosome to another. The CROSSOVER operation happens in an ENVIRONMENT where the selection of who gets to mate is a function of the FITNESS of the INDIVIDUAL, i.e. how good the individual is at competing in its environment. Some GENETIC ALGORITHMs use a simple function of the fitness measure to select individuals (probabilistically) to undergo genetic operations such as crossover or REPRODUCTION (the propagation of genetic material unaltered). This is fitness-proportionate SELECTION. Other implementations use a model in which certain randomly selected individuals in a subgroup compete and the fittest is selected. This is called tournament selection and is the form of selection we see in nature when stags rut to vie for the privilege of mating with a herd of hinds. The two processes that most contribute to EVOLUTION are crossover and fitness based selection/reproduction. As it turns out, there are mathematical proofs that indicate that the process of FITNESS proportionate REPRODUCTION is, in fact, near optimal in some senses. MUTATION also plays a role in this process, though it is not the dominant role that is popularly believed to be the process of EVOLUTION, i.e. random mutation and survival of the fittest. It cannot be stressed too strongly that the GENETIC ALGORITHM (as a simulation of a genetic process) is not a "random search" for a solution to a problem (highly fit INDIVIDUAL). The genetic algorithm uses stochastic processes, but the result is distinctly non-random (better than random). GENETIC ALGORITHMs are used for a number of different application areas. An example of this would be multidimensional optimization problems in which the character string of the CHROMOSOME can be used to encode the values for the different parameters being optimized. Issue 1.10 Posted: 20 December 1993 15 FAQ(1/3) ANSWERS FAQ(1/3) In practice, therefore, we can implement this genetic model of computation by having arrays of bits or characters to represent the CHROMOSOMEs. Simple bit manipulation operations allow the implementation of CROSSOVER, MUTATION and other operations. Although a substantial amount of research has been performed on variable- length strings and other structures, the majority of work with GENETIC ALGORITHMs is focussed on fixed-length character strings. We should focus on both this aspect of fixed-lengthness and the need to encode the representation of the solution being sought as a character string, since these are crucial aspects that distinguish GENETIC PROGRAMMING, which does not have a fixed length representation and there is typically no encoding of the problem. When the GENETIC ALGORITHM is implemented it is usually done in a manner that involves the following cycle: Evaluate the FITNESS of all of the INDIVIDUALs in the POPULATION. Create a new population by performing operations such as CROSSOVER, fitness-proportionate REPRODUCTION and MUTATION on the individuals whose fitness has just been measured. Discard the old population and iterate using the new population. One iteration of this loop is referred to as a GENERATION. There is no theoretical reason for this as an implementation model. Indeed, we do not see this punctuated behavior in POPULATIONs in nature as a whole, but it is a convenient implementation model. The first GENERATION (generation 0) of this process operates on a POPULATION of randomly generated INDIVIDUALs. From there on, the genetic operations, in concert with the FITNESS measure, operate to improve the population. PSEUDO CODE Algorithm GA is // start with an initial time t := 0; // initialize a usually random population of individuals initpopulation P (t); // evaluate fitness of all initial individuals of population evaluate P (t); // test for termination criterion (time, fitness, etc.) while not done do // increase the time counter t := t + 1; // select a sub-population for offspring production P' := selectparents P (t); Issue 1.10 Posted: 20 December 1993 16 FAQ(1/3) ANSWERS FAQ(1/3) // recombine the "genes" of selected parents recombine P' (t); // perturb the mated population stochastically mutate P' (t); // evaluate it's new fitness evaluate P' (t); // select the survivors from actual fitness P := survive P,P' (t); od end GA. A1.2) What's Evolutionary Programming (EP)? Introduction Evolutionary Programming is a stochastic optimization strategy similar to GENETIC ALGORITHMs, but which dispenses with both "genomic" representations and with RECOMBINATION as a MUTATION strategy. Like GENETIC ALGORITHMs, the EP technique is useful for optimizing problem solutions when other techniques like gradient descent or direct, analytical discovery are not possible. Combinatoric and real-valued FUNCTION OPTIMIZATION in which the optimization surface or "fitness landscape" is "rugged", possessing many locally optimal solutions, are well-suited for the EP technique. History The 1966 book, "Artificial Intelligence Through Simulated Evolution" by Fogel, Owens and Walsh is the landmark publication for applications of the EP technique. In the work, automata were evolved to predict symbol strings generated from Markov processes. In 1992, the First Annual Conference on Evolutionary Programming was held in La Jolla, CA. A second was held in 1993 and a third is planned for 1994. The first conference attracted a diverse group of academic, commericial and military researchers engaged in both developing the theory of the EP technique and in applying EP to a wide range of optimization problems. Rather than list and analyze the sources in detail, I have included several fundamental sources below which should serve as good pointers to the entire body of work in the field. The Process For EP, like GAs, there is an underlying assumption that a "fitness" landscape can be characterized in terms of variables, and that there is an optimum solution in terms of those variables. For example, if one were trying to find the shortest path in a Traveling Salesman Problem, each solution would be a path. The length of the path could Issue 1.10 Posted: 20 December 1993 17 FAQ(1/3) ANSWERS FAQ(1/3) be expressed as a number, which would serve as the solution's "fitness". The "fitness landscape" for this problem could be characterized as a hypersurface proportional to the path lengths in a space of possible paths. The goal would be to find the globally shortest path in that space. The basic EP method involves 3 steps (Repeat until a threshold for iteration is exceeded or an adequate solution is obtained): (1) Choose an initial POPULATION of trial solutions at random. The number of solutions in a population is highly relevant to the speed of optimization, but no definite answers are available as to how many solutions are appropriate (other than >1) and how many solutions are just wasteful. (2) Each solution is replicated into a new POPULATION. Each of these offspring solutions are mutated according to a distribution of MUTATION types, ranging from minor to extreme with a continuum of mutation types between. (3) Each offspring solution is assessed by computing it's FITNESS. The N best solutions, or *stochastically* N of the best solutions, are retained for the next POPULATION of solutions. EP and GAs There are two important ways in which the EP method differs from the GA technique. First, there is no constraint on the representation. The typical GA approach involves encoding the problem solutions as a string of representative tokens, the "genome". In the EP approach, the representation follows from the problem. A neural network can be represented in the same manner as it is implemented, for example, because the MUTATION operation does not demand a linear encoding. Second, the MUTATION operation simply changes aspects of the solution according to a statistical distribution which weights minor variations in offspring as highly probable and substantial variations as increasingly unlikely as the global optimum is approached. There is a certain tautology here: if the global optimum is not already known, how can the spread of the mutation operation be damped as the solutions approach it? Several techniques have been proposed and implemented which address this difficulty, the most widely studied being the "Meta-Evolutionary" technique (see Sources, below ) in which the variance of the mutation distribution is subject to mutation by a fixed variance mutation operator and evolves along with the solution. Evolution and Sex: The Argumentative Side of EP CROSSOVER as an abstraction of sexual RECOMBINATION has been questioned on several fronts by the EP community. Issue 1.10 Posted: 20 December 1993 18 FAQ(1/3) ANSWERS FAQ(1/3) The strongest criticisms have been raised by Atmar (1992) in his introductory papers in the first EP conference proceedings as well as his substantially biological "On the Role of Males" in Animal Behavior (1991). Atmar criticizes the use of terminology, indicating that "crossing-over" is a process that occurs prior to sex during meiotic cell division and its actual role in EVOLUTION is not clearly understood. More than just simple semantics, he argues a reversal of the common assumption that sex acts as an accelerator of diversity, instead casting sex as a mechanism for expunging genetic defects from the germline. Atmar additionally argues that simplistic encodings of parameters for optimization in GENETIC ALGORITHMs where one "trait" is equivalent to one symbol pattern in the GENOME misrepresents the process of natural selection and miscontrues cause and effect. He argues instead for selection at the phenotypic level. He characterizes the EP approach as being "top down" in that expressed variation at the level of the phenotype is selected without concern for the representation at lower levels, while the GA approach "celebrates" coding details potentially to the exclusion of arriving at optimal solutions. Several empirical evaluations of the value of CROSSOVER have been reported, all of which suggest that the value of crossover is not clear. References Some references to proceedings, books and journal articles which provide an excellent introduction (by no means extensive) to the field, include: Fogel, LJ, Owens, AJ and Walsh, MJ (1966) "Artificial Intelligence Through Simulated Evolution," John Wiley and Sons, NY. [primary] Fogel, DB and Atmar, JW, (eds.) (1992) "Proceedings of the First Annual Conference on Evolutionary Programming," Evolutionary Programming Society, San Diego, CA. [primary] Atmar, JW (1991) "On the Role of Males," Animal Behavior, Vol. 41, pp. 195-205. [biological] Ambati, BK, Ambati, J and Mokhtar, MM (1991) "Heuristic COMBINATORIAL OPTIMIZATION by Simulated Darwinian EVOLUTION: A Polynomial Time Algorithm for the Traveling Salesman Problem," Biological Cybernetics, Vol. 65, pp 31-35. [mathematical] Sebald, AV, Schlenzig, J and Fogel, DB (1991) "Minimax Design of CMAC Neural Controllers Using Evolutionary Programming," Proc. of the 25th Asilomar Conf. on Signals, Systems and Computers, Chen, RR (ed.), Pacific Grove, CA, pp 551-555. [practical] Issue 1.10 Posted: 20 December 1993 19 FAQ(1/3) ANSWERS FAQ(1/3) PSEUDO CODE Algorithm EP is // start with an initial time t := 0; // initialize a usually random population of individuals initpopulation P (t); // evaluate fitness of all initial individuals of population evaluate P (t); // test for termination criterion (time, fitness, etc.) while not done do // increase the time counter t := t + 1; // perturb the whole population stochastically P' := mutate P (t); // evaluate it's new fitness evaluate P' (t); // select the survivors from actual fitness P := survive P,P' (t); od end EP. It should be pointed out that EP does not use any CROSSOVER as a GENETIC OPERATOR. A1.3) What's an Evolution Strategy (ES)? [preliminary] In 1963 two students at the Technical University of Berlin (TUB) met and were soon to collaborate on experiments which used the wind tunnel of the Institute of Flow Engineering. During the search for the optimal shapes of bodies in a flow, which was then a matter of laborious intuitive experimentation, the idea was conceived of proceeding strategically. However, attempts with the coordinate and simple gradient strategies (cf Q5) were unsuccessful. Then one of the students, Ingo Rechenberg, now Professor of Bionics and Evolutionary Engineering, hit upon the idea of trying random changes in the parameters defining the shape, following the example of natural MUTATIONs. The EVOLUTION STRATEGY was born. A third student, Peter Bienert, joined them and started the construction of an automatic experimenter, which would work according to the simple rules of mutation and selection. The second student, Hans-Paul Schwefel, set about testing the efficiency of the new methods with the help of a Zuse Z23 computer; for there were plenty of objections to these "random strategies." Issue 1.10 Posted: 20 December 1993 20 FAQ(1/3) ANSWERS FAQ(1/3) In spite of an occasional lack of financial support, the Evolutionary Engineering Group which had been formed held firmly together. Ingo Rechenberg received his doctorate in 1970 (Rechenberg 73). It contains the theory of the two membered EVOLUTION strategy and a first proposal for a multimembered strategy which in the nomenclature introduced here is of the (m+1) type. In the same year financial support from the Deutsche Forschungsgemeinschaft (DFG, Germany's National Science Foundation) enabled the work, that was concluded, at least temporarily, in 1974 with the thesis "Evolutionsstrategie und numerische Optimierung" (Schwefel 77). Thus, EVOLUTION STRATEGIES were invented to solve technical optimization problems (TOPs) like e.g. constructing an optimal flashing nozzle, and until recently ES were only known to civil engineering folks, as an alternative to standard solutions. Usually no closed form analytical objective function is available for TOPs and hence, no applicable optimization method exists, but the engineer's INTUITION. The first attempts to imitate principles of organic EVOLUTION on a computer still resembled the iterative optimization methods known up to that time (cf Q5): In a two-membered or (1+1) ES, one parent generates one offspring per GENERATION by applying NORMALLY DISTRIBUTED MUTATIONs, i.e. smaller steps occur more likely than big ones, until a child performs better than its ancestor and takes its place. Because of this simple structure, theoretical results for stepsize control and CONVERGENCE VELOCITY could be derived. The ratio between successful and all mutations should come to 1/5: the so- called 1/5 SUCCESS RULE was discovered. This first algorithm, using mutation only, has then been enhanced to a (m+1) strategy which incorporated RECOMBINATION due to several, i.e. m parents being available. The mutation scheme and the exogenous stepsize control were taken across unchanged from (1+1) ESs. Schwefel later generalized these strategies to the multimembered ES now denoted by (m+l) and (m,l) which imitates the following basic principles of organic EVOLUTION: a POPULATION, leading to the possibility of RECOMBINATION with random mating, MUTATION and SELECTION. These strategies are termed PLUS STRATEGY and COMMA STRATEGY, respectively: in the plus case, the parental GENERATION is taken into account during selection, while in the comma case only the offspring undergoes selection, and the parents die off. m (usually a lowercase my, denotes the population size, and l, usually a lowercase lambda denotes the number of offspring generated per generation). Or to put it in an utterly insignificant and hopelessly outdated language: (define (Evolution-strategy population) (if (terminate? population) population (evolution-strategy Issue 1.10 Posted: 20 December 1993 21 FAQ(1/3) ANSWERS FAQ(1/3) (select (cond (plus-strategy? (union (mutate (recombine population)) population)) (comma-strategy? (mutate (recombine population)))))))) However, dealing with ES is sometimes seen as "strong tobacco," for it takes a decent amount of PROBABILITY THEORY and applied STATISTICS to understand the inner workings of an ES, while it navigates through the hyperspace of the usually n-dimensional problem space, by throwing hyperelipses into the deep... Luckily, this medium doesn't allow for much mathematical ballyhoo; the author therefore has to come up with a simple but brilliantly intriguing explanation to save the reader from falling asleep during the rest of this section, so here we go: Imagine a black box. A large black box. As large as, say for example, a Coca-Cola vending machine. Now, [..] (to be continued) A single INDIVIDUAL of the ES' POPULATION consists of the following GENOTYPE representing a point in the SEARCH SPACE: OBJECT VARIABLES Real-valued x_i have to be tuned by RECOMBINATION and MUTATION such that an objective function reaches its global optimum. Referring to the metaphor mentioned previously, the x_i represent the regulators of the alien Coka-Cola vending machine. STRATEGY VARIABLES Real-valued s_i (usually denoted by a lowercase sigma) or mean STEPSIZES determine the mutability of the x_i. They represent the STANDARD DEVIATION of a (0, s_i) GAUSSIAN DISTRIBUTION (GD) being added to each x_i as an undirected MUTATION. With an EXPECTANCY VALUE of 0 the parents will produce offsprings similar to themselves on average. In order to make a doubling and a halving of a stepsize equally probable, the s_i mutate LOG-NORMALLY, distributed, i.e. exp(GD), from generation to GENERATION. These stepsizes hide the INTERNAL MODEL the POPULATION has made of its ENVIRONMENT, i.e. a SELF-ADAPTATION of the stepsizes has replaced the exogenous control of the (1+1) ES. This concept works because selection sooner or later prefers those INDIVIDUALs having built a good model of the objective function, thus producing better offspring. Hence, LEARNING takes place on two levels: (1) at the genotypic, i.e. the object and strategy variable level and (2) at the phenotypic level, i.e. the FITNESS level. Issue 1.10 Posted: 20 December 1993 22 FAQ(1/3) ANSWERS FAQ(1/3) Depending on an individual's x_i, the resulting objective function value f(x), where x denotes the vector of objective variables, serves as the PHENOTYPE (FITNESS) in the selection step. In a plus strategy, the m best of all (m+l) INDIVIDUALs survive to become the parents of the next GENERATION. Using the comma variant, selection takes place only among the l offspring. The second scheme is more realistic and therefore more successful, because no individual may survive forever, which could at least theoretically occur using the plus variant. Untypical for conventional optimization algorithms and lavish at first sight, a comma strategy allowing intermediate deterioration performs better! Only by FORGETTING highly fit individuals a permanent adaptation of the stepsizes can take place and avoid long stagnation phases due to misadapted s_i's. This means that these individuals have built an internal model that is no longer appropriate for further progress, and thus should better be discarded. By choosing a certain ratio m/l, one can determine the convergence property of the EVOLUTION strategy: If one wants a fast, but local convergence, one should choose a small HARD SELECTION, ratio, e.g. (5,100), but looking for the global optimum, one should favour a SOFTer SELECTION (15,100). Self-adaptation within ESs depends on the following AGENTS (Schwefel 87): RANDOMNESS: One cannot model MUTATION as a pure random process. This would mean that a child is completely independent of its parents. POPULATION SIZE: The POPULATION has to be sufficiently large. Not only the current best should be allowed to reproduce, but a set of good INDIVIDUALs. Biologists have coined the term REQUISITE VARIETY being necessary to prevent a SPECIES from becoming poorer and poorer genetically and eventually dying out. COOPERATION: In order to exploit the effects of a POPULATION (m > 1), the INDIVIDUALs should recombine their knowledge with that of others (cooperate) because one cannot expect the knowledge to accumulate in the best individual only. DETERIORATION: In order to allow better internal models (stepsizes) to provide better progress in the future, one should accept deterioration from one GENERATION to the next. A limited life-span in nature is not a sign of failure, but an important means of preventing a SPECIES from freezing genetically. Issue 1.10 Posted: 20 December 1993 23 FAQ(1/3) ANSWERS FAQ(1/3) ESs prove to be successful when compared to other iterative methods on a large number of test problems (Schwefel 77). They are adaptable to nearly all sorts of problems in optimization, because they need very little information about the problem, esp. no derivatives of the objective function. For a list of some 300 applications of EAs, see the SyS-2/92 report (cf Q14). ESs are capable of solving high dimensional, multimodal, nonlinear problems subject to linear and/or nonlinear constraints. The objective function can also, e.g. be the result of a SIMULATION, it does not have to be given in a closed form. This also holds for the constraints which may represent the outcome of, e.g. a finite elements method (FEM). ESs have been adapted to VECTOR OPTIMIZATION problems (Kursawe 92), and they can also serve as a heuristic for NP-complete combinatorial problems like the TRAVELLING SALESMAN problem or problems with a noisy or changing response surface. References Kursawe, F. (1992) "Evolution strategies for vector optimization", Taipei, National Chiao Tung University, 187-193. Kursawe, F. (1994) "Evolution strategies: Simple models of natural processes?", Revue Internationale de Systemique, France (to appear). Rechenberg, I. (1973) "Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution", Stuttgart: Fromman-Holzboog. Schwefel, H.-P. (1977) "Numerische Optimierung von Computermodellen mittels der Evolutionsstrategie", Basel: Birkhaeuser. Schwefel, H.-P. (1987) "Collective Phaenomena in Evolutionary Systems", 31st Annu. Meet. Inter'l Soc. for General System Research, Budapest, 1025-1033. A1.4) What's a Classifier System (CFS)? [preliminary] The name of the Game First, a word on naming conventions is due, for no other paradigm of EC has undergone more changes to it's name space than the thread we're currently talking about. Initially, Holland called his cognitive models "Classifier Systems" abbrv. with CS, and sometimes CFS, as can be found in [GOLD89]. Whence Riolo came into play in 1986 and Holland added a REINFORCEMENT component to the overall design of a CFS, that emphasized its ability to learn, thus, the word "learning" was prepended to the name to stress the MACHINE LEARNING notion of the then called "Learning Classifier Systems" abbrv. with LCS. On October 6-9, 1992 the "1st Inter'l Workshop on Learning Classifier Systems" took place at the NASA Johnson Space Center, Houston, TX. A summary of this "summit" of all leading researchers in LCS can be found on SAFIER as Issue 1.10 Posted: 20 December 1993 24 FAQ(1/3) ANSWERS FAQ(1/3) sfi.santafe.edu:/pub/EC/CFS/papers/lcs92.ps.gz Today, the story continues, LCSs are sometimes subsumed under a "new" MACHINE LEARNING paradigm called EVOLUTIONARY REINFORCEMENT LEARNING or ERL for short, incorporating LCSs, Q-Learning, devised by Watkins (1989), and a paradigm of the same name, devised by Ackley and Littman [ALIFEIII]. On Schema Processors and ANIMATS So, to get back to the question above, "What are CFSs?", we first might answer, "Well, there are many interpretations of Holland's ideas...what do you like to know in particular?" And then we'd start with a recitation from [HOLLAND75,92], and explain all the schema processors, the broadcast language, etc. But, we will take a more comprehensive, and intuitive way to understand what classifier systems are all about. The easiest road to explore the very nature of classifier systems, is to take the ANIMAT (ANIMAl + roboT = ANIMAT) "lane" devised by Booker (1982) and later studied extensively by Wilson (1985), who also coined the term for this approach. Work continues on ANIMATs but is often regarded as ARTIFICIAL LIFE rather than EVOLUTIONARY COMPUTATION. This thread of research has even its own conference series: "Simulation of Adaptive Behavior (SAB)" (cf Q12), including other notions from machine learning, connectionist learning, evolutionary robotics, etc. [NB: the latter is obvious, if an ANIMAT lives in a digital microcosm, it can be put into the real world by implantation into an autonomous robot vehicle, that has sensors/detectors (camera eyes, whiskers, etc.) and effectors (wheels, robot arms, etc.); so all what's needed is to use our algorithm as the "brain" of this vehicle, connecting the hardware parts with the software learning component. For a fascinating intro to the field see, e.g. Braitenberg (1984)] CLASSIFIER SYSTEMS, however, are yet another offspring of John Holland's aforementioned book, and can be seen as one of the early applications of GAs, for CFSs use this evolutionary algorithm to adopt their behavior toward a changing environment, as is explained below in greater detail. Holland envisioned a cognitive system capable of classification the ongoings in its environment, and then react to these ongoings appropriately. So what does it need to build such a system? Obviously, we need (1) an environment; (2) receptors that tell our system about the ongoings; (3) effectors, that let our system manipulate its environment; and (4) the system itself, conveniently a "black box" in this first approach, that has (2) and (3) attached to it, and "lives" in (1). In the ANIMAT approach, (1) usually is an artificially created digital world, e.g. in Booker's GOFER system, a 2 dimensional grid Issue 1.10 Posted: 20 December 1993 25 FAQ(1/3) ANSWERS FAQ(1/3) that contains "food" and "poison". And the GOFER itself, that walks across this grid and tries (a) to learn to distinguish between these two items, and (b) survive well fed. Much the same for Wilson's animat, called "*". Yes, it's just an asterisk, and a "Kafka-esque naming policy" is one of the sign posts of the whole field; e.g. the first implementation by Holland and Reitmann 1978 was called CS-1, cognitive system 1; Smith' Poker player LS-1 (1980) followed this "convention"; Riolo's 1988 LCS implementations on top of his CFS-C library (cf Q20), were dubbed FSW-1 (Finite State World 1), and LETSEQ-1 (LETter SEQuence predictor 1). So from the latter paragraph we can conclude that ENVIRONMENT can also mean something completely different (e.g. an infinite stream of letters, time serieses, etc.) than in the ANIMAT approach, but anyway; we'll stick to it, and go on. Imagine a very simple ANIMAT, e.g., a simplified model of a frog. Now, we know that frogs live in (a) Muppet Shows, or (b) little ponds; so we chose the latter as our demo environment (1); and the former for a non-Kafka-esque name of our model, so let's dub it "Kermit". Kermit has eyes, i.e. sensorial input detectors (2); hands and legs, i.e. environment-manipulating effectors (3); is a spicy-fly- detecting-and-eating device, i.e. a frog (4); so we got all the 4 pieces needed. Inside the Black Box The most primitive "black box" we can think of is a computer. It has inputs (2), and outputs (3), and a message passing system inbetween, that converts (i.e., computes), certain input messages into output messages, according to a set of rules, usually called the "program" of that computer. From the theory of computer science, we now borrow the simplest of all program structures, that is something called "production system" or PS for short. A PS has been shown to be computationally complete by Post (1943), that's why it is sometimes called a "Post System", and later by Minsky (1967). Although it merely consists of a set of if-then rules, it still resembles a full- fledged computer. We now term a single "if-then" rule a "classifier", and choose a representation that makes it easy to manipulate these, for example by encoding them into binary strings. We then term the set of classifiers, a "classifier population", and immediately know how to breed new rules for our system: just use a GA to generate new rules/classifiers from the current population! All what's left are the messages floating through the black box. They should also be simple strings of zeroes and ones, and are to be Issue 1.10 Posted: 20 December 1993 26 FAQ(1/3) ANSWERS FAQ(1/3) kept in a data structure, we call "the message list". With all this given, we can imagine the ongoings inside the black box as follows: The input interface (2) generates messages, i.e., 0/1 strings, that are written on the message list. Then these messages are matched against the condition-part of all classifiers, to find out which actions are to be triggered. The message list is then emptied, and the encoded actions, themselves just messages, are posted to the message list. Then, the output interface (3) checks the message list for messages concerning the effectors. And the cycle restarts. Note, that it is possible in this set-up to have "internal messages", because the message list is not emptied after (3) has checked; thus, the input interface messages are added to the initially empty list. (cf Algorithm CFS, LCS below) The general idea of the CFS is to start from scratch, i.e., from tabula rasa (without any knowledge) using a randomly generated classifier population, and let the system learn its program by INDUCTION, (cf Holland et al. 1986), this reduces the input stream to recurrent input patterns, that must be repeated over and over again, to enable the ANIMAT to classify its current situation/context and react on the ongoings appropriately. What does it need to be a frog? Let's take a look at the behavior emitted by Kermit. It lives in its digital microwilderness where it moves around randomly. [NB: This seemingly "random" behavior is not that random at all; for more on instinctive, i.e., innate behavior of non-artificial animals see, e.g. Tinbergen (1951)] Whenever a small flying object appears, that has no stripes, Kermit should eat it, because it's very likely a spicy fly, or other flying insect. If it has stripes, the insect is better left alone, because Kermit better don't bother with wasps, hornets, or bees. If Kermit encounters a large, looming object, it immediately uses its effectors to jump away, as far as possible. So, part of these behavior patterns within the "pond world", in AI sometimes called a "frame," from traditional knowledge representation techniques, Rich (1983), can be expressed in a set of "if <condition> then <action>" rules, as follows: IF small, flying object to the left THEN send @ IF small, flying object to the right THEN send % IF small, flying object centered THEN send $ IF large, looming object THEN send ! IF no large, looming object THEN send * IF * and @ THEN move head 15 degrees left IF * and % THEN move head 15 degrees right Issue 1.10 Posted: 20 December 1993 27 FAQ(1/3) ANSWERS FAQ(1/3) IF * and $ THEN move in direction head pointing IF ! THEN move rapidly away from direction head pointing Now, this set of rules has to be encoded for use within a classifier system. A possible encoding of the above rule set in CFS-C (Riolo) classifier terminology. The condition part consists of two conditions, that are combined with a logical AND, thus must be met both to trigger the associated action. This structure needs a NOT operation, (so we get NAND, and know from hardware design, that we can build any computer solely with NANDs), in CFS-C this is denoted by the `~' prefix character (rule #5). IF THEN 0000, 00 00 00 00 0000, 00 01 00 01 0000, 00 10 00 10 1111, 01 ## 11 11 ~1111, 01 ## 10 00 1000, 00 00 01 00 1000, 00 01 01 01 1000, 00 10 01 10 1111, ## ## 01 11 Obviously, string `0000' denotes small, and `00' in the fist part of the second column, denotes flying. The last two bits of column #2 encode the direction of the object approaching, where `00' means left, `01' means right, etc. In rule #4 a the "don't care symbol" `#' is used, that matches `1' and `0', i.e., the position of the large, looming object, is completely arbitrary. A simple fact, that can save Kermit's (artificial) life. PSEUDO CODE (Non-Learning CFS) Algorithm CFS is // start with an initial time t := 0; // an initially empty message list initMessageList ML (t); // and a randomly generated population of classifiers initClassifierPopulation P (t); // test for cycle termination criterion (time, fitness, etc.) while not done do // increase the time counter t := t + 1; Issue 1.10 Posted: 20 December 1993 28 FAQ(1/3) ANSWERS FAQ(1/3) // 1. detectors check whether input messages are present ML := readDetectors (t); // 2. compare ML to the classifiers and save matches ML' := matchClassifiers ML,P (t); // 3. process new messages through output interface ML := sendEffectors ML' (t); od end CFS. To convert the previous, non-learning CFS into a learning classifier system LCS, as has been proposed in Holland (1986), it takes two steps: (1) the major cycle has to be changed such that the activation of each classifier depends on some additional parameter, that can be modified as a result of experience, i.e. reinforcement from the environment; (2) and/or change the contents of the classifier list, i.e., generate new classifiers/rules, by removing, adding, or combining condition/action-parts of existing classifiers. The algorithm thus changes accordingly: PSEUDO CODE (Learning CFS) Algorithm LCS is // start with an initial time t := 0; // an initially empty message list initMessageList ML (t); // and a randomly generated population of classifiers initClassifierPopulation P (t); // test for cycle termination criterion (time, fitness, etc.) while not done do // increase the time counter t := t + 1; // 1. detectors check whether input messages are present ML := readDetectors (t); // 2. compare ML to the classifiers and save matches ML' := matchClassifiers ML,P (t); Issue 1.10 Posted: 20 December 1993 29 FAQ(1/3) ANSWERS FAQ(1/3) // 3. highest bidding classifier(s) collected in ML' wins the // "race" and post the(ir) message(s) ML' := selectMatchingClassifiers ML',P (t); // 4. tax bidding classifiers, reduce their strength ML' := taxPostingClassifiers ML',P (t); // 5. effectors check new message list for output msgs ML := sendEffectors ML' (t); // 6. receive payoff from environment (REINFORCEMENT) C := receivePayoff (t); // 7. distribute payoff/credit to classifiers (e.g. BBA) P' := distributeCredit C,P (t); // 8. Eventually (depending on t), an EA (usually a GA) is // applied to the classifier population if criterion then P := generateNewRules P' (t); else P := P' od end LCS. What's the problem with CFSs? Just to list the currently known problems that come with CFSs, would take some additional pages; therefore only some interesting papers dealing with unresolved riddles are listed; probably the best paper containing most of these is the aforementioned summary of the LCS Workshop: Smith, R.E. (1992) "A report on the first Inter'l Workshop on LCSs" avail. from SAFIER as: sfi.santafe.edu:/pub/EC/CFS/papers/lcs92.ps.gz Other noteworthy critiques on LCSs include: Wilson, S.W. (1987) "Classifier Systems and the Animat Problem" Machine Learning, 2. Wilson, S.W. (1988) "Bid Competition and Specificity Reconsidered" Complex Systems, 2(5):705-723. Wilson, S.W. & Goldberg, D.E. (1989) "A critical review of classifier systems" [ICGA89], 244-255. Goldberg, D.E., Horn, J. & Deb, K. (1992) "What makes a problem hard for a classifier system?" (containing the Goldberg citation below) is also available from SAFIER as: sfi.santafe.edu:/pub/EC/CFS/papers/lcs92-2.ps.gz Issue 1.10 Posted: 20 December 1993 30 FAQ(1/3) ANSWERS FAQ(1/3) Dorigo, M. (1993) "Genetic and Non-genetic Operators in ALECSYS" Evolutionary Computation, 1(2):151-164. The technical report, the journal article is based on is avail. from SAFIER as: sfi.santafe.edu:/pub/EC/CFS/papers/icsi92.ps.gz Smith, R.E. Forrest, S. & Perelson, A.S. (1993) "Searching for Diverse, Cooperative Populations with Genetic Algorithms" Evolutionary Computation, 1(2):127-149. Conclusions? Generally speaking: "There's much to do in CFS research!" No other notion of EC provides more space to explore and given you are interested in a PhD in the field, you might want to take a closer look at CFS. However, be warned!, to quote Goldberg: "classifier systems are a quagmire---a glorious, wondrous, and inventing quagmire, but a quagmire nonetheless." References Booker, L.B. (1982) "Intelligent behavior as an adaption to the task environment" PhD Dissertation, Univ. of Michigan, Logic of Computers Group, Ann Arbor, MI. Braitenberg, V. (1984) "Vehicles: Experiments in Synthetic Psychology" Boston, MA: MIT Press. Holland, J.H. (1986) "Escaping Brittleness: The possibilities of general-purpose learning algorithms applied to parallel rule-based systems". In: R.S. Michalski, J.G. Carbonell & T.M. Mitchell (eds), Machine Learning: An artificial intelligence approach, Vol II, 593-623, Los Altos, CA: Morgan Kaufman. Holland, J.H., et al. (1986) "Induction: Processes of Inference, Learning, and Discovery", Cambridge, MA: MIT Press. Holland, J.H. (1992) "Adaptation in natural and artificial systems" Boston, MA: MIT Press. Holland, J.H. & Reitman, J.S. (1978) "Cognitive Systems based on Adaptive Algorithms" In D.A. Waterman & F.Hayes-Roth, (eds) Pattern- directed inference systems. NY: Academic Press. Minsky, M.L. (1961) "Steps toward Artificial Intelligence" Proceedings IRE, 49, 8-30. Reprinted in E.A. Feigenbaum & J. Feldman (eds) Computers and Thought, 406-450, NY: McGraw-Hill, 1963. Minsky, M.L. (1967) "Computation: Finite and Infinite Machines" Englewood Cliffs, NJ: Prentice-Hall. Issue 1.10 Posted: 20 December 1993 31 FAQ(1/3) ANSWERS FAQ(1/3) Post, E.L. (1943) "Formal reductions of the general combinatorial decision problem" American Journal of Mathematics, 65, 197-268. Rich, E. (1983) "Artificial Intelligence" NY: McGraw-Hill. Tinbergen, N. (1951) "The Study of Instinct" NY: Oxford Univ. Press. Watkins, C. (1989) "Learning from Delayed Rewards" PhD Dissertation, Department of Psychology, Cambridge Univ., UK. Wilson, S.W. (1985) "Knowledge growth in an artificial animal" in [ICGA95], 16-23. A1.5) What's Genetic Programming (GP)? GENETIC PROGRAMMING is the extension of the genetic model of learning into the space of programs. That is, the objects that constitute the POPULATION are not fixed-length character strings that encode possible solutions to the problem at hand, they are programs that, when executed, "are" the candidate solutions to the problem. These programs are expressed in genetic programming as parse trees, rather than as lines of code. Thus, for example, the simple program "a + b * c" would be represented as: + / \ a * / \ b c or, to be precise, as suitable data structures linked together to achieve this effect. Because this is a very simple thing to do in the programming language Lisp, many GPers tend to use Lisp. However, this is simply an implementation detail. There are straightforward methods to implement GP using a non-Lisp programming ENVIRONMENT. The programs in the POPULATION are composed of elements from the FUNCTION SET and the TERMINAL SET, which are typically fixed sets of symbols selected to be appropriate to the solution of problems in the domain of interest. In GP the CROSSOVER operation is implemented by taking randomly selected subtrees in the INDIVIDUALs (selected according to FITNESS) and exchanging them. It should be pointed out that GP usually does not use any MUTATION as a GENETIC OPERATOR. A2) What can EAs do for you? What can't they do? In principle, EAs can compute any computable function, i.e. everything a normal digital computer can do. Issue 1.10 Posted: 20 December 1993 32 FAQ(1/3) ANSWERS FAQ(1/3) EAs are especially bad suited for problems that are already known how to solve, unless these problems are intended to serve as BENCHMARK PROGRAMS. Special purpose algorithms, i.e. algorithms that have a certain amount of PROBLEM DOMAIN KNOWLEDGE hard coded in them, will usually outperform EAs, so there is no BLACK MAGIC in EC. EAs should be used when there is no other known problem solving strategy, and the problem domain is NP-complete. That's where EAs come into play: heuristically finding solutions where all else fails. Following is an incomplete (sic!) list of successful EA applications: TIMETABLING Another thing that has been addressed quite successfully with GAs is timetabling. A very common manifestation of this kind of problem is the timetabling of exams or classes in Universities, etc. At the Department of ARTIFICIAL INTELLIGENCE, University of Edinburgh, timetabling the MSc exams is now done using a GA (Corne et al. 93, Fang 92). An example of the use of GAs for timetabling classes is (Abramson & Abela 1991). In the exam timetabling case, the FITNESS function for a GENOME representing a timetable involves computing degrees of punishment for various problems with the timetable, such as clashes, instances of students having to take consecutive exams, instances of students having (eg) three or more exams in one day, the degree to which heavily-subscribed exams occur late in the timetable (which makes marking harder), overall length of timetable, etc. The modular nature of the fitness function has the key to the main potential strength of using GAs for this sort of thing as opposed to using conventional search and/or constraint programming methods. The power of the GA approach is the ease with which it can handle arbitrary kinds of constraints and objectives; all such things can be handled as weighted components of the fitness function, making it easy to adapt the GA to the particular requirements of a very wide range of possible overall objectives . Very few other timetabling methods, for example, deal with such objectives at all, which shows how difficult it is (without GAs) to graft the capacity to handle arbitrary objectives onto the basic "find shortest- length timetable with no clashes" requirement. The proper way to weight/handle different objectives in the fitness function in relation to the general GA dynamics remains, however, an important research problem! GAs thus offer a combination of simplicity, flexibility & speed which competes very favorably with other approaches, but are unlikely to outperform knowledge-based (etc) methods if the best possible solution is required at any cost. Even then, however, hybridisation may yield the best of both worlds; also, the ease (if the hardware is available!) of implementing GAs in parallel enhances the possibility of using them for good, fast solutions to very hard timetabling and similar problems. Issue 1.10 Posted: 20 December 1993 33 FAQ(1/3) ANSWERS FAQ(1/3) References Corne, D. Fang, H.-L. & Mellish, C. (1993) "Solving the Modular Exam Scheduling Problem with Genetic Algorithms". Proc. of 6th Int'l Conf. on Industrial and Engineering Applications of ARTIFICIAL INTELLIGENCE & Expert Systems, ISAI, (to appear). Fang, H.-L. (1992) "Investigating GAs for scheduling", MSc Dissertation, University of Edinburgh Dept. of ARTIFICIAL INTELLIGENCE, Edinburgh, UK. Abramson & Abela (1991) "A Parallel GENETIC ALGORITHM for Solving the School Timetabling Problem'', Technical Report, Division of I.T., C.S.I.R.O, April 1991. (Division of Information Technology, C.S.I.R.O., c/o Dept. of Communication & Electronic Engineering, Royal Melbourne Institute of Technology, PO BOX 2476V, Melbourne 3001, Australia) JOB-SHOP SCHEDULING The Job-Shop Scheduling Problem (JSSP) is a very difficult NP- complete problem which, so far, seems best addressed by sophisticated branch and bound search techniques. GA researchers, however, are continuing to make progress on it. (Davis 85) started off GA research on the JSSP, (Whitley 89) reports on using the edge RECOMBINATION operator (designed initially for the TSP) on JSSPs too. More recent work includes (Nakano 91),(Yamada & Nakano 92), (Fang et al. 93). The latter three report increasingly better results on using GAs on fairly large benchmark JSSPs (from Muth & Thompson 63); neither consistently outperform branch & bound search yet, but seem well on the way. A crucial aspect of such work (as with any GA application) is the method used to encode schedules. An important aspect of some of the recent work on this is that better results have been obtained by rejecting the conventional wisdom of using binary representations (as in (Nakano 91)) in favor of more direct encodings. In (Yamada & Nakano 92), for example, a GENOME directly encodes operation completion times, while in (Fang et al. 93) genomes represent implicit instructions for building a schedule. The success of these latter techniques, especially since their applications are very important in industry, should eventually spawn advances in GA theory. Concerning the point of using GAs at all on hard job-shop scheduling problems, the same goes here as suggested above for `Timetabling': The GA approach enables relatively arbitrary constraints and objectives to be incorporated painlessly into a single optimization method. It is unlikely that GAs will outperform specialized knowledge-based and/or conventional OR-based approaches to such problems in terms of raw solution quality, however GAs offer much greater simplicity and flexibility, and so, for example, may be the best method for quick high-quality solutions, rather than finding the best possible solution at any cost. Also, of course, hybrid methods Issue 1.10 Posted: 20 December 1993 34 FAQ(1/3) ANSWERS FAQ(1/3) will have a lot to offer, and GAs are far easier to parallelize than typical knowledge-based/OR methods. Similar to the JSSP is the Open Shop Scheduling Problem (OSSP). (Fang et al. 93) reports an initial attempt at using GAs for this. Ongoing results from the same source shows reliable achievement of results within less than 0.23% of optimal on moderately large OSSPs (so far, up to 20x20), including an improvement on the previously best known solution for a benchmark 10x10 OSSP. A simpler form of job shop problem is the Flow-Shop Sequencing problem; recent successful work on applying GAs to this includes (Reeves 93)." References Davis, L. (1985) "Job-Shop Scheduling with Genetic Algorithms", [ICGA85], 136-140. Muth, J.F. & Thompson, G.L. (1963) "Industrial Scheduling". Prentice Hall, Englewood Cliffs, NJ, 1963. Nakano, R. (1991) "Conventional GENETIC ALGORITHMs for Job-Shop Problems", [ICGA91], 474-479. Reeves, C.R. (1993) "A GENETIC ALGORITHM for Flowshop Sequencing", Coventry Polytechnic Working Paper, Coventry, UK. Whitley, D., Starkweather, T. & D'Ann Fuquay (1989) "Scheduling Problems and Traveling Salesmen: The Genetic Edge RECOMBINATION Operator", [ICGA89], 133-140. Fang, H.-L., Ross, P., & Corne D. (1993) "A Promising GENETIC ALGORITHM Approach to Job - Shop Scheduling, Rescheduling & Open-Shop Scheduling Problems", [ICGA93], 375-382. Yamada, T. & Nakano, R. (1992) "A GENETIC ALGORITHM Applicable to Large-Scale Job-Shop Problems", [PPSN92], 281-290. MANAGEMENT SCIENCES "Applications of EA in management science and closely related fields like organizational ecology is a domain that has been covered by some EA researchers - with considerable bias towards scheduling problems. Since I believe that EA have considerable potential for applications outside the rather narrow domain of scheduling and related combinatorial problems, I started collecting references about the status quo of EA-applications in management science. This report intends to make available my findings to other researchers in the field. It is a short overview and lists some 230 references to current as well as finished research projects. [..] At the end of the paper, a questionnaire has been incorporated that may be used for this purpose. Other comments are also appreciated." Issue 1.10 Posted: 20 December 1993 35 FAQ(1/3) ANSWERS FAQ(1/3) --- from the Introduction of (Nissen 93) References Nissen, V. (1993) "Evolutionary Algorithms in Management Science: An Overview and List of References", Papers on Economics and EVOLUTION, edited by the European Study Group for Evolutionary Economics. This report is also avail. via anon. ftp to gwdu03.gwdg.de in directory "pub/msdos/reports/wi", file "earef.eps". Boulding, K.E. (1991) "What is evolutionary economics?", Journal of Evolutionary Economics, 1, 9-17. FURTHER APPLICATION(S) [..] References [..] A3) Who is concerned with EAs? EVOLUTIONARY COMPUTATION attracts researchers and people of quite dissimilar disciplines, i.e. EC is a interdisciplinary research field: Computer scientists Want to find out about the properties of sub-symbolic information processing with EAs and about learning, i.e. adaptive systems in general. They also build the hardware necessary to enable future EAs (precursors are already beginning to emerge) to huge real world problems, i.e. the term "massively parallel computation" [HILLIS92], springs to mind. Engineers Of many kinds want to exploit the capabilities of EAs on many areas to solve their application, esp. optimization problems. Roboticists Want to build MOBOTs (MOBile ROBOTs, i.e. R2D2's and #5's cousins) that navigate through UNCERTAIN ENVIRONMENTs, without using built-in "maps". The MOBOTS thus have to adapt to their surroundings, and learn what they can do "move-through-door" and what they can't "move- through-wall" on their own by "trial-and-error". Cognitive scientists Might view CFS as a possible apparatus to describe models of thinking and cognitive systems. Issue 1.10 Posted: 20 December 1993 36 FAQ(1/3) ANSWERS FAQ(1/3) Physicists Use EC hardware, e.g. Hillis' (Thinking Machine Corp.'s) Connection Machine to model real world problems which include thousands of variables, that run "naturally" in parallel, and thus can be modelled more easily and esp. "faster" on a parallel machine, than on a serial "PC" one. Biologists In fact many working biologists are hostile to modeling, but an entire community of POPULATION Biologists arose with the 'evolutionary synthesis' of the 1930's created by the polymaths R.A. Fisher, J.B.S. Haldane, and S. Wright. Wright's 'shifting balance' theory (balancing drift and selection in small POPULATIONS thereby avoiding local optima) is of current interest to both biologists and ECers -- populations are naturally parallel. A good exposition of current POPULATION Biology modeling is J. Maynard Smith's text Evolutionary Genetics. Richard Dawkin's Selfish Gene and Extended Phenotype are unparalleled (sic!) prose expositions of evolutionary processes. Rob Collins' papers are excellent parallel GA models of evolutionary processes (available in ICGA91 and by ftp from ftp.cognet.ucla.edu "/pub/alife/papers"). As fundamental motivation, consider Fisher's comment: "No practical biologist interested in [e.g.] sexual REPRODUCTION would be led to work out the detailed consequences experienced by organisms having three or more sexes; yet what else should [s/]he do if [s/]he wishes to understand why the sexes are, in fact, always two?" (Three sexes would make for even weirder grammar, [s/]he said...) Philosophers and some other really curious people may also be interested in EC for various reasons. A4) How many EAs exist? Which? The All Stars There are currently 3 main paradigms in EA research: GENETIC ALGORITHMs, Evolutionary Programming, and EVOLUTION Strategies. Classifier Systems and GENETIC PROGRAMMING are offspring of the GA community. Besides this leading crop, there are numerous other different approaches, alongside to hybrid experiments, i.e. there exist pieces of software that reside in some researchers computer, that have been described in papers of proceedings volumes, and may someday prove useful on a certain task. To stay in EA slang, we should think of these evolving strands as BUILDING BLOCKs, that when recombined someday, will produce new offspring and give birth to new EA paradigm(s). Promising Rookies Issue 1.10 Posted: 20 December 1993 37 FAQ(1/3) ANSWERS FAQ(1/3) As far as "solving complex function and COMBINATORIAL OPTIMIZATION tasks" is concerned, Davis work on real-valued representations and adaptive operators should be mentioned (Davis 89). Moreover Whitley's GENITOR system incorporating ranking and "steady state" mechanism (Whitley 89), Goldberg's "messy GAs", involves adaptive representations (Goldberg 91), and Eshelman's CHC algorithm (Eshelman 91). For "the design of robust learning systems", i.e. the field characterized by CFS, Holland's (1986) classifier system, with it's state-of-the-art implementation CFS-C (Riolo 88), we should note recent developments in SAMUEL (Grefenstette 89), GABIL (De Jong & Spears 91), and GIL (Janikow 91). References Davis, L. (1989) "Adapting operator probabilities in genetic algorithms", [ICGA89], 60-69. Whitley, D. et al. (1989) "The GENITOR algorithm and selection pressure: why rank-based allocation of reproductive trials is best", [ICGA89], 116-121. Goldberg, D. et al. (1991) "Don't worry, be messy", [ICGA91], 24-30. Eshelman, L.J. et al. (1991) "Preventing premature convergence in Genetic Algorithms by preventing incest", [ICGA91], 115-122. Holland, J.H. (1986) "Escaping brittleness: The possibilities of general-purpose learning algorithms applied to parallel rule-based systems". In R. Michalski, J. Carbonell, T. Mitchell (eds), Machine Learning: An Artificial Intelligence Approach. Los Altos: Morgan Kaufmann. Riolo, R.L. (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. Grefenstette, J.J. (1989) "A system for learning control strategies with genetic algorithms", [ICGA89], 183-190. De Jong K.A. & Spears W. (1991) "Learning concept classification rules using genetic algorithms". Proc. 12th IJCAI, 651-656, Sydney, Australia: Morgan Kaufmann. Janikow C. (1991) "Inductive learning of decision rules from attribute-based examples: A knowledge-intensive Genetic Algorithm approach". TR91-030, The University of North Carolina at Chapel Hill, Dept. of Computer Science, Chapel Hill, NC. Issue 1.10 Posted: 20 December 1993 38 FAQ(1/3) ANSWERS FAQ(1/3) A4.1) What about Tierra, VENUS, etc.? None of these are Evolutionary Algorithms, but all of them use the evolutionary methaphora as their "playing field". Tierra Synthetic organisms have been created based on a computer metaphor of organic life in which CPU time is the ``energy'' resource and memory is the ``material'' resource. Memory is organized into informational patterns that exploit CPU time for self-replication. MUTATION generates new forms, and EVOLUTION proceeds by natural selection as different genotypes compete for CPU time and memory space. Observation of nature shows that EVOLUTION by natural selection is capable of both optimization and creativity. Artificial models of evolution have demonstrated the optimizing ability of evolution, as exemplified by the field of GENETIC ALGORITHMs. The creative aspects of evolution have been more elusive to model. The difficulty derives in part from a tendency of models to specify the meaning of the ``genome'' of the evolving entities, precluding new meanings from emerging. I will present a natural model of evolution demonstrating both optimization and creativity, in which the GENOME consists of sequences of executable machine code. From a single rudimentary ancestral ``creature'', very quickly there evolve parasites, which are not able to replicate in isolation because they lack a large portion of the GENOME. However, these parasites search for the missing information, and if they locate it in a nearby creature, parasitize the information from the neighboring genome, thereby effecting their own replication. In some runs, hosts evolve immunity to attack by parasites. When immune hosts appear, they often increase in frequency, devastating the parasite POPULATIONs. In some runs where the community comes to be dominated by immune hosts, parasites evolve that are resistant to immunity. Hosts sometimes evolve a response to parasites that goes beyond immunity, to actual (facultative) hyper-parasitism. The hyper- parasite deceives the parasite causing the parasite to devote its energetic resources to replication of the hyper-parastie GENOME. This drives the parasites to extinction. Evolving in the absence of parasites, hyper-parasites completely dominate the community, resulting in a relatively uniform community characterize by a high degree of relationship between INDIVIDUALs. Under these circumstances, sociality evolves, in the form of creatures which can only replicate in aggregations. The cooperative behavior of the social hyper-parasites makes them vulnerable to a new class of parasites. These cheaters, hyper-hyper- parasites, insert themselves between cooperating social INDIVIDUALs, deceiving the social creatures, causing them to replicate the GENOMEs Issue 1.10 Posted: 20 December 1993 39 FAQ(1/3) ANSWERS FAQ(1/3) of the cheaters. The only genetic change imposed on the simulator is random bit flips in the machine code of the creatures. However, it turns out that parasites are very sloppy replicators. They cause significant RECOMBINATION and rearrangement of the GENOMEs. This spontaneous sexuality is a powerful force for evolutionary change in the system. One of the most interesting aspects of this instance of life is that the bulk of the EVOLUTION is based on adaptation to the biotic ENVIRONMENT rather than the physical environment. It is co-evolution that drives the system. --- "Tierra announcement" by Tom Ray (1991) Further Reseach on Tierra? This (future) project involves inoculating the process of EVOLUTION into an artificial medium. Self-replicating machine code algorithms (``creatures'') are run on computers in which MUTATIONs occur in the form of bit flips. The result is evolution by natural selection. The project encompasses both biological and computational goals: To study the PROCESS of evolution in detail, through analysis of sequences of events and genetic changes. To observe the envelopes of evolutionary possibilities, both under identical and very different conditions. To understand what factors affect the shapes of phylogenetic trees. To understand what are the elements of evolvability in genetic languages. To understand what elements are required for an evolving system to spontaneously increase in diversity and complexity, as in the transition from single celled to multi-cellular life. To experiment with the control of evolution of machine code algorithms, for the purpose of breeding programs to do useful work. This work will lead to a greater understanding of the process of evolution, and to the possible forms that life may take on throughout the universe. In addition, it may provide a means (through evolution) of developing the software of the future, particularly software for massively parallel computers. --- "A Proposal: Evolution of Digital Organisms" by Tom Ray (1992) How to get Tierra? The Tierra V4.1 source code; and the source code, and DOS executables of all tools is available now. Please note that the source code in the ftp site and the source code provided on disk will each compile and run on either DOS or UNIX platforms. It is exactly the same source code in either case. The DOS executables are available only on disk, and can not be freely distributed. If you purchase this program on disk, thank you for your support. If you obtain the source code through the net or friends, we invite you to contribute an amount that represents the program's worth to you. You may make a check in US dollars payable to Virtual Life, and mail Issue 1.10 Posted: 20 December 1993 40 FAQ(1/3) ANSWERS FAQ(1/3) the check to the address listed below. Tierra by FTP? If you use the software, be sure to pick up new versions from the ftp site. The source in the ftp site will be replaced on an occassional basis. The complete source code and documentation (but not executables) is available by anonymous ftp at: tierra.slhs.udel.edu [128.175.41.34] and life.slhs.udel.edu [128.175.41.33] in the directories: almond/, beagle/, doc/, and tierra/. To get it, ftp to tierra or life, log in as user "anonymous" and give your email address (eg. tom@udel.edu) as a password. Be sure to transfer binaries in binary mode (it is safe to transfer everything in binary mode). Each directory contains a compressed tar file (filename.tar.Z) and a SRC directory that contains all the files in raw ascii format. You can just pick up the .tar.Z files, and they will expand into the complete directory structure with the following commands (Unix only): uncompress tierra.tar.Z tar oxvf tierra.tar Tierra by snail mail? The source code, documentation and the beagle.exe file can be distributed freely, however, the executables (the .exe files in DOS) are for sale and cannot be freely distributed (with the exeception of beagle.exe). If you do not have ftp access you may obtain everything on DOS disks by making a check for $50 (US dollars drawn on a US bank) payable to Virtual Life. $20 for upgrade from earlier version (please specify your serial number and version number). Specify 3.5" 720K, or 3.5" 1.4Mb, or 5.25" 360K, or 5.25" 1.2Mb disks. Send the check to the following address: Virtual Life 25631 Jorgensen Rd. Newman, CA 95360 The DOS disks contain everything but ALmond (ALmond can be provided on disk by request, but it only runs on a Unix platform). The disks include DOS executables, source code and documentation. The DOS disks include an easy installation program. This is the same source code available in the ftp site. If you have ftp access and a compiler, there is no need to buy the disks. Issue 1.10 Posted: 20 December 1993 41 FAQ(1/3) ANSWERS FAQ(1/3) References Ray, T. S. (1991) "Is it alive, or is it GA?" Proceedings of the 1991 International Conference on Genetic Algorithms, Eds. Belew, R. K., and L. B. Booker, San Mateo, CA: Morgan Kaufmann, 527--534. Ray, T. S. (1991) "An approach to the synthesis of life." Artificial Life II, Santa Fe Institute Studies in the Sciences of Complexity, vol. XI, Eds. C. Langton, C. Taylor, J. D. Farmer, & S. Rasmussen, Redwood City, CA: Addison-Wesley, 371--408. Ray, T. S. (1991) "Population dynamics of digital organisms." Artificial Life II Video Proceedings, Ed. C. G. Langton, Redwood City, CA: Addison Wesley. Ray, T. S. (1991) "Evolution and optimization of digital organisms." Scientific Excellence in Supercomputing: The IBM 1990 Contest Prize Papers, Eds. Keith R. Billingsley, Ed Derohanes, Hilton Brown, III. Athens, GA, 30602, The Baldwin Press, The University of Georgia. Ray, T. S. (1992) "Evolution, ecology and optimization of digital organisms." Santa Fe Institute working paper 92-08-042. Ray, T. S. "Evolution, complexity, entropy, and artificial reality." submitted Physica D. Avail. as "tierra.slhs.udel.edu:/doc/PhysicaD.tex" Ray, T. S. (1993) "An evolutionary approach to synthetic biology, Zen and the art of creating life. Artificial Life 1(1): (in press). Avail. as "tierra.slhs.udel.edu:/doc/Zen.tex" VENUS Steen Rasmussen's (et al.) VENUS I+II "coreworlds" as described in [ALIFEII] and [LEVY92], are inspired by A.K. Dewdney's well-known article (Dewdney 1984). Dewdney proposed a game called "Core Wars", in which hackers create computer programs that battle for control of a computer's "core" memory (Strack 93). Since computer programs are just patterns of information, a successful program in core wars is one that replicates its pattern within the memory, so that eventually most of the memory contains its pattern rather than that of the competing program. VENUS is a modification of Core Wars in which the Computer programs can mutate, thus the pseudo assembler code creatures of VENUS evolve steadily. Furthermore each memory location is endowed with "resources" which, like sunshine are added at a steady state. A program must have sufficient resources in the regions of memory it occupies in order to execute. The input of resources determines whether the VENUS ecosystem is a "jungle" or a "desert." In jungle ENVIRONMENTs, Rasmussen et al. observe the spontaneous emergence of Issue 1.10 Posted: 20 December 1993 42 FAQ(1/3) ANSWERS FAQ(1/3) primitive "copy/split" organisms starting from (structured) random initial conditions. --- [ALIFEII], p.821 Dewdney, A.K. (1984) "Computer Recreations: In the Game called Core War Hostile Programs Engage in a Battle of Bits", Sci. Amer. 250(5), 14-22. Farmer & Belin (1992) "Artificial Life: The Coming Evolution", [ALIFEII], 815-840. Rasmussen, et al. (1990) "The Coreworld: Emergence and evolution of Cooperative Structures in a Computational Chemistry", [FORREST90], 111-134. Rasmussen, et al. (1992) "Dynamics of Programmable Matter", [ALIFEII], 211-254. Strack (1993) "Core War Frequently Asked Questions (rec.games.corewar FAQ)" Avail. by anon. ftp from rtfm.mit.edu as file "pub/usenet/news.answers/games/corewar-faq.Z". PolyWorld Larry Yaeger's PolyWorld as described in [ALIFEIII] and [LEVY92] is available via anonymous ftp from ftp.apple.com in directory "/pub/polyworld". "The subdirectories in this "polyworld" area contain the source code for the PolyWorld ecological simulator, designed and written by Larry Yaeger, and Copyright 1990, 1991, 1992 by Apple Computer. PostScript versions of my Artificial Life III technical paper have now been added to the directory. These should be directly printable from most machines. Because some unix systems' "lpr" commands cannot handle very large files (ours at least), I have split the paper into Yaeger.ALife3.1.ps and Yaeger.ALife3.2.ps. These files can be ftp-ed in "ascii" mode. For unix users I have also included compressed versions of both these files (indicated by the .Z suffix), but have left the uncompressed versions around for people connecting from non- unix systems. I have not generated PostScript versions of the images, because they are color and the resulting files are much too large to store, retrieve, or print. Accordingly, though I have removed a Word-formatted version of the textual body of the paper that used to be here, I have left a Word-formatted version of the color images. If you wish to acquire it, you will need to use the binary transfer mode to move it to first your unix host and then to a Macintosh (unless Word on a PC can read it - I don't know), and you may need to do something nasty like use ResEdit to set the file type and creator to match those of a standard Word document (Type = WDBN, Creator = MSWD). [..]" Issue 1.10 Posted: 20 December 1993 43 FAQ(1/3) ANSWERS FAQ(1/3) --- from the README by Larry Yaeger <larryy@apple.com> General Alife repositories? Also, all of the following ftp sites carry ALife related info: ftp.cognet.ucla.edu:/pub/alife life.anu.edu.au:/pub/complex_systems/alife ftp.cogs.susx.ac.uk:/pub/reports/csrp xyz.lanl.gov:/nlin-sys Issue 1.10 Posted: 20 December 1993 44 -- -joke -- Joerg Heitkoetter Systems Analysis Group "Why was I born with such University of Dortmund, Germany contemporaries?" <joke@ls11.informatik.uni-dortmund.de> -- Oscar Wilde