ftp.pasteur.org/FAQ/

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

/ ftp.pasteur.org/FAQ/ / ftp-pasteur-org-FAQ.zip / FAQ / ai-faq / genetic / part1 next >

Wrap

Internet Message Format | 2001-04-12 | 24.0 KB

Path: senator-bedfellow.mit.edu!bloom-beacon.mit.edu!howland.erols.net!newspharm.inet.tele.dk.MISMATCH!news.tele.dk!195.224.53.60!nntp.news.xara.net!xara.net!gxn.net!server6.netnews.ja.net!server4.netnews.ja.net!fafnir.cf.ac.uk!scmdb From: David.Beasley@cs.cf.ac.uk (David Beasley) Newsgroups: comp.ai.genetic,comp.answers,news.answers Subject: FAQ: comp.ai.genetic part 1/6 (A Guide to Frequently Asked Questions) Supersedes: <part1_969480833@cs.cf.ac.uk> Followup-To: comp.ai.genetic Date: 11 Apr 2001 20:23:07 GMT Organization: Posted through the Joint Cardiff Computing Service, Wales, UK Lines: 526 Approved: news-answers-request@MIT.Edu Expires: 25 May 2001 20:22:54 GMT Message-ID: <part1_987020574@cs.cf.ac.uk> References: <NEWS_987020574@cs.cf.ac.uk> NNTP-Posting-Host: thrall.cs.cf.ac.uk X-Trace: fafnir.cf.ac.uk 987020587 25694 131.251.42.22 (11 Apr 2001 20:23:07 GMT) X-Complaints-To: abuse@cf.ac.uk NNTP-Posting-Date: 11 Apr 2001 20:23:07 GMT Summary: This is part 1 of a <trilogy> 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: scmdb@thrall.cs.cf.ac.uk Xref: senator-bedfellow.mit.edu comp.ai.genetic:21403 comp.answers:44992 news.answers:205228 Archive-name: ai-faq/genetic/part1 Last-Modified: 4/12/01 Issue: 9.1 Important note: Do NOT send email to the cs.cf.ac.uk address above: it will be ignored. Corrections and other correspondence should be sent to david.beasley@iee.org The Hitch-Hiker's Guide to Evolutionary Computation (FAQ for comp.ai.genetic) edited by Joerg Heitkoetter UUnet Deutschland GmbH Sebrathweg 20 D-44149 Dortmund, Germany <joke@de.uu.net> or <joke@santafe.edu> and David Beasley ingenta ltd BUCS Building, University of Bath, Bath, United Kingdom BA2 7AY <david.beasley@iee.org> 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-2001 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. HOW TO USE THIS GUIDE 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 [xxxx99] 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: <ftp-site- name>/<the-complete-filename> 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:// WHERE TO FIND THIS GUIDE Between postings to comp.ai.genetic , this FAQ is available on the World Wide Web. Get it from any ENCORE site (See Q15.3). The following Encore sites can be accessed by HTTP. If you use the one closest to you, you should get the best speed of service. (Note, however, that some sites are not always up to date. The guide is normally issued every 3 months.) o UUnet Deutschland GmbH (Germany) (definitive location): http://surf.de.uu.net/encore/www/ o The Chinese University of Hong Kong (China): http://www.cs.cuhk.hk/pub/EC/FAQ/www/top.htm o Ecole Polytechnique (France): http://www.eark.polytechnique.fr/EC/FAQ/www/top.htm o The University of Oviedo (Spain): http://www.etsimo.uniovi.es/ftp/pub/EC/FAQ/www/ o The University of Birmingham (UK) http://www.cs.bham.ac.uk/Mirrors/ftp.de.uu.net/EC/clife/www/ o The Santa Fe Institute (USA): http://alife.santafe.edu/~joke/encore/www/ Other Encore sites can be accessed by FTP, and the FAQ can be found in the file FAQ/www/top.htm or something similar. The FAQ is also available in plain text format on Encore, and from 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 <mail- server@rtfm.mit.edu>. Send a message to the mail-server with "help" and "index" in the body on separate lines for more information. 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 in file FAQ/hhgtec.ps.gz (the plain 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 Referencing this Guide If you want to reference this guide it should look like: Heitkoetter, Joerg and Beasley, David, eds. (2001) "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 110 pages. Or simply call it "the Guide", or "HHGTEC" for acronymaniacs. 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 comp.ai.genetic? 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 comp.ai.genetic? 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 <mail-server@rtfm.mit.edu>: send usenet/news.answers/introduction send usenet/news.answers/news-newusers-intro quit Netiquette "Usenet is a convention, in every sense of the word." Although USENET is usually characterized as "an anarchy, with no laws and no one in charge" there have "emerged" several rules over the past years that shall facilitate life within newsgroups. Thus, you will probably find the following types of articles: 1. Requests Requests are articles of the form "I am looking for X" where X is something public like a book, an article, a piece of software. If multiple different answers can be expected, the person making the request should prepare to make a summary of the answers he/she got and announce to do so with a phrase like "Please e-mail, I'll summarize" at the end of the posting. The Subject line of the posting should then be something like "Request: X" 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-2000 by J. Heitkoetter and D. Beasley, all rights reserved. This FAQ may be posted to any USENET newsgroup, on-line service, or BBS as long as it is posted in its entirety and includes this copyright statement. This FAQ may not be distributed for financial gain. This FAQ may not be included in commercial collections or compilations without express permission from the author. End of ai-faq/genetic/part1 *************************** --