Path: senator-bedfellow.mit.edu!enterpoop.mit.edu!gatech!howland.reston.ans.net!spool.mu.edu!uunet!mcsun!Germany.EU.net!Informatik.Uni-Dortmund.DE!lusty!heitkoet From: joke@ls11.informatik.uni-dortmund.de (Joerg Heitkoetter) Newsgroups: comp.ai.genetic Subject: FAQ: genetic-faq/part3 (A Guide to Frequently Asked Questions) Followup-To: unido.test Date: 21 Jun 1993 16:10:04 GMT Organization: CS Department, University of Dortmund, Germany Lines: 1597 Expires: 4 Aug 1993 16:09:55 GMT Message-ID: References: NNTP-Posting-Host: lusty.informatik.uni-dortmund.de Summary: This is part 3 of a triology entitled "The Hitch-Hiker's Guide to Evolutionary Computation". A monthly published list of Frequently Asked Questions (and their answers) about Evolutionary Algorithms, Life and Everything. It should be read by anyone who whishes to post to the comp.ai.genetic newsgroup, preferably *before* posting. Originator: joke@ls11.informatik.uni-dortmund.de (Joerg Heitkoetter) Archive-name: genetic-faq/part3 Last-Modified: 06/20/93 Version: 0.03j FAQ(3/3) ANSWERS FAQ(3/3) [eds note: This is a preliminary version, ie. a "proposal", of the forthcoming FAQ to comp.ai.genetic. If you want to contribute new items, make corrections, or want to fill in a "[..]" template, drop me a mail.] A20) Available EA software packages? [eds note: the following is a reformatted and slightly expanded version of a survey that, until recently, was maintained by Nici Schraudolph. Nici and I agreed to incorporate the file into this FAQ and he will no longer maintain his original version; instead he will send all further updates he receives to me, and replace his file with a pointer to this FAQ, so there will be only ONE version of this survey in the future.] "As part of the workshop on Software Support and Test Functions at the 4th International Conference on Genetic Algorithms (ICGA) I began to solicit and collect information about available GA software packages. Having received a surprising number of responses, I feel that the following is a fairly comprehensive picture of what's out there at this time. Additions and corrections are of course welcome and may make it into future updates of this file. Many thanks to all the informants, including - but not limited to - the authors/contacts listed below. Special thanks to Jose Ribeiro Filho, Cesare Alippi and Philip Treleaven, whose survey article "Genetic Algorithm Programming Environments" (to appear) was an invaluable source of information. The descriptions of PC/Beagle, XpertRule GenAsys, Omega and EnGENEer are adapted from that article with their kind permission." --- Nici Schraudolph , San Diego, 07/09/92 ## PLEASE NOTE: ########################################################## # # # For many of these software packages, specific ordering instructions # # are given in the descriptions below. Please read and follow them # # before unnecessarily bothering the listed author or contact! Also # # note that I haven't tested any of these programs (with the exception # # the one I administer), so I can't give any comments or recommenda- # # tions regarding their quality. # # # ########################################################################## Legend Type (this is a very ad-hoc classification) GE: generational GA SS: steady-state GA ES: evol. strategy OO: object-oriented XP: expert system ED: educational/demo CF: classifier system Version 0.03j Posted: 20 June 1993 1 FAQ(3/3) ANSWERS FAQ(3/3) OS Operating System: X11 implies Unix; "Win" = Microsoft Windows 3.x (PC) Lang Programming Language; in parentheses: source code not included; TPas = "Think Pascal" Price (1) free to government contractors, $221 otherwise (2) 69 pounds sterling for educational use (3) educational discount available (4) available as addendum to a book Author or Contact given as Internet e-mail address if possible Name Type OS Lang Price Author or Contact ----------------------------------------------------------------------- GA GE, DOS (C++) free Mark Hughes Workbench ED Splicer GE Mac, C (1) Steve Bayer X11 Evolution GE, DOS C free Joachim Born Machine ES Genie GE Mac TPas free Lance Chambers GAGA GE Unix C free Jon Crowcroft GAucsd GE Unix C free Nici Schraudolph GENOCOP, GE Unix C free Zbigniew Michalewicz WOLF SS Mac, C $20/ David Rogers Unix free GAC GE Unix C free Bill Spears GAL " Lisp " ESCaPaDE ES Unix C free Frank Hoffmeister mGA1.0 GE Lisp free SGA-C " Unix C " Robert E. Smith SGA-Cube " nCube " " Version 0.03j Posted: 20 June 1993 2 FAQ(3/3) ANSWERS FAQ(3/3) BUGS GE, X11, C free Joshua Smith ED Suntools PARA- GENESIS GE CM C* free Michael van Lent Genitor SS Unix C free Darrell Whitley OOGA OO Lisp $60/ Lawrence Davis and GENESIS GE DOS C both John Grefenstette GENEsYs GE Unix C free Thomas Baeck SCS-C CF Unix C free Joerg Heitkoetter ED DOS Atari TOS CFS-C CF DOS C free Rick Riolo ED Unix Commercial Packages: EnGENEer OO X11 C ? George Robbins Logica Cambridge Ltd. Evolver GE DOS, (C, $345 Phil Rybeck, Axcelis Inc. Mac Pascal) XpertRule GenAsys XP DOS ? ? Attar Software PC/Beagle XP DOS ? (2) Richard Forsyth Omega ? DOS ? ? David Barrow, KiQ Ltd. MicroGA OO Mac, C++ $249 Emergent Behavior, Inc. Win (3) Under Development: GAME OO X11 C++ (4) Jose R. Filho XYpe SS Mac (C) $725 Ed Swartz, Virtual Image Inc. DGENESIS GE Unix C free Erick Cantu Version 0.03j Posted: 20 June 1993 3 FAQ(3/3) ANSWERS FAQ(3/3) A20.1) Free software packages? 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 (WSMR-SIMTEL20.Army.Mil) as pd1:gaw110.zip or free on 5.25'' disk by request from: Mark Hughes Cambridge Consultants Ltd. The Science Park, Milton Road Cambridge CB4 4DW, UK Net: Splicer: Splicer is a genetic algorithm tool that can be used to solve search and optimization problems, created by the Software Technology Branch (STB) of the Information Systems Directorate at NASA/Johnson Space Center with support from the MITRE Corporation. Splicer was written in C on an Apple Macintosh, then ported to Unix workstations running X11; it has a modular architecture with well-defined interfaces between a GA kernel, representation libraries, fitness modules, and user interface libraries. The representation libraries contain functions for defining, creating, and decoding genetic strings, as well as multiple crossover and mutation operators. Libraries supporting binary strings and permutations are provided, others can be created by the user. Fitness modules are typically written by the user, although some sample applications are provided. The modules may contain a fitness function, initial values for various control parameters, and a function which graphically displays the best solutions. Splicer provides event-driven graphic user interface libraries for the Macintosh and the X11 window system (using the HP widget set); a menu-driven ASCII interface is also available though not fully supported. The extensive documentation includes a reference manual and a user's manual; an architecture manual and the advanced programmer's manual are currently being written. An electronic bulletin board (300/1200/2400 baud, 8N1) with information regarding Splicer can be reached at (713) 280-3896 or Version 0.03j Posted: 20 June 1993 4 FAQ(3/3) ANSWERS FAQ(3/3) (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 Tel: (404) 542-3265 Evolution Machine: The "Evolution Machine" (EM) is a collection of evolutionary algorithms (Genetic Algorithms and Evolution Strategies) within a common framework. It runs on PCs under MS-DOS and includes extensive menu techniques. EM is available by anonymous ftp from ftp-bionik.fb10.tu-berlin.de (130.149.192.50) in the "pub/software/Evolution-Machine" directory, which contains the ARJ 2.10 archive files em_tc.exe (EM for Turbo C), em_tcp.exe (EM for Turbo C++) and em_man.exe (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 archive files (660 kB). We welcome bug reports, comments and suggestions, but have only limited manpower for providing help, patches and new releases. We are making EM available in order to encourage the experimental use of evolutionary algorithms, and to get feedback as to its strengths and weaknesses. Joachim Born Technical University Berlin Bionics and Evolution Techniques Laboratory Bio- and Neuroinformatics Research Group Ackerstrasse 71-76 (ACK1) D-13355 Berlin, Germany Net: Tel: +49 30-314-72-677 Genie: Genie is a GA-based modelling/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 arguements 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 Version 0.03j Posted: 20 June 1993 5 FAQ(3/3) ANSWERS FAQ(3/3) 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: GAGA: GAGA (GA for General Application) is a self-contained, re-entrant procedure which is suitable for the minimisation of many "difficult" cost functions. Originally written in Pascal by Ian Poole, it was rewritten in C by Jon Crowcroft. GAGA can be obtained by request from the author; given sufficient interest it will be made available via anonymous ftp. GAucsd: GAucsd is a GENESIS-based GA package incorporating numerous bug fixes and user interface improvements. Major additions include a wrapper that simplifies the writing of evaluation functions, a facility to distribute experiments over networks of machines, and Dynamic Parameter Encoding, a technique that improves GA performance in continuous search spaces by adaptively refining the genomic representation of real-valued parameters. GAucsd was written in C for Unix systems, but the central GA engine is easily ported to other platforms. The entire package can be ported to systems where implementations of the Unix utilities "make", "awk" and "sh" are available. GAucsd can be obtained via anonymous ftp from cs.ucsd.edu (132.239.51.3), file "pub/GAucsd/GAucsd14.sh.Z", or via mail server - send an EMPTY message with the subject line containing "send GAucsd source" to nici@cs.ucsd.edu. Requests to be added to a mailing list for dissemination of GAucsd bug reports, patches and updates should be directed to the same address. GENOCOP, Genetic-2, Genetic-2N: These three genetic optimization packages are available as compressed tar files via anonymous ftp from unccsun.uncc.edu (152.15.10.88), directory "coe/evol". They have been developed by Zbigniew Michalewicz and are described in detail in his recent book "Genetic Algorithms + Data Structures = Evolution Programs" (Springer Verlag, August 1992). GENOCOP (GEnetic algorithm for Numerical Optimization for COnstrained Problems) optimizes a function with any number of linear constraints Version 0.03j Posted: 20 June 1993 6 FAQ(3/3) ANSWERS FAQ(3/3) (equalities and inequalities). Genetic-2 is an optimization package for the linear transportation problem; Genetic-2N for the nonlinear one. WOLF: This is a simulator for the G/SPLINES (genetic spline models) algorithm which builds spline-based functional models of experimental data, using crossover and mutation to evolve a population towards a better fit. It is derived from Friedman's MARS models. The original work was presented at ICGA-4, and further results including additional basis function types such as B-splines have been presented at the NIPS-91 meeting. Available at no cost via anonymous FTP by contacting the author; runs on SUN (and possibly any SYSV) UNIX box. Macintosh version available on floppy disk for a $20 fee. Both versions can be redistributed for noncommercial use. Simulator includes executable and C source code; a technical report (RIACS tech report 91.10) is also available. David Rogers MS Ellis, NASA Ames Research Center Moffett Field, CA 94035, USA Net: GAC, GAL: For those of you interested in obtaining some free GA software, I'm providing the packages I've been using for a few years. GAC is a GA written in C. GAL is my Common Lisp version. They are similar in spirit to John Grefenstette's Genesis, but they don't have all the nice bells and whistles. Both versions currently run on Sun workstations. If you have something else, you might need to do a little modification. [Alan Schultz informs me that GAL is easily ported to the Mac - although his version is no longer available.] In the spirit of "freeware", I am willing to e-mail either version (or both) to anyone who wants it. All I ask is that I be credited when it is appropriate. Also, I would appreciate hearing about improvements! This software is the property of the Department of the Navy. The code will be in a "shar" format that will be easy to install. This code is "as is", however. There is a README and some documentation in the code. There is NO user's guide, though (nor am I planning on writing one at this time). I am interested in hearing about bugs, but I may not get around to fixing them for a while. Also, I will be unable to answer many questions about the code, or about GAs in general. This is not due to a lack of interest, but due to a lack of free time! --- Bill Spears Version 0.03j Posted: 20 June 1993 7 FAQ(3/3) ANSWERS FAQ(3/3) ESCaPaDE: ESCaPaDE is a sophisticated software environment to run experiments with Evolutionary Algorithms, such as e.g. an Evolution Strategy. Future versions of the software will provide a well-defined interface to any kind of Evolutionary Algorithm, for instance Genetic Algorithms. The main support for experimental work is provided by two internal tables: o a table of objective functions and o a table of so-called data monitors, which allow easy implementation of functions for monitoring all types of information inside the Evolutionary Algorithm under experiment. ESCaPaDE 1.2 comes with the KORR implementation of the Evolution Strategy by H.-P. Schwefel which offers simple and correlated mutations. KORR is provided as a FORTRAN 77 subroutine, and its cross-compiled C version is used internally by ESCaPaDE. ESCaPaDE 1.2 will be available by e-mail request in order to track the spread of the software as this is its first public release. An extended version of the package was used for several investigations so far and has proven to be very reliable. The software and its documentation is fully copyrighted although it may be freely used for scientific work; it requires 5-6 MB of disk space. In order to obtain ESCaPaDE via mail request, please send a message to the e-mail address below. The SUBJECT line should contain the request 'help' or 'get ESCaPaDE'. (If the subject line does not match a predefined set of mail requests the mail handler will NOT recognize your request!) For more information contact: Frank Hoffmeister Systems Analysis Research Group, LSXI Department of Computer Science University of Dortmund D-44221 Dortmund, Germany Net: Fax: +49 231 755-2450 mGA1.0, SGA-C, SGA-Cube: mGA1.0 is a Common Lisp implementation of a messy GA as described in TCGA report No. 90004. Messy GAs overcome the linkage problem of simple genetic algorithms by combining variable-length strings, gene expression, messy operators, and a nonhomogeneous phasing of evolutionary processing. Results on a number of difficult deceptive Version 0.03j Posted: 20 June 1993 8 FAQ(3/3) ANSWERS FAQ(3/3) test functions have been encouraging with the messy GA always finding global optima in a polynomial number of function evaluations. See TCGA reports 89003, 90005, 90006, and 91004 for more information on messy GAs; they can be obtained from the address below. Please note that 91004 is a dissertation and requires a pre-payment of $9.00 US ($12.00 US to ship overseas) to offset the cost of copying, binding and shipping. SGA-C is a C-language translation and extension of the original Pascal SGA code presented in Goldberg's book "Genetic Algorithms in Search, Optimization & Machine Learning" (Addison Wesley 1989). It has some additional features, but its operation is essentially the same as that of the Pascal version. SGA-C is described in TCGA report No. 91002, which is included in the distribution as a PostScript file. SGA-Cube is a C-language translation of Goldberg's SGA code with modifications to allow execution on the nCUBE 2 Hypercube Parallel Computer. When run on the nCUBE 2, SGA-Cube can take advantage of the hypercube architecture, and is scalable to any hypercube dimension. The hypercube implementation is modular, so that the algorithm for exploiting parallel processors can be easily modified. In addition to its parallel capabilities, SGA-Cube can be compiled on various serial computers via compile-time options. In fact, when compiled on a serial computer, SGA-Cube is essentially identical to SGA-C. SGA-Cube has been nominally tested on a Sun 4/70 workstation, a VAX Ultrix system, a Cray X-MP/24 running UNICOS 5.1, and the nCUBE 2. It is described in TCGA report No. 91005, which is included in the distribution as a PostScript file. Each of these programs is distributed in form of a Unix shar file, available via e-mail or on various formatted media by request from: Robert Elliott Smith Department of Engineering of Mechanics Room 210 Hardaway Hall The University of Alabama P.O. Box 870278 Tuscaloosa, Alabama 35487, USA Net: Tel: (205) 348-1618 Fax: (205) 348-6419 SGA-C and SGA-Cube are also available in compressed tar form via anonymous ftp from the GA-List archive server ftp.aic.nrl.navy.mil (192.26.18.56) in the "pub/galist/source-code/ga-source" directory. Version 0.03j Posted: 20 June 1993 9 FAQ(3/3) ANSWERS FAQ(3/3) BUGS: BUGS (Better to Use Genetic Systems) is an interactive program for demonstrating the Genetic Algorithm and is written in the spirit of Richard Dawkins' celebrated Blind Watchmaker software. The user can play god (or `GA fitness function,' more accurately) and try to evolve lifelike organisms (curves). Playing with BUGS is an easy way to get an understanding of how and why the GA works. In addition to demonstrating the basic genetic operators (selection, crossover, and mutation), it allows users to easily see and understand phenomena such as genetic drift and premature convergence. BUGS is written in C and runs under Suntools and X Windows. BUGS was written by Joshua Smith at Williams College and is available via anonymous ftp from santafe.edu, directory pub/misc/BUGS. Note that it is unsupported software, copyrighted but freely distributable. PARAGENESIS: "I spent this past summer at the Naval Research Lab working with Ken Dejong and John Grefenstette to implement John Grefenstette's GENESIS on the CM-200 in C*. The result, which I've been calling PARAGENESIS, is an attempt to improve performance as much as possible without changing the behavior of the genetic algorithm. Unlike the 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 seperate processor allowing initialization, evaluation and mutation to be completely parallel. The costs of global control and communication in selection and crossover are present but minimized as much as possible. In general PARAGENESIS on an 8k CM-200 seems to run 10-100 times faster than GENESIS on a Sparc 2 and finds equivalent solutions. The solutions are not identical only because the parallel random number generator gives a different stream of numbers. PARAGENESIS includes all the features of serial GENESIS plus some additions. The additions include the ability to collect timing statistics, probabilistic selection(as opposed to Baker's stochastic universal sampling), uniform crossover and local or neighborhood selection. Anyone familiar with the serial implementation of GENESIS and C* should have little problem using PARAGENESIS. PARAGENESIS is available via anonymous ftp from the GA-List archive at ftp.aic.nrl.navy.mil (192.26.18.74). The compressed and tar-ed code is found in the file /pub/galist/src/ga/paragenesis.tar.Z. DISCLAIMER: PARAGENESIS is fairly untested at this point and may contain some bugs. I will try to fix any reported bugs as my schedule and my access to the CM allows." Version 0.03j Posted: 20 June 1993 10 FAQ(3/3) ANSWERS FAQ(3/3) Michael van Lent Computer Science Dept. University of Tennessee Knoxville TN 37996-1301, USA Net: 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 modelling. (cf Q20) GENEsYs: GENEsYs is a GENESIS-based GA implementation which includes extensions and new features for experimental purposes, such as selection schemes like linear ranking, Boltzmann, (mu, lambda)-selection, and general extinctive selection variants, crossover operators like n-point and uniform crossover as well as discrete and intermediate recombination. Self-adaptation of mutation rates is also possible. A set of objective functions is provided, including De Jong's functions, complicated continuous functions, a TSP-problem, binary functions, and a fractal function. There are also additional data- monitoring facilities such as recording average, variance and skew of object variables and mutation rates, or creating bitmap-dumps of the population. GENEsYs 1.0 is available via ftp from lumpi.informatik.uni- dortmund.de (129.217.36.140). Log on with user name "ftp" and give your full e-mail address as password. The file GENEsYs-1.0.tar.Z in directory "pub/GA/src" contains the complete software distribution; the documentation alone is available as GENEsYs-1.0-doc.tar.Z in the same location. For more information contact: Thomas Baeck Systems Analysis Research Group, LSXI Department of Computer Science University of Dortmund D-44221 Dortmund, Germany Net: Fax: +49 231 755-2450 SCS-C: SCS-C is a (`mostly ANSI') C language translation and extension of Goldberg's Simple Classifier System, as presented in Appendix D in his seminal book "Genetic Algorithms in Search, Optimization, and Machine Learning", Addison-Wesley, Reading, MA, 1989. Version 0.03j Posted: 20 June 1993 11 FAQ(3/3) ANSWERS FAQ(3/3) SCS-C has been developed in parallel on a Sun 10/30 and an ATARI ST, and thus should be quite portable; it's distributed free of charge and the other terms of the GPL, ie. the GNU General Public License. SCS-C v0.98j is available via ftp from lumpi.informatik.uni- dortmund.de (129.217.36.140). Log on with user name "ftp" and give your full e-mail address as password. The file scs-c-0.98j.tar.Z in directory "pub/LCS/src" contains the complete software distribution; the documentation alone is available as scs-c-doc.tar.Z in directory "pub/LCS/docs". For more information contact: Joerg Heitkoetter Systems Analysis Research Group, LSXI Department of Computer Science University of Dortmund D-44221 Dortmund, Germany Net: Fax: +49 231 755-2450 CFS-C: CFS-C is a domain independent collection of classifier system routines written by Rick L. Riolo as part of his PhD dissertation. [eds note: it's simply the state-of-the-art implementation concerning CFS] CFS-C is available by anonymous ftp to um.cc.umich.edu (35.1.1.43) in the directory "LBTS:" (including the colon). FTP-HOW-TO tells how to get started. The file cfsc1.tar.z contains everything (ignore all the other files). Publications on CFS-C include: 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. Version 0.03j Posted: 20 June 1993 12 FAQ(3/3) ANSWERS FAQ(3/3) A20.2) Commercial software packages? [preliminary] OOGA, GENESIS: OOGA (Object-Oriented GA) is a genetic algorithm designed for industrial use. It includes examples accompanying the tutorial in the companion "Handbook of Genetic Algorithms". OOGA is designed such that each of the techniques employed by a GA is an object that may be modified, displayed or replaced in object-oriented fashion. OOGA is especially well-suited for individuals wishing to modify the basic GA techniques or tailor them to new domains. The buyer of OOGA also receives GENESIS, a generational GA system written by John Grefenstette. As the first widely available GA program GENESIS has been very influential in stimulating the use of GAs, and several other GA packages are based on it. This release sports an improved user interface. OOGA and GENESIS are available together on 3.5'' or 5.25'' disk for $60 ($52.50 inside North America) by order from: T.S.P. P.O. Box 991 Melrose, MA 02176, USA 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 on-line help system) and can be defined either "on the fly" or loaded from audit files which are automatically created during a GA run. Version 0.03j Posted: 20 June 1993 13 FAQ(3/3) ANSWERS FAQ(3/3) 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 71 6379111 Fax: +44 223 322315 Evolver: Evolver is a spreadsheet add-in which incorporates the first commercially available genetic algorithm to search for solutions. Evolver can be customized through the macro language, and is available for $345 on 3.5'' or 5.25'' floppies for the Excel, WingZ and Resolve spreadsheets on the Mac and PC computers. For further information, contact: Axcelis, Inc. 4668 Eastern Avenue North Seattle, WA 98103-6932, USA Tel: (206) 632-0885 To order Evolver, contact: Spreadware Distributors P.O. Box 4552 Palm Desert, CA 92261, USA Tel: (619) 347-2365 Fax: (619) 347-6045 Version 0.03j Posted: 20 June 1993 14 FAQ(3/3) ANSWERS FAQ(3/3) XpertRule GenAsys: XpertRule GenAsys is an expert system shell with embedded genetic algorithms 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 Fax: +44 942 601991 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 59 Cranbrook Rd Bristol BS6 7BS, UK Tel: +44 272 428692 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 modelling, validation sample tests, advanced confidence tests, real time graphics, and optional control over the internal GA. Version 0.03j Posted: 20 June 1993 15 FAQ(3/3) ANSWERS FAQ(3/3) For further information, contact: KiQ Business Modelling Systems Ltd. Attn David Barrow Managing Director, UK Tel: +44 371 870254 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. For further information and orders, contact: Steve Wilson Emergent Behavior 635 Wellsbury Way Palo Alto, CA 94306, USA Net: Tel: (415) 494-6763 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: Version 0.03j Posted: 20 June 1993 16 FAQ(3/3) ANSWERS FAQ(3/3) Ed Swartz Virtual Image, Inc. 75 Sandy Pond Road #11 Ayer, MA 01432, USA Tel: (508) 772-4225 GAME: GAME (GA Manipulation Environment) aims to demonstrate GA applications and build a suitable programming environment. Currently in the early development stage, the programming environment will comprise a graphic interface (using X-Windows), a library of parameterized algorithms and applications, a specialized high level language based on C++, and compilers to various workstations and parallel machines. 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). DGENESIS: Based on GENESIS 5.0, this project at ITAM (Mexico) aims to implement a distributed GA on a network of workstations. For more information, contact Erick Cantu . A20.3) Current research projects? PAPAGENA: The European ESPRIT III project PAPAGENA is pleased to announce the availability of the following book and software: Parallel Genetic Algorithms: Theory and Applications was recently published by IOS press. The book, edited by Joachim Stender, provides an overview of the theoretical, as well as practical, aspects involved in the study and implementation of parallel genetic algorithms (PGAs). The book comes with a floppy disk version of GAME (Gentic Algorithm Manipulation Environment). The disk contains the C++ source code for the sequential version the the GAME Virtual Machine. Also two simple demonstration examples are included (an analytical function and a TSP) to illustrate the use of the VM. Code is provided for both UNIX and MS-DOS. GAME provides a general purpose toolkit for the programming and simulation of a wide range of GA and PGA algorithms and applications. The GAME environment is being upgraded to include graphical monitoring tools, and to allow for abitrary levels of addressing for GA manipulation (ie., populations can be broken down into arbitrary substructutes beyond individuals, chromosomes, and genes, with Version 0.03j Posted: 20 June 1993 17 FAQ(3/3) ANSWERS FAQ(3/3) biological operators acting at all levels). New releases will be announced later in the year. The table of contents for "PGAs: Theory and Applications" is as follows: 1. Introduction and Historical Background J. Stender and C.J.A. Chisholm 2. Foundations and Theoretical Issues M. Dorigo and V. Maniezzo Parallel Genetic Algorithms: Introduction and Overview of Current Research 3. Implementation I. East, D. Macfarlane Implementation in Occam of Parallel Genetic Algorithms on Transputer Networks 4. GAME - a Genetic Algorithms Manpulation Environment J. Ribeiro Filho et al. Genetic Algorithm Programming Environments J. Kingdon et al. The GAME Programming Environment Architecture L. Dekker and J. Ribeiro Filho The GAME Virtual Machine Architecture J. Ribeiro Filho GAME's Library Structure 5. Appliacations J. Stender et al. Priciple-Based Engineering and Economic Modeling S. Schulze-Kremer. Genetic Algorithms for Protein Tertiary Structure Prediction B. Kroger et al. Parallel Genetic Packing on Transputers J. Paul et al. Applications of Neural Networks and Genetic Algorithms in the Diagnosis of Cancer, Anorexia Nervosa and AIDS. For more information contact: Jose' Luiz Ribeiro Filho Department of Computer Science University College London Version 0.03j Posted: 20 June 1993 18 FAQ(3/3) ANSWERS FAQ(3/3) Gower Street London WC1E 6BT, UK Net: Tel: +44 (071) 387 7050 x 3701 Fax: +44 (071) 387 1397 A42) 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. A98) Any patents on EAs? Process patents have been issued both for the Bucket Brigade Algorithm (BBA) in classifier systems: U.S. patent #[..] (to John Holland) and for GP: U.S. patent #4,935,877 (to John Koza). This FAQ does not attempt to provide legal advice. However, use of the Lisp code in the book [KOZA92] is freely licensed for academic use. Although those wishing to make commercial use of any process should obviously consult any patent holders in question, it is pretty clear that it's not in anyone's best interests to stifle GA/GP research and/or development. Commericial licenses much like those used for CAD software can presumably be obtained for the use of these processes where necessary. There are currently no known patents for other EA paradigms; but there is a periodic posting on comp.ai.neural-nets by Gregory Aharonian about patents on Artificial Neural Networks (ANNs). A99) A Glossary on EAs? A Artificial Life, Alife Term coined by Christopher G. Langton for his 1987 [ALIFEI] Version 0.03j Posted: 20 June 1993 19 FAQ(3/3) GLOSSARY FAQ(3/3) conference. In the preface of the proceedings he defines Alife as "...the study of simple computer generated hypothetical life forms, ie. life-as-it-could-be." C Crossover The genetic process by which genetic material is exchanged between individuals in the population. D DNA Desoxyribonucleic 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 desoxyribose (sugar) and phosphate molecules. Each desoxyribose part is coupled to a nucleotid base, which is reponsible 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] D.N.A. 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 The Domain Name System, a distributed database system for translating computer names (eg. lumpi.informatik.uni- dortmund.de) into numeric Internet, ie. 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 Environment [..] Exploitation [..] Exploration [..] Version 0.03j Posted: 20 June 1993 20 FAQ(3/3) GLOSSARY FAQ(3/3) Evolution [..] F Fitness [..] 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 Generation An iteration of the measurement of fitness and the creation of a new population by means of genetic operations. Genetic Algorithm, GA Model of machine learning that uses a genetic/evolutionary metaphor. Implementations typically use fixed-length character strings to represent their genetic information. Genetic Operator [..] Genetic Programming, GP 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. M Mobot MOBile roBOT (-> Robot) O Ontogenesis Refers to a single organism, and means the time span of an organism from it's birth to death. (-> Phylogenesis) P Performance [..] Phylogenesis refers to a population of organisms. The time span of a population of organisms from pre-historic times until today. (-> Ontogenesis) Population Version 0.03j Posted: 20 June 1993 21 FAQ(3/3) GLOSSARY FAQ(3/3) [..] R Recombination (-> Crossover) Reproduction The genetic operation which causes an exact copy of the genetic representation of an individual to be made in the population. Reproduction, Asexual [..] Reproduction, Sexual [..] Robot "The Encyclopedia Galactica defines a robot as a mechanical apparatur 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'." --- Doglas Adams (1985) S Search Operator [..] Selection [..] 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, (-> Q42) or a function taking no arguments, such as (move-north). 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) ACKNOWLEDGEMENTS 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 Version 0.03j Posted: 20 June 1993 22 FAQ(3/3) GLOSSARY FAQ(3/3) "variations on English grammar". In the order I received their contributions, thanks to: Contributers 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), David Corne, Peter Ross, and Hsiao-Lan Fang (University of Edinburgh) for their TIMETABLING and JSSP entries, Mark Kantrowitz (CMU) for mocking about this-and-that, and being a "mostly valuable" source concerning FAQ maintenance; parts of A11 have been stripped from "his" ai-faq/part4 FAQ; Mark also contributed the less verbose ARCHIVE SERVER infos. The texts of A1.1, A1.5, A98 and some entries of A99 are courtesy by James Rice (Stanford University), stripped from his genetic-programming FAQ (cf Q15). Jonathan I. Kamens (MIT) provided infos on how-to-hook-into the USENET FAQ system. Daniel Polani (Gutenberg University, Mainz) "contributed" the Alife II Video proceedings info. Reviewers and Robert Elliott Smith (The University of Alabama) reviewed the TCGA infos (Q14), and Nici Schraudolph (UCSD) unconsciously provided about 97% of Q20* answers. Nicheal Lynn Cramer (BBN) adjusted my historic view of GP genesis. David Fogel (ORINCON) commented and helped on this-and-that (where this-and-that is closely related to EP). Kazuhiro M. Saito (MIT) catched one of my favourite typo(s). Everybody... Last not least I'd like to thank Hans-Paul Schwefel, Thomas Baeck and the rest of the Systems Analysis Research Group for wholly remarkable patience and almost incredible unflappability during my various extravangances and ego-trips over the past years. Thanks! EPILOGUE "Natural selection is a mechanism for Use of uninitialized value in concatenation (.) or string at E:\listplex\SYSTEM\SCRIPTS\filearea.cgi line 455, line 1620. generating an exceedingly high degree of improbability." --- Sir Ronald Aylmer Fisher (1890-1962) "`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 formedby combining the conscious thought Version 0.03j Posted: 20 June 1993 23 FAQ(3/3) EPILOGUE FAQ(3/3) frequencies with nerve signals picked up from the speech centres 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 (1985) "Well, people; I really wish this thingie to turn into a paper babel- fish for all those young ape-descendent organic life forms, 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...!" --- 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 Version 0.03j Posted: 20 June 1993 24 -- -joke -- Joerg Heitkoetter | "Don't ask what the FAQ Systems Analysis Group | can do for you, University of Dortmund, Germany | but what you can do (joke@ls11.informatik.uni-dortmund.de). | for the FAQ."