Newsgroups: comp.ai.genetic,comp.answers,news.answers Path: senator-bedfellow.mit.edu!bloom-beacon.mit.edu!spool.mu.edu!howland.reston.ans.net!EU.net!peer-news.britain.eu.net!yama.mcc.ac.uk!thor.cf.ac.uk!news From: David.Beasley@cs.cf.ac.uk (David Beasley) Subject: FAQ: comp.ai.genetic part 1/6 (A Guide to Frequently Asked Questions) Summary: This is part 1 of a entitled "The Hitch-Hiker's Guide to Evolutionary Computation". A periodically 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: David.Beasley@cs.cf.ac.uk (David Beasley) Sender: news@cf.ac.uk (USENET News System) Message-ID: Supersedes: Approved: news-answers-request@MIT.Edu Date: Tue, 12 Dec 1995 16:12:59 GMT Expires: Fri, 15 Mar 1996 16:13:00 GMT X-Nntp-Posting-Host: thrall References: Organization: Cardiff University of Wales Followup-To: comp.ai.genetic Lines: 512 Xref: senator-bedfellow.mit.edu comp.ai.genetic:7426 comp.answers:15858 news.answers:59798 Archive-name: ai-faq/genetic/part1 Last-Modified: 12/20/95 Issue: 3.4 The Hitch-Hiker's Guide to Evolutionary Computation (FAQ for comp.ai.genetic) edited by Joerg Heitkoetter c/o EUnet Deutschland GmbH, Research & Development TechologiePark, Emil-Figge-Str. 80, D-44227 Dortmund, Germany or and David Beasley Praxis plc 20 Manvers Street, Bath, United Kingdom BA1 1PX PLEASE: Search this document first if you have a question and If someone posts a question to the newsgroup which is answered in here DON'T POST THE ANSWER TO THE NEWSGROUP: POINT THE ASKER TO THIS FAQ and finally DON'T PANIC! Copyright (c) 1993, 1994, 1995 by Joerg Heitkoetter and David Beasley, all rights reserved. This FAQ may be posted to any USENET newsgroup, on-line service, or BBS as long as it is posted in its entirety and includes this copyright statement. This FAQ may not be distributed for financial gain. This FAQ may not be included in commercial collections or compilations without express permission from the author. 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. 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. ... --- "The on-line hacker Jargon File, version 3.0, 29 July 1993" PREFACE This guide 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 worth copying are those principles 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). 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, and theories of EVOLUTION. The inspired algorithms are thus termed Evolutionary Algorithms (EA). Moreover, this guide is intended to help those who are just beginning to read the comp.ai.genetic 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 which are boring to read again and again by comp.ai.genetic "old-timers." You will see this guide popping up periodically in the USENET newsgroup comp.ai.genetic (and also comp.answers, and news.answers, where it should be locatable at any time). ORIGIN This guide was produced by Joerg Heitkoetter (known as Joke) in early 1993, using material from many sources (see Acknowledgements ), mixed with his own brand of humour. Towards the end of 1993, Joerg handed over editorial responsibility to David Beasley . He reorganised the guide in various ways, and generally attempted to inject his own brand of orderliness. Thus, any jokes are the work of Joke. The mundane bits are David's responsibility. The guide is kept up to date, as far as possible, and new versions are issued several times a year. However, we do rely on useful information being sent to us for inclusion in the guide (we dont always have time to read comp.ai.genetic, for example). Contributions, additions, corrections, cash, etc. are therefore always welcome. Send e-mail to the address at the beginning of the guide. DISCLAIMER This periodic posting 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 editors' institutions or employers, neither as a whole, nor in part. They are just the amalgamation of the editors' collections of ideas, and contributions gleaned from other sources. NOTE: some portions of this otherwise 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" -- which, like all successful trilogies, eventually ends up consisting of more than three parts. Searching for answers To find the answer of question number x, just search for the string "Qx:". (So the answer to question 42 is at "Q42:"!) What does, e.g. [ICGA85] mean? Some books are referenced again and again, that's why they have this kind of "tag", that an experienced hitch-hiker will search for in the list of books (see Q10 and Q12 and other places) to dissolve the riddle. Here, they have a ":" appended, thus you can search for the string "[ICGA85]:" for example. Why all this UPPERCASING in running text? Words written in all uppercase letters are cross-references to entries in the Glossary (see Q99). Again, they have a ":" appended, thus if you find, say EVOLUTION, you can search for the string "EVOLUTION:" in the Glossary. FTP and HTTP naming conventions A file available on an FTP server will be specified as: : So for example, the file bar.tar.gz in the directory /pub/foo on the ftp server ftp.certain.site would be specified as: ftp.certain.site:/pub/foo/bar.tar.gz A specification ending with a "/" is a reference to a whole directory, e.g. ftp.certain.site:/pub/foo/ HTTP files are specified in a similar way, but with the prefix: http:// Referencing this Guide If you want to reference this guide it should look like: Heitkoetter, Joerg and Beasley, David, eds. (1995) "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:/pub/usenet/news.answers/ai-faq/genetic/ About 100 pages. Or simply call it "the Guide", or "HHGTEC" for acronymaniacs. Obtaining copies of this guide This FAQ is available between postings on rtfm.mit.edu:/pub/usenet/news.answers/ai-faq/genetic/ as the files: part1 to part6. The FAQ may also be retrieved by e-mail from . Send a message to the mail-server with "help" and "index" in the body on separate lines for more information. A PostScript version is also available. This looks really crisp (using boldface, italics, etc.), and is available for those who prefer offline reading. Get it from ENCORE (See Q15.3) in file FAQ/hhgtec.ps.gz (the ASCII text versions are in the same directory too). "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 your time being a scientist, it's all just for the fun of it... Enjoy the trip! TABLE OF CONTENTS Part1 Q0: How about an introduction to all this? Part2 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)? Part3 Q2: What applications of EAs are there? Q3: Who is concerned with EAs? Q4: How many EAs exist? Which? Q4.1: What about Alife systems, like Tierra and VENUS? Q5: What about all this Optimization stuff? Part4 Q10: What introductory material on EAs is there? Q10.1: Suitable background reading for beginners? Q10.2: Textbooks on EC? Q10.3: The Classics? Q10.4: Introductory Journal Articles? Q10.5: Introductory Technical Reports? Q10.6: Not-quite-so-introductory Literature? Q10.7: Biological Background Readings? Q10.8: On-line bibliography collections? Q10.9: Videos? Q10.10: CD-ROMs? Q10.11: How do I get a copy of a dissertation? Q11: What EC related journals and magazines are there? Q12: What are the important conferences/proceedings on EC? Q13: What Evolutionary Computation Associations exist? Q14: What Technical Reports are available? Q15: What information is available over the net? Q15.1: What digests are there? Q15.2: What mailing lists are there? Q15.3: What online information repositories are there? Q15.4: What relevant newsgroups and FAQs are there? Q15.5: What about all these Internet Services? Part5 Q20: What EA software packages are available? Q20.1: Free software packages? Q20.2: Commercial software packages? Q20.3: Current research projects? Part6 Q21: What are Gray codes, and why are they used? Q22: What test data is available? Q42: What is Life all about? Q42b: Is there a FAQ to this group? Q98: Are there any patents on EAs? Q99: A Glossary on EAs? ---------------------------------------------------------------------- Subject: Q0: How about an introduction to all this? Certainly. See below. What is comp.ai.genetic all about? 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). 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 can skip to the end of this answer; 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 : 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" 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:" 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... Thanks in advance for your patience! The Internet For information on internet services, see Q15.5. ------------------------------ Copyright (c) 1993-1995 by J. Heitkoetter and D. Beasley, all rights reserved. This FAQ may be posted to any USENET newsgroup, on-line service, or BBS as long as it is posted in its entirety and includes this copyright statement. This FAQ may not be distributed for financial gain. This FAQ may not be included in commercial collections or compilations without express permission from the author. End of ai-faq/genetic/part1 *************************** -- Newsgroups: comp.ai.genetic,comp.answers,news.answers Path: senator-bedfellow.mit.edu!bloom-beacon.mit.edu!news!uhog.mit.edu!news.kei.com!newsfeed.internetmci.com!in2.uu.net!EU.net!peer-news.britain.eu.net!yama.mcc.ac.uk!thor.cf.ac.uk!news From: David.Beasley@cs.cf.ac.uk (David Beasley) Subject: FAQ: comp.ai.genetic part 2/6 (A Guide to Frequently Asked Questions) Summary: This is part 2 of a entitled "The Hitch-Hiker's Guide to Evolutionary Computation". A periodically 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: David.Beasley@cs.cf.ac.uk (David Beasley) Sender: news@cf.ac.uk (USENET News System) Message-ID: Supersedes: Approved: news-answers-request@MIT.Edu Date: Tue, 12 Dec 1995 16:13:06 GMT Expires: Fri, 15 Mar 1996 16:13:00 GMT X-Nntp-Posting-Host: thrall References: Organization: Cardiff University of Wales Followup-To: comp.ai.genetic Lines: 1124 Xref: senator-bedfellow.mit.edu comp.ai.genetic:7458 comp.answers:15904 news.answers:60019 Archive-name: ai-faq/genetic/part2 Last-Modified: 12/20/95 Issue: 3.4 TABLE OF CONTENTS OF PART 2 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)? ---------------------------------------------------------------------- Subject: Q1: What are Evolutionary Algorithms (EAs)? Evolutionary algorithm is an umbrella term used to describe computer- based problem solving systems which use computational models of some of the known mechanisms EVOLUTION as key elements in their design and implementation. A variety of evolutionary algorithms have been proposed. The major ones are: GENETIC ALGORITHMs (see Q1.1), EVOLUTIONARY PROGRAMMING (see Q1.2), EVOLUTION STRATEGIEs (see Q1.3), CLASSIFIER SYSTEMs (see Q1.4), and GENETIC PROGRAMMING (see Q1.5). They all share a common conceptual base of simulating the evolution of INDIVIDUAL structures via processes of SELECTION, MUTATION, and REPRODUCTION. The processes depend on the perceived PERFORMANCE of the individual structures as defined by an ENVIRONMENT. More precisely, EAs maintain a POPULATION of structures, that evolve according to rules of SELECTION and other operators, that are referred to as "search operators", (or GENETIC OPERATORs), such as RECOMBINATION and MUTATION. Each INDIVIDUAL in the population receives a measure of it's FITNESS in the ENVIRONMENT. REPRODUCTION focuses attention on high fitness individuals, thus exploiting (cf. EXPLOITATION) the available fitness information. Recombination and mutation perturb those individuals, providing general heuristics for EXPLORATION. Although simplistic from a biologist's viewpoint, these algorithms are sufficiently complex to provide robust and powerful adaptive search mechanisms. --- "An Overview of Evolutionary Computation" [ECML93], 442-459. BIOLOGICAL BASIS To understand EAs, it is necessary to have some appreciation of the biological processes on which they are based. Firstly, we should note that EVOLUTION (in nature or anywhere else) is not a purposive or directed process. That is, there is no evidence to support the assertion that the goal of evolution is to produce Mankind. Indeed, the processes of nature seem to boil down to a haphazard GENERATION of biologically diverse organisms. Some of evolution is determined by natural SELECTION or different INDIVIDUALs competing for resources in the ENVIRONMENT. Some are better than others. Those that are better are more likely to survive and propagate their genetic material. In nature, we see that the encoding for genetic information (GENOME) is done in a way that admits asexual REPRODUCTION. Asexual reproduction typically results in OFFSPRING that are genetically identical to the PARENT. (Large numbers of organisms reproduce asexually; this includes most bacteria which some biologists hold to be the most successful SPECIES known.) Sexual REPRODUCTION allows some shuffing of CHROMOSOMEs, producing OFFSPRING that contain a combination of information from each PARENT. At the molecular level what occurs (wild oversimplification alert!) is that a pair of almost identical chromosomes bump into one another, exchange chunks of genetic information and drift apart. This is the RECOMBINATION operation, which is often referred to as CROSSOVER because of the way that biologists have observed strands of chromosomes crossing over during the exchange. RECOMBINATION happens in an ENVIRONMENT where the SELECTION of who gets to mate is largely a function of the FITNESS of the INDIVIDUAL, i.e. how good the individual is at competing in its environment. Some "luck" (random effect) is usually involved too. Some EAs use a simple function of the fitness measure to select individuals (probabilistically) to undergo genetic operations such as CROSSOVER or asexual REPRODUCTION (the propagation of genetic material unaltered). This is fitness-proportionate selection. Other implementations use a model in which certain randomly selected individuals in a subgroup compete and the fittest is selected. This is called tournament selection and is the form of selection we see in nature when stags rut to vie for the privilege of mating with a herd of hinds. Much EA research has assumed that the two processes that most contribute to EVOLUTION are CROSSOVER and FITNESS based selection/reproduction. As it turns out, there are mathematical proofs that indicate that the process of fitness proportionate REPRODUCTION is, in fact, near optimal in some senses. EVOLUTION, by definition, absolutely requires diversity in order to work. In nature, an important source of diversity is MUTATION. In an EA, a large amount of diversity is usually introduced at the start of the algorithm, by randomising the GENEs in the POPULATION. The importance of mutation, which introduces further diversity while the algorithm is running, therefore continues to be a matter of debate. Some refer to it as a background operator, simply replacing some of the original diversity which has been lost, while others view it as playing the dominant role in the evolutionary process. It cannot be stressed too strongly that an evolutionary algorithm (as a SIMULATION of a genetic process) is not a random search for a solution to a problem (highly fit INDIVIDUAL). EAs use stochastic processes, but the result is distinctly non-random (better than random). 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. ------------------------------ Subject: Q1.1: What's a Genetic Algorithm (GA)? The GENETIC ALGORITHM is a model of machine learning which derives its behavior from a metaphor of some of the mechanisms 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 simulated "evolution". 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. 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); // 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. ------------------------------ Subject: Q1.2: What's Evolutionary Programming (EP)? Introduction EVOLUTIONARY PROGRAMMING, originally conceived by Lawrence J. Fogel in 1960, is a stochastic OPTIMIZATION strategy similar to GENETIC ALGORITHMs, but instead places emphasis on the behavioral linkage between PARENTS and their OFFSPRING, rather than seeking to emulate specific GENETIC OPERATORS as observed in nature. EVOLUTIONARY PROGRAMMING is similar to EVOLUTION STRATEGIES, although the two approaches developed independently (see below). Like both ES and GAs, EP is a useful method of OPTIMIZATION when other techniques such as 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 EVOLUTIONARY PROGRAMMING. History The 1966 book, "Artificial Intelligence Through Simulated Evolution" by Fogel, Owens and Walsh is the landmark publication for EP applications, although many other papers appear earlier in the literature. In the book, finite state automata were evolved to predict symbol strings generated from Markov processes and non- stationary time series. Such evolutionary prediction was motivated by a recognition that prediction is a keystone to intelligent behavior (defined in terms of adaptive behavior, in that the intelligent organism must anticipate events in order to adapt behavior in light of a goal). In 1992, the First Annual Conference on EVOLUTIONARY PROGRAMMING was held in La Jolla, CA. Further conferences have been held annually (See Q12). The conferences attract a diverse group of academic, commercial and military researchers engaged in both developing the theory of the EP technique and in applying EP to a wide range of OPTIMIZATION problems, both in engineering and biology. Rather than list and analyze the sources in detail, several fundamental sources are listed 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 (or multiple such optima) 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 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, or more practically, to find very short tours very quickly. 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. The severity of MUTATION is judged on the basis of the functional change imposed on the PARENTS. (3) Each OFFSPRING solution is assessed by computing it's FITNESS. Typically, a stochastic tournament is held to determine N solutions to be retained for the POPULATION of solutions, although this is occasionally performed deterministically. There is no requirement that the POPULATION SIZE be held constant, however, nor that only a single OFFSPRING be generated from each PARENT. It should be pointed out that EP typically does not use any CROSSOVER as a GENETIC OPERATOR. EP and GAs There are two important ways in which EP differs from GAs. 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 EP, 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. (In this case, for a fixed topology, real- valued weights could be coded directly as their real values and mutation operates by perturbing a weight vector with a zero mean multivariate Gaussian perturbation. For variable topologies, the architecture is also perturbed, often using Poisson distributed additions and deletions.) Second, the MUTATION operation simply changes aspects of the solution according to a statistical distribution which weights minor variations in the behavior of the OFFSPRING as highly probable and substantial variations as increasingly unlikely. Further, the severity of MUTATIONS is often reduced 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 in which the variance of the mutation distribution is subject to mutation by a fixed variance mutation operator and evolves along with the solution. EP and ES The first communication between the EVOLUTIONARY PROGRAMMING and EVOLUTION STRATEGY groups occurred in early 1992, just prior to the first annual EP conference. Despite their independent development over 30 years, they share many similarities. When implemented to solve real-valued FUNCTION OPTIMIZATION problems, both typically operate on the real values themselves (rather than any coding of the real values as is often done in GAs). Multivariate zero mean Gaussian MUTATIONs are applied to each PARENT in a POPULATION and a SELECTION mechanism is applied to determine which solutions to remove (i.e., "cull") from the population. The similarities extend to the use of self-adaptive methods for determining the appropriate mutations to use -- methods in which each PARENT carries not only a potential solution to the problem at hand, but also information on how it will distribute new trials (OFFSPRING). Most of the theoretical results on CONVERGENCE (both asymptotic and velocity) developed for ES or EP also apply directly to the other. The main differences between ES and EP are: 1. SELECTION: EP typically uses STOCHASTIC SELECTION via a tournament. Each trial SOLUTION in the POPULATION faces competition against a preselected number of opponents and receives a "win" if it is at least as good as its opponent in each encounter. SELECTION then eliminates those SOLUTIONS with the least wins. In contrast, ES typically uses deterministic SELECTION in which the worst SOLUTIONS are purged from the POPULATION based directly on their function evaluation. 2. RECOMBINATION: EP is an abstraction of EVOLUTION at the level of reproductive POPULATIONs (i.e., SPECIES) and thus no RECOMBINATION mechanisms are typically used because RECOMBINATION does not occur between SPECIES (by definition: see Mayr's biological species concept). In contrast, ES is an abstraction of EVOLUTION at the level of INDIVIDUAL behavior. When self-adaptive information is incorporated this is purely GENETIC information (as opposed to PHENOTYPIC) and thus some forms of RECOMBINATION are reasonable and many forms of RECOMBINATION have been implemented within ES. Again, the effectiveness of such operators depends on the problem at hand. References Some references which provide an excellent introduction (by no means extensive) to the field, include: ARTIFICIAL INTELLIGENCE Through Simulated EVOLUTION [Fogel66] (primary) Fogel DB (1995) "Evolutionary Computation: Toward a New Philosophy of Machine Intelligence," IEEE Press, Piscataway, NJ. Proceeding of the first [EP92], second [EP93] and third [EP94] Annual Conference on EVOLUTIONARY PROGRAMMING (primary) (See Q12). 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 // perturb the whole population stochastically P'(t) := mutate P (t); // evaluate it's new fitness evaluate P' (t); // stochastically select the survivors from actual fitness P(t+1) := survive P(t),P'(t); // increase the time counter t := t + 1; od end EP. [Eds note: An extended version of this introduction is available from ENCORE (see Q15.3) in /FAQ/supplements/what-is-ep ] ------------------------------ Subject: Q1.3: What's an Evolution Strategy (ES)? 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." 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 mu, 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 (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. 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 can a permanent adaptation of the STEPSIZEs 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 purely 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" to mean the genetic variety 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. 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. ------------------------------ Subject: Q1.4: What's a Classifier System (CFS)? 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 this one. 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. So, the word "learning" was prepended to the name, to make: "Learning Classifier Systems" (abbrv. to 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 ENCORE (See Q15.3) in file 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]. And then, this latter statement is really somewhat confusing, as Marco Dorigo has pointed out in a recent letter to editors of this guide, since Q-Learning has no evolutionary component. So please let the Senior editor explain: When I wrote this part of the guide, I just had in mind that Q-Learning would make for a pretty good replacement of Holland's bucket-brigade algorithm, so I used this litte speculation to see what comes out of it; in early December 95, almost two years later, it has finally caught Marco's attention. But meanwhile, I have been proven right: Wilson has suggested to use Q- Learning in classifier system (Wilson 1994) and Dorigo & Bersini (1994) have shown that Q-Learning and the bucket-brigade are truly equivalent concepts. We would therefore be allowed to call a CFS that uses Q-Learning for rule discovery, rather than a bucket-brigade, a Q-CFS, Q-LCS, or Q- CS; in any case would the result be subsumed under the term ERL, even if Q-Learning itself is not an evolutionary algorithm! Interestingly, Wilson called his system ZCS (apparantly no "Q" inside), while Dorigo & Bersini called their system a D-Max-VSCS, or "discounted max very simple classifier system" (and if you know Q- Learning at least the D-Max part of the name will remind you of that algorithm). The latter paper can be found on ENCORE (See Q15.3) in file CFS/papers/sab94.ps.gz And by the way in [HOLLAND95] the term "classifier system" is not used anymore. You cannot find it in the index. It's a gone! Holland now stresses the adaptive component of his invention, and simply calls the resulting systems adaptive agents. These agents are then implemented within the framework of his recent invention called ECHO. (See http://alife.santafe.edu/alife/software/echo.html for more.) 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 that'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 adapt their behavior toward a changing ENVIRONMENT, as is explained below in greater detail. Holland envisioned a cognitive system capable of classifying the goings on in its ENVIRONMENT, and then reacting to these goings on appropriately. So what is needed to build such a system? Obviously, we need (1) an environment; (2) receptors that tell our system about the goings on; (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 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's 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 that's left are the messages floating through the black box. They should also be simple strings of zeroes and ones, and are to be kept in a data structure, we call "the message list". With all this given, we can imagine the goings on 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 goings on 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 had better not 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 then " 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 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; // 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); // 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 ENCORE (See Q15.3) in file 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 ENCORE (See Q15.3) in file CFS/papers/lcs92-2.ps.gz 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 ENCORE (See Q15.3) in file 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 if 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. Dorigo M. & H. Bersini (1994). "A Comparison of Q-Learning and Classifier Systems." Proceedings of From Animals to Animats, Third International Conference on Simulation of Adaptive Behavior (SAB94), Brighton, UK, D.Cliff, P.Husbands, J.-A.Meyer and S.W.Wilson (Eds.), MIT Press, 248-255. http://iridia.ulb.ac.be/dorigo/dorigo/conferences/IC.11-SAB94.ps.gz 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. (1995) "Hidden Order: How adaptation builds complexity" Reading, MA: Addison-Wesley. 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. Post, Emil L. (1943) "Formal reductions of the general combinatorial decision problem" American Journal of Mathematics, 65, 197-215. 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 [ICGA85], 16-23. Wilson, S.W. (1994) "ZCS: a zeroth level classifier system" in EC 2(1), 1-18. ------------------------------ Subject: Q1.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. More information is available in the GP mailing list FAQ. (See Q15.2) ------------------------------ Copyright (c) 1993-1995 by J. Heitkoetter and D. Beasley, all rights reserved. This FAQ may be posted to any USENET newsgroup, on-line service, or BBS as long as it is posted in its entirety and includes this copyright statement. This FAQ may not be distributed for financial gain. This FAQ may not be included in commercial collections or compilations without express permission from the author. End of ai-faq/genetic/part2 *************************** -- Newsgroups: comp.ai.genetic,comp.answers,news.answers Path: senator-bedfellow.mit.edu!bloom-beacon.mit.edu!gatech2!news.jsums.edu!news.uoregon.edu!news.kreonet.re.kr!news.kigam.re.kr!xpat.postech.ac.kr!usenet.kornet.nm.kr!agate!howland.reston.ans.net!EU.net!peer-news.britain.eu.net!yama.mcc.ac.uk!thor.cf.ac.uk!news From: David.Beasley@cs.cf.ac.uk (David Beasley) Subject: FAQ: comp.ai.genetic part 3/6 (A Guide to Frequently Asked Questions) Summary: This is part 3 of a entitled "The Hitch-Hiker's Guide to Evolutionary Computation". A periodically 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: David.Beasley@cs.cf.ac.uk (David Beasley) Sender: news@cf.ac.uk (USENET News System) Message-ID: Supersedes: Approved: news-answers-request@MIT.Edu Date: Tue, 12 Dec 1995 16:13:14 GMT Expires: Fri, 15 Mar 1996 16:13:00 GMT X-Nntp-Posting-Host: thrall References: Organization: Cardiff University of Wales Followup-To: comp.ai.genetic Lines: 809 Xref: senator-bedfellow.mit.edu comp.ai.genetic:7451 comp.answers:15897 news.answers:59983 Archive-name: ai-faq/genetic/part3 Last-Modified: 12/20/95 Issue: 3.4 TABLE OF CONTENTS OF PART 3 Q2: What applications of EAs are there? Q3: Who is concerned with EAs? Q4: How many EAs exist? Which? Q4.1: What about Alife systems, like Tierra and VENUS? Q5: What about all this Optimization stuff? ---------------------------------------------------------------------- Subject: Q2: What applications of EAs are there? In principle, EAs can compute any computable function, i.e. everything a normal digital computer can do. But EAs are especially badly suited for problems where efficient ways of solving them are already known, (unless these problems are intended to serve as benchmarks). Special purpose algorithms, i.e. algorithms that have a certain amount of problem domain knowledge hard coded into 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 This has been addressed quite successfully with GAs. A very common manifestation of this kind of problem is the timetabling of exams or classes in Universities, etc. The first application of GAs to the timetabling problem was to build the schedule of the teachers in an Italian high school. The research, conducted at the Department of Electronics and Information of Politecnico di Milano, Italy, showed that a GA was as good as Tabu Search, and better than simulated annealing, at finding teacher schedules satisfying a number of hard and soft constraints. The software package developed is now in current use in some high schools in Milano. (Colorni et al 1990) 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. References 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) Colorni A., M. Dorigo & V. Maniezzo (1990). Genetic Algorithms And Highly Constrained Problems: The Time-Table Case. Proceedings of the First International Workshop on Parallel Problem Solving from Nature, Dortmund, Germany, Lecture Notes in Computer Science 496, Springer- Verlag, 55-59. http://iridia.ulb.ac.be/dorigo/dorigo/conferences/IC.01-PPSN1.ps.gz Colorni A., M. Dorigo & V. Maniezzo (1990). Genetic Algorithms: A New Approach to the Time-Table Problem. NATO ASI Series, Vol.F 82, COMBINATORIAL OPTIMIZATION, (Ed. M.Akguel and others), Springer- Verlag, 235-239. http://iridia.ulb.ac.be/dorigo/dorigo/conferences/IC.02-NATOASI90.ps.gz Colorni A., M. Dorigo & V. Maniezzo (1990). A Genetic Algorithm to Solve the Timetable Problem. Technical Report No. 90-060, Politecnico di Milano, Italy. http://iridia.ulb.ac.be/dorigo/dorigo/tec.reps/TR.01-TTP.ps.gz 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. Fang, H.-L. (1992) "Investigating GAs for scheduling", MSc Dissertation, University of Edinburgh Dept. of Artificial Intelligence, Edinburgh, UK. 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 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)." Other scheduling problems In contrast to job shop scheduling some maintenance scheduling problems consider which activities to schedule within a planned maintenance period, rather than seeking to minimise the total time taken by the activities. The constraints on which parts may be taken out of service for maintenance at particular times may be very complex, particularly as they will in general interact. Some initial work is given in (Langdon, 1995). 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. Langdon, W.B. (1995) "Scheduling Planned Maintenance of the (UK) National Grid", cs.ucl.ac.uk:/genetic/papers/grid_aisb-95.ps 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." --- 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 from ftp.gwdg.de:/pub/msdos/reports/wi/earef.eps Boulding, K.E. (1991) "What is evolutionary economics?", Journal of Evolutionary Economics, 1, 9-17. GAME PLAYING GAs can be used to evolve behaviors for playing games. Work in evolutionary GAME THEORY typically surrounds the EVOLUTION of a POPULATION of players who meet randomly to play a game in which they each must adopt one of a limited number of moves. (Maynard-Smith 1982). Let's suppose it is just two moves, X and Y. The players receive a reward, analogous to Darwinian FITNESS, depending on which combination of moves occurs and which move they adopted. In more complicated models there may be several players and several moves. The players iterate such a game a series of times, and then move on to a new partner. At the end of all such moves, the players will have a cumulative payoff, their FITNESS. This fitness can then be used as a means of conducting something akin to Roulette-Wheel SELECTION to generate a new POPULATION. The real key in using a GA is to come up with an encoding to represent player's strategies, one that is amenable to CROSSOVER and to MUTATION. possibilities are to suppose at each iteration a player adopts X with some probability (and Y with one minus such). A player can thus be represented as a real number, or a bit-string by interpreting the decimal value of the bit string as the inverse of the probability. An alternative characterisation is to model the players as Finite State Machines, or Finite Automata (FA). These can be though of as a simple flow chart governing behaviour in the "next" play of the game depending upon previous plays. For example: 100 Play X 110 If opponent plays X go to 100 120 Play Y 130 If opponent plays X go to 100 else go to 120 Represents a strategy that does whatever its opponent did last, and begins by playing X, known as "Tit-For-Tat." (Axelrod 1982). Such machines can readily be encoded as bit-strings. Consider the encoding "1 0 1 0 0 1" to represent TFT. The first three bits, "1 0 1" are state 0. The first bit, "1" is interpreted as "Play X." The second bit, "0" is interpreted as "if opponent plays X go to state 1," the third bit, "1", is interpreted as "if the opponent plays Y, go to state 1." State 1 has a similar interpretation. Crossing over such bit-strings always yields valid strategies. SIMULATIONs in the Prisoner's dilemma have been undertaken (Axelrod 1987, Fogel 1993, Miller 1989) of these machines. Alternative representations of game players include CLASSIFIER SYSTEMs (Marimon, McGrattan and Sargent 1990, [GOLD89]), and Neural- networks (Fogel and Harrald 1994), though not necessarily with a GA. (Fogel 1993), and Fogel and Harrald 1994 use an Evolutionary Program). Other methods of evolving a POPULATION can be found in Lindgren 1991, Glance and Huberman 1993 and elsewhere. References. Axelrod, R. (1987) ``The Evolution of Strategies in the Repeated Prisoner's Dilemma,'' in [DAVIS91] Miller, J.H. (1989) ``The Coevolution of Automata in the Repeated Prisoner's Dilemma'' Santa Fe Institute Working Paper 89-003. Marimon, Ramon, Ellen McGrattan and Thomas J. Sargent (1990) ``Money as a Medium of Exchange in an Economy with Artificially Intelligent Agents'' Journal of Economic Dynamics and Control 14, pp. 329--373. Maynard-Smith, (1982) Evolution and the Theory of Games, CUP. Lindgren, K. (1991) ``Evolutionary Phenomena in Simple Dynamics,'' in [ALIFEI]. Holland, J.H and John Miller (1990) ``Artificially Adaptive Agents in Economic Theory,'' American Economic Review: Papers and Proceedings of the 103rd Annual Meeting of the American Economics Association: 365--370. Huberman, Bernado, and Natalie S. Glance (1993) "Diversity and Collective Action" in H. Haken and A. Mikhailov (eds.) Interdisciplinary Approaches to Nonlinear Systems, Springer. Fogel (1993) "Evolving Behavior in the Iterated Prisoner's Dilemma" Evolutionary Computation 1:1, 77-97 Fogel, D.B. and Harrald, P. (1994) ``Evolving Complex Behaviour in the Iterated Prisoner's Dilemma,'' Proceedings of the Fourth Annual Meetings of the Evolutionary Programming Society, L.J. Fogel and A.W. Sebald eds., World Science Press. Lindgren, K. and Nordahl, M.G. "Cooperation and Community Structure in Artificial Ecosystems", Artificial Life, vol 1:1&2, 15-38 Stanley, E.A., Ashlock, D. and Tesfatsion, L. (1994) "Iterated Prisoners Dilemma with Choice and Refusal of Partners in [ALIFEIII] 131-178 ------------------------------ Subject: Q3: 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. 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 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. ------------------------------ Subject: Q4: 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 hybrid experiments, i.e. there exist pieces of software residing in some researchers computers, that have been described in papers in conference proceedings, and may someday prove useful on certain tasks. 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 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. De Jong K.A. & Spears W. (1991) "Learning concept classification rules using genetic algorithms". Proc. 12th IJCAI, 651-656, Sydney, Australia: Morgan Kaufmann. Dorigo M. & E. Sirtori (1991)."ALECSYS: A Parallel Laboratory for Learning Classifier Systems". Proceedings of the Fourth International Conference on Genetic Algorithms, San Diego, California, R.K.Belew and L.B.Booker (Eds.), Morgan Kaufmann, 296-302. Dorigo M. (1995). "ALECSYS and the AutonoMouse: Learning to Control a Real Robot by Distributed Classifier Systems". Machine Learning, 19, 3, 209-240. Eshelman, L.J. et al. (1991) "Preventing premature convergence in genetic algorithms by preventing incest", [ICGA91], 115-122. Goldberg, D. et al. (1991) "Don't worry, be messy", [ICGA91], 24-30. Grefenstette, J.J. (1989) "A system for learning control strategies with genetic algorithms", [ICGA89], 183-190. 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. 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. 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. Whitley, D. et al. (1989) "The GENITOR algorithm and selection pressure: why rank-based allocation of reproductive trials is best", [ICGA89], 116-121. ------------------------------ Subject: Q4.1: What about Alife systems, like Tierra and VENUS? None of these are Evolutionary Algorithms, but all of them use the evolutionary metaphor 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 characterized 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 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) How to get Tierra? The complete source code and documentation (but not executables) is available by anonymous FTP at: tierra.slhs.udel.edu:/ and life.slhs.udel.edu:/ in the directories: almond/, beagle/, doc/, and tierra/. If you do not have FTP access you may obtain everything on DOS disks. For details, write to: Virtual Life, 25631 Jorgensen Rd., Newman, CA 95360. References Ray, T. S. (1991) "Is it alive, or is it GA?" in [ICGA91], 527--534. Ray, T. S. (1991) "An approach to the synthesis of life." in [ALIFEII], 371--408. Ray, T. S. (1991) "Population dynamics of digital organisms." in [ALIFEII-V]. 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). 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 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:/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:/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). [..]" --- from the README by Larry Yaeger 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/ , alife.santafe.edu:/pub/ ------------------------------ Subject: Q5: What about all this Optimization stuff? Just think of an OPTIMIZATION problem as a black box. A large black box. As large as, for example, a Coca-Cola vending machine. Now, we don't know nothing about the inner workings of this box, but see, that there are some regulators to play with, and of course we know, that we want to have a bottle of the real thing... Putting this everyday problem into a mathematical model, we proceed as follows: (1) we label all the regulators with x and a number starting from 1; the result is a vector x, i.e. (x_1,...,x_n), where n is the number of visible regulators. (2) we must find an objective function, in this case it's obvious, we want to get k bottles of the real thing, where k is equal to 1. [some might want a "greater or equal" here, but we restricted ourselves to the visible regulators (we all know that sometimes a "kick in the right place" gets use more than 1, but I have no idea how to put this mathematically...)] (3) thus, in the language some mathematicians prefer to speak in: f(x) = k = 1. So, what we have here is a maximization problem presented in a form we know from some boring calculus lessons, and we also know that there at least a dozen utterly uninteresting techniques to solve problems presented this way... What can we do in order to solve this problem? We can either try to gain more knowledge or exploit what we already know about the interior of the black box. If the objective function turns out to be smooth and differentiable, analytical methods will produce the exact solution. If this turns out to be impossible, we might resort to the brute force method of enumerating the entire SEARCH SPACE. But with the number of possibilities growing exponentially in n, the number of dimensions (inputs), this method becomes infeasible even for low- dimensional spaces. Consequently, mathematicians have developed theories for certain kinds of problems leading to specialized OPTIMIZATION procedures. These algorithms perform well if the black box fulfils their respective prerequisites. For example, Dantzig's simplex algorithm (Dantzig 66) probably represents the best known multidimensional method capable of efficiently finding the global optimum of a linear, hence convex, objective function in a SEARCH SPACE limited by linear constraints. (A USENET FAQ on linear programming is maintained by John W. Gregory of Cray Research, Inc. Try to get your hands on "linear-programming-faq" (and "nonlinear-programming-faq") that is posted monthly to sci.op-research and is mostly interesting to read.) Gradient strategies are no longer tied to these linear worlds, but they smooth their world by exploiting the objective function's first partial derivatives one has to supply in advance. Therefore, these algorithms rely on a locally linear internal model of the black box. Newton strategies additionally require the second partial derivatives, thus building a quadratic internal model. Quasi-Newton, conjugate gradient and variable metric strategies approximate this information during the search. The deterministic strategies mentioned so far cannot cope with deteriorations, so the search will stop if anticipated improvements no longer occur. In a multimodal ENVIRONMENT these algorithms move "uphill" from their respective starting points. Hence, they can only converge to the next local optimum. Newton-Raphson-methods might even diverge if a discrepancy between their internal assumptions and reality occurs. But of course, these methods turn out to be superior if a given task matches their requirements. Not relying on derivatives, polyeder strategy, pattern search and rotating coordinate search should also be mentioned here because they represent robust non-linear OPTIMIZATION algorithms (Schwefel 81). Dealing with technical OPTIMIZATION problems, one will rarely be able to write down the objective function in a closed form. We often need a SIMULATION model in order to grasp reality. In general, one cannot even expect these models to behave smoothly. Consequently, derivatives do not exist. That is why optimization algorithms that can successfully deal with black box-type situations habe been developed. The increasing applicability is of course paid for by a loss of "convergence velocity," compared to algorithms specially designed for the given problem. Furthermore, the guarantee to find the global optimum no longer exists! But why turn to nature when looking for more powerful algorithms? In the attempt to create tools for various purposes, mankind has copied, more often instinctively than geniously, solutions invented by nature. Nowadays, one can prove in some cases that certain forms or structures are not only well adapted to their ENVIRONMENT but have even reached the optimum (Rosen 67). This is due to the fact that the laws of nature have remained stable during the last 3.5 billion years. For instance, at branching points the measured ratio of the diameters in a system of blood-vessels comes close to the theoretical optimum provided by the laws of fluid dynamics (2^-1/3). This, of course, only represents a limited, engineering point of view on nature. In general, nature performs adaptation, not optimization. The idea to imitate basic principles of natural processes for optimum seeking procedures emerged more than three decades ago (cf Q10.3). Although these algorithms have proven to be robust and direct OPTIMIZATION tools, it is only in the last five years that they have caught the researchers' attention. This is due to the fact that many people still look at organic EVOLUTION as a giantsized game of dice, thus ignoring the fact that this model of evolution cannot have worked: a human germ-cell comprises approximately 50,000 GENEs, each of which consists of about 300 triplets of nucleic bases. Although the four existing bases only encode 20 different amino acids, 20^15,000,000, ie circa 10^19,500,000 different GENOTYPEs had to be tested in only circa 10^17 seconds, the age of our planet. So, simply rolling the dice could not have produced the diversity of today's complex living systems. Accordingly, taking random samples from the high-dimensional parameter space of an objective function in order to hit the global optimum must fail (Monte-Carlo search). But by looking at organic EVOLUTION as a cumulative, highly parallel sieving process, the results of which pass on slightly modified into the next sieve, the amazing diversity and efficiency on earth no longer appears miraculous. When building a model, the point is to isolate the main mechanisms which have led to today's world and which have been subjected to evolution themselves. Inevitably, nature has come up with a mechanism allowing INDIVIDUALs of one SPECIES to exchange parts of their genetic information (RECOMBINATION or CROSSOVER), thus being able to meet changing environmental conditions in a better way. Dantzig, G.B. (1966) "Lineare Programmierung und Erweiterungen", Berlin: Springer. (Linear pogramming and extensions) Kursawe, F. (1994) " Evolution strategies: Simple models of natural processes?", Revue Internationale de Systemique, France (to appear). Rosen, R. (1967) "Optimality Principles in Biologie", London: Butterworth. Schwefel, H.-P. (1981) "Numerical OPTIMIZATION of Computer Models", Chichester: Wiley. ------------------------------ Copyright (c) 1993-1995 by J. Heitkoetter and D. Beasley, all rights reserved. This FAQ may be posted to any USENET newsgroup, on-line service, or BBS as long as it is posted in its entirety and includes this copyright statement. This FAQ may not be distributed for financial gain. This FAQ may not be included in commercial collections or compilations without express permission from the author. End of ai-faq/genetic/part3 *************************** -- Newsgroups: comp.ai.genetic,comp.answers,news.answers Path: senator-bedfellow.mit.edu!bloom-beacon.mit.edu!news!uhog.mit.edu!news.kei.com!newsfeed.internetmci.com!in2.uu.net!EU.net!peer-news.britain.eu.net!yama.mcc.ac.uk!thor.cf.ac.uk!news From: David.Beasley@cs.cf.ac.uk (David Beasley) Subject: FAQ: comp.ai.genetic part 4/6 (A Guide to Frequently Asked Questions) Summary: This is part 4 of a entitled "The Hitch-Hiker's Guide to Evolutionary Computation". A periodically 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: David.Beasley@cs.cf.ac.uk (David Beasley) Sender: news@cf.ac.uk (USENET News System) Message-ID: Supersedes: Approved: news-answers-request@MIT.Edu Date: Tue, 12 Dec 1995 16:13:26 GMT Expires: Fri, 15 Mar 1996 16:13:00 GMT X-Nntp-Posting-Host: thrall References: Organization: Cardiff University of Wales Followup-To: comp.ai.genetic Lines: 1492 Xref: senator-bedfellow.mit.edu comp.ai.genetic:7459 comp.answers:15905 news.answers:60020 Archive-name: ai-faq/genetic/part4 Last-Modified: 12/20/95 Issue: 3.4 TABLE OF CONTENTS OF PART 4 Q10: What introductory material on EAs is there? Q10.1: Suitable background reading for beginners? Q10.2: Textbooks on EC? Q10.3: The Classics? Q10.4: Introductory Journal Articles? Q10.5: Introductory Technical Reports? Q10.6: Not-quite-so-introductory Literature? Q10.7: Biological Background Readings? Q10.8: On-line bibliography collections? Q10.9: Videos? Q10.10: CD-ROMs? Q10.11: How do I get a copy of a dissertation? Q11: What EC related journals and magazines are there? Q12: What are the important conferences/proceedings on EC? Q13: What Evolutionary Computation Associations exist? Q14: What Technical Reports are available? Q15: What information is available over the net? Q15.1: What digests are there? Q15.2: What mailing lists are there? Q15.3: What online information repositories are there? Q15.4: What relevant newsgroups and FAQs are there? Q15.5: What about all these Internet Services? ---------------------------------------------------------------------- Subject: Q10: What introductory material on EAs is there? There are many sources of introductory material on evolutionary algorithms: background books (see Q10.1), textbooks (see Q10.2), classical works (see Q10.3), journal articles (see Q10.4), technical reports (see Q10.5), more advanced literature (see Q10.6), biological background reading (see Q10.7), bibliography collections (see Q10.8), videos (see Q10.9) and CD-ROMs (Q10.10). Information on how to get dissertations is also given below (see Q10.11). Conference proceedings (see Q12) are also a good source of up-to-date (and sometimes introductory) material. ------------------------------ Subject: Q10.1: Suitable background reading for beginners? These books give a "flavor" of what the subject is about. Dawkins, R. (1976, 1989 2nd ed) "The Selfish Gene", Oxford: Oxford University Press. [The 2nd edition includes two new chapters] Dawkins, R. (1982) "The Extended Phenotype: The Gene as a Unit of Selection", Oxford: Oxford University Press. Dawkins, R. (1986) "The Blind Watchmaker", New York: W.W. Norton. Gonick, L. (1983) "The Cartoon Guide to Computer Science", New York: Barnes & Nobel. [eds note: features an interesting chapter on Charles Babbage in conjunction with "horse racing forecasting", if you want to use EAs to fullfill this task, better read this section first] Gonick, L. (1983) "The Cartoon Guide to Genetics", New York: Barnes & Nobel. Regis, E. (1987) "Who got Einstein's Office? Eccentricity and Genius at the Institute for Advanced Study", Reading, MA: Addison Wesley [eds note: chapters 5, 10 and 12] Levy, S. (1992) "Artificial Life: The Quest for a new Creation", New York, NY: Pantheon. [LEVY92]: [eds note: read this and you will have the urge to work in this field] Sigmund, K. (1993) "Games of Life: Explorations in Ecology, Evolution and Behaviour", Oxford: Univ. Press. 252 pp. Hard/Softcover avail. ------------------------------ Subject: Q10.2: Textbooks on EC? These books go into the "nuts and bolts" of EC. Goldberg, D.E. (1989) "Genetic Algorithms in Search, Optimization, and Machine Learning",Addison-Wesley. [GOLD89]: (Probably the most widely referenced book in the field!) Davis, L. (ed) (1991) "Handbook of Genetic Algorithms", Van Nostrand Reinhold, New York, NY. [DAVIS91]: Michalewicz, Z. (1992) Genetic algorithms + Data Structures = Evolution Programs", Springer-Verlag, New York, NY. Also second, extended edition (1994) with index. Koza, J.R. (1992), Genetic Programming: On the Programming of Computers by means of Natural Selection", Cambridge, MA: MIT Press. [KOZA92]: ------------------------------ Subject: Q10.3: The Classics? Mostly older works which have helped to shape the field. Charles Darwin (1859), "The Origin of Species", London: John Murray. (Penguin Classics, London, 1985; New American Library, Mentor Paperback) Box, G.E.P. (1957) "Evolutionary operation: a method of increasing industrial productivity", Applied Statistics, 6, 81-101. Fraser, A.S. (1957) "Simulation of genetic systems by automatic digital computers", Australian Journal of Biological Sciences, 10, 484-491. Friedman, G.J. (1959) "Digital simulation of an evolutionary process", General Systems Yearbook, 4:171-184. Bremermann, H.J. (1962) "Optimization through evolution and recombination". In M.C. Yovits, et al, (eds) Self-Organizing Systems. Washington, DC: Spartan Books. Holland, J.H. (1962) "Outline for a logical theory of adaptive systems", JACM, 3, 297-314. Samuel, A.L. (1963) "Some Studies in Machine Learning using the Game of Checkers", in Computers and Thought, E.A. Feigenbaum and J. Feldman (eds), New York: McGraw-Hill. Walter, W.G. (1963) "The Living Brain", New York: W.W. Norton. Fogel, L.J., Owens, A.J. & Walsh, M.J. (1966) "Artificial Intelligence through Simulated Evolution", New York: Wiley. [Fogel66]: Rosen, R. (1967) "Optimality Principles in Biology", London: Butterworths. Rechenberg, I. (1973, 1993 2nd edn) "Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution", Stuttgart: Fromman-Holzboog. (Evolution Strategy: Optimization of technical systems by means of biological evolution) Holland, J.H. (1975) "Adaptation in natural and artificial systems", Ann Arbor, MI: The University of Michigan Press. De Jong, K.A. (1975) "An analysis of the behavior of a class of genetic adaptive systems", Doctoral thesis, Dept. of Computer and Communication Sciences, University of Michigan, Ann Arbor. Schwefel, H.-P. (1977) "Numerische Optimierung von Computer-Modellen mittels der Evolutionsstrategie", Basel: Birkhaeuser. Schwefel, H.-P. (1981) "Numerical Optimization of Computer Models", Chichester: Wiley. [eds note: English translation of the previous entry; a reworked edition is currently in preparation for 1994] Axelrod, R. (1984) "The evolution of cooperation", NY: Basic Books. Cramer, N.L. (1985) "A Representation for the Adaptive Generation of Simple Sequential Programs" [ICGA85], 183-187. Baeck, T., Hoffmeister, F. & Schwefel, H.-P. (1991) "A Survey of Evolution Strategies" [ICGA91], 2-9. ------------------------------ Subject: Q10.4: Introductory Journal Articles? Goldberg, D.E. (1986) "The Genetic Algorithm: Who, How, and What Next?". In Kumpati S. Narenda, ed., Adaptive and Learning Systems, Plenum, New York, NY. Dawkins, R. (1987) "The Evolution of Evolvability", [ALIFEI], 201-220. Hillis, W.D. (1987) "The Connection Machine", Scientific American, 255(6). Holland, J.H. (1989) "Using Classifier Systems to Study Adaptive Nonlinear Networks". In: Lectures in the Science of Complexity, SFI Studies in the Science of Complexity, D. Stein, (ed), Addison Wesley. Brooks, R.A. (1991) "Intelligence without Reason", MIT AI Memo No. 1293. Appeared in "Computer's and Thought", IJCAI-91. Hillis, W.D. (1992) "Massively Parallel Computing" Daedalus, winter, 121(1), 1-29. [HILLIS92]: Holland, J.H. (1992) "Genetic Algorithms", Scientific American, 267(1), 66-72. [HOLLAND92]: Holland, J.H. (1992) "Complex Adaptive Systems" Daedalus, winter, 121(1), 17-30. Sims, K. (1991) "Artificial Evolution for Computer Graphics", Computer Graphics, 25(4), 319-328 Spears, W.M., DeJong, K.A., Baeck, T., Fogel, D. & de Garis, H. (1993) "An Overview of Evolutionary Computation", [ECML93], 442-459. Baeck, T. & Schwefel, H.-P. (1993) "An Overview of Evolutionary Algorithms for Parameter Optimization", Evolutionary Computation, 1(1), 1-23. Baeck, T., Rudolph, G. & Schwefel, H.-P. (1993) "Evolutionary Programming and Evolution Strategies: Similarities and Differences", [EP93], 11-22. Mitchell, M. & Forrest S. (1993) "Genetic Algorithms and Artificial Life", Artificial Life, 1(1). Also avail. as SFI Working Paper 31-11-072. Beasley, D., Bull, D.R., & Martin, R.R. (1993) "An Overview of Genetic Algortihms: Part 1, Fundamentals", University Computing, 15(2) 58-69. Available by ftp from ENCORE (See Q15.3) in file: GA/papers/over93.ps.gz or from ralph.cs.cf.ac.uk:/pub/papers/GAs/ga_overview1.ps Beasley, D., Bull, D.R., & Martin, R.R. (1993) "An Overview of Genetic Algortihms: Part 2, Research Topics", University Computing, 15(4) 170-181. Available by ftp from ENCORE (See Q15.3) in file: GA/papers/over93-2.ps.gz or from ralph.cs.cf.ac.uk:/pub/papers/GAs/ga_overview2.ps Peter Wayner (1991), "Genetic Algorithms: Programming takes a valuable tip from nature", BYTE, January, 361--368. Goldberg, D. (1994), "Genetic and Evolutionary Algorithms Come of Age", Communications of the ACM, 37(3), 113--119. ------------------------------ Subject: Q10.5: Introductory Technical Reports? Hoffmeister, F. & Baeck, T. (1990, 1992) "Genetic Algorithms and Evolution Strategies: Similarities and Differences", University of Dortmund, Dept. of CS, SyS-1/92. Available by ftp from lumpi.informatik.uni-dortmund.de: Whitley, D. (1993) "A Genetic Algorithm Tutorial", Colorado State University, Dept. of CS, TR CS-93-103. Available by ftp from beethoven.cs.colostate.edu: ------------------------------ Subject: Q10.6: Not-quite-so-introductory Literature? Bock, P. (1993) "The Emergence of Artificial Cognition: An Introduction to Collective Learning", Singapore: World Scientific. Davis, L. (ed) (1987) "Genetic Algorithms and Simulated Annealing", available from Morgan Kaufmann Publishers Inc., 340 Pine St, San Francisco, CA 94104, (415-392-2665). Davidor, Y. (1991) "Genetic Algorithms and Robotics", Singapore: World Scientific. ISBN 9-810202172. Forrest, S. (ed) (1990) "Emergent Computation. Self-Organizing, Collective, and Cooperative Phenomena in Natural and Artificial Computing Networks", [FORREST90]:, Cambridge, MA: MIT Press. (Special issue of Physica D.) Hillis, W.D. (1990) "Co-Evolving Parasites Improve Simulated Evolution as an Optimization procedure", [ALIFEII], 313-324. Holland, J.H., Holyoak, K.J., Nisbett, R.E. & Thagard, P.R. (1986) "Induction: Processes of Inference, Learning, and Discovery", Cambridge, MA: MIT Press. Holland, J.H. (1992) "Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence, Cambridge, MA: MIT Press/Bradford Books, (2nd edn). Hard: ISBN 0-262-08213-6. Soft: ISBN 0-262-58111-6. Serra, R. & Zanarini, G. (1990) "Complex Systems and Cognitive Processes", New York, NY: Springer-Verlag. Stender, J. (ed.). (1993) "Parallel Genetic Algorithms", IOS Publishing. [Cites just about everything in the parallel GA field. -- John Koza] Rujan, P. (1988) "Searching for optimal configurations by simulated tunneling", Zeitschrift der Physik B", Vol.73, 391-416. Rudolph, G. (1994) "Convergence Analysis of Canonical Genetic Algorithms", IEEE Trans. on Neural Networks, Special issue on EP. Available by ftp from ENCORE (See Q15.3) in file: GA/papers/canon94.ps.gz Fogel, D. (1995), "Evolutionary Computation: Toward a New Philosophy of Machine Intelligence", Piscataway, NJ: IEEE Press. ISBN 0-7803-1048-0. Schwefel, H-P. (1995) "Evolution and Optimum Seeking", New York: Wiley. ISBN 0-471-57148-2 ------------------------------ Subject: Q10.7: Biological Background Readings? Adams, D. with Carwardine M. (1990) "Last Chance to see...", London: Heinemann. [David Corne: I strongly suggest you read this. Its a report on visits to various parts of the world to see endangered species. It is remarkably and wonderfully funny and illuminating. It would actually be a good reference to have in any bit of the FAQ to do with genetic diversity and/or the lack of it, or the remarkable kinds of adaptations that can occur for the strangest reasons.] Cairns-Smith, A.G. (1985) "Seven Clues to the Origin of Life", Cambridge: Cambridge Univ. Press. Fisher, R.A. (1958) "The Genetic Theory of Natural Selection", New York: Dover. Futuyma, D.J. (1986) "Evolutionary Biology", Sunderland, MA: Sinauer Assoc. [eds note: the bibliography of this book is truly a treasure chest] Lewin, B. (1993) "Genes IV". Lewontin, R.C. (1974) "The Genetic Basis of Evolutionary Change", New York: Columbia Univ. Press. Maynard Smith, J. (1972) "On Evolution", Edinburgh: Edinburgh Univ. Press. Maynard Smith, J. (1978) "Optimization Theory in Evolution", Annual Review of Ecology and Systematics 9:31-56. Maynard Smith, J. (1982) "Evolution and the Theory of Games", Cambridge: Cambridge Univ. Press. Maynard Smith, J. (1989) "The Problems of Biology", Oxford: Oxford Univ. Press. Maynard Smith, J. (1989) "Evolutionary Genetics", Oxford: Oxford Univ. Press. Mayr, E. (1963) "Animal Species and Evolution", Cambridge, MA: Harvard Univ. Press. Mayr, E. (1982) "The Groth of Biological Thought", Cambridge, MA: The Belknap Press of Harvard Univ. Press. Ridley, M. (1985) "The Problems of Evolution", Oxford: Oxford Univ. Press. Watson, J.D. (1966) "Molecular Biology of the Gene", Menlo Park: Benjamin. Watson, J.D., Hopkins, N.H., Roberts, J.W., Steitz, J.A. & Weiner, A.M. (1987) "Molecular Biology of the Gene (4th edn)", Menlo Park: Benjamin. Williams, G.C. (1966) "Adaptation and Natural Selection", Princeton, NJ: Princeton Univ. Press. Wright, S. (1932) "The roles of mutation, inbreeding, crossbreeding and selection in evolution", in: Proc. of the 6th Int'l Congress on Genetics I, 356. There is a *lot* of interesting material on biology and evolution in the talk.origins newsgroup repository, available by FTP. The index of files, available from ics.uci.edu:/pub/origins/Index , lists what's there, and includes files on Darwinism, definition of evolution, introduction to evolutionary biology, a list of important FAQ files, speciation, and genetic drift. ------------------------------ Subject: Q10.8: On-line bibliography collections? The Big One Jarmo Alander has compiled probably the biggest EC bibliography around. It has 2500 entries, and is available in postscript form by ftp from: garbo.uwasa.fi:/pc/research/2500GArefs.ps.gz and also from ENCORE (see Q15.3) in file refs/2500GArefs.ps.gz Please send any additions or corrections to The same directory on ENCORE also contains some other bibliography collections. Combinations of GAs and NNs Dave Schaffer has compiled a bibliograpy on combinations of GAs and neural networks. About 150 entries, available in Bib format from ENCORE (See Q15.3) in file refs/cogann.bib.gz Jochen Ruhland has also compiled a bibliography on this topic. Some papers deal only with neural networks, some only with genetic algorithms. About 300 references altogether. Some include an abstract. Available from: ftp.neuro.informatik.uni-kassel.de:/pub/NeuralNets/ in We_and_our_work/papers/diplom.1.bib.gz There are plans to expand this bibliography from time to time; the sequels will have names diplom.2.bib.gz, etc. Bibliography at IlliGAL A bibliography on Genetic Algorithms compiled by David E. Goldberg, Kelsey Milman, and Christina Tidd is available as IlliGAL Report No 92008 (see Q14), via ftp from: gal4.ge.uiuc.edu:/pub/papers/IlliGALs/92008part1.ps.Z and 92008part2.ps.Z GAPHD Bibliography Collection Martyn Amos has assembled a collection of bibliographies from various sources, tidied up the entries and removed duplicates. The collections are as follows: Alife.bib.gz - General Artificial Life ICGA-93.bib.gz - Proc. International Conference on GAs (1993) chaos.bib.gz - Chaos theory ga+nn.bib.gz - GAs and neural networks ga.bib.gz - General GA references ga2.bib.gz - General GA references parallelGA.bib.gz - Parallel GAs theory.bib.gz - Theoretical computer science (bias towards graph theory, stochasic modelling and pobability theory) misc.bib.gz - Miscellaneous topics (eg. Internet) There are about 6200 references in total, although the biggest file by far is theory.bib, which is not directly related to EC. The references are in BibTeX format. The files are available by FTP from ftp.dcs.warwick.ac.uk:/pub/gaphd/Bibliographies/ or by WWW from http://www.dcs.warwick.ac.uk/~martyn/ga.html Genetic Programming Bibliography A collection of Genetic Programming references (and other tools) is maintained by Bill Langdon and is available via anonymous ftp from cs.ucl.ac.uk:/genetic/biblio/ Evolutionary Models in the Social Sciences Edmund Chattoe has set up a bibliorgraphy/mailing list on Evolutionary Models In Economics and the Social Sciences. You can subscribe to the list by sending a message with the string "subs-list" in the subject line to . The latest copy of the EMSS bibliography and some accompanying notes can be retrieved from this site automatically. GAs and Economics Bernard Manderick has compiled a bibliography on the use of GAs in economics, and this was published in GA-Digest, v7n4 (with some followup comments in v7n5 & v7n7). This can be retrieved by FTP from ftp.aic.nrl.navy.mil:/pub/galist/digests/v7n4 (see Q15.1). GAs in Control Carlos Fonseca has compiled a bibliography of about 50 references on GAs in Control, and it was published in GA-Digest, v7n18. This can be retrieved by FTP from ftp.aic.nrl.navy.mil:/pub/galist/digests/v7n18 (see Q15.1). Parallel GAs A parallel GA bibliography is available via ftp from: unix.hensa.ac.uk:/pub/parallel/faqs/parallel-genetic-algorithms Andreas Uhl has also compiled a parallel GA bibliography with about 80 entries. It is available by WWW in: http://www.mat.sbg.ac.at/~uhl/GA.html Genetic Programming John Koza has compiled an annotated bibliography on GP, and about 60 references were published in GA- Digest, v7n30. This can be retrieved by FTP from ftp.aic.nrl.navy.mil:/pub/galist/digests/v7n30 or from ENCORE (See Q15.3) in file refs/gp-ref.gz GAs and protein folding Melanie Mitchell has compiled a bibliography of about 40 references on this topic, and it was published in GA-Digest, v7n33. This can be retrieved by FTP from ftp.aic.nrl.navy.mil:/pub/galist/digests/v7n33 (see Q15.1). GAs in Image Processing and Computer Vision Kyeongmo Park has compiled a bibliography of about 20 references on this topic, and it was published in GA-Digest, v8n10. This can be retrieved by FTP from ftp.aic.nrl.navy.mil:/pub/galist/digests/v8n10 (see Q15.1). Masters and PhD theses Richard K. Belew has collected information on approximately 2600 Masters and Ph.D. theses, nominally in the area of AI. The entire list (about 170KB) is available for anonymous FTP at: cs.ucsd.edu:/pub/rik/aigen.rpt Questions, suggestions, additions etc. to . ------------------------------ Subject: Q10.9: Videos? Sims, K. (1990) "Panspermia", ACM Sigraph Review. Order form available by FTP from siggraph.org:/publications/video_review/order_blank Look in that directory for other useful information. Note that "Panspermia" is Item 23 of Issue 62 of the "SIGGRAPH Video Review". Langton, C.G. (ed) (1992) "Artificial Life II Video Proceedings" The Advanced Book Program of the Santa Fe Institute: Studies in the Sciences of Complexity, Addison Wesley, ISBN 0-201-55492-5. [ALIFEII- V]: Koza, J.R. & Rice, J.P. (1992) "Genetic Programming: The Movie", Cambridge, MA: MIT Press. See GP-faq for an order form. (see Q15) The Santa Fe Institute has produced a thirteen minute promotional video, which includes a five minute segment discussing the Tierra research project, illustrated with a very high quality animation produced by the Anti Gravity Workshop in Santa Monica, CA. To obtain the video, contact the Santa Fe Institute at: 1660 Old Pecos Trail, Suite A, Santa Fe, New Mexico 87501 (Tel: 505-984-8800, Fax: 505-982-0565, Net: ) or contact Linda Feferman: or <0005851689@mcimail.com> ------------------------------ Subject: Q10.10: CD-ROMs? PTF for AI by CMU Carnegie Mellon University is establishing an Artificial Intelligence Repository to contain public domain and freely distributable software, publications, and other materials of interest to AI researchers, educators, and students. The AI Repository will be accessible by anonymous FTP and Andrew File System (AFS) without charge (See Q15.3). The contents of the repository will also be published by Prime Time Freeware as an inexpensive mixed-media (Book/CD-ROM) publication. For your information, here is a precis of the CD-ROM: PTF for AI is a periodic collection of AI-related source code and documentation. PTF for AI in no way modifies the legal restrictions on any package it includes. The first issue (1-1; Summer, 1993) consisted of an ISO-9660 CD-ROM bound into a ~100 page book. It contained ~600 MB of gzipped archives (2+ GB uncompressed and unpacked). Cost: $60 US. For more information contact: Mark Kantrowitz, Archivist, CMU AI Repository, Editor, PTF for AI. Net: , Tel: +1 412-268-2582, Fax: +1 412-681-5739. AI CD-ROM by NCC Network Cybernetics Corporation has released a new CD-ROM title, the AI CD-ROM Revision 3 (ISBN 1-886376-01-8). This is the newest version of an annually updated collection of artificial intelligence programming and research tools. This ISO-9660 format CD-ROM contains thousands of programs, source code collections, tutorials, research papers, Internet journals, and other resources. Previous versions of the AI CD-ROM are currently in use as teaching aids for AI-related University courses, as research aids to computer scientists, and as a source of advanced computer programming tools for application program developers around the world. The AI CD-ROM contains thousands of up to date files covering a wide range of topics including: Fuzzy Logic, Genetic Algorithms, Neural Networks, Expert Systems, Robotics, Machine Vision, Natural Language, Prolog, Lisp, Embedded AI, Virtual Reality, Cellular Automata, Chaos, Fractals, and more. The disc is divided into topical subdirectories and each directory contains an index file with descriptive listings of the contents. The AI CD-ROM has received good reviews in many magazines including Byte (Jerry Pournelle, March '93) and IEEE Computer (J. Zalewski, July '93), CD-ROM Professional and others. The CD-ROM has a list price of $89.00. For people wanting to see a complete listing of the CD's contents, FTP to ftp.ncc.com:/ and get the file AICD3.ZIP. The file is also available from the Compuserve AIEXPERT forum, and the NCC dial-up BBS at 214-258-1832. Also check out the WWW site at: http://www.ncc.com:/ncc/ai Enquiries to: Network Cybernetics Corporation, 4201 Wingren Road, Suite 202, Irving, TX 75062-2763, USA ------------------------------ Subject: Q10.11: How do I get a copy of a dissertation? All US American dissertations are available from: UMI Dissertation Information Service, University Microfilms International, A Bell & Howell Information Company, 300 N. Zeeb Road, Ann Arbor, Michigan 48106, USA. Tel.: 800-521-0600, or +1 (313) 761-4700 ------------------------------ Subject: Q11: What EC related journals and magazines are there? [eds note: comments on speed of reviewing and publishing, whether they accept LaTeX/TeX format or ASCII by e-mail, etc. are welcome] 1. Dedicated EC Journals: Evolutionary Computation Published quarterly by: MIT Press Journals, 55 Hayward Street, Cambridge, MA 02142-1399, USA. Tel: (617) 253-2889, Fax: (617) 258-6779, Along with the explosive growth of the computing industry has come the need to design systems capable of functioning in complex, changing ENVIRONMENTs. Considerable effort is underway to explore alternative approaches to designing more robust computer systems capable of learning from and adapting to the environment in which they operate. One broad class of such techniques takes its inspiration from natural systems with particular emphasis on evolutionary models of computation such as GAs, ESs. CFS, and EP. Until now, information on these techniques has been widely spread over numerous disciplines, conferences, and journals. [eds note: The editorial board reads like a who-is-who in EC.] For paper e-mail submission, use one of the following addresses: o America: John Grefenstette o Europe: Heinz Muehlenbein o Asia: Hiroaki Kitano o Ed-in-chief: Ken De Jong Please note, that submissions should be sent to one of the sub- editors. Grefenstette and Kitano accept LaTeX or PostScript submissions. BioSystems Journal of Biological and Information Processing Sciences, Elsevier Science Publishers, P.O. Box 1527, 1000 BM Amsterdam, The Netherlands. BioSystems encourages experimental, computational, and theoretical articles that link biology, evolutionary thinking, and the information processing sciences. The link areas form a circle that encompasses the fundamental nature of biological information processing, computational modeling of complex biological systems, evolutionary models of computation, the application of biological principles to the design of novel computing systems, and the use of biomolecular materials to synthesize artificial systems that capture essential principles of natural biological information processing. Topics: Molecular EVOLUTION: Self-organizing and self-replicating systems, Origin and evolution of the genetic mechanism; Biological Information Processing: Molecular recognition, Cellular control, Neuromuscular computing, Biological adaptability, Molecular computing technologies; EVOLUTIONARY SYSTEMS: Stochastic evolutionary algorithms, Evolutionary OPTIMIZATION, SIMULATION of genetic and ecological systems, Applications (neural nets, machine learning, robotics)) 2. Related Journals: Complex Systems Published by: Complex Systems Publications, Inc., P.O. Box 6149, Champaign, IL 61821-8149, USA. Complex Systems devotes to the rapid publication of research on the science, mathematics, and engineering of systems with simple components but complex overall behavior. Try finger(1) on for additional info. Machine Learning Published by: Kluwer Academic Publishers, P.O. Box 358, Accord Station, Hingham, MA 02018-0358 USA. Machine Learning is an international forum for research on computational approaches to learning. The journal publishes articles reporting substantive research results on a wide range of learning methods applied to a variety of task domains. The ideal paper will make a theoretical contribution supported by a computer implementation. The journal has published many key papers in learning theory, reinforcement learning, and decision tree methods. The journal regularly publishes special issues devoted to GAs and CFS as well. Adaptive Behavior Published quarterly by: MIT Press Journals, details above. Broadly, behavior is adaptive if it deals successfully with changes circumstances. For example, when surprised, a hungry --but environmentally informed-- mouse may dart for cover rather than another piece of cheese. Similarly, a tripped-up ROBOT [eds note: not necessarily built by Sirius Cybernetics Corp.] could get back on its feet and accomplish a moonrock-finding mission if it had learned to cope with unanticipated lunar potholes. Adaptive Behavior thus takes an approach complementary to traditional AI. Now basic abilities that allow animals to survive, or ROBOTs to perform their mission in unpredictable ENVIRONMENTs, will be studied in preference to more elaborate and human-specific abilities. The journal also aims to investigate which new insights into intelligence and cognition can be achieved by explicitly taking into account the ENVIRONMENT feedback --mediated by behavior-- that an animal or a ROBOT receives, instead of studying components of intelligence in isolation. Topics: INDIVIDUAL and Collective Behavior. Neural Correlates of Behavior. Perception and Motor Control. Motivation and Emotion. Action SELECTION and Behavioral Sequences. Internal World Models. Ontogeny, Learning, and EVOLUTION. Characterization of ENVIRONMENTs. Artificial Life Published quarterly by: MIT Press Journals, details above. Artificial Life is intended to be the primary forum for the dissemination of scientific and engineering research in the field of ARTIFICIAL LIFE. It will report on synthetic biological work being carried out in any and all media, from the familiar "wetware" of organic chemistry, through the inorganic "hardware" of mobile ROBOTs, all the way to the virtual "software" residing inside computers. Research topics ranging from the fabrication of self-replicating molecules to the study of evolving POPULATIONs of computer programs will be included. There will also be occasional issues devoted to special topics, such as L-Systems, GENETIC ALGORITHMs, in-vitro EVOLUTION of molecules, artificial cells, computer viruses, and many social and philosophical issues arising from the attempt to synthesize life artificially. [eds note: The editorial board reads like a who-is-who in ALIFE] Evolutionary Economics Published quarterly by: Springer-Verlag New York, Inc., Service Center Secaucus, 44 Hartz Way, Secaucus, NJ 07094, USA. Tel: (201) 348-4033, Fax: (201) 348-4505. Evolutionary Economics aims to provide an international forum for a new approach to economics. Following the tradition of Joseph A. Schlumpeter, it is designed to focus on original research with an evolutionary conception of the economy. The journal will publish articles with strong emphasis on dynamics, changing structures (including technologies, institutions, beliefs, imitation, etc.). It favors interdisciplinary analysis and is devoted to theoretical, methodological and applied work. Research areas include: industrial dynamics; multi-sectoral and cross-country studies of productivity; innovations and new technologies; dynamic competition and structural change in a national and international context; causes and effects of technological, political and social changes; cyclic processes in economic EVOLUTION; the role of governments in a dynamic world; modeling complex dynamic economic systems; application of concepts, such as self-organization, bifurcation, and chaos theory to economics; evolutionary games. ------------------------------ Subject: Q12: What are the important conferences/proceedings on EC? 1. Dedicated EC Conferences: ICGA: International Conference on Genetic Algorithms Major international conference held in North America in odd-numbered years. Covers all aspects of EVOLUTIONARY COMPUTATION. The 1995 conference was held at the University of Pittsburgh on July 15--20. Details from http://www.aic.nrl.navy.mil:/galist/icga95 Proceedings of the 1st International Conference on Genetic Algorithms (1985) J.J. Grefenstette (ed) [ICGA85]: and Proc. of the 2nd Int'l Conf. on Genetic Algorithms (1987) J.J. Grefenstette (ed) [ICGA87]: available from Lawrence Erlbaum Associates, Inc., 365 Broadway, Hillsdale, New Jersey, 07642, (800) 926-6579. Proc. of the 3rd Int'l Conf. on Genetic Algorithms (1989) J.D. Schaffer (ed) [ICGA89]: and Proc. of the 4th Int'l Conf. on Genetic Algorithms (1991) R.K. Belew and L.B. Booker (eds) [ICGA91]: and Proc. of the 5th Int'l Conf. on Genetic Algorithms (1993) S. Forrest (ed) [ICGA93]: available from Morgan Kaufmann Publishers, Inc., San Francisco (415-392-2665). FOGA: Foundations of Genetic Algorithms Major international workshop focusing on theoretical aspects of EC, that's usually limited to some 50 participants and is held somewhere in North America. FOGA 3 took place from July 30 to August 3 in 1994. Enquires to: Darrell Whitley, Dept. of CS, Colorado State University, Fort Collins, CO 80523. Foundations of Genetic Algorithms (1991) G.J.E. Rawlins (ed) [FOGA91]: and Foundations of Genetic Algorithms 2 (1993) L.D. Whitley [FOGA93]: available from Morgan Kaufmann Publishers, Inc., San Francisco (415-392-2665). PPSN: Parallel Problem Solving from Nature Major international conference held in Europe in even-numbered years. Covers all aspects of problem solving inspired by natural processes. The 1996 conference will be held in Berlin, September 22-27. Further information from: http://LS11-www.informatik.uni-dortmund.de/PPSN/ Parallel Problem Solving from Nature, (1990) H.-P. Schwefel and R. Maenner (eds) [PPSN90]: published by Springer-Verlag, 175 5th Avenue, New York, NY, 10010, (212) 460-1500. Parallel Problem Solving from Nature 2, (1992) R. Maenner and B. Manderick (eds) [PPSN92]: published by North-Holland, Elsevier Science Publishers, Sara Burgerhartstraat 25, P.O. Box 211, 1000 AE Amsterdam, The Netherlands. Parallel Problem Solving from Nature 3, (1994) Y. Davidor (ed.), [PPSN94]: EP: Annual Conference on Evolutionary Programming Major international annual conference held in San Diego, CA, USA. Covers all aspects of EC with emphasis on EP related research. The 1995 conference was held on March 1-4. For details contact David Fogel . Proceedings of the 1st Annual Conference on Evolutionary Programming, (1992) D.B. Fogel and W. Atmar (eds), [EP92]:, and Proc. of the 2nd Annual Conf. on Evolutionary Programming, (1993) D.B. Fogel and W. Atmar (eds), [EP93]: published by the Evolutionary Programming Society, 9363 Towne Centre Dr., San Diego, CA 92121, Attn: Bill Porto, Treasurer (cf Q13). Proceedings of the Third Annual Conference on Evolutionary Programming, (1994) A.V. Sebald and L.J. Fogel (eds), [EP94]:, World Scientific Publishers, River Edge, NJ. ICEC: IEEE Conference on Evolutionary Computation Major international conference covering all aspects of EC. The first took place in June 1994 at the World Congress on Computational Intelligence, Florida. The second was on 29 Nov--1 Dec 1995 in Perth, Australia. Details from . Proceedings of the 1st IEEE Conference on Evolutionary Computation, (1994) D.B. Fogel (ed.) (2 Volumes). Published by IEEE, 445 Hoes Lane, PO Box 1331, Piscataway, NJ 08855-1331. Also, talks from invited speakers are published in "Computational Intelligence Imitating Life" (1994) J.M. Zurada, R.J. Marks, C.J. Robinson (eds), IEEE. 2. Related Conferences: Alife: International Conference on Artificial Life Proceedings of the 1st International Conference on ARTIFICIAL LIFE, (1989) C.G. Langton (ed), Santa Fe Institute Studies in the Sciences of Complexity, Proc. Vol. VI, [ALIFEI]: and Proc. of the 2nd Int'l Conf. on Artificial Life II, (1992) C.G. Langton, C. Taylor, J. Doyne Farmer and S. Rasmussen (eds), Santa Fe Institute Studies in the Sciences of Complexity, Proc. Vol. X, [ALIFEII]: and Proc. of the 3rd Int'l Conf. on Artificial Life III, (1993) C.G. Langton (ed), [ALIFEIII]: published by Addison Wesley, Redwood City, CA, USA. ARTIFICIAL LIFE IV, was organized by Rodney Brooks, MIT AI Lab, and held on July 6-8, 1994. Proceedings edited by R. Brooks and P. Maes. [ALIFEIV]: ECAL: European Conference on Artificial Life Proceedings of the 1st European Conference on ARTIFICIAL LIFE, (1991) F.J. Varela and P. Bourgine (eds), [ECAL91]: and Proc. of the 2nd European Conf. on ALIFE: Self-organization and life, from simple rules to global complexity, (1993), (? eds) (? pub) [ECAL93]: published by MIT Press, Cambridge, MA, USA. ECML: European Conference on Machine Learning Machine Learning: ECML-93, Proc. European Conf. on Machine Learning, (1993) P.B. Brazil (ed), [ECML93]: published by Springer, New York, NY, USA. SAB: International Conference on Simulation of Adaptive Behavior From Animals to Animats. Proceedings of the 1st International Conference on SIMULATION of Adaptive Behavior, (1991) [SAB90]: J.-A. Meyer and S.W. Wilson, ISBN 0-262-63138-5, and Proc. of the 2nd Int'l Conf. on Simulation of Adaptive Behavior, (1993) [SAB92]:, J.-A. Meyer, H. Roitblat and S.W. Wilson (eds) and Proc. of the 3rd Int'l Conf. on Simulation of Adaptive Behavior, [SAB94]:, P. Husbands, J.-A. Meyer and S.W. Wilson (eds) published by MIT Press, Cambridge, MA, USA. SAB94 took place on August 8-12, 1994 in Brighton, UK. 3. Pointers to upcoming Conferences: The Genetic Algorithm Digest Aka "GA-Digest" always starts with a "Calendar of GA-related Events," i.e. a list of upcoming conferences, covering the complete field of EAs. (cf Q15) The Artificial Life Digest Aka "Alife digest" always starts with a "Calendar of Alife-related Events," that lists conferences, workshops, etc. (cf Q15) The Evolutionary Programming Digest Aka "EP-digest" doesn't list conferences explicitly, like the previously mentioned ones, but carries most CFP's; that can be looked at in the backissues folder: amazon.eng.fau.edu:/pub/ep-list/digest/ (cf Q15) ------------------------------ Subject: Q13: What Evolutionary Computation Associations exist? ISGA: International Society on Genetic Algorithms The ISGA is a mostly fascinating society: it neither has a membership fee (which makes it even more fascinating), nor an address. However, ISGA meetings usually take place during ICGA conferences, in so-called business meetings (BMs). [eds note: So during a conference, ask for BMs, if you want to join; or be ready to dart out of the room if you don't...] EPS: Evolutionary Programming Society Membership is $40/year ($10/year for students with id) and also gives you a discounted registration at the annual conference. You can also order EP proceedings ($30/members, $45/other) from EPS. Address: EVOLUTIONARY PROGRAMMING Society, 9363 Towne Centre Dr., San Diego, CA 92121, Attn: Bill Porto, Treasurer. ------------------------------ Subject: Q14: What Technical Reports are available? Technical reports are informally published, unrefereed papers giving up-to-date information on what is going on at research institutes. Many later go on to be formally published in journals or at conferences. TCGA Reports The Clearing House for Genetic Algorithms (TCGA) at the Univ. of Alabama (Tuscaloosa) distributes TCGA technical reports. A number of these are now available in compressed Postscript form via FTP from: aramis.cs.ua.edu:/pub/tech-reports/ Read the file README first. Contact: Robert Elliott Smith, Department of Engineering of Mechanics, Room 210 Hardaway Hall, The University of Alabama, P.O. Box 870278, Tuscaloosa, AL 35487, USA. Tel: (205) 348-1618, , or Dr. Ron Sun IlliGAL Reports The Illinois Genetic Algorithms Laboratory distributes IlliGAL technical reports, as well as reprints of other publications; they are available in hardcopy and can be ordered from: IlliGAL Librarian, Department of General Engineering, 117 Transportation Building, 104 South Mathews Avenue, Urbana, IL 61801-2996, USA. NOTE: When ordering, please include your surface mail address! IlliGAL also have an anonymous-FTP server, holding most of the existing IlliGAL reports, at: gal4.ge.uiuc.edu:/pub/papers/IlliGALs/ There is also a WWW home page with a complete list, order form, and other information at: ftp://gal4.ge.uiuc.edu:/illigal.home.html SyS Reports The Systems Analysis Research Group (SyS) at the University of Dortmund, maintains an experimental anonymous FTP server: lumpi.informatik.uni-dortmund.de:/pub/ On lumpi you can find SyS- Reports from 1992 on. (Get "/pub/ls-Ral.Z" and look for "papers" folders, the server is sorted by EA paradigms, i.e. "/pub/GA/papers" contains papers related to GAs, etc.). A strongly recommended, and quarterly updated, report is a list of current applications of GAs, EP and ESs; get "/pub/EA/papers/ea-app.ps.gz" (SyS-2/92). Bionics Reports The Bionics and EVOLUTION Techniques Laboratory at the Technical University of Berlin maintains an anonymous FTP server: ftp- bionik.fb10.tu-berlin.de:/pub/ On ftp-bionik you find reports and software, related to Evolutionary Algorithms and Artificial Neural Networks. University College London Reports A number of GENETIC ALGORITHM reports produced by UCL are available via anonymous FTP at cs.ucl.ac.uk:/genetic/papers/ Abstracts of others can be obtained via WWW at http://www.cs.ucl.ac.uk/rns/ Other Sources of Reports Reports are also available from some of the sources listed in Q15.1, Q15.2 and Q15.3. ------------------------------ Subject: Q15: What information is available over the net? A whole lot of information is available "electronically" via the internet, accessible using e-mail or (more easily) FTP. There are electronic digests (see Q15.1), electronic mailing lists (see Q15.2), online FTP repositories (see Q15.3), and various USENET news groups (see Q15.4). ------------------------------ Subject: Q15.1: What digests are there? Digests are regulated, moderated, information sources in which many contributions are combined together before being posted out to subscribers, usually on a regular basis (eg. weekly). Mailing lists are listed in Q15.2. Genetic Algorithm Digest The GA research community exchanges news, CFP's, etc. through this (approximately weekly) digest, currently moderated by Bill Spears (formerly by Connie Ramsey and by Alan C. Schultz, Naval Research Laboratory, Washington, DC). A statistic published in v7,i3 stated that GA-digest is sent out world-wide to 1800 addresses in 28 countries. The digest is also posted to the comp.ai.genetic newsgroup. o Send administrative requests to o The anonymous FTP archive: ftp.aic.nrl.navy.mil:/pub/galist/ contains back issues, GA-code, conference announcements (in "/pub/galist/information/conferences") and many other things. Info in "/pub/galist/FTP". o The archive may also be accessed via the World Wide Web at http://www.aic.nrl.navy.mil/galist Also, links are given to many interesting sites around the World with material related to EVOLUTIONARY COMPUTATION. Artificial Life Digest The ALIFE research community exchanges news, CFP's, etc. through this digest, edited by Liane Gabora and Rob Collins of the ARTIFICIAL LIFE Research Group at UCLA. o Send administrative requests to o Anonymous FTP archive: ftp.cognet.ucla.edu:/pub/alife/ Evolutionary Programming Digest The digest is intended to promote discussions on a wide range of technical issues in evolutionary OPTIMIZATION, as well as provide information on upcoming conferences, events, journals, special issues, and other items of interest to the EP community. Discussions on all areas of EVOLUTIONARY COMPUTATION are welcomed, including ARTIFICIAL LIFE, EVOLUTION STRATEGIEs, and GENETIC ALGORITHMs. The digest is meant to encourage interdisciplinary communications. Your suggestions and comments regarding the digest are always welcome. To subscribe to the digest, send mail to and include the line "subscribe ep-list" in the body of the text. Further instructions will follow your subscription. The digest is moderated by N. Saravan of Florida Atlantic University. ------------------------------ Subject: Q15.2: What mailing lists are there? Mailing lists are unregulated, unmoderated, information sources in which messages sent in by subscribers are posted out immediately and individually to all other subscribers. Digests are listed in Q15.1. Genetic Programming Mailing List The GP community uses this list as a discussion forum, news exchange and FAQ distribution channel, originally set up by John Koza and James Rice at Stanford. o Admin requests: o The anonymous FTP archive: ftp.io.com:/pub/genetic-programming/ includes a lengthy, but "mostly interesting" FAQ by James Rice on GP related subjects. A HTML version is accessible at: http://www.salford.ac.uk:/docs/depts/eee/genetic.html (there are also a lot of other GP resources here too). Tierra Mailing List Thomas Ray's Tierra is discussed elsewhere (see Q4.1); here's how to obtain Tierra electronically and get in contact with other users. o Admin requests: o Anonymous FTP archive: tierra.slhs.udel.edu:/pub/ (tierra, almond, beagle, etc.) GA-Molecule mailing list o Admin details: UK's Evolutionary-Computation mailing list o Admin details: GEnetic Algorithm Research Student mailing list Provides a forum for research students interested in GENETIC ALGORITHMs. o Admin requests: GANN: Genetic Algorithms and Neural Networks This list will focus on the use of evolutionary algorithms (GENETIC ALGORITHMs, GENETIC PROGRAMMING and their variants) in the EXPLORATION of the design space of (artificial) neural network architectures and algorithms. The list will be semi-moderated to keep the signal to noise ratio as high as possible. (This list was formerly known as the neuro-evolution e-mail list.) o Admin requests/enquiries: gann-request@cs.iastate.edu o Subscription requests to the admin address with Subject: subscribe gattbl: Timetabling mailing list This group is for people using GAs and other techniques for exam or course scheduling for academic institutions. To subscribe, send email to . Evolutionary Models in the Social Sciences See Q10.8 for details. Genetic Algorithms in Production Scheduling The GASched list is for discussion of the use of GENETIC ALGORITHMs on Production Scheduling Problems (only). Possible subjects for the list include: GAs for job-shop scheduling theory, GAs for practical problem solving in industry, problem representation within the GA, combinatorial optimisation techniques for scheduling problems, results & effects of GA-based systems working in industry, techniques for improving PERFORMANCE, problem data, or any other burning issues which come into GAs for production scheduling. To send an administration message (to subscribe, be removed, or if you have a question about the list rather than *for* it), email with your name and email address, and you should hear back within a few days. Autopoiesis There is an Autopoiesis Email List for the discussion of the theory of Autopoiesis of H. Maturana and F. Varela. Autopoiesis means self- production and concerns self-organizing systems. To join send a message containing the text: SUB AUTOPOIESIS to To see what other systems and philosophy lists exist at this site send the message: HELP instead. ------------------------------ Subject: Q15.3: What online information repositories are there? Many research institutes have online repositories of information which my be retrieved using FTP or (increasingly), World Wide Web (WWW). NOTE: See also Q14 above. ENCORE ENCORE (The EvolutioNary COmputation REpository network) is a collection of anonymous FTP servers/World Wide Web sites providing a wealth of information in the area of EC, from technical reports, copies of journal articles, down to source code for various EAs. ENCORE acts as a distributor of much material generated at research institutes (and other places) which don't necessarily have their own FTP servers. Each node of ENCORE is referred to as an "EClair". There are numerous nodes around the world, all carrying copies of the same information. The sites may be accessed using FTP or WWW browsers. If using FTP, omit the initial "ftp://" and the final "Welcome.html" in the file specification in order to access the top-level directory. The sites include: EUnet Deutschland GmbH (Germany): o ftp://ftp.Germany.EU.net:/pub/research/softcomp/EC/Welcome.html Technical University of Berlin (Germany): o ftp://ftp-bionik.fb10.tu-berlin.de:/pub/EC/Welcome.html Ecole Polytechnique, Palaiseau (France): o ftp://blanche.polytechnique.fr:/pub/eark/EC/Welcome.html The University of Warwick (United Kingdom): o ftp://ftp.dcs.warwick.ac.uk:/pub/mirrors/EC/Welcome.html The University of Oviedo (Spain): o ftp://zeus.etsimo.uniovi.es:/pub/EC/Welcome.html The Santa Fe Institute (USA): o ftp://alife.santafe.edu:/pub/USER-AREA/EC/Welcome.html The California Institute of Technology (USA): o ftp://ftp.krl.caltech.edu:/pub/EC/Welcome.html Wayne State University, Detroit (USA): o ftp://ftp.cs.wayne.edu:/pub/EC/Welcome.html The Michigan State University, East Lansing (USA): o ftp://ftp.egr.msu.edu:/pub/EC/Welcome.html Purdue University, West Lafayette, IN (USA): o ftp://coast.cs.purdue.edu:/pub/EC/Welcome.html The Chinese University of Hong Kong: o ftp://ftp.cs.cuhk.hk:/pub/EC/Welcome.html University of Cape Town (South Africa): o ftp://ftp.uct.ac.za:/pub/mirrors/EC/Welcome.html CEFET-PR, Curitiba (Brazil): o ftp://ftp.cefetpr.br/pub/EC/Welcome.html Well worth getting is "The Navigator's Guide to ENCORE", a handbook to this service, in file: o handbook/encore.ps.gz (A4 paper) or o handbook/encore-US.ps.gz (US letter size paper). ENCORE is administered by Joerg Heitkoetter . The Santa Fe Institute The Santa Fe Institute Studies in the Sciences of Complexity (SFI) issues a recommended series: SFI Studies in the Science of Complexity, published by Addison Wesley and maintains a well-sorted FTP server with EC related material. o Admin requests: o Anonymous FTP archive: ftp.santafe.edu:/pub/ Information on SUMMERSCHOOLs held by the SFI can be obtained from: Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, NM 87501, USA. The Australian National University (ANU) The Bioinformatics facility at Australian National University has set up an anonymous FTP server, that contains EC related material, maintained by David G. Green. o Admin requests: o Anonymous FTP archive: life.anu.edu.au:/pub/complex_systems/alife/ o Gopher protocol: Besides direct access to all FTP information, the gopher server offers online access to relevant newsgroups, online databases and direct links to relevant international services. Name=Complex systems, Host=life.anu.edu.au, Type=1, Port=70, Path=1/complex_systems. o World Wide Web protocol: Besides access to all of the above, the hypermedia server offers introductory tutorials, preprints and papers online. The URL for this service is http://life.anu.edu.au/complex_systems/complex.html or link via the servers home page http://life.anu.edu.au/ LGI laboratory, Grenoble, France Research into Parallel GENETIC ALGORITHMs: papers (technical reports, conference and journal articles, theses, monographies, etc...) written by members of the SYMPA team are available by FTP from o imag.fr:/pub/SYMPA/ Their adress is: SYMPA/LGI - Institut IMAG, BP 53 38041 Grenoble Cedex, FRANCE The University of Alabama, Department of Computer Science A number of papers and preprints are available in compressed Postscript form by FTP from the Univ. of Alabama (Tuscaloosa) from aramis.cs.ua.edu:/pub/tech-reports/ The naming convention for files is: (author's last name).(journal name).ps . Maintained by Dr. Ron Sun CMU Artificial Intelligence Repository Holds more than a gigabyte of software, publications, and other materials of interest to AI researchers, educators, students, and practitioners. The AI Programming Languages and the AI Software Packages sections of the repository can be accessed in the lang/ and areas/ subdirectories. Other directories, which are in varying states of completion, are events/ and pubs/ (Publications, including technical reports, books, mail/news archives). The AI Programming Languages section includes directories for Common Lisp, Prolog, Scheme, Smalltalk, and other AI-related programming languages. The AI Software Packages section includes subdirectories for: alife/ (ARTIFICIAL LIFE), anneal/ (Simulated Annealing), genetic/ (GENETIC ALGORITHMs etc., including benchmarks and test problems) and many more. The AI Repository is accessible by FTP at: ftp.cs.cmu.edu:/user/ai/ (Be sure to read the files 0.doc and readme.txt in this directory) and by WWW at the URL: http://www.cs.cmu.edu:8001/Web/Groups/AI/html/repository.html It is also available on CD-ROM (See Q10.10). The MSU Genetic Algorithms Research and Applications Group (GARAGe) GARAGe has a number of interesting projects, both in terms of GA and GP fundamental research and in GA/GP applications including: parallelization of GAs/GPs; multiple POPULATION topologies and interchange methodologies; scheduling applications, including sponsored research on job-floor scheduling; design applications, including sponsored research on composite material design; configuration applications, particularly physics applications of optimal molecule configurations for particular systems like C60 (buckyballs) and others. Information on GARAGe research projects is available by WWW at the URL: http://isl.cps.msu.edu/GA School of Cognitive and Computing Sciences, University of Sussex The Evolutionary and Adaptive Systems Group in COGS does a significant amount of research in the area of GAs and Neural Networks and modeling the process of biological development. For purposes of artificial EVOLUTION, many at COGS see this as the major issue to be tackled. For general info about the group, consult the WWW server at: http://www.cogs.susx.ac.uk:/lab/adapt/index.html The Navy Center for Applied Research in Artificial Intelligence The Navy Center for Applied Research in ARTIFICIAL INTELLIGENCE (NCARAI) is conducting basic research in the analysis of GAs and other evolutionary algorithms. GAs are being applied to the learning of strategies and behaviors for autonomous vehicles, and for adaptively testing complex systems such as vehicle controllers. You will find description of projects, researchers, and downloadable papers at URL http://www.aic.nrl.navy.mil/ in addition to other information. The GA-digest and the GENETIC ALGORITHMs Archive are maintained at NCARAI. See Q15.1, "Genetic Algorithms Digest", for more information. Case Western Reserve University A WWW home page is available for the CWRU Autonomous Agents Research Group at: ftp://alpha.ces.cwru.edu/pub/agents/home.html The group, led by Randall Beer, conducts interdisciplinary research in the departments of Computer Engineering and Science, Biology, Mechanical Engineering, and Systems Engineering. This research includes work in evolutionary algorithms, mobile robotics, and computational biology. The aim is to study the mechanisms that can produce adaptive behavior in animals and ROBOTs. Currently available are Postscript versions of a number of our research papers (in particular, those related to mobile robotics, evolving recurrent neural networks, and computational models of development), an HTML version of a paper on computational development which appeared in ALIFE IV, and images of the ROBOTs used in our research. Comments to Genetic Algorithms Group, George Mason University Members of the research group are working on a variety of projects including GA theory, coevolutionary algorithms, decentralized GAs, representation issues, evolutionary microeconomics, the application of GAs to molecular biology, and GA-based machine learning. There is an online publications list that contains links to PostScript copies of many of their published papers. A WWW home page is available at: http://www.cs.gmu.edu/research/gag/ ------------------------------ Subject: Q15.4: What relevant newsgroups and FAQs are there? Besides the obvious comp.ai.genetic, there exist some other newsgroups that sometimes carry EC related topics: o comp.ai (FAQ in news.answers, comp.answers) o comp.ai.digest o comp.ai.fuzzy (FAQ in news.answers, comp.answers) o comp.ai.jair.announce (FAQ in news.answers, comp.answers) o comp.ai.jair.papers (PostScript papers of the Journal of AI Research, published by Morgan Kaufmann ) [eds note: this is the first journal that's completely published on USENET first, and later in paper form; read the jair-faq, that's posted to the announcement group to find out how to submit your papers, get JAIR papers by FTP, Gopher or e-mail, etc.] o comp.ai.neural-nets (FAQ in news.answers, comp.answers) o comp.robotics (FAQ in news.answers, comp.answers) o comp.theory.cell-automata (no FAQ) o comp.theory.dynamic-sys (no FAQ) o comp.theory.self-org-sys (no FAQ) o sci.bio.evolution (no FAQ as such, but there is an archive of interesting material, accessible via WWW at http://www.cqs.washington.edu/~evolution ) o sci.math.num-analysis (some FAQs in news.answers, sci.answers) o sci.op-research (some FAQs in news.answers, sci.answers) o talk.origins (discusses origins of life, EVOLUTION, etc. FTP repository index at ics.uci.edu:/pub/origins/Index -- see Q10.7 for more details.) ------------------------------ Subject: Q15.5: What about all these Internet Services? The Internet supports a variety of on-line services, and a number of tools are available to enable people to make good use of these, including: telnet, FTP, gopher, veronica, archie, Wide Area Information Servers (WAIS), and the World-Wide Web (WWW). Information about using Internet is available from a number of sources, many accesible on-line, via email or FTP. For example, the EFF (Electronic Frontier Foundation) publishes two guides for novices on all the Internet has to offer, by Adam Gaffin and Joerg Heitkoetter (see below). These are avaiable over the net. To receive a short guide to using anonymous FTP, send e-mail with the text "help" to . If you dont have FTP access, you can retrieve documents using the FTP-by-email service. The "ftpmail" service is installed on several sites to allow transmission of FTPable files from almost anywhere. To get the PostScript version of this FAQ from ENCORE, (See Q15.3) for example, send a message to (for example) containing the lines: reply connect alife.santafe.edu get pub/USER-AREA/EC/FAQ/hhgtec.ps.gz quit where is e.g. foo@bar.edu FTPmail sites available are listed below. Use one that is near you for best performance. (USA) (Europe) or to Documents from the archive at can be retrieved similarly by sending email to , containing a message such as: send usenet/news.answers/index send usenet/news.answers/ai-faq/genetic/part1 quit References Kehoe, B.P. (1992) "Zen and the Art of the Internet: A Beginner's Guide to the Internet", 2nd Edition (July). Prentice Hall, Englewood Cliffs, NJ. 112 pages. The 1st Edition, (February) is available in PostScript format via anonymous FTP from ftp.cs.widener.edu: and many other Internet archives. Krol, E. (1992) "The Whole Internet: Catalog & User's Guide". O'Reilly & Associates, Inc., Sebastopol, CA. 376 pages. LaQuey, T. and J.C. Ryer (1992) "The Internet Companion: A Beginner's Guide to Global Networking". Addison-Wesley Publishing Co., Reading, MA. 208 pages. Smith, Una R. (1993) "A Biologist's Guide to Internet Resources." USENET sci.answers. ~45 pages. Available via gopher, anonymous FTP and e-mail from many archives, eg. rtfm.mit.edu:/pub/usenet/sci.answers/biology/guide/part? Gaffin, A. (1994) "Everybody's Guide to the Internet." Published by the EFF and MIT Press. $14.95. ISBN 9-780262-67105-7. This book is available in ASCII by sending e-mail to ; you'll receive the book split into several pieces; for a more elaborate version of the guide see the following entry. Gaffin, A. with Heitkoetter, J. (1994) "EFF's (Extended) Guide to the Internet: A round trip through Global Networks, Life in Cyberspace, and Everything...", aka `eegtti.texi'. This is available from ftp.eff.org:/pub/Net_info/Net_Guide/Other_versions/ (Texinfo, ASCII, HTML, DVI and PostScript). The European edition is kept on ftp.germany.eu.net:/pub/books/eff-guide/ ~300 pages. A README file gives more information. The hypertext (HTML) version can be browsed by using a WWW reader, such as mosaic, and opening a URL with the address: http://www.germany.eu.net:/books/eegtti/eegtti.html The EARN Association (May 1993) "A Guide to Network Resource Tools", available via e-mail from , by sending the message "get nettools ps" (PostScript) or "get nettools memo" (plain text). ------------------------------ Copyright (c) 1993-1995 by J. Heitkoetter and D. Beasley, all rights reserved. This FAQ may be posted to any USENET newsgroup, on-line service, or BBS as long as it is posted in its entirety and includes this copyright statement. This FAQ may not be distributed for financial gain. This FAQ may not be included in commercial collections or compilations without express permission from the author. End of ai-faq/genetic/part4 *************************** -- Newsgroups: comp.ai.genetic,comp.answers,news.answers Path: senator-bedfellow.mit.edu!bloom-beacon.mit.edu!gatech2!news.jsums.edu!news.uoregon.edu!news.kreonet.re.kr!usenet.kornet.nm.kr!agate!howland.reston.ans.net!EU.net!peer-news.britain.eu.net!yama.mcc.ac.uk!thor.cf.ac.uk!news From: David.Beasley@cs.cf.ac.uk (David Beasley) Subject: FAQ: comp.ai.genetic part 5/6 (A Guide to Frequently Asked Questions) Summary: This is part 5 of a entitled "The Hitch-Hiker's Guide to Evolutionary Computation". A periodically 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: David.Beasley@cs.cf.ac.uk (David Beasley) Sender: news@cf.ac.uk (USENET News System) Message-ID: Supersedes: Approved: news-answers-request@MIT.Edu Date: Tue, 12 Dec 1995 16:13:36 GMT Expires: Fri, 15 Mar 1996 16:13:00 GMT X-Nntp-Posting-Host: thrall References: Organization: Cardiff University of Wales Followup-To: comp.ai.genetic Lines: 1643 Xref: senator-bedfellow.mit.edu comp.ai.genetic:7453 comp.answers:15898 news.answers:59988 Archive-name: ai-faq/genetic/part5 Last-Modified: 12/20/95 Issue: 3.4 TABLE OF CONTENTS OF PART 5 Q20: What EA software packages are available? Q20.1: Free software packages? Q20.2: Commercial software packages? Q20.3: Current research projects? ---------------------------------------------------------------------- Subject: Q20: What EA software packages are available? This gives a list of all known EA software packages available to the public. The list was originally maintained by Nici Schraudolph. In June '93 it was agreed that it would be incorporated into this FAQ and the responsibility for maintenance taken over by the FAQ editor. A copy of most of the packages described below are kept at ENCORE, (See Q15.3), available by anonymous FTP. Most GENETIC PROGRAMMING software is available by FTP in: ftp.io.com:/pub/genetic-programming/ There are subdirectories containing papers related to GP, archives of the mailing list, as well as a suite of programs for implementing GP. These programs include the Lisp code from Koza's "Genetic Programming" [KOZA92], as well as implementations in C and C++, as for example SGPC: Simple Genetic Programming in C by Walter Alden Tackett and Aviram Carmi . A survey paper entitled "Genetic Algorithm Programming Environments" was published in IEEE Computer in the February 1994 issue. Written by Filho, Alippi and Treleaven of University College, London, UK. It's available by FTP as bells.cs.ucl.ac.uk:/papagena/game/docs/gasurvey.ps PLEASE NOTE For many of these software packages, specific ordering instructions are given in the descriptions below (see Q20.1 - Free Software packages, Q20.2 - Commercial Software Packages, Q20.3 - Research Projects). Please read and follow them before unnecessarily bothering the listed author or contact! Also note that these programs haven't been independently tested, so there are no guarantees of their quality. A major revision was undertaken in August 1994, when all authors were contacted, and asked to confirm the accuracy of the information contained here. A few authors did not respond to the request for information. These are noted below by: (Unverified 8/94). In these cases, FTP address were checked by the FAQ editor, to confirm that this information (at least) is correct. In two cases, email to the author bounced back as "undeliverable" -- these are noted below. Legend Type (this is a very ad-hoc classification) GE: generational GA SS: steady-state GA PA: (pseudo) parallel GA ES: evolution strategy OO: object-oriented XP: expert system ED: educational/demo CF: classifier system OS Operating System; X11 implies Unix; "Win" means Microsoft Windows 3.x/NT (PC); "DOS" means MS-DOS or compatibles. Lang Programming Language; in parentheses: source code not included; "OPas" = MPW Object Pascal Price (1) free to government contractors, $221 otherwise, (2) educational discount available, (3) available as addendum to a book, (4) single 1850 DM, site license 5200 DM, (5) single 200 DM, site license 500 DM, (6) free for academic and educational use. Author or Contact given as Internet e-mail address if possible ES/GA/XP System Implementations: ========================================================================= Name Type OS Lang Price Author/Contact ========================================================================= BUGS GE, X11, C free Joshua Smith ED Suntools DGenesis GE, Unix C free Erick Cantu-Paz PA,ED DOUGAL SS, DOS Turbo free Brett Parker GE Pascal ESCaPaDE ES Unix C free Frank Hoffmeister Evolution GE, DOS C free Hans-Michael Voigt and Machine ES Joachim Born GAC, GE Unix C free Bill Spears GAL " " Lisp " GAGA GE Unix C free Jon Crowcroft GAGS GE, Unix, C++ free JJ Merelo SS,OO DOS GAlib GA Unix, C++ free Matthew Wall Mac,DOS GALOPPS GE, Unix, C free Erik Goodman PA DOS GAMusic ED Win (Visual $10 Jason H. Moore Basic) GANNET GE, Unix C free Darrell Duane NN GAucsd GE Unix C free Nici Schraudolph GA GE, DOS (C++) free Mark Hughes Workbench ED GECO GE, Unix, Lisp free George P. W. Williams, Jr. OO,ED MacOS Genesis GE, Unix, C free John Grefenstette ED DOS GENEsYs GE Unix C free Thomas Baeck GenET SS, Unix, C free Cezary Z. Janikow ES,ED X, etc. Genie GE Mac Think free Lance Chambers Pascal Genitor SS Unix C free Darrell Whitley GENlib SS Unix, C (6) Jochen Ruhland DOS GENOCOP GE Unix C free Zbigniew Michalewicz GIGA SS Unix C free Joe Culberson GPEIST GP Win, Small- free Tony White OS/2 talk Imogene GP Win C++ free Harley Davis LibGA GE, Unix/DOS C free Art Corcoran SS,ED NeXT/Amiga LICE ES Unix, C free Joachim Sprave DOS Matlab-GA GE ? Matlab free ? mGA GE Unix C, free Dave Goldberg Lisp PARAGenesis PA, CM C* free Michael van Lent GE PGA PA, Unix, C free Peter Ross SS,GE etc. PGAPack GA, any C free David Levine PA SGA-C, GE Unix C free Robert E. Smith SGA-Cube nCube Splicer GE Mac, C (1) Steve Bayer X11 TOLKIEN OO, Unix, C++ free Anthony Yiu-Cheung Tang GE DOS Trans-Dimensional Steve Romaniuk Learning NN Win ? free WOLF SS Unix C free David Rogers ========================================================================= Classifier System Implementations: ========================================================================= Name Type OS Lang Price Author/Contact ========================================================================= CFS-C CF, Unix/DOS C free Rick Riolo ED SCS-C CF, Unix/DOS C free Joerg Heitkoetter ED Atari TOS ========================================================================== Commercial Packages: ========================================================================= Name Type OS Lang Price Author/Contact ========================================================================= Computer- ED, Win ? $10 Scott Kennedy, Axcelis Inc. Ants GA <72723.3614@compuserve.com> EnGENEer OO, X11 C ? George Robbins, GA Logica Cambridge Ltd. EvoFrame/ OO, Mac, C++/ (4,2) Optimum Software REALizer ES DOS OPas (5,2) Evolver GE DOS, (C, $349 Scott Kennedy, Axcelis Inc. Mac Pascal) <72723.3614@compuserve.com> FlexTool GA ? Matlab ? Flexible Intelligence Group GAME OO, X11 C++ (3) Jose R. Filho GA Generator GE,SS Win, (C++) $379 Steve McGrew, New Light Industries ES,OO,ED Excel MicroGA/ OO, Mac, C++ $249 Emergent Behavior, Inc. Galapagos SS Win (2) Omega ? DOS ? ? David Barrow, KiQ Ltd. OOGA OO, Mac, Lisp $60 Lawrence Davis GE DOS PC/Beagle XP DOS ? 69UKP Richard Forsyth XpertRule/XP DOS (Think 995UKP Attar Software GenAsys Pascal) XYpe SS Mac (C) $725 Ed Swartz, Virtual Image Inc. ========================================================================= ------------------------------ Subject: Q20.1: Free software packages? BUGS: BUGS (Better to Use Genetic Systems) is an interactive program for demonstrating the GENETIC ALGORITHM and is written in the spirit of Richard Dawkins' celebrated Blind Watchmaker software. The user can play god (or `GA FITNESS function,' more accurately) and try to evolve lifelike organisms (curves). Playing with BUGS is an easy way to get an understanding of how and why the GA works. In addition to demonstrating the basic GENETIC OPERATORs (SELECTION, CROSSOVER, and MUTATION), it allows users to easily see and understand phenomena such as GENETIC DRIFT and premature convergence. BUGS is written in C and runs under Suntools and X Windows. BUGS was written by Joshua Smith at Williams College and is available by FTP from santafe.edu:/pub/misc/BUGS/BUGS.tar.Z and from ftp.aic.nrl.navy.mil:/pub/galist/src/ga/BUGS.tar.Z Note that it is unsupported software, copyrighted but freely distributable. Address: Room E15-492, MIT Media Lab, 20 Ames Street, Cambridge, MA 02139. (Unverified 8/94). DGenesis: DGenesis is a distributed implementation of a Parallel GA. It is based on Genesis 5.0. It runs on a network of UNIX workstations. It has been tested with DECstations, microVAXes, Sun Workstations and PCs running 386BSD 0.1. Each subpopulation is handled by a UNIX process and the communication between them is accomplished using Berkeley sockets. The system is programmed in C and is available free of charge by anonymous FTP from lamport.rhon.itam.mx:/ and from ftp.aic.nrl.navy.mil:/pub/galist/src/ga/dgenesis-1.0.tar.Z DGenesis allows the user to set the MIGRATION interval, the migration rate and the topology between the SUB-POPULATIONs. There has not been much work investigating the effect of the topology on the PERFORMANCE of the GA, DGenesis was written specifically to encourage experimentation in this area. It still needs many refinements, but some may find it useful. Contact Erick Cantu-Paz at the Instituto Tecnologico Autonomo de Mexico (ITAM) Dougal: DOUGAL is a demonstration program for solving the TRAVELLING SALESMAN PROBLEM using GAs. The system guides the user through the GA, allowing them to see the results of altering parameters relating to CROSSOVER, MUTATION etc. The system demonstrates graphicaly the OPTIMIZATION of the route. The options open to the user to experiment with include percentage CROSSOVER and MUTATION, POPULATION size, steady state or generational replacement, FITNESS technique (linear normalised, is evaluation, etc). DOUGAL requires an IBM compatible PC with a VGA monitor. The software is free, however I would appreciate feedback on what you think of the software. Dougal is available by FTP from ENCORE (see Q15.3) in file EC/GA/src/dougal.zip It's pkzipped and contains executable, vga driver, source code and full documentation. It is important to place the vga driver (egavga.bgi) in the same directory as DOUGAL. Author: Brett Parker, 7 Glencourse, East Boldon, Tyne + Wear, NE36 0LW, England. ESCaPaDE: ESCaPaDE is a sophisticated software environment to run experiments with Evolutionary Algorithms, such as e.g. an EVOLUTION STRATEGY. The main support for experimental work is provided by two internal tables: (1) a table of objective functions and (2) a table of so- called data monitors, which allow easy implementation of functions for monitoring all types of information inside the Evolutionary Algorithm under experiment. ESCaPaDE 1.2 comes with the KORR implementation of the EVOLUTION STRATEGY by H.-P. Schwefel which offers simple and correlated MUTATIONs. KORR is provided as a FORTRAN 77 subroutine, and its cross-compiled C version is used internally by ESCaPaDE. An extended version of the package was used for several investigations so far and has proven to be very reliable. The software and its documentation is fully copyrighted although it may be freely used for scientific work; it requires 5-6 MB of disk space. In order to obtain ESCaPaDE, please send a message to the e-mail address below. The SUBJECT line should contain 'help' or 'get ESCaPaDE'. (If the subject lines is invalid, your mail will be ignored!). For more information contact: Frank Hoffmeister, Systems Analysis Research Group, LSXI, Department of Computer Science, University of Dortmund, D-44221 Dortmund, Germany. Net: Evolution Machine: The Evolution Machine (EM) is universally applicable to continuous (real-coded) OPTIMIZATION problems. In the EM we have coded fundamental evolutionary algorithms (GENETIC ALGORITHMs and EVOLUTION STRATEGIEs), and added some of our approaches to evolutionary search. The EM includes extensive menu techniques with: o Default parameter setting for unexperienced users. o Well-defined entries for EM-control by freaks of the EM, who want to leave the standard process control. o Data processing for repeated runs (with or without change of the strategy parameters). o Graphical presentation of results: online presentation of the EVOLUTION progress, one-, two- and three-dimensional graphic output to analyse the FITNESS function and the evolution process. o Integration of calling MS-DOS utilities (Turbo C). We provide the EM-software in object code, which can be run on PC's with MS-DOS and Turbo C, v2.0, resp. Turbo C++,v1.01. The Manual to the EM is included in the distribution kit. The EM software is available by FTP from ftp-bionik.fb10.tu- berlin.de:/pub/software/Evolution-Machine/ This directory contains the compressed files em_tc.exe (Turbo C), em_tcp.exe (Turbo C++) and em_man.exe (the manual). There is also em-man.ps.Z, a compressed PostScript file of the manual. If you do not have FTP access, please send us either 5 1/4 or 3 1/2 MS-DOS compatible disks. We will return them with the compressed files (834 kB). Official contact information: Hans-Michael Voigt or Joachim Born, Technical University Berlin, Bionics and EVOLUTION Techniques Laboratory, Bio- and Neuroinformatics Research Group, Ackerstrasse 71-76 (ACK1), D-13355 Berlin, Germany. Net: <{voigt,born}@fb10.tu- berlin.de> (Unverified 8/94). GAC, GAL: Bill Spears writes: These are packages I've been using for a few years. GAC is a GA written in C. GAL is my Common Lisp version. They are similar in spirit to John Grefenstette's Genesis, but they don't have all the nice bells and whistles. Both versions currently run on Sun workstations. If you have something else, you might need to do a little modification. Both versions are free: All I ask is that I be credited when it is appropriate. Also, I would appreciate hearing about improvements! This software is the property of the US Department of the Navy. The code will be in a "shar" format that will be easy to install. This code is "as is", however. There is a README and some documentation in the code. There is NO user's guide, though (nor am I planning on writing one at this time). I am interested in hearing about bugs, but I may not get around to fixing them for a while. Also, I will be unable to answer many questions about the code, or about GAs in general. This is not due to a lack of interest, but due to a lack of free time! Available by FTP from ftp.aic.nrl.navy.mil:/pub/galist/src/ga/GAC.shar.Z and GAL.shar.Z . PostScript versions of some papers are under "/pub/spears". Feel free to browse. GAGA: GAGA (GA for General Application) is a self-contained, re-entrant procedure which is suitable for the minimization of many "difficult" cost functions. Originally written in Pascal by Ian Poole, it was rewritten in C by Jon Crowcroft. GAGA can be obtained by request from the author: Jon Crowcroft , Univeristy College London, Gower Street, London WCIE 6BT, UK, or by FTP from ftp://cs.ucl.ac.uk:/darpa/gaga.shar GAGS: GAGS 0.92 (Genetic Algorithms from Granada, Spain) is a library and companion programs written and designed to take the heat out of designing a GENETIC ALGORITHM. It features a class library for genetic algorithm programming, but, from the user point of view, is a genetic algorithm application generator. Just write the function you want to optimize, and GAGS surrounds it with enough code to have a genetic algorithm up and running, compiles it, and runs it. GAGS Is written in C++, so that it can be compiled in any platform running this GNU utility. It has been tested on various machines. Documentation is available. GAGS includes: o Steady-state, roulette-wheel, tournament and elitist SELECTION. o FITNESS evaluation using training files. o Graphics output through gnuplot. o Uniform and 2-point CROSSOVER, and bit-flip and gene-transposition MUTATION. o Variable length CHROMOSOMEs and related operators. The application generator gags.pl is written in perl, so this language must also be installed before GAGS. Available by FTP from: kal-el.ugr.es:/pub/GAGS-0.92.tar.gz The programmer's manual is in the same directory, file gagsprogs.ps.gz. GAGS is also available from ENCORE (see Q15.3) in file EC/GA/src/gags-0.92.tar.gz with documentation in EC/GA/docs/gagsprog.ps.gz Maintained by J.J. Merelo, Grupo Geneura, Univ. Granada GAlib: GAlib is a C++ library that provides the application programmer with a set of GENETIC ALGORITHM objects. With GAlib you can add GA OPTIMIZATION to your program using any data representation and standard or custom SELECTION, CROSSOVER, MUTATION, scaling, and replacement, and termination methods. View the documentation on-line at http://lancet.mit.edu:/ga/ There you will find a complete description of the programming interface, features, and examples. The canonical source for this library is the FTP site: lancet.mit.edu:/pub/ga/ This directory contains UNIX (.tar.gz), MacOS (.sea.hqx), and DOS (.zip) versions of the GA library. Once you have downloaded the file, uncompress and extract it. It will expand to its own directory. If you extract the DOS version be sure to use the -d option to keep everything in one directory. GAlib requires a cfront 3.0 compatible C++ compiler. It has been used on the following systems: SGI IRIX 4.0.x (Cfront); SGI IRIX 5.x (DCC 1.0, g++ 2.6.8, 2.7.0); IBM RSAIX 3.2 (g++ 2.6.8, 2.7.0); DEC MIPS ultrix 4.2 (g++ 2.6.8, 2.7.0); SUN SOLARIS 5.3 (g++ 2.6.8, 2.7.0); HP-UX (g++); MacOS (MetroWerks CodeWarrior 5); MacOS (Symantec THINK C++ 7.0); DOS/Windows (Borland Turbo C++ 3.0). Maintained by: Matthew Wall GALOPPS: GALOPPS (Genetic Algorithm Optimized for Portability and Parallelism) is a flexible, generic GA, based upon SGA-C. It has been extended to provide three types of island parallelism, ranging from a single PC simulating parallel subpopulations, to multiple computers on a network. It's been tested on a wide variety of DOS and UNIX machines. An 80-page User Guide is provided. GALOPPS extends the SGA capabilities several fold: o 5 SELECTION methods. o Random or superuniform initialization of binary CHROMOSOMEs. o 3 CROSSOVER routines for value-based representations, and 4 for order-based reps. o 3 MUTATION routines. o 4 FITNESS scaling routines. o Various replacement strategy options, including crowding replacement and new incest-reduction option. o ELITISM is optional. o Convergence: lost, CONVERGED, percent converged, etc. o Various PERFORMANCE measures o Uses "SGA philosophy" of one template file for the user to modify, but enriched with many additional user callbacks, for added flexibility, extensibility. Ten sample applications are provided -- "standard" ones are Goldberg's three examples, Holland's Royal Road "Challenge" problem, and a blind traveling salesperson problem. For portability, the user interface in the standard distribution is non-graphical. A number of GUIs are in development. GALOPPS Release 2.20 and manual v2.20.ps are available by FTP from isl.cps.msu.edu:/pub/GA/GALOPPS2.20/ Contact: Erik Goodman, Genetic Algorithms Research and Applications Group (GARAGe), Computer Science and Case Center for Computer-Aided Engineering and Manufacturing, 112 Engineering Building, Michigan State University, East Lansing 48824. GAMusic: GAMusic 1.0 is a user-friendly interactive demonstration of a simple GA that evolves musical melodies. Here, the user is the FITNESS function. Melodies from the POPULATION can be played and then assigned a fitness. Iteration, RECOMBINATION frequency and MUTATION frequency are all controlled by the user. This program is intended to provide an introduction to GAs and may not be of interest to the experienced GA programmer. GAMusic was programmed with Microsoft Visual Basic 3.0 for Windows 3.1x. No special sound card is required. GAMusic is distributed as shareware (cost $10) and can be obtained by FTP from wuarchive.wustl.edu:/pub/MSDOS_UPLOADS/GenAlgs/gamusic.zip or from fly.bio.indiana.edu:/science/ibmpc/gamusic.zip The program is also available from the America Online archive. Contact: Jason H. Moore or GANNET: GANNET (Genetic Algorithm / Neural NETwork) is a software package written by Jason Spofford in 1990 which allows one to evolve neural networks. It offers a variety of configuration options related to rates of the GENETIC OPERATORs. GANNET evolves nets based upon three FITNESS functions: Input/Output Accuracy, Output 'Stability', and Network Size. The evolved neural network presently has a binary input and binary output format, with neurodes that have either 2 or 4 inputs and weights ranging from -3 to +4. GANNET allows for up to 250 neurodes in a net. Research using GANNET is continuing. GANNET is available by FTP from fame.gmu.edu:/gannet/source/ There are separate directories for GANNET itself, a verifier program which verifies the best neural network generated (/gannet/verifier), and some sample datasets (/gannet/datasets). Further, Spofford's masters thesis descrribing GANNET is available in postscript format (/gannet/thesis). Contact: Darrell Duane or Dr. Kenneth Hintz, George Mason University, Dept. of Electrical & Computer Engineering, Mail Stop 1G5, 4400 University Drive, Fairfax, VA 22033-4444 USA. Net: or GAucsd: GAucsd is a Genesis-based GA package incorporating numerous bug fixes and user interface improvements. Major additions include a wrapper that simplifies the writing of evaluation functions, a facility to distribute experiments over networks of machines, and Dynamic Parameter Encoding, a technique that improves GA PERFORMANCE in continuous SEARCH SPACEs by adaptively refining the genomic representation of real-valued parameters. GAucsd was written in C for Unix systems, but the central GA engine is easily ported to other platforms. The entire package can be ported to systems where implementations of the Unix utilities "make", "awk" and "sh" are available. GAucsd is available by FTP from cs.ucsd.edu:/pub/GAucsd/GAucsd14.sh.Z or from ftp.aic.nrl.navy.mil:/pub/galist/src/ga/GAucsd14.sh.Z To be added to a mailing list for bug reports, patches and updates, send "add GAucsd" to . Cognitive Computer Science Research Group, CSE Department, UCSD 0114, La Jolla, CA 92093-0114, USA. Net: GA Workbench: A mouse-driven interactive GA demonstration program aimed at people wishing to show GAs in action on simple FUNCTION OPTIMIZATIONs and to help newcomers understand how GAs operate. Features: problem functions drawn on screen using mouse, run-time plots of GA POPULATION distribution, peak and average FITNESS. Useful population STATISTICS displayed numerically, GA configuration (population size, GENERATION gap etc.) performed interactively with mouse. Requirements: MS-DOS PC, mouse, EGA/VGA display. Available by FTP from the simtel20 archive mirrors, e.g. wsmr- simtel20.army.mil:/pub/msdos/neurlnet/gaw110.zip or wuarchive.wustl.edu: or oak.oakland.edu: Produced by Mark Hughes . A windows version is in preparation. GECO: GECO (Genetic Evolution through Combination of Objects) is an extensible, object-oriented framework for prototyping GENETIC ALGORITHMs in Common Lisp. GECO makes extensive use of CLOS, the Common Lisp Object System, to implement its functionality. The abstractions provided by the classes have been chosen with the intent both of being easily understandable to anyone familiar with the paradigm of genetic algorithms, and of providing the algorithm developer with the ability to customize all aspects of its operation. It comes with extensive documentation, in the form of a PostScript file, and some simple examples are also provided to illustrate its intended use. GECO Version 2.0 is available by FTP. See the file ftp.aic.nrl.navy.mil:/pub/galist/src/ga/GECO-v2.0.README for more information. George P. W. Williams, Jr., 1334 Columbus City Rd., Scottsboro, AL 35768. Net: . Genesis: Genesis is a generational GA system written in C by John Grefenstette. As the first widely available GA program Genesis has been very influential in stimulating the use of GAs, and several other GA packages are based on it. Genesis is available together with OOGA (see below), or by FTP from ftp.aic.nrl.navy.mil:/pub/galist/src/ga/genesis.tar.Z (Unverified 8/94). GENEsYs: GENEsYs is a Genesis-based GA implementation which includes extensions and new features for experimental purposes, such as SELECTION schemes like linear ranking, Boltzmann, (mu, lambda)-selection, and general extinctive selection variants, CROSSOVER operators like n-point and uniform crossover as well as discrete and intermediate RECOMBINATION. SELF-ADAPTATION of MUTATION rates is also possible. A set of objective functions is provided, including De Jong's functions, complicated continuous functions, a TSP-problem, binary functions, and a fractal function. There are also additional data- monitoring facilities such as recording average, variance and skew of OBJECT VARIABLES and MUTATION rates, or creating bitmap-dumps of the POPULATION. GENEsYs 1.0 is available via FTP from lumpi.informatik.uni- dortmund.de:/pub/GA/src/GENEsYs-1.0.tar.Z The documentation alone is available as /pub/GA/docs/GENEsYs-1.0-doc.tar.Z For more information contact: Thomas Baeck, Systems Analysis Research Group, LSXI, Department of Computer Science, University of Dortmund, D-44221 Dortmund, Germany. Net: (Unverified 8/94). GenET: GenET is a "generic" GA package. It is generic in the sense that all problem independent mechanisms have been implemented and can be used regardless of application domain. Using the package forces (or allows, however you look at it) concentration on the problem: you have to suggest the best representation, and the best operators for such space that utilize your problem-specific knowledge. You do not have to think about possible GA models or their implementation. The package, in addition to allowing for fast implementation of applications and being a natural tool for comparing different models and strategies, is intended to become a depository of representations and operators. Currently, only floating point representation is implemented in the library with few operators. The algorithm provides a wide selection of models and choices. For example, POPULATION models range from generational GA, through steady-state, to (n,m)-EP and (n,n+m)-EP models (for arbitrary problems, not just parameter OPTIMIZATION). (Some are not finished at the moment). Choices include automatic adaptation of operator probabilities and a dynamic ranking mechanism, etc. Even though the implementation is far from optimal, it is quite efficient - implemented in ATT's C++ (3.0) (functional design) and also tested on gcc. Along with the package you will get two examples. They illustrate how to implement problems with heterogeneous and homogeneous structures, with explicit rep/opers and how to use the existing library (FP). Very soon I will place there another example - our GENOCOP operators for linearly constrained OPTIMIZATION. One more example soon to appear illustrates how to deal with complex structures and non-stationary problems - this is a fuzzy rule-based controller optimized using the package and some specific rep/operators. If you start using the package, please send evaluations (especially bugs) and suggestions for future versions to the author. GenET Version 1.00 is available by FTP from radom.umsl.edu:/var/ftp/GenET.tar.Z To learn more, you may get the User's Manual, available in compressed postscript in "/var/ftp/userMan.ps.Z". It also comes bundled with the complete package. Cezary Z. Janikow, Department of Math and CS, CCB319, St. Louis, MO 63121, USA. Net: Genie: Genie is a GA-based modeling/forecasting system that is used for long-term planning. One can construct a model of an ENVIRONMENT and then view the forecasts of how that environment will evolve into the future. It is then possible to alter the future picture of the environment so as to construct a picture of a desired future (I will not enter into arguments of who is or should be responsible for designing a desired or better future). The GA is then employed to suggest changes to the existing environment so as to cause the desired future to come about. Genie is available free of charge via e-mail or on 3.5'' disk from: Lance Chambers, Department of Transport, 136 Stirling Hwy, Nedlands, West Australia 6007. Net: It is also available by FTP from hiplab.newcastle.edu.au:/pub/Genie&Code.sea.Hqx Genitor: "Genitor is a modular GA package containing examples for floating- point, integer, and binary representations. Its features include many sequencing operators as well as subpopulation modeling. The Genitor Package has code for several order based CROSSOVER operators, as well as example code for doing some small TSPs to optimality. We are planning to release a new and improved Genitor Package this summer (1993), but it will mainly be additions to the current package that will include parallel island models, cellular GAs, delta coding, perhaps CHC (depending on the legal issues) and some other things we have found useful." Genitor is available from Colorado State University Computer Science Department by FTP from ftp.cs.colostate.edu:/pub/GENITOR.tar Please direct all comments and questions to . If these fail to work, contact: L. Darrell Whitley, Dept. of Computer Science, Colorado State University, Fort Collins, CO 80523, USA. Net: (Unverified 8/94). GENlib: GENlib is a library of functions for GENETIC ALGORITHMs. Included are two applications of this library to the field of neural networks. The first one called "cosine" uses a genetic algorithm to train a simple three layer feed-Forward network to work as a cosine-function. This task is very difficult to train for a backprop algorithm while the genetic algorithm produces good results. The second one called "vartop" is developing a Neural Network to perform the XOR-function. This is done with two genetic algorithms, the first one develops the topology of the network, the second one adjusts the weights. GENlib may be obtained by FTP from ftp.neuro.informatik.uni- kassel.de:/pub/NeuralNets/GA-and-NN/ Author: Jochen Ruhland, FG Neuronale Netzwerke / Uni Kassel, Heinrich-Plett-Str. 40, D-34132 Kassel, Germany. GENOCOP: This is a GA-based OPTIMIZATION package that has been developed by Zbigniew Michalewicz and is described in detail in his book "Genetic Algorithms + Data Structures = Evolution Programs" (Springer Verlag, 2nd ed, 1994). GENOCOP (Genetic Algorithm for Numerical Optimization for COnstrained Problems) optimizes a function with any number of linear constraints (equalities and inequalities). The second version of the system is available by FTP from ftp.uncc.edu:/coe/evol/genocop2.tar.Z Zbigniew Michalewicz, Dept. of Computer Science, University of North Carolina, Chappel-Hill, NC, USA. Net: GIGA: GIGA is designed to propogate information through a POPULATION, using CROSSOVER as its operator. A discussion of how it propogates BUILDING BLOCKs, similar to those found in Royal Road functions by John Holland, is given in the DECEPTION section of: "Genetic Invariance: A New Paradigm for Genetic Algorithm Design." University of Alberta Technical Report TR92-02, June 1992. See also: "GIGA Program Description and Operation" University of Alberta Computing Science Technical Report TR92-06, June 1992 These can be obtained, along with the program, by FTP from ftp.cs.ualberta.ca:/pub/TechReports/ in the subdirectories TR92-02/ and TR92-06/ . Also, the paper "Mutation-Crossover Isomorphisms and the Construction of Discriminating Functions" gives a more in-depth look at the behavior of GIGA. Its is available from ftp.cs.ualberta.ca:/pub/joe/Preprints/xoveriso.ps.Z Joe Culberson, Department of Computer Science, University of Alberta, CA. Net: GPEIST: The GENETIC PROGRAMMING ENVIRONMENT in Smalltalk (GPEIST) provides a framework for the investigation of Genetic Programming within a ParcPlace VisualWorks 2.0 development system. GPEIST provides program, POPULATION, chart and report browsers and can be run on HP/Sun/PC (OS/2 and Windows) machines. It is possible to distribute the experiment across several workstations - with subpopulation exchange at intervals - in this release 4.0a. Experiments, populations and INDIVIDUAL genetic programs can be saved to disk for subsequent analysis and experimental statistical measures exchanged with spreadsheets. Postscript printing of charts, programs and animations is supported. An implementation of the Ant Trail problem is provided as an example of the use of the GPEIST environment. GPEIST is available from ENCORE (see Q15.3) in file: EC/GP/src/GPEIST4.tar.gz Contact: Tony White, Bell-Northern Research Ltd., Computer Research Lab - Gateway, 320 March Road, Suite 400, Kanata, Ontario, Canada, K2K 2E3. tel: (613) 765-4279 Imogene: Imogene is a Windows 3.1 shareware program which generates pretty images using GENETIC PROGRAMMING. The program displays GENERATIONs of 9 images, each generated using a formula applied to each pixel. (The formulae are initially randomly computed). You can then select those images you prefer. In the next generation, the nine images are generated by combining and mutating the formulae for the most- preferred images in the previous generation. The result is a SIMULATION of natural SELECTION in which images evolve toward your aesthetic preferences. Imogene supports different color maps, palette animation, saving images to .BMP files, changing the wallpaper to nice images, printing images, and several other features. Imogene works only in 256 color mode and requires a floating point coprocessor and a 386 or better CPU. Imogene is based on work originally done by Karl Sims at (ex-)Thinking Machines for the CM-2 massively parallel computer - but you can use it on your PC. You can FTP Imogene from: ftp.io.com:/pub/genetic-programming/code/imogenes.zip Contact: Harley Davis, ILOG S.A., 2 Avenue Gallini, BP 85, 94253 Gentilly Cedex, France. tel: +33 1 46 63 66 66 LibGA: LibGA is a library of routines written in C for developing GENETIC ALGORITHMs. It is fairly simple to use, with many knobs to turn. Most GA parameters can be set or changed via a configuration file, with no need to recompile. (E.g., operators, pool size and even the data type used in the CHROMOSOME can be changed in the configuration file.) Function pointers are used for the GENETIC OPERATORs, so they can easily be manipulated on the fly. Several genetic operators are supplied and it is easy to add more. LibGA runs on many systems/architectures. These include Unix, DOS, NeXT, and Amiga. LibGA Version 1.00 is available by FTP from ftp.aic.nrl.navy.mil:/pub/galist/src/ga/libga100.tar.Z or by email request to its author, Art Corcoran (Unverified 8/94). LICE: LICE is a parameter OPTIMIZATION program based on EVOLUTION STRATEGIEs (ES). In contrast to classic ES, LICE has a local SELECTION scheme to prevent premature stagnation. Details and results were presented at the EP'94 conference in San Diego. LICE is written in ANSI-C (more or less), and has been tested on Sparc-stations and Linux-PCs. If you want plots and graphics, you need X11 and gnuplot. If you want a nice user interface to create parameter files, you also need Tk/Tcl. LICE-1.0 is available as source code by FTP from lumpi.informatik.uni-dortmund.de:/pub/ES/src/LICE-1.0.tar.gz Author: Joachim Sprave Matlab-GA: The MathWorks FTP site has some Matlab GA code in the directory ftp.mathworks.com:/pub/contrib/optim/genetic It's a bunch of .m files that implement a basic GA. mGA: mGA is an implementation of a messy GA as described in TCGA report No. 90004. Messy GAs overcome the linkage problem of simple GENETIC ALGORITHMs by combining variable-length strings, GENE expression, messy operators, and a nonhomogeneous phasing of evolutionary processing. Results on a number of difficult deceptive test functions have been encouraging with the messy GA always finding global optima in a polynomial number of function evaluations. See TCGA reports 89003, 90005, 90006, and 91004, and IlliGAL report 91008 for more information on messy GAs (See Q14). The C language version is available by FTP from IlliGAL in the directory gal4.ge.uiuc.edu:/pub/src/messyGA/C/ PARAGenesis: PARAGenesis is the result of a project implementing Genesis on the CM-200 in C*. It is an attempt to improve PERFORMANCE as much as possible without changing the behavior of the GENETIC ALGORITHM. Unlike the punctuated equilibria and local SELECTION models, PARAGenesis doesn't modify the genetic algorithm to be more parallelizable as these modifications can drastically alter the behavior of the algorithm. Instead each member is placed on a separate processor allowing initialization, evaluation and MUTATION to be completely parallel. The costs of global control and communication in selection and CROSSOVER are present but minimized as much as possible. In general PARAGenesis on an 8k CM-200 seems to run 10-100 times faster than Genesis on a Sparc 2 and finds equivalent solutions. PARAGenesis includes all the features of serial Genesis plus some additions. The additions include the ability to collect timing STATISTICS, probabilistic SELECTION (as opposed to Baker's stochastic universal sampling), uniform CROSSOVER and local or neighborhood selection. Anyone familiar with the serial implementation of Genesis and C* should have little problem using PARAGenesis. PARAGenesis is available by FTP from ftp.aic.nrl.navy.mil:/pub/galist/src/ga/paragenesis.tar.Z DISCLAIMER: PARAGenesis is fairly untested at this point and may contain some bugs. Michael van Lent, Advanced Technology Lab, University of Michigan, 1101 Beal Av., Ann Arbor, MI 48109, USA. Net: . PGA: PGA is a simple testbed for basic explorations in GENETIC ALGORITHMs. Command line arguments control a range of parameters, there are a number of built-in problems for the GA to solve. The current set includes: o maximize the number of bits set in a CHROMOSOME o De Jong's functions DJ1, DJ2, DJ3, DJ5 o binary F6, used by Schaffer et al o a crude 1-d knapsack problem; you specify a target and a set of numbers in an external file, GA tries to find a subset that sums as closely as possible to the target o the `royal road' function(s); a CHROMOSOME is regarded as a set of consecutive blocks of size K, and scores K for each block entirely filled with 1s, etc; a range of parameters. o max contiguous bits, you choose the ALLELE range. o timetabling, with various smart MUTATION options; capable of solving a good many real-world timetabling problems (has done so) Lots of GA options: rank, roulette, tournament, marriage-tournament, spatially-structured SELECTION; one-point, two-point, uniform or no CROSSOVER; fixed or adaptive MUTATION; one child or two; etc. Default output is curses-based, with optional output to file; can be run non-interactively too for batched series of experiments. It's easy to add your own problems. CHROMOSOMEs are represented as character arrays, so you are not (quite) stuck with bit-string problem encodings. PGA has been used for teaching for a couple of years now, and has been used as a starting point by a fair number of people for their own projects. So it's reasonably reliable. However, if you find bugs, or have useful contributions to make, Tell Me! It is available by FTP from ftp.dai.ed.ac.uk:pub/pga-2.7/pga-2.7.tar.Z (see the file pga.README in the same directory for more information) Peter Ross, Department of AI, University of Edinburgh, 80 South Bridge, Edinburgh EH1 1HN, UK. Net: PGAPack: PGAPack is a general-purpose, data-structure-neutral parallel GENETIC ALGORITHM library under development at Argonne National Laboratory. Features: o Callable from Fortran or C. o Binary-, integer-, and real-valued native data types o Object-oriented data structure neutral design. o Parameterized POPULATION replacement. o Multiple choices for SELECTION, CROSSOVER, and MUTATION operators o Easy integration of hill-climbing heuristics. o Easy-to-use interface for novice and application users. o Access to all library calls for expert users. o Fully extensibile to support custom operators and new data types. o Extensive debugging facilities o An extensive test set. o Support for parallel GA models and parallel computing hardware (not included in this release - but expected late 1995/early 1996). Availability: PGAPack is freely available and may be obtained by anonymous FTP from info.mcs.anl.gov:/pub/pgapack/pgapack.tar.Z Further Information from David Levine, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, Illinois 60439, (708)-252-6735 http://www.mcs.anl.gov:/home/levine SGA-C, SGA-Cube: SGA-C is a C-language translation and extension of the original Pascal SGA code presented in Goldberg's book [GOLD89]. It has some additional features, but its operation is essentially the same as that of the Pascal version. SGA-C is described in TCGA report No. 91002. SGA-Cube is a C-language translation of Goldberg's SGA code with modifications to allow execution on the nCUBE 2 Hypercube Parallel Computer. When run on the nCUBE 2, SGA-Cube can take advantage of the hypercube architecture, and is scalable to any hypercube dimension. The hypercube implementation is modular, so that the algorithm for exploiting parallel processors can be easily modified. In addition to its parallel capabilities, SGA-Cube can be compiled on various serial computers via compile-time options. In fact, when compiled on a serial computer, SGA-Cube is essentially identical to SGA-C. SGA-Cube is described in TCGA report No. 91005. Each of these programs is distributed in the form of a Unix shar file, available via e-mail or on various formatted media by request from: Robert Elliott Smith, Department of Engineering of Mechanics, Room 210 Hardaway Hall,, The University of Alabama P.O. Box 870278, Tuscaloosa, Alabama 35487, USA. Net: SGA-C and SGA-Cube are also available in compressed tar form by FTP from ftp.aic.nrl.navy.mil:/pub/galist/src/ga/sga-c.tar.Z and sga- cube.tar.Z . Splicer: Splicer is a GENETIC ALGORITHM tool created by the Software Technology Branch (STB) of the Information Systems Directorate at NASA/Johnson Space Center with support from the MITRE Corporation. Splicer has well-defined interfaces between a GA kernel, representation libraries, FITNESS modules, and user interface libraries. The representation libraries contain functions for defining, creating, and decoding genetic strings, as well as multiple CROSSOVER and MUTATION operators. Libraries supporting binary strings and permutations are provided, others can be created by the user. FITNESS modules are typically written by the user, although some sample applications are provided. The modules may contain a fitness function, initial values for various control parameters, and a function which graphically displays the best solutions. Splicer provides event-driven graphic user interface libraries for the Macintosh and the X11 window system (using the HP widget set); a menu-driven ASCII interface is also available though not fully supported. The extensive documentation includes a reference manual and a user's manual; an architecture manual and the advanced programmer's manual are currently being written. An electronic bulletin board (300/1200/2400 baud, 8N1) with information regarding Splicer can be reached at (713) 280-3896 or (713) 280-3892. Splicer is available free to NASA and its contractors for use on government projects by calling the STB Help Desk weekdays 9am-4pm CST at (713) 280-2233. Government contractors should have their contract monitor call the STB Help Desk; others may purchase Splicer for $221 (incl. documentation) from: COSMIC, 382 E. Broad St., Athens, GA 30602, USA. (Unverified 8/94). Last known address (Steve Bayer). This now bounces back with "user unknown". TOLKIEN: TOLKIEN (TOoLKIt for gENetics-based applications) is a C++ class library, intended for those involved in GAs and CLASSIFIER SYSTEM research with a working knowledge of C++. It is designed to reduce effort in developing genetics-based applications by providing a collection of reusable objects. For portability, no compiler specific or class library specific features are used. The current version has been compiled successfully using Borland C++ Version 3.1 and GNU C++. TOLKIEN contains a lot of useful extensions to the generic GENETIC ALGORITHM and CLASSIFIER SYSTEM architecture. Examples include: (i) CHROMOSOMEs of user-definable types; binary, character, integer and floating point; (ii) Gray code encoding and decoding; (iii) multi- point and uniform CROSSOVER; (iv) diploidy and dominance; (v) various SELECTION schemes such as tournament selection and linear ranking; (vi) linear FITNESS scaling and sigma truncation; (vii) the simplest one-taxon-one-action classifiers and the general two-taxa-one-action classifiers. TOLKIEN is available from ENCORE (See Q15.3) in file: GA/src/TOLKIEN.tar.gz The documentation and two primers on how to build GA and CFS applications alone are available as: GA/docs/tolkien-doc.tar.gz Author: Anthony Yiu-Cheung Tang , Department of Computer Science (Rm 913), The Chinese University of Hong Kong. Tel: 609-8403, 609-8404. Trans-Dimensional Learning: This is a Windows 3.1 artificial neural netwrk and GA program (shareware). TDL v1.0 allows users to perform pattern recognition by utilizing software that allows for fast, automatic construction of Neural Networks, mostly alleviating the need for parameter tuning. Evolutionary processes combined with semi-weighted networks (hybrid cross between standard weighted neurons and weightless n-level threshold units) generally yield very compact networks (i.e., reduced connections and hidden units). By supporting multi-shot learning over standard one-shot learning, multiple data sets (characterized by varying input and output dimensions) can be learned incrementally, resulting in a single coherent network. This can also lead to significant improvements in predictive accuracy (Trans-dimensional generalization). Graphical support and several data files are also provided. Available by FTP from: oak.oakland.edu:/SimTel/win3/neurlnet/tdl10.zip also available on WWW from: http://www.acs.oakland.edu:/oak/SimTel/win3/neurlnet.html For further details contact: Steve Romaniuk WOLF: This is a simulator for the G/SPLINES (genetic spline models) algorithm which builds spline-based functional models of experimental data, using CROSSOVER and MUTATION to evolve a POPULATION towards a better fit. It is derived from Friedman's MARS models. The original work was presented at ICGA-4, and further results including additional basis function types such as B-splines have been presented at the NIPS-91 meeting. Available free by FTP by contacting the author; runs on SUN (and possibly any SYSV) UNIX box. Can be redistributed for noncommercial use. Simulator includes executable and C source code; a technical report (RIACS tech report 91.10) is also available. David Rogers, MS Ellis, NASA Ames Research Center, Moffett Field, CA 94035, USA. Net: CLASSIFIER SYSTEMS CFS-C: CFS-C 1.0 is a domain independent collection of CLASSIFIER SYSTEM routines written by Rick L. Riolo as part of his PhD dissertation. A completely rewritten CFS-C is planned for 1994/95; this may include the features of CFS-C 2.0 mentioned in [SAB90] (e.g. "latent learning") or they may be included in a separate package released in 1995. An ANSIfied version of CFS-C 1.0 (CFS-C 1.98j) is available by FTP. CFS-C is available from ENCORE (See Q15.3) in file: CFS/src/cfsc-1.98j.tar.gz and includes the original 1.02 CFS-C in it's "cfsc/orig" folder after unpacking. On the "SyS" FTP server it's: lumpi.informatik.uni-dortmund.de:/pub/LCS/src/cfsc-1.98j.tar.gz with documentation in /pub/LCS/docs/cfsc.ps.gz Another version of CFS-C (version XV 0.1) by Jens Engel is also available. This includes bug fixes of earlier versions, allowing it to run on a wider range of machines (e.g. Linux and nCUBE). It also has an XView front end that makes it easier to control, and some extensions to the algorithms. It is available from ENCORE in file: CFS/src/cfscxv-0.1.tar.gz with documentation in CFS/docs/cfscxv-0.1.readme.gz References Rick L. Riolo (1988) "CFS-C: A package of domain independent subroutines for implementing classifier systems in arbitrary, user- defined environments", Logic of computers group, Division of computer science and engineering, University of Michigan. Rick L. Riolo (1988) "LETSEQ: An implementation of the CFS-C classifier-system in a task-domain that involves learning to predict letter sequences", Logic of computers group, Division of computer science and engineering, University of Michigan. Rick L. Riolo (1988) "CFS-C/FSW1: An implementation of the CFS-C classifier system in a task domain that involves learning to traverse a finite state world", Logic of computers group, Division of computer science and engineering, University of Michigan. SCS-C: SCS-C is a (`mostly ANSI') C language translation and extension of Goldberg's Simple CLASSIFIER SYSTEM, as presented in Appendix D in his seminal book [GOLD89]. SCS-C has been developed in parallel on a Sun 10/40 and an ATARI ST, and thus should be quite portable; it's distributed free of charge under the terms of the GNU General Public License. Included are some additional goodies, e.g. the VAX/VMS version of SCS, rewritten in C by Erik Mayer . SCS-C v1.0j is available from ENCORE (See Q15.3), by FTP in file EC/CFS/src/scsc-1.0j.tar.gz For more information contact: Joerg Heitkoetter, EUnet Deutschland GmbH, Techo-Park, Emil-Figge-Str. 80, D-44227 Dortmund, Germany. Net: . ------------------------------ Subject: Q20.2: Commercial software packages? ComputerAnts: ComputerAnts is a $10 Windows program that teaches principles of GENETIC ALGORITHMs by breeding a colony of ants on your computer screen. Users create ants, food, poison, and set CROSSOVER and MUTATION rates. Then they watch the colony slowly evolve. Includes extensive on-line help and tutorials on genetic algorithms. For further information or to order, contact: Axcelis, Inc., 4668 Eastern Avenue North, Seattle, WA 98103-6932, USA Tel: (206) 632-0885. <72723.3614@compuserve.com> EnGENEer: Logica Cambridge Ltd. developed EnGENEer as an in-house GENETIC ALGORITHM environment to assist the development of GA applications on a wide range of domains. The software was written in C and runs under Unix as part of a consultancy and systems package. It supports both interactive (X-Windows) and batch (command-line) modes of operation. EnGENEer provides a number of flexible mechanisms which allow the developer to rapidly bring the power of GAs to bear on new problem domains. Starting with the Genetic Description Language, the developer can describe, at high level, the structure of the ``genetic material'' used. The language supports discrete GENEs with user defined cardinality and includes features such as multiple CHROMOSOMEs models, multiple SPECIES models and non-evolvable parsing symbols which can be used for decoding complex genetic material. The user also has available a descriptive high level language, the Evolutionary Model Language. It allows the description of the GA type used in terms of configurable options including: POPULATION size, population structure and source, SELECTION method, CROSSOVER and MUTATION type and probability, INVERSION, dispersal method, and number of OFFSPRING per GENERATION. Both the Genetic Description Language and the Evolutionary Model Language are fully supported within the interactive interface (including online help system) and can be defined either "on the fly" or loaded from audit files which are automatically created during a GA run. Monitoring of GA progress is provided via both graphical tools and automatic storage of results (at user defined intervals). This allows the user to restart EnGENEer from any point in a run, by loading both the POPULATION at that time and the evolutionary model that was being used. Connecting EnGENEer to different problem domains is achieved by specifying the name of the program used to evaluate the problem specific FITNESS function and constructing a simple parsing routine to interpret the genetic material. A library of standard interpretation routines are also provided for commonly used representation schemes such as gray-coding, permutations, etc. The fitness evaluation can then be run as either a slave process to the GA or via a standard handshaking routines. Better still, it can be run on either the machine hosting the EnGENEer or on any sequential or parallel hardware capable of connecting to a Unix machine. For more information, contact: George Robbins, Systems Intelligence Division, Logica Cambridge Ltd., Betjeman House, 104 Hills Road, Cambridge CB2 1LQ, UK. Tel: +44 716 379111, Fax: +44 223 322315 (Unverified 8/94). EvoFrame: EvoFrame is to EVOLUTION STRATEGIEs what MicroGA is to GENETIC ALGORITHMs, a toolkit for application development incorporating ESs as the OPTIMIZATION engine. EvoFrame is an object oriented implemented programming tool for EVOLUTION STRATEGIEs (Rechenberg/Schwefel, Germany) for easy implementation and solution of numerical and combinatorical problems. EvoFrame gives you freedom of implementing every byte of the OPTIMIZATION principle and its user interface. You can focus on the optimization problem and forget about all the rest. EvoFrame is available as Version 2.0 in Borland-Pascal 7.0 and Turbo- Vision for PC's and as Version 1.0 in C++ for Apple Macintosh using MPW and MacApp. Both implementations allow full typed implementation, i.e. no more translation from problem specific format to an OPTIMIZATION specific one. A prototyping tool (cf REALizer) exists for both platforms too. EvoFrame allows pseudoparallel OPTIMIZATION of many problems at once and you can switch optimization parameters and internal methods (i.e. quality function etc.) during runtime and during optimization cycle. Both tools can be modified or extended by overloading existing methods for experimental use. They are developed continously in correlation to new research results. The PC version is prepared for experimental use due to a comprehensive protocolling mechanism of optimzation cycles and user data. It also allows compilation of executable files with different complexity by setting conditional compilation flags. It can be used with 3 levels of stacked POPULATIONs. The Mac version is the more complex (recursive) implementation. It allows stacking of any number of POPULATIONs for modelling of complex systems. Theory stops at multipopulation level at the time. EvoFrame for Mac is ready for the future, allowing any number of population levels. Ask for porting the Mac version (C++) to any other platform, i.e. X Windows. REALizer is a tool for rapid prototyping of EvoFrame applications. It's an override of the corresponding framework which is prepared to optimize using a vector of real numbers. All methods for standard EVOLUTION and file handling, etc. are ready implemented. The remaining work for the user is to define a constant for the problem size, fill in the quality function and start the OPTIMIZATION process. For further information, current prices and orders, contact: Wolfram Stebel, Optimum Software, Braunfelser Str. 26, 35578 Wetzlar, Germany. Net: Evolver: Evolver is a GENETIC ALGORITHM package for Windows. Beginners can use the Excel add-in to model and solve problems from within Excel. Advanced users can use the included Evolver API to build custom applications that access any of the six different genetic algorithms. Evolver can be customized and users can monitor progress in real-time graphs, or change parameters through the included EvolverWatcher program. The $349 package comes on two 3.5" disks, and includes support for Visual Basic. For further information or to order, contact: Axcelis, Inc., 4668 Eastern Avenue North, Seattle, WA 98103-6932, USA Tel: (206) 632-0885. <72723.3614@compuserve.com> FlexTool: FlexTool(GA) is a modular software tool which provides an ENVIRONMENT for applying a GA to diverse domains with minimum user interaction and design iteration. Version M1.1 is the MATLAB version which provides a total GA based design and development environment in MATLAB. MATLAB provides us with an interactive computation intensive environment. FlexTool(GA) Version M1.1 is designed with emphasis on modularity, flexibility, user friendliness, environment transparency, upgradability, and reliability. FlexTool(GA) M 1.1 Features: o Modular, User Friendly, Hardware and operating system transparent o Expert, Intermediate, and Novice help settings o Hands-on tutorial with step by step application guidelines o GA options : generational GA, steady state GA, micro GA o Coding schemes include binary, logarithmic (real) o SELECTION strategies : tournament, roulette wheel, ranking o CROSSOVER techniques include 1, 2, multiple point crossover o Niching module to identify multiple solutions o Clustering module : Use separately or with Niching module o Can optimize multiple objectives o STATISTICS, figures, and data collection MATLAB is a registered trademark of The MathWorks, Inc. FlexTool(GA) is a Trademark of Flexible Intelligence Group, L.L.C. Contact for more information GAME: GAME (GA Manipulation Environment) aims to demonstrate GA applications and build a suitable programming ENVIRONMENT. GAME is being developed as part of the PAPAGENA project of the European Community's Esprit III initiative. GAME is available as an addendum to a book on PGAs (cf PAPAGENA, Q20.3). And from the project's FTP server bells.cs.ucl.ac.uk:/papagena/ e.g. "papagena/game/docs" contains all the papers that have been produced over the course of the GAME project. The sources can also be obtained by FTP see papagena/game/version2.01/ GAME is now in version 2.01. This version is still able to run only sequential GAs, but version 3.0 will handle parallel GAs as well. Unfortunately, The project yet only produced a Borland C++ 3.x version, so far. It is intended to distribute a version for UNIX/GNU C++ as well, when some compatibility issues concerning C++ "standards" have been resolved. Afterward a UNIX version will be released, but this will be only happen after the release of PC version 3.0. For more information contact: Jose Luiz Ribeiro Filho, Department of Computer Science, University College London, Gower Street, London WC1E 6BT, UK. Net: (Unverified 8/94). Generator: GENERATOR is a GENETIC ALGORITHM package designed to interact with Microsoft Excel for Windows. Users are able to define and solve problems using Excel formulas, tables and functions. FITNESS is easily defined as an Excel formula or optionally a macro. Progress can be monitored using GENERATOR's real-time fitness graph and status window as well as user-defined Excel graphs. GENERATOR can be paused at any time to allow adjustment of any of the parameters and then resumed. GENERATOR Features: o Multiple GENE types: integer, real and permutation. o Combined roulette-wheel and elitist SELECTION method. o ELITISM is optional and adjustable. o None, two-point, and a proprietary permutation CROSSOVER. o Random, Random Hillclimb and Directional Hillclimb MUTATION methods. o Special hillclimbing features to find solutions faster. o FITNESS goal: maximize, minimize or seek value. o Convergence: duplicates not allowed. o Real-Time alteration of parameters relating to CROSSOVER, MUTATION, POPULATION, etc. o Real-Time progress graph of Best, Worst and Median FITNESS. o FITNESS defined using an Excel formula or macro. The parameters available to the user include MUTATION probability for POPULATION and GENEs, control of mutation limit per gene, control of hillclimbing, population size, elite group size, RECOMBINATION method, and mutation technique. Connecting generator to problems defined on the Excel spreadsheet is achieved by first specifying the spreadsheet locations of the GENE group cells and their type, and lastly, the location of the formula used to evaluate the problem-specific FITNESS function. GENERATOR requires at least a 386 IBM compatible PC with 2 MB of RAM, Windows 3.0 (or later) and Microsoft Excel 4.0 (or later). A comprehensive manual includes an explanation of GENETIC ALGORITHMs and several tutorial example problems. The $379 package.includes GENERATOR on a 3.5" diskette, the manual, and free customer support. For further information or to order, contact: New Light Industries, Ltd.; 9713 W. Sunset Hwy; Spokane, WA USA 99204 Tel: (509) 456-8321; Fax (509) 456-8351; E-mail: WWW page: http://www.iea.com:/~nli MicroGA: MicroGA is a powerful and flexible new tool which allows programmers to integrate GAs into their software quickly and easily. It is an object-oriented C++ framework that comes with full source code and documentation as well as three sample applications. Also included is the Galapagos code generator which allows users to create complete applications interactively without writing any C++ code, and a sample MacApp interface. MicroGA is available for Macintosh II or higher with MPW and a C++ compiler, and also in a Microsoft Windows version for PC compatibles. Compiled applications made with MicroGA can be sold without license fee. MicroGA is priced at $249. Galapagos is a tool for use with Emergent Behavior's MicroGA Toolkit. It allows a user to define a function and set of constraints for a problem that the user wants to solve using the GA. Galapagos then generates a complete C++ program using the information supplied. Then all the user has to do is to compile these files, using either Turbo/Borland C++ (PC, MS Windows), or MPW and C++ compiler (Macintosh), and link the resulting code to the MicroGA library. Then just run the program. Galapagos comes free with every copy of MicroGA. For further information and orders, contact: Steve Wilson, Emergent Behavior, 635 Wellsbury Way, Palo Alto, CA 94306, USA. Net: MicroGA is distributed in Germany by Optimum Software (cf EvoFrame & REALizer entries). Omega: The Omega Predictive Modeling System, marketed by KiQ Limited, is a powerful approach to developing predictive models. It exploits advanced GA techniques to create a tool which is "flexible, powerful, informative and straightforward to use". Omega is geared to the financial domain, with applications in Direct Marketing, Insurance, Investigations and Credit Management. The ENVIRONMENT offers facilities for automatic handling of data; business, statistical or custom measures of PERFORMANCE, simple and complex profit modeling, validation sample tests, advanced confidence tests, real time graphics, and optional control over the internal GA. For further information, contact: KiQ, Business Modeling Systems Ltd., Easton Hall, Great Easton, Essex CM6 2HD, UK. Tel: +44 371 870254 (Unverified 8/94). OOGA: OOGA (Object-Oriented GA) is a GENETIC ALGORITHM designed for industrial use. It includes examples accompanying the tutorial in the companion "Handbook of Genetic Algorithms". OOGA is designed such that each of the techniques employed by a GA is an object that may be modified, displayed or replaced in object-oriented fashion. OOGA is especially well-suited for individuals wishing to modify the basic GA techniques or tailor them to new domains. The buyer of OOGA also receives Genesis (see above). This release sports an improved user interface. OOGA and Genesis are available together on 3.5'' or 5.25'' disk for $60 ($52.50 inside North America) by order from: The Software Partnership (T.S.P.), P.O. Box 991, Melrose, MA 02176, USA. Tel: +1 617 662 8991 (Unverified 8/94). PC-Beagle: PC-Beagle is a rule-finder program for PCs which examines a database of examples and uses machine-learning techniques to create a set of decision rules for classifying those examples, thus turning data into knowledge. The system contains six major components, one of which (HERB - the "Heuristic Evolutionary Rule Breeder") uses GA techniques to generate rules by natural SELECTION. PC-Beagle is available to educational users for 69 pounds sterling. Orders, payment or requests for information should be addressed to: Richard Forsyth, Pathway Research Ltd., 59 Cranbrook Rd., Bristol BS6 7BS, UK. Tel: +44 272 428692 (Unverified 8/94). XpertRule GenAsys: XpertRule GenAsys is an expert system shell with embedded GENETIC ALGORITHM marketed by Attar Software. Targeted to solve scheduling and design applications, this system combines the power of genetic algorithms in evolving solutions with the power of rule-based programming in analyzing the effectiveness of solutions. Rule-based programming can also be used to generate the initial POPULATION for the genetic algorithm and for post-optimization planning. Some examples of design and scheduling problems which can be solved by this system include: OPTIMIZATION of design parameters in electronic and avionic industries, route optimization in the distribution sector, production scheduling in manufacturing, etc. For further information, contact: Attar Software, Newlands Road, Leigh, Lancashire, UK. Tel: +44 942 608844. (Unverified 8/94). Last known address <100166.1547@CompuServe.com>. This now bounces back with "user unknown". XYpe: XYpe (The GA Engine) is a commercial GA application and development package for the Apple Macintosh. Its standard user interface allows you to design CHROMOSOMEs, set attributes of the genetic engine and graphically display its progress. The development package provides a set of Think C libraries and include files for the design of new GA applications. XYpe supports adaptive operator weights and mixtures of alpha, binary, gray, ordering and real number codings. The price of $725 (in Massachusetts add 5% sales tax) plus $15 shipping and handling includes technical support and three documentation manuals. XYpe requires a Macintosh SE or newer with 2MB RAM running OS V6.0.4 or greater, and Think C if using the development package. Currently the GA engine is working; the user interface will be completed on demand. Interested parties should contact: Ed Swartz, Virtual Image, Inc., 75 Sandy Pond Road #11, Ayer, MA 01432, USA. Tel: +1 (508) 772-4225 (Unverified 8/94). ------------------------------ Subject: Q20.3: Current research projects? PAPAGENA: The European ESPRIT III project PAPAGENA is pleased to announce the availability of the following book and software: Parallel Genetic Algorithms: Theory and Applications was recently published by IOS press. The book, edited by Joachim Stender, provides an overview of the theoretical, as well as practical, aspects involved in the study and implementation of parallel GENETIC ALGORITHMs (PGAs). The book comes with a floppy disk version of GAME (Genetic Algorithm Manipulation Environment). For more information see the section on GAME in Q20.2. PeGAsuS: PeGAsuS is a general programming environment for evolutionary algorithms. developed at the German National Research Center for Computer Science. Written in ANSI-C, it runs on MIMD parallel machines, such as transputers, and distributed systems, as well as serial machines. The Library contains GENETIC OPERATORs, a collection of FITNESS functions, and input/output and control procedures. It provides the user with a number of validated modules. Currently, PeGAsuS can be compiled with the GNU C, RS/6000 C, ACE-C, and Alliant's FX/2800 C compilers. It runs on SUNs and RS/6000 workstations, as well as on the Alliant FX/28. PeGAsuS is not available to the public. For more information contact: Dirk Schlierkamp-Voosen, Research Group for Adative Systems, German National Research Center for Computer Science, 53731 Sankt Augustin, Germany. Net: ------------------------------ Copyright (c) 1993-1995 by J. Heitkoetter and D. Beasley, all rights reserved. This FAQ may be posted to any USENET newsgroup, on-line service, or BBS as long as it is posted in its entirety and includes this copyright statement. This FAQ may not be distributed for financial gain. This FAQ may not be included in commercial collections or compilations without express permission from the author. End of ai-faq/genetic/part5 *************************** -- Newsgroups: comp.ai.genetic,comp.answers,news.answers Path: senator-bedfellow.mit.edu!bloom-beacon.mit.edu!crl.dec.com!caen!newsxfer.itd.umich.edu!news.kreonet.re.kr!usenet.kornet.nm.kr!agate!howland.reston.ans.net!newsfeed.internetmci.com!in2.uu.net!EU.net!peer-news.britain.eu.net!yama.mcc.ac.uk!thor.cf.ac.uk!news From: David.Beasley@cs.cf.ac.uk (David Beasley) Subject: FAQ: comp.ai.genetic part 6/6 (A Guide to Frequently Asked Questions) Summary: This is part 6 of a entitled "The Hitch-Hiker's Guide to Evolutionary Computation". A periodically 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: David.Beasley@cs.cf.ac.uk (David Beasley) Sender: news@cf.ac.uk (USENET News System) Message-ID: Supersedes: Approved: news-answers-request@MIT.Edu Date: Tue, 12 Dec 1995 16:13:46 GMT Expires: Fri, 15 Mar 1996 16:13:00 GMT X-Nntp-Posting-Host: thrall References: Organization: Cardiff University of Wales Followup-To: comp.ai.genetic Lines: 1534 Xref: senator-bedfellow.mit.edu comp.ai.genetic:7444 comp.answers:15880 news.answers:59916 Archive-name: ai-faq/genetic/part6 Last-Modified: 12/20/95 Issue: 3.4 TABLE OF CONTENTS OF PART 6 Q21: What are Gray codes, and why are they used? Q22: What test data is available? Q42: What is Life all about? Q42b: Is there a FAQ to this group? Q98: Are there any patents on EAs? Q99: A Glossary on EAs? ---------------------------------------------------------------------- Subject: Q21: What are Gray codes, and why are they used? The correct spelling is "Gray"---not "gray", "Grey", or "grey"--- since Gray codes are named after the Frank Gray who patented their use for shaft encoders in 1953 [1]. Gray codes actually have a longer history, and the inquisitive reader may want to look up the August, 1972, issue of Scientific American, which contains two articles of interest: one on the origin of binary codes [2], and another by Martin Gardner on some entertaining aspects of Gray codes [3]. Other references containing descriptions of Gray codes and more modern, non-GA, applications include the second edition of Numerical Recipes [4], Horowitz and Hill [5], Kozen [6], and Reingold [7]. A Gray code represents each number in the sequence of integers {0...2^N-1} as a binary string of length N in an order such that adjacent integers have Gray code representations that differ in only one bit position. Marching through the integer sequence therefore requires flipping just one bit at a time. Some call this defining property of Gray codes the "adjacency property" [8]. Example (N=3): The binary coding of {0...7} is {000, 001, 010, 011, 100, 101, 110, 111}, while one Gray coding is {000, 001, 011, 010, 110, 111, 101, 100}. In essence, a Gray code takes a binary sequence and shuffles it to form some new sequence with the adjacency property. There exist, therefore, multiple Gray codings for any given N. The example shown here belongs to a class of Gray codes that goes by the fancy name "binary-reflected Gray codes". These are the most commonly seen Gray codes, and one simple scheme for generationg such a Gray code sequence says, "start with all bits zero and successively flip the right-most bit that produces a new string." Hollstien [9] investigated the use of GAs for optimizing functions of two variables and claimed that a Gray code representation worked slightly better than the binary representation. He attributed this difference to the adjacency property of Gray codes. Notice in the above example that the step from three to four requires the flipping of all the bits in the binary representation. In general, adjacent integers in the binary representaion often lie many bit flips apart. This fact makes it less likely that a MUTATION operator can effect small changes for a binary-coded INDIVIDUAL. A Gray code representation seems to improve a MUTATION operator's chances of making incremental improvements, and a close examination suggests why. In a binary-coded string of length N, a single mutation in the most significant bit (MSB) alters the number by 2^(N-1). In a Gray-coded string, fewer mutations lead to a change this large. The user of Gray codes does, however, pay a price for this feature: those "fewer mutations" lead to much larger changes. In the Gray code illustrated above, for example, a single mutation of the left-most bit changes a zero to a seven and vice-versa, while the largest change a single mutation can make to a corresponding binary- coded INDIVIDUAL is always four. One might still view this aspect of Gray codes with some favor: most mutations will make only small changes, while the occasional mutation that effects a truly big change may initiate EXPLORATION of an entirely new region in the space of CHROMOSOMEs. The algorithm for converting between the binary-reflected Gray code described above and the standard binary code turns out to be surprisingly simple to state. First label the bits of a binary-coded string B[i], where larger i's represent more significant bits, and similarly label the corresponding Gray-coded string G[i]. We convert one to the other as follows: Copy the most significant bit. Then for each smaller i do either G[i] = XOR(B[i+1], B[i])---to convert binary to Gray---or B[i] = XOR(B[i+1], G[i])---to convert Gray to binary. One may easily implement the above algorithm in C. Imagine you do something like typedef unsigned short ALLELE; and then use type "allele" for each bit in your CHROMOSOME, then the following two functions will convert between binary and Gray code representations. You must pass them the address of the high-order bits for each of the two strings as well as the length of each string. (See the comment statements for examples.) NB: These functions assume a chromosome arranged as shown in the following illustration. index: C[9] C[0] *-----------------------------------------------------------* Char C: | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | *-----------------------------------------------------------* ^^^^^ ^^^^^ high-order bit low-order bit C CODE /* Gray <==> binary conversion routines */ /* written by Dan T. Abell, 7 October 1993 */ /* please send any comments or suggestions */ /* to dabell@quark.umd.edu */ void gray_to_binary (Cg, Cb, n) /* convert chromosome of length n from */ /* Gray code to binary representation */ allele *Cg,*Cb; int n; { int j; *Cb = *Cg; /* copy the high-order bit */ for (j = 0; j < n; j++) { Cb--; Cg--; /* for the remaining bits */ *Cb= *(Cb+1)^*Cg; /* do the appropriate XOR */ } } void binary_to_gray(Cb, Cg, n) /* convert chromosome of length n from */ /* binary to Gray code representation */ allele *Cb, *Cg; int n; { int j; *Cg = *Cb; /* copy the high-order bit */ for (j = 0; j < n; j++) { Cg--; Cb--; /* for the remaining bits */ *Cg= *(Cb+1)^*Cb; /* do the appropriate XOR */ } } References [1] F. Gray, "Pulse Code Communication", U. S. Patent 2 632 058, March 17, 1953. [2] F. G. Heath, "Origins of the Binary Code", Scientific American v.227,n.2 (August, 1972) p.76. [3] Martin Gardner, "Mathematical Games", Scientific American v.227,n.2 (August, 1972) p.106. [4] William H. Press, et al., Numerical Recipes in C, Second Edition (Cambridge University Press, 1992). [5] Paul Horowitz and Winfield Hill, The Art of Electronics, Second Edition (Cambridge University Press, 1989). [6] Dexter Kozen, The Design and Analysis of Algorithms (Springer- Verlag, New York, NY, 1992). [7] Edward M. Reingold, et al., Combinatorial Algorithms (Prentice Hall, Englewood Cliffs, NJ, 1977). [8] David E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning (Addison-Wesley, Reading, MA, 1989). [9] R. B. Hollstien, Artificial Genetic Adaptation in Computer Control Systems (PhD thesis, University of Michigan, 1971). ------------------------------ Subject: Q22: What test data is available? TSP DATA There is a TSP library (TSPLIB) available which has many solved and semi-solved TSPs and different variants. The library is maintained by Gerhard Reinelt . It is available from various FTP sites, including: softlib.cs.rice.edu:/pub/tsplib/tsblib.tar OPERATIONAL RESERACH DATA Information about Operational Research test problems in any of the areas listed below can be obtained by emailing with the body of the email message being just the word "info". The files in OR-Library are also available via anonymous FTP from mscmga.ms.ic.ac.uk:/pub/ A WWW page is also available at URL: http://mscmga.ms.ic.ac.uk/ Instructions on how to use OR-Library can be found in the file "paper.txt", or in the article: J.E.Beasley, "OR-Library: distributing test problems by electronic mail", Journal of the Operational Research Society 41(11) (1990) pp1069-1072. File Problem area assigninfo.txt Assignment problem cspinfo.txt Crew scheduling deainfo.txt Data envelopment analysis gapinfo.txt Generalised assignment problem mipinfo.txt Integer programming lpinfo.txt Linear programming Location: capmstinfo.txt capacitated minimal spanning tree capinfo.txt capacitated warehouse location pmedinfo.txt p-median uncapinfo.txt uncapacitated warehouse location mknapinfo.txt Multiple knapsack problem qapinfo.txt Quadratic assignment problem rcspinfo.txt Resource constrained shortest path Scheduling: flowshopinfo.txt flow shop jobshopinfo.txt job shop openshopinfo.txt open shop scpinfo.txt Set covering sppinfo.txt Set partitioning Steiner: esteininfo.txt Euclidean Steiner problem rsteininfo.txt Rectilinear Steiner problem steininfo.txt Steiner problem in graphs tspinfo.txt Travelling salesman problem Two-dimensional cutting: assortinfo.txt assortment problem cgcutinfo.txt constrained guillotine ngcutinfo.txt constrained non-guillotine gcutinfo.txt unconstrained guillotine Vehicle routing: areainfo.txt fixed areas fixedinfo.txt fixed routes periodinfo.txt period routing vrpinfo.txt single period OTHER DATA William Spears maintains a WWW page titled: Test Functions for Evolutionary Algorithms which contians links to various sources of test functions. http://www.aic.nrl.navy.mil:80/~spears/functs.html ENCORE (see Q15.3) also contains some test data. See directories under /etc/data/ ------------------------------ Subject: Q42: What is Life all about? 42 References Adams, D. (1979) "The Hitch Hiker's Guide to the Galaxy", London: Pan Books. Adams, D. (1980) "The Restaurant at the End of the Universe", London: Pan Books. Adams, D. (1982) "Life, the Universe and Everything", London: Pan Books. Adams, D. (1984) "So long, and thanks for all the Fish", London: Pan Books. Adams, D. (1992) "Mostly Harmless", London: Heinemann. ------------------------------ Subject: Q42b: Is there a FAQ to this group? Yes. ------------------------------ Subject: Q98: Are there any patents on EAs? Process patents have been issued both for the Bucket Brigade Algorithm in CLASSIFIER SYSTEMs: U.S. patent #4,697,242: J.H. Holland and A. Burks, "Adaptive computing system capable of learning and discovery", 1985, issued Sept 29 1987; and for GP: U.S. patent #4,935,877 (to John Koza). This FAQ does not attempt to provide legal advice. However, use of the Lisp code in the book [KOZA92] is freely licensed for academic use. Although those wishing to make commercial use of any process should obviously consult any patent holders in question, it is pretty clear that it's not in anyone's best interests to stifle GA/GP research and/or development. Commercial licenses much like those used for CAD software can presumably be obtained for the use of these processes where necessary. Jarmo Alander's massive bibliography of GAs (see Q10.8) includes a (probably) complete list of all currently know patents. There is also a periodic posting on comp.ai.neural-nets by Gregory Aharonian about patents on Artificial Neural Networks (ANNs). ------------------------------ Subject: Q99: A Glossary on EAs? 1 1/5 SUCCESS RULE: Derived by I. Rechenberg, the suggestion that when Gaussian MUTATIONs are applied to real-valued vectors in searching for the minimum of a function, a rule-of-thumb to attain good rates of error convergence is to adapt the STANDARD DEVIATION of mutations to generate one superior solution out of every five attempts. A ADAPTIVE BEHAVIOUR: "...underlying mechanisms that allow animals, and potentially, ROBOTs to adapt and survive in uncertain environments" --- Meyer & Wilson (1991), [SAB90] AI: See ARTIFICIAL INTELLIGENCE. ALIFE: See ARTIFICIAL LIFE. ALLELE : (biol) Each GENE is able to occupy only a particular region of a CHROMOSOME, it's locus. At any given locus there may exist, in the POPULATION, alternative forms of the gene. These alternative are called alleles of one another. (EC) The value of a GENE. Hence, for a binary representation, each gene may have an ALLELE of 0 or 1. ARTIFICIAL INTELLIGENCE: "...the study of how to make computers do things at which, at the moment, people are better" --- Elaine Rich (1988) ARTIFICIAL LIFE: Term coined by Christopher G. Langton for his 1987 [ALIFEI] conference. In the preface of the proceedings he defines ALIFE as "...the study of simple computer generated hypothetical life forms, i.e. life-as-it-could-be." B BUILDING BLOCK: (EC) A small, tightly clustered group of GENEs which have co- evolved in such a way that their introduction into any CHROMOSOME will be likely to give increased FITNESS to that chromosome. The "building block hypothesis" [GOLD89] states that GAs find solutions by first finding as many BUILDING BLOCKs as possible, and then combining them together to give the highest FITNESS. C CENTRAL DOGMA: (biol) The dogma that nucleic acids act as templates for the synthesis of proteins, but never the reverse. More generally, the dogma that GENEs exert an influence over the form of a body, but the form of a body is never translated back into genetic code: acquired characteristics are not inherited. cf LAMARCKISM. (GA) The dogma that the behaviour of the algorithm must be analysed using the SCHEMA THEOREM. (life in general) The dogma that this all is useful in a way. "You guys have a dogma. A certain irrational set of believes. Well, here's my irrational set of beliefs. Something that works." --- Rodney A. Brooks, [LEVY92] CFS: See CLASSIFIER SYSTEM. CHROMOSOME: (biol) One of the chains of DNA found in cells. CHROMOSOMEs contain GENEs, each encoded as a subsection of the DNA chain. Chromosomes are usually present in all cells in an organism, even though only a minority of them will be active in any one cell. (EC) A datastructure which holds a `string' of task parameters, or GENEs. This may be stored, for example, as a binary bit- string, or an array of integers. CLASSIFIER SYSTEM: A system which takes a (set of) inputs, and produces a (set of) outputs which indicate some classification of the inputs. An example might take inputs from sensors in a chemical plant, and classify them in terms of: 'running ok', 'needs more water', 'needs less water', 'emergency'. See Q1.4 for more information. COMBINATORIAL OPTIMIZATION: Some tasks involve combining a set of entities in a specific way (e.g. the task of building a house). A general combinatorial task involves deciding (a) the specifications of those entities (e.g. what size, shape, material to make the bricks from), and (b) the way in which those entities are brought together (e.g. the number of bricks, and their relative positions). If the resulting combination of entities can in some way be given a FITNESS score, then COMBINATORIAL OPTIMIZATION is the task of designing a set of entities, and deciding how they must be configured, so as to give maximum fitness. cf ORDER-BASED PROBLEM. COMMA STRATEGY: Notation originally proposed in EVOLUTION STRATEGIEs, when a POPULATION of "mu" PARENTs generates "lambda" OFFSPRING and the mu parents are discarded, leving only the lambda INDIVIDUALs to compete directly. Such a process is written as a (mu,lambda) search. The process of only competing offspring then is a "comma strategy." cf. PLUS STRATEGY. CONVERGED: A GENE is said to have CONVERGED when 95% of the CHROMOSOMEs in the POPULATION all contain the same ALLELE for that gene. In some circumstances, a population can be said to have converged when all genes have converged. (However, this is not true of populations containing multiple SPECIES, for example.) Most people use "convergence" fairly loosely, to mean "the GA has stopped finding new, better solutions". Of course, if you wait long enough, the GA will *eventually* find a better solution (unless you have already found the global optimum). What people really mean is "I'm not willing to wait for the GA to find a new, better solution, because I've already waited longer than I wanted to and it hasn't improved in ages." An interesting discussion on convergence by Michael Vose can be found in GA-Digest v8n22, available from ftp.aic.nrl.navy.mil:/pub/galist/digests/v8n22 CONVERGENCE VELOCITY: The rate of error reduction. COOPERATION: The behavior of two or more INDIVIDUALs acting to increase the gains of all participating individuals. CROSSOVER: (EC) A REPRODUCTION OPERATOR which forms a new CHROMOSOME by combining parts of each of two `parent' chromosomes. The simplest form is single-point CROSSOVER, in which an arbitrary point in the chromosome is picked. All the information from PARENT A is copied from the start up to the crossover point, then all the information from parent B is copied from the crossover point to the end of the chromosome. The new chromosome thus gets the head of one parent's chromosome combined with the tail of the other. Variations exist which use more than one crossover point, or combine information from parents in other ways. (biol) A complicated process which typically takes place as follows: CHROMOSOMEs, while engaged in the production of GAMETEs, exchange portions of genetic material. The result is that an almost infinite variety of gametes may be produced. Subsequently, during sexual REPRODUCTION, male and female gametes (i.e. sperm and ova) fuse to produce a new DIPLOID cell with a pair of chromosomes. In [HOLLAND92] the sentence "When sperm and ova fuse, matching CHROMOSOMEs line up with one another and then cross over partway along their length, thus swapping genetic material" is thus wrong, since these two activities occur in different parts of the life cycle. [eds note: If sexual REPRODUCTION (the Real Thing) worked like in GAs, then Holland would be right, but as we all know, it's not the case. We just encountered a Freudian slip of a Grandmaster. BTW: even the German translation of this article has this "bug", although it's well-hidden by the translator.] CS: See CLASSIFIER SYSTEM. D DARWINISM: (biol) Theory of EVOLUTION, proposed by Darwin, that evolution comes about through random variation of heritable characteristics, coupled with natural SELECTION (survival of the fittest). A physical mechanism for this, in terms of GENEs and CHROMOSOMEs, was discovered many years later. DARWINISM was combined with the selectionism of Weismann and the genetics of Mendel to form the Neo-Darwinian Synthesis during the 1930s-1950s by T. Dobzhansky, E. Mayr, G. Simpson, R. Fisher, S. Wright, and others. The talk.origins FAQ contains more details (See Q10.7). cf LAMARCKISM. (EC) Theory which inspired all branches of EC. DECEPTION: The condition where the combination of good BUILDING BLOCKs leads to reduced FITNESS, rather than increased fitness. Proposed by [GOLD89] as a reason for the failure of GAs on many tasks. DIPLOID: (biol) This refers to a cell which contains two copies of each CHROMOSOME. The copies are homologous i.e. they contain the same GENEs in the same sequence. In many sexually reproducing SPECIES, the genes in one of the sets of chromosomes will have been inherited from the father's GAMETE (sperm), while the genes in the other set of chromosomes are from the mother's gamete (ovum). DNA: (biol) Deoxyribonucleic Acid, a double stranded macromolecule of helical structure (comparable to a spiral staircase). Both single strands are linear, unbranched nucleic acid molecules build up from alternating deoxyribose (sugar) and phosphate molecules. Each deoxyribose part is coupled to a nucleotide base, which is responsible for establishing the connection to the other strand of the DNA. The 4 nucleotide bases Adenine (A), Thymine (T), Cytosine (C) and Guanine (G) are the alphabet of the genetic information. The sequences of these bases in the DNA molecule determines the building plan of any organism. [eds note: suggested reading: James D. Watson (1968) "The Double Helix", London: Weidenfeld and Nicholson] (literature) Douglas Noel Adams, contemporary Science Fiction comedy writer. Published "The Hitch-Hiker's Guide to the Galaxy" when he was 25 years old, which made him one of the currently most successful British authors. [eds note: interestingly Watson was also 25 years old, when he discovered the DNA; both events are probably not interconnected; you might also want to look at: Neil Gaiman's (1987) "DON'T PANIC -- The Official Hitch-Hiker's Guide to the Galaxy companion", and of course get your hands on the wholly remarkable FAQ in alt.fan.douglas- adams] DNS: (biol) Desoxyribonukleinsaeure, German for DNA. (comp) The Domain Name System, a distributed database system for translating computer names (e.g. lumpi.informatik.uni- dortmund.de) into numeric Internet, i.e. IP-addresses (129.217.36.140) and vice-versa. DNS allows you to hook into the net without remembering long lists of numeric references, unless your system administrator has incorrectly set-up your site's system. E EC: See EVOLUTIONARY COMPUTATION. ELITISM: ELITISM (or an elitist strategy) is a mechanism which is employed in some EAs which ensures that the CHROMOSOMEs of the most highly fit member(s) of the POPULATION are passed on to the next GENERATION without being altered by GENETIC OPERATORs. Using elitism ensures that the mamimum FITNESS of the population can never reduce from one generation to the next. Elitism usually brings about a more rapid convergence of the population. In some applications elitism improves the chances of locating an optimal INDIVIDUAL, while in others it reduces it. ENCORE: The EvolutioNary Computation REpository Network. An network of anonymous FTP sites holding all manner of interesting things related to EC. The mirror "EClair" nodes include The Santa Fe Institute (USA): alife.santafe.edu:/pub/USER-AREA/EC/ The Chinese University of Hong Kong: ftp.cs.cuhk.hk:/pub/EC/ The University of Warwick (United Kingdom): ftp.dcs.warwick.ac.uk:/pub/mirrors/EC/ EUnet Deutschland GmbH: ftp.Germany.EU.net:/pub/research/softcomp/EC/ and The California Institute of Technology: ftp.krl.caltech.edu:/pub/EC/ See Q15.3 for more information. ENVIRONMENT: (biol) That which surrounds an organism. Can be 'physical' (abiotic), or biotic. In both, the organism occupies a NICHE which influences its FITNESS within the total ENVIRONMENT. A biotic environment may present frequency-dependent fitness functions within a POPULATION, that is, the fitness of an organism's behaviour may depend upon how many others are also doing it. Over several GENERATIONs, biotic environments may foster co-evolution, in which fitness is determined with SELECTION partly by other SPECIES. EP: See EVOLUTIONARY PROGRAMMING. EPISTASIS: (biol) A "masking" or "switching" effect among GENEs. A biology textbook says: "A gene is said to be epistatic when its presence suppresses the effect of a gene at another locus. Epistatic genes are sometimes called inhibiting genes because of their effect on other genes which are described as hypostatic." (EC) When EC researchers use the term EPISTASIS, they are generally referring to any kind of strong interaction among GENEs, not just masking effects. A possible definition is: EPISTASIS is the interaction between different GENEs in a CHROMOSOME. It is the extent to which the contribution to FITNESS of one gene depends on the values of other genes. Problems with little or no EPISTASIS are trivial to solve (hillclimbing is sufficient). But highly epistatic problems are difficult to solve, even for GAs. High epistasis means that BUILDING BLOCKs cannot form, and there will be DECEPTION. ES: See EVOLUTION STRATEGY. EVOLUTION: That process of change which is assured given a reproductive POPULATION in which there are (1) varieties of INDIVIDUALs, with some varieties being (2) heritable. See the talk.origins FAQ for further details (See Q10.7). "Don't assume that all people who accept EVOLUTION are atheists" --- Talk.origin FAQ EVOLUTION STRATEGIE: EVOLUTION STRATEGY: A type of evolutionary algorithm developed in the early 1960s in Germany. It employs real-coded parameters, and in its original form, it relied on MUTATION as the search operator, and a POPULATION size of one. Since then it has evolved to share many features with GENETIC ALGORITHMs. See Q1.3 for more information. EVOLUTIONARILY STABLE STRATEGY: A strategy that does well in a POPULATION dominated by the same strategy. (cf Maynard Smith, 1974) Or, in other words, "An 'ESS' ... is a strategy such that, if all the members of a population adopt it, no mutant strategy can invade." (Maynard Smith "Evolution and the Theory of Games", 1982). EVOLUTIONARY COMPUTATION: Encompasses methods of simulating EVOLUTION on a computer. The term is relatively new and represents an effort bring together researchers who have been working in closely related fields but following different paradigms. The field is now seen as including research in GENETIC ALGORITHMs, EVOLUTION STRATEGIEs, EVOLUTIONARY PROGRAMMING, ARTIFICIAL LIFE, and so forth. For a good overview see the editorial introduction to Vol. 1, No. 1 of "Evolutionary Computation" (MIT Press, 1993). That, along with the papers in the issue, should give you a good idea of representative research. EVOLUTIONARY PROGRAMMING: An evolutionay algorithm developed in the mid 1960s. It is a stochastic OPTIMIZATION strategy, which is similar to GENETIC ALGORITHMs, but dispenses with both "genomic" representations and with CROSSOVER as a REPRODUCTION OPERATOR. See Q1.2 for more information. EVOLUTIONARY SYSTEMS: A process or system which employs the evolutionary dynamics of REPRODUCTION, MUTATION, competition and SELECTION. The specific forms of these processes are irrelevant to a system being described as "evolutionary." EXPECTANCY: Or expected value. Pertaining to a random variable X, for a continuous random variable, the expected value is: E(X) = INTEGRAL(-inf, inf) [X f(X) dX]. The discrete expectation takes a similar form using a summation instead of an integral. EXPLOITATION: When traversing a SEARCH SPACE, EXPLOITATION is the process of using information gathered from previously visited points in the search space to determine which places might be profitable to visit next. An example is hillclimbing, which investigates adjacent points in the search space, and moves in the direction giving the greatest increase in FITNESS. Exploitation techniques are good at finding local maxima. EXPLORATION: The process of visiting entirely new regions of a SEARCH SPACE, to see if anything promising may be found there. Unlike EXPLOITATION, EXPLORATION involves leaps into the unknown. Problems which have many local maxima can sometimes only be solved by this sort of random search. F FAQ: Frequently Asked Questions. See definition given before the main table of contents. FITNESS: (biol) Loosely: adaptedness. Often measured as, and sometimes equated to, relative reproductive success. Also proportional to expected time to extinction. "The fit are those who fit their existing ENVIRONMENTs and whose descendants will fit future environments." (J. Thoday, "A Century of Darwin", 1959). Accidents of history are relevant. (EC) A value assigned to an INDIVIDUAL which reflects how well the individual solves the task in hand. A "fitness function" is used to map a CHROMOSOME to a FITNESS value. A "fitness landscape" is the hypersurface obtained by applying the fitness function to every point in the SEARCH SPACE. FUNCTION OPTIMIZATION: For a function which takes a set of N input parameters, and returns a single output value, F, FUNCTION OPTIMIZATION is the task of finding the set(s) of parameters which produce the maximum (or minimum) value of F. Function OPTIMIZATION is a type of VALUE-BASED PROBLEM. FTP: File Transfer Protocol. A system which allows the retrieval of files stored on a remote computer. Basic FTP requires a password before access can be gained to the remote computer. Anonymous FTP does not require a special password: after giving "anonymous" as the user name, any password will do (typically, you give your email address at this point). Files available by FTP are specified as : See Q15.5. FUNCTION SET: (GP) The set of operators used in GP. These functions label the internal (non-leaf) points of the parse trees that represent the programs in the POPULATION. An example FUNCTION SET might be {+, -, *}. G GA: See GENETIC ALGORITHM. GAME THEORY: A mathematical theory originally developed for human games, and generalized to human economics and military strategy, and to EVOLUTION in the theory of EVOLUTIONARILY STABLE STRATEGY. GAME THEORY comes into it's own wherever the optimum policy is not fixed, but depends upon the policy which is statistically most likely to be adopted by opponents. GAMETE: (biol) Cells which carry genetic information from their PARENTs for the purposes of sexual REPRODUCTION. In animals, male GAMETEs are called sperm, female gametes are called ova. Gametes have a HAPLOID number of CHROMOSOMEs. GAUSSIAN DISTRIBUTION: See NORMALLY DISTRIBUTED. GENE: (EC) A subsection of a CHROMOSOME which (usually) encodes the value of a single parameter. (biol) The fundamental unit of inheritance, comprising a segment of DNA that codes for one or several related functions and occupies a fixed position (locus) on CHROMOSOME. However, the term may be defined in different ways for different purposes. For a fuller story, consult a book on genetics (See Q10.7). GENE-POOL: The whole set of GENEs in a breeding POPULATION. The metaphor on which the term is based de-emphasizes the undeniable fact that genes actually go about in discrete bodies, and emphasizes the idea of genes flowing about the world like a liquid. Everybody out of the gene-pool, now! --- Author prefers to be anonymous GENERATION: (EC) An iteration of the measurement of FITNESS and the creation of a new POPULATION by means of REPRODUCTION OPERATORs. GENETIC ALGORITHM: A type of EVOLUTIONARY COMPUTATION devised by John Holland [HOLLAND92]. A model of machine learning that uses a genetic/evolutionary metaphor. Implementations typically use fixed-length character strings to represent their genetic information, together with a POPULATION of INDIVIDUALs which undergo CROSSOVER and MUTATION in order to find interesting regions of the SEARCH SPACE. See Q1.1 for more information. GENETIC DRIFT: Changes in gene/allele frequencies in a POPULATION over many GENERATIONs, resulting from chance rather than SELECTION. Occurs most rapidly in small populations. Can lead to some ALLELEs becoming `extinct', thus reducing the genetic variability in the population. GENETIC PROGRAMMING: GENETIC ALGORITHMs applied to programs. GENETIC PROGRAMMING is more expressive than fixed-length character string GAs, though GAs are likely to be more efficient for some classes of problems. See Q1.5 for more information. GENETIC OPERATOR: A search operator acting on a coding structure that is analogous to a GENOTYPE of an organism (e.g. a CHROMOSOME). GENOTYPE: The genetic composition of an organism: the information contained in the GENOME. GENOME: The entire collection of GENEs (and hence CHROMOSOMEs) possessed by an organism. GLOBAL OPTIMIZATION: The process by which a search is made for the extremum (or extrema) of a functional which, in EVOLUTIONARY COMPUTATION, corresponds to the FITNESS or error function that is used to assess the PERFORMANCE of any INDIVIDUAL. GP: See GENETIC PROGRAMMING. H HAPLOID: (biol) This refers to cell which contains a single CHROMOSOME or set of chromosomes, each consisting of a single sequence of GENEs. An example is a GAMETE. cf DIPLOID. In EC, it is usual for INDIVIDUALs to be HAPLOID. HARD SELECTION: SELECTION acts on competing INDIVIDUALs. When only the best available individuals are retained for generating future progeny, this is termed "hard selection." In contrast, "soft selection" offers a probabilistic mechanism for maitaining individuals to be PARENTs of future progeny despite possessing relatively poorer objective values. I INDIVIDUAL: A single member of a POPULATION. In EC, each INDIVIDUAL contains a CHROMOSOME (or, more generally, a GENOME) which represents a possible solution to the task being tackled, i.e. a single point in the SEARCH SPACE. Other information is usually also stored in each individual, e.g. its FITNESS. INVERSION: (EC) A REORDERING operator which works by selecting two cut points in a CHROMOSOME, and reversing the order of all the GENEs between those two points. L LAMARCKISM: Theory of EVOLUTION which preceded Darwin's. Lamarck believed that evolution came about through the inheritance of acquired characteristics. That is, the skills or physical features which an INDIVIDUAL acquires during its lifetime can be passed on to its OFFSPRING. Although Lamarckian inheritance does not take place in nature, the idea has been usefully applied by some in EC. cf DARWINISM. LCS: See LEARNING CLASSIFIER SYSTEM. LEARNING CLASSIFIER SYSTEM: A CLASSIFIER SYSTEM which "learns" how to classify its inputs. This often involves "showing" the system many examples of input patterns, and their corresponding correct outputs. See Q1.4 for more information. M MIGRATION: The transfer of (the GENEs of) an INDIVIDUAL from one SUB- POPULATION to another. MOBOT: MOBile ROBOT. cf ROBOT. MUTATION: (EC) a REPRODUCTION OPERATOR which forms a new CHROMOSOME by making (usually small) alterations to the values of GENEs in a copy of a single, PARENT chromosome. N NICHE: (biol) In natural ecosystems, there are many different ways in which animals may survive (grazing, hunting, on the ground, in trees, etc.), and each survival strategy is called an "ecological niche." SPECIES which occupy different NICHEs (e.g. one eating plants, the other eating insects) may coexist side by side without competition, in a stable way. But if two species occupying the same niche are brought into the same area, there will be competition, and eventually the weaker of the two species will be made (locally) extinct. Hence diversity of species depends on them occupying a diversity of niches (or on geographical separation). (EC) In EC, we often want to maintain diversity in the POPULATION. Sometimes a FITNESS function may be known to be multimodal, and we want to locate all the peaks. We may consider each peak in the fitness function as analogous to a NICHE. By applying techniques such as fitness sharing (Goldberg & Richardson, [ICGA87]), the population can be prevented from converging on a single peak, and instead stable SUB-POPULATIONs form at each peak. This is analogous to different SPECIES occupying different niches. See also SPECIES, SPECIATION. NORMALLY DISTRIBUTED: A random variable is NORMALLY DISTRIBUTED if its density function is described as f(x) = 1/sqrt(2*pi*sqr(sigma)) * exp(-0.5*(x-mu)*(x- mu)/sqr(sigma)) where mu is the mean of the random variable x and sigma is the STANDARD DEVIATION. O OBJECT VARIABLES: Parameters that are directly involved in assessing the relative worth of an INDIVIDUAL. OFFSPRING: An INDIVIDUAL generated by any process of REPRODUCTION. OPTIMIZATION: The process of iteratively improving the solution to a problem with respect to a specified objective function. ORDER-BASED PROBLEM: A problem where the solution must be specified in terms of an arrangement (e.g. a linear ordering) of specific items, e.g. TRAVELLING SALESMAN PROBLEM, computer process scheduling. ORDER-BASED PROBLEMs are a class of COMBINATORIAL OPTIMIZATION problems in which the entities to be combined are already determined. cf VALUE-BASED PROBLEM. ONTOGENESIS: Refers to a single organism, and means the life span of an organism from it's birth to death. cf PHYLOGENESIS. P PANMICTIC POPULATION: (EC, biol) A mixed POPULATION. A population in which any INDIVIDUAL may be mated with any other individual with a probability which depends only on FITNESS. Most conventional evolutionary algorithms have PANMICTIC POPULATIONs. The opposite is a POPULATION divided into groups known as SUB- POPULATIONs, where INDIVIDUALs may only mate with others in the same sub-population. cf SPECIATION. PARENT: An INDIVIDUAL which takes part in REPRODUCTION to generate one or more other individuals, known as OFFSPRING, or children. PERFORMANCE: cf FITNESS. PHENOTYPE: The expressed traits of an INDIVIDUAL. PHYLOGENESIS: Refers to a POPULATION of organisms. The life span of a population of organisms from pre-historic times until today. cf ONTOGENESIS. PLUS STRATEGY: Notation originally proposed in EVOLUTION STRATEGIEs, when a POPULATION of "mu" PARENTs generates "lambda" OFFSPRING and all mu and lambda INDIVIDUALs compete directly, the process is written as a (mu+lambda) search. The process of competing all parents and offspring then is a "plus strategy." cf. COMMA STRATEGY. POPULATION: A group of INDIVIDUALs which may interact together, for example by mating, producing OFFSPRING, etc. Typical POPULATION sizes in EC range from 1 (for certain EVOLUTION STRATEGIEs) to many thousands (for GENETIC PROGRAMMING). cf SUB- POPULATION. R RECOMBINATION: cf CROSSOVER. REORDERING: (EC) A REORDERING operator is a REPRODUCTION OPERATOR which changes the order of GENEs in a CHROMOSOME, with the hope of bringing related genes closer together, thereby facilitating the production of BUILDING BLOCKs. cf INVERSION. REPRODUCTION: (biol, EC) The creation of a new INDIVIDUAL from two PARENTs (sexual REPRODUCTION). Asexual reproduction is the creation of a new individual from a single parent. REPRODUCTION OPERATOR: (EC) A mechanism which influences the way in which genetic information is passed on from PARENT(s) to OFFSPRING during REPRODUCTION. REPRODUCTION OPERATORs fall into three broad categories: CROSSOVER, MUTATION and REORDERING operators. REQUISITE VARIETY: In GENETIC ALGORITHMs, when the POPULATION fails to have a "requisite variety" CROSSOVER will no longer be a useful search operator because it will have a propensity to simply regenerate the PARENTs. ROBOT: "The Encyclopedia Galactica defines a ROBOT as a mechanical apparatus designed to do the work of man. The marketing division of the Sirius Cybernetics Corporation defines a robot as `Your Plastic Pal Who's Fun To Be With'." --- Douglas Adams (1979) S SAFIER: An EVOLUTIONARY COMPUTATION FTP Repository, now defunct. Superceeded by ENCORE. SCHEMA: A pattern of GENE values in a CHROMOSOME, which may include `dont care' states. Thus in a binary chromosome, each SCHEMA (plural schemata) can be specified by a string of the same length as the chromosome, with each character one of {0, 1, #}. A particular chromosome is said to `contain' a particular schema if it matches the schema (e.g. chromosome 01101 matches schema #1#0#). The `order' of a SCHEMA is the number of non-dont-care positions specified, while the `defining length' is the distance between the furthest two non-dont-care positions. Thus #1##0# is of order 2 and defining length 3. SCHEMA THEOREM: Theorem devised by Holland [HOLLAND92] to explain the behaviour of GAs. In essence, it says that a GA gives exponentially increasing reproductive trials to above average schemata. Because each CHROMOSOME contains a great many schemata, the rate of SCHEMA processing in the POPULATION is very high, leading to a phenomenon known as implicit parallelism. This gives a GA with a population of size N a speedup by a factor of N cubed, compared to a random search. SEARCH SPACE: If the solution to a task can be represented by a set of N real- valued parameters, then the job of finding this solution can be thought of as a search in an N-dimensional space. This is referred to simply as the SEARCH SPACE. More generally, if the solution to a task can be represented using a representation scheme, R, then the search space is the set of all possible configurations which may be represented in R. SEARCH OPERATORS: Processes used to generate new INDIVIDUALs to be evaluated. SEARCH OPERATORS in GENETIC ALGORITHMs are typically based on CROSSOVER and point MUTATION. Search operators in EVOLUTION STRATEGIEs and EVOLUTIONARY PROGRAMMING typically follow from the representation of a solution and often involve Gaussian or lognormal perturbations when applied to real-valued vectors. SELECTION: The process by which some INDIVIDUALs in a POPULATION are chosen for REPRODUCTION, typically on the basis of favoring individuals with higher FITNESS. SELF-ADAPTATION: The inclusion of a mechanism not only to evolve the OBJECT VARIABLES of a solution, but simultaneously to evolve information on how each solution will generate new OFFSPRING. SIMULATION: The act of modeling a natural process. SOFT SELECTION: The mechanism which allows inferior INDIVIDUALs in a POPULATION a non-zero probability of surviving into future GENERATIONs. See HARD SELECTION. SPECIATION: (biol) The process whereby a new SPECIES comes about. The most common cause of SPECIATION is that of geographical isolation. If a SUB-POPULATION of a single species is separated geographically from the main POPULATION for a sufficiently long time, their GENEs will diverge (either due to differences in SELECTION pressures in different locations, or simply due to GENETIC DRIFT). Eventually, genetic differences will be so great that members of the sub-population must be considered as belonging to a different (and new) species. SPECIATION is very important in evolutionary biology. Small SUB- POPULATIONs can evolve much more rapidly than a large POPULATION (because genetic changes don't take long to become fixed in the population). Sometimes, this EVOLUTION will produce superior INDIVIDUALs which can outcompete, and eventually replace the SPECIES of the original, main population. (EC) Techniques analogous to geographical isolation are used in a number of GAs. Typically, the POPULATION is divided into SUB- POPULATIONs, and INDIVIDUALs are only allowed to mate with others in the same sub-population. (A small amount of MIGRATION is performed.) This produces many SUB-POPULATIONs which differ in their characteristics, and may be referred to as different "species". This technique can be useful for finding multiple solutions to a problem, or simply maintaining diversity in the SEARCH SPACE. Most biology/genetics textbooks contain information on SPECIATION. A more detailed account can be found in "Genetics, Speciation and the Founder Principle", L.V. Giddings, K.Y. Kaneshiro and W.W. Anderson (Eds.), Oxford University Press 1989. SPECIES: (biol) There is no universally-agreed firm definition of a SPECIES. A species may be roughly defined as a collection of living creatures, having similar characteristics, which can breed together to produce viable OFFSPRING similar to their PARENTs. Members of one species occupy the same ecological NICHE. (Members of different species may occupy the same, or different niches.) (EC) In EC the definition of "species" is less clear, since generally it is always possible for a pair INDIVIDUALs to breed together. It is probably safest to use this term only in the context of algorithms which employ explicit SPECIATION mechanisms. (biol) The existence of different SPECIES allows different ecological NICHEs to be exploited. Furthermore, the existence of a variety of different species itself creates new niches, thus allowing room for further species. Thus nature bootstraps itself into almost limitless complexity and diversity. Conversely, the domination of one, or a small number of SPECIES reduces the number of viable NICHEs, leads to a decline in diversity, and a reduction in the ability to cope with new situations. "Give any one species too much rope, and they'll fuck it up" --- Roger Waters, "Amused to Death", 1992 STANDARD DEVIATION: A measurement for the spread of a set of data; a measurement for the variation of a random variable. STATISTICS: Descriptive measures of data; a field of mathematics that uses probability theory to gain insight into systems' behavior. STEPSIZE: Typically, the average distance in the appropriate space between a PARENT and its OFFSPRING. STRATEGY VARIABLE: Evolvable parameters that relate the distribution of OFFSPRING from a PARENT. SUB-POPULATION: A POPULATION may be sub-divided into groups, known as SUB- POPULATIONs, where INDIVIDUALs may only mate with others in the same group. (This technique might be chosen for parallel processors). Such sub-divisions may markedly influence the evolutionary dynamics of a population (e.g. Wright's 'shifting balance' model). Sub-populations may be defined by various MIGRATION constraints: islands with limited arbitrary migration; stepping-stones with migration to neighboring islands; isolation-by-distance in which each individual mates only with near neighbors. cf PANMICTIC POPULATION, SPECIATION. SUMMERSCHOOL: (USA) One of the most interesting things in the US educational system: class work during the summer break. T TERMINAL SET: (GP) The set of terminal (leaf) nodes in the parse trees representing the programs in the POPULATION. A terminal might be a variable, such as X, a constant value, such as 42, (cf Q42) or a function taking no arguments, such as (move-north). TRAVELLING SALESMAN PROBLEM: The travelling salesperson has the task of visiting a number of clients, located in different cities. The problem to solve is: in what order should the cities be visited in order to minimise the total distance travelled (including returning home)? This is a classical example of an ORDER-BASED PROBLEM. TSP: See TRAVELLING SALESMAN PROBLEM. U USENET: "Usenet is like a herd of performing elephants with diarrhea -- massive, difficult to redirect, awe-inspiring, entertaining, and a source of mind-boggling amounts of excrement when you least expect it." --- Gene Spafford (1992) V VALUE-BASED PROBLEM: A problem where the solution must be specified in terms of a set of real-valued parameters. FUNCTION OPTIMIZATION problems are of this type. cf SEARCH SPACE, ORDER-BASED PROBLEM. VECTOR OPTIMIZATION: Typically, an OPTIMIZATION problem wherein multiple objectives must be satisfied. Z ZEN NAVIGATION: A methodology with tremendous propensity to get lost during a hike from A to B. ZEN NAVIGATION simply consists in finding something that looks as if it knew where it is going to and follow it. The results are more often surprising than successful, but it's usually being worth for the sake of the few occasions when it is both. Sometimes ZEN NAVIGATION is referred to as "doing scientific research," where A is a state of mind being considered as pre- PhD, and B (usually a different) state of mind, known as post- PhD. While your time spent in state C, somewhere inbetween A and B, is usually referred to as "being a nobody." ACKNOWLEDGMENTS Finally, credit where credit is due. I'd like to thank all the people who helped in assembling this guide, and their patience with my "variations on English grammar". In the order I received their contributions, thanks to: Contributors, Lutz Prechelt (University of Karlsruhe) the comp.ai.neural-nets FAQmeister, for letting me strip several ideas from "his" FAQ. Ritesh "peace" Bansal (CMU) for lots of comments and references. David Beasley (University of Wales) for a valuable list of publications (Q12), and many further additions. David Corne, Peter Ross, and Hsiao-Lan Fang (University of Edinburgh) for their TIMETABLING and JSSP entries. Mark Kantrowitz (CMU) for mocking about this-and-that, and being a "mostly valuable" source concerning FAQ maintenance; parts of Q11 have been stripped from "his" ai- faq/part4 FAQ; Mark also contributed the less verbose archive server infos. The texts of Q1.1, Q1.5, Q98 and some entries of Q99 are courtesy by James Rice (Stanford University), stripped from his genetic-programming FAQ (Q15). Jonathan I. Kamens (MIT) provided infos on how-to-hook-into the USENET FAQ system. Una Smith (Yale University) contributed the better parts of the Internet resources guide (Q15.5). Daniel Polani (Gutenberg University, Mainz) "contributed" the ALIFE II Video proceedings info. Jim McCoy (University of Texas) reminded me of the GP archive he maintains (Q20). Ron Goldthwaite (UC Davis) added definitions of Environment, EVOLUTION, Fitness, and Population to the glossary, and some thoughts why Biologists should take note of EC (Q3). Joachim Geidel (University of Karlsruhe) sent a diff of the current "navy server" contents and the software survey, pointing to "missing links" (Q20). Richard Dawkins "Glossary" section of "The extended phenotype" served for many new entries, too numerous to mention here (Q99). Mark Davis (New Mexico State University) wrote the part on EVOLUTIONARY PROGRAMMING (Q1.2). Dan Abell (University of Maryland) contributed the section on efficient greycoding (Q21). Walter Harms (University of Oldenburg) commented on introductory EC literature. Lieutenant Colonel J.S. Robertson (USMA, West Point), for providing a home for this subversive posting on their FTP server euler.math.usma.edu/pub/misc/GA Rosie O'Neill for suggesting the PhD thesis entry (Q10.11). Charlie Pearce (University of Nottingham) for critical remarks concerning "tables"; well, here they are! J. Ribeiro Filho (University College London) for the pointer to the IEEE Computer GA Software Survey; the PeGAsuS description (Q20) was stripped from it. Paul Harrald for the entry on game playing (Q2). Laurence Moran (Uni Toronto) for corrections to some of the biological information in Q1 and Q99. Marco Dorigo (Uni Libre Bruxelles) gets the award for reading the guide more thoroughly than (including the editors). He suggested additions to Q1.4, Q2, Q4 and Q22, and pointed out various typos. Reviewers, Robert Elliott Smith (The University of Alabama) reviewed the TCGA infos (Q14), and Nici Schraudolph (UCSD) first unconsciously, later consciously, provided about 97% of Q20* answers. Nicheal Lynn Cramer (BBN) adjusted my historic view of GP genesis. David Fogel (ORINCON) commented and helped on this-and-that (where this-and-that is closely related to EP), and provided many missing entries for the glossary (Q99). Kazuhiro M. Saito (MIT) and Mark D. Smucker (Iowa State) caught my favorite typo(s). Craig W. Reynolds was the first who solved one of the well-hidden puzzles in the FAQ, and also added some valuable stuff. Joachim Born (TU Berlin) updated the EVOLUTION Machine (EM) entry and provided the pointer to the Bionics technical report FTP site (Q14). Pattie Maes (MIT Media Lab) reviewed the ALIFE IV additions to the list of conferences (Q12). Scott D. Yelich (Santa Fe Institute) reviewed the SFI connectivity entry (Q15). Rick Riolo (MERIT) reviewed the CFS-C entry (Q20). Davika Seunarine (Acadia Univ.) for smoothing out this and that. Paul Field (Queen Mary and Westfield College) for correcting typos, and providing insights into the blindfold pogo-sticking nomads of the Himalayas. and Everybody... Last not least I'd like to thank Hans-Paul Schwefel, Thomas Baeck, Frank Kursawe, Guenter Rudolph for their contributions, and the rest of the Systems Analysis Research Group for wholly remarkable patience and almost incredible unflappability during my various extravangances and ego-trips during my time (1990-1993) with this group. It was a tremendously worthwhile experience. Thanks! --- The Editor, Joerg Heitkoetter (1993) "And all our yesterdays have lighted fools; the way to dusty death; out, out brief candle; life's but a walking shadow; a poor player; that struts and gets his hour upon the stage; and then is heared no more; it is a tale; told by an idiot, full of sound an fury, signifying nothing." --- Shakespeare, Macbeth EPILOGUE "Natural SELECTION is a mechanism for generating an exceedingly high degree of improbability." --- Sir Ronald Aylmer Fisher (1890-1962) This is a GREAT quotation, it sounds like something directly out of a turn of the century Douglas Adams: Natural SELECTION: the original "Infinite Improbability Drive" --- Craig Reynolds, on reading the previous quote `The Babel fish,' said The Hitch Hiker's Guide to the Galaxy quietly, `is small, yellow and leech-like, and probably the oddest thing in the Universe. It feeds on brainwave energy received not from his own carrier but from those around it. It absorbs all unconscious mental frequencies from this brainwave energy to nourish itself with. It then excretes into the mind of its carrier a telepathic matrix formed by combining the conscious thought frequencies with nerve signals picked up from the speech centers of the brain which has supplied them. The practical upshot of all this is that if you stick a Babel fish in your ear you can instantly understand anything said to you in any form of language. The speech patterns you actually hear decode the brainwave matrix which has been fed into your mind by your Babel fish. `Now it is such a bizarrely improbable coincidence than anything so mindbogglingly useful could have evolved purely by chance that some thinkers have chosen to see it as a final and clinching proof of the non-existence of God. `The argument goes something like this: ``I refuse to prove that I exist,'' says God, ``for proof denies faith, and without faith I am nothing.'' ``But,'' says Man, ``The Babel fish is a dead giveaway isn't it? It could not have evolved by chance. It proves you exist, and so therefore, by your own arguments, you don't. QED.'' ``Oh dear,'' says God, ``I hadn't thought of that,'' and promptly vanishes in a puff of logic. ``Oh, that was easy,'' says Man, and for an encore goes on to prove that black is white and gets himself killed on the next zebra crossing. --- Douglas Adams (1979) "Well, people; I really wish this thingie to turn into a paper babel- fish for all those young ape-descended organic life forms on this crazy planet, who don't have any clue about what's going on in this exciting "new" research field, called EVOLUTIONARY COMPUTATION. However, this is just a start, I need your help to increase the usefulness of this guide, especially its readability for natively English speaking folks; whatever it is: I'd like to hear from you...!" --- The Editor, Joerg Heitkoetter (1993) "Parents of young organic life forms should be warned, that paper babel-fishes can be harmful, if stuck too deep into the ear." --- Encyclopedia Galactica ABOUT THE EDITORS Joerg Heitkoetter, was born in 1965 in Recklinghausen, a small but beautiful 750 year old town at the northern rim of the Ruhrgebiet, Germany's coal and steal belt. He was educated at Hittorf-Gymnasium, Recklinghausen, Ruhruniversitaet Bochum (RUB) and Universitaet Dortmund (UNIDO), where he read theoretical medicine, biology, philosophy and (for whatever reason) computer sciences. He volunteered as a RA in the Biomathematics Research Group from 1987 to 1989, at the former ``Max-Planck-Institute for Nutrition Physiology,'' in Dortmund (since March 1, 1993 renamed to ``MPI for Molecular Physiology''), and spent 3 years at the ``Systems Analysis Research Group,'' at the Department of Computer Science of UniDO, where he wrote a particularly unsuccesful thesis on LEARNING CLASSIFIER SYSTEMs, In 1995 he finally gave up trying to break Chris Langton's semester record, and dropped out of university. He nonetheless became the head of EUnet Deutschland GmbH's Fun & Games division, currently working on adaptive agents that intelligently search and compile content over the 'net, and many more things. His electronic publications range from a voluntary job as senior editor of the FAQ in Usenet's comp.ai.genetic newsgroup, entitled The Hitch-Hiker's Guide to Evolutionary Computation, over many other projects he helped bootstrapping, for example Howard Gutowitz' FAQ on Cellular Automata, available on USENET via comp.theory.cell-automata, to about a dozen of so-called ``multimediagrams'' written in HTML, the language that builds the World-Wide Web. The most useful ones being ENCORE, the EVOLUTIONARY COMPUTATION Repository Network that today, after 2 years of weekend hacking, is accessible world-wide. And the latest additions Zooland, the definite collection of pointers to ARTIFICIAL LIFE resources on the 'net; Mindland an evolving anti- thesis to Marvin Minsky's marvellously erroneous book The Society of Mind. And Webland a KISS model of the Internet at large, including ``guided tours'' across the myriads of info-bits out there. With Adam Gaffin, a former senior newspaper reporter from Middlesex News, Boston, MA, who is now with Networks World, he edited the most read book on Internet, that was launched by a joined venture of Mitch Kapor's Electronic Frontier Foundation (EFF) and the Apple Computer Library, initially called Big Dummy's Guide to the Internet it was later renamed to EFF's (Extended) Guide to the Internet: A round trip through Global Networks, Life in Cyberspace, and Everything... If you want to find it, just fire up Netscape and select About the Internet from the Directory menu...there you go! Since a very special event, he has severe problems to take life seriously, and consequently started signing everything with ``-joke,'' while developing a liquid fixation on all flavours of whiskey. He continues to work on a diary-like lyrics collection of questionable content, entitled A Pocketful of Eloquence, with the parts Tears of Ink (1986), Epitaph to a Broken Dream (1989, 1990). ...with the Eyes of a Child (1991), Telltale Songs from a Rumblefish (1993), The Last Bohemian's Rhapsody... (1993, 1994), Script from a Jester's Travels... (1994, 1995) already finished and the last piece Monolith (1995) in its final stage. He still lacks a publisher for the book, though. He likes Mickey Rourke's movies (especially Rumblefish), English poetry of medieval times, especially Edmund Spenser, McDonald's Hamburgers, diving into the analysis of complex systems of any kind, (but prefers the long-legged ones) and the books by Erasmus of Rotterdam, Robert Sheckley, Alexei Panshin, and, you name it, Douglas Adams. He has a strong aversion against people who abuse their superior intellect to manipulate others. And suffers from something he calls ``my personal Mother Theresa syndrome,'' which eventually cast him into the role of a guiding light for a whole bunch of menthally weak characters. (So, if you need a helping hand, that won't let you down, drop him a line. His office is open 24 hours a day. 7 days a week.) Due to all these circumstances he leads a life on the edge, is usually single, has no time to get married, would love to have children, but has none (he'd know of), and still doesn't live in Surrey. NOTABLE WRITINGS Tuschetraenen, (1986) unpublished. Epitaph to a Broken Dream, (1989, 1990) unpublished. ...with the Eyes of a Child: Another Pilgrimage into the casualties of Life, (1991) unpublished. Telltale Songs from a Rumblefish, (1992, 1993) published on USENET in rec.arts.poetry. A Pocketful of Eloquence, (1993) unpublished. With Adam Gaffin: The Texinfo edition of Big Dummy's Guide to the Internet: A round trip through Global Networks, Life in Cyberspace, and Everything... (1993) available via anonymous FTP from ftp.eff.org:/pub/Net_info/Big_Dummy/big-dummys-guide-texi ; or in Europe try ftp.germany.eu.net:/pub/books/big-dummys-guide/big-dummys- guide-texi . David Beasley, was born in London, England in 1961. He was educated at Southampton University where he read (for good reasons) Electronic Engineering. After spending several years at sea, he went to the Department of Computing Mathematics of the University of Wales, Cardiff, where he studied ARTIFICIAL INTELLIGENCE for a year. He then went on to write a thesis on GAs applied to Digital Signal Processing, and tried to break Joke's publications record. Since a very special event, he has taken over writing this FAQ, and consequently started signing everything with ``The FAQmaster'' (He's had severe problems taking life seriously for some time before that, however.) He likes Woody Allen's movies, English clothing of medieval times, especially Marks and Spencer, hates McDonald's Hamburgers, but occasionally dives into the analysis of complex systems of any kind, (but prefers those with pedals and handlebars) and the books by (of course) Douglas Adams. He is not married, has no children, and also also doesn't live in Surrey. He now works for a (mostly interesting) software company, Praxis ( http://www.praxis.co.uk ) in Bath, England. NOTABLE WRITINGS A number of publications related to GENETIC ALGORITHMs. The most notable ones being: A Sequential Niche Technique for Multimodal Function Optimization, Evolutionary Computation, 1(2) pp 101-125, 1993. Available from ralph.cs.cf.ac.uk:/pub/papers/GAs/seq_niche.ps Reducing Epistasis in Combinatorial Problems by Expansive Coding, in S. Forrest (ed), Proceedings of the Fifth International Conference on Genetic Algorithms, Morgan-Kaufmann, pp 400-407, 1993. Available from ralph.cs.cf.ac.uk:/pub/papers/GAs/expansive_coding.ps An Overview of Genetic Algorithms: Part 1, Fundamentals, University Computing, 15(2) pp 58-69, 1993. Alailable from ENCORE (See Q15.3) in file: GA/papers/over93.ps.gz or from ralph.cs.cf.ac.uk:/pub/papers/GAs/ga_overview1.ps An Overview of Genetic Algorithms: Part 2, Research Topics, University Computing, 15(4) pp 170-181, 1993. Available from ENCORE (See Q15.3) in file: GA/papers/over93-2.ps.gz or from ralph.cs.cf.ac.uk:/pub/papers/GAs/ga_overview2.ps THAT'S ALL FOLKS! ------------------------------ Copyright (c) 1993-1995 by J. Heitkoetter and D. Beasley, all rights reserved. This FAQ may be posted to any USENET newsgroup, on-line service, or BBS as long as it is posted in its entirety and includes this copyright statement. This FAQ may not be distributed for financial gain. This FAQ may not be included in commercial collections or compilations without express permission from the author. End of ai-faq/genetic/part6 *************************** --