Article View: comp.ai.genetic
Article #3FAQ: comp.ai.genetic part 3/3 (A Guide to Frequently Asked Questions)
From: Joerg Heitkoetter
Date: Mon, 27 Dec 1993 18:06
Date: Mon, 27 Dec 1993 18:06
3115 lines
120399 bytes
120399 bytes
Archive-name: ai-faq/genetic/part3
Last-Modified: 12/20/93
Issue: 1.10
FAQ(3/3) ANSWERS FAQ(3/3)
A20) Available EA software packages?
[eds note: the following is a reformatted, alphabetised and updated
version of a survey that, until June '93, was maintained by Nici
Schraudolph. Nici and I agreed to incorporate the file into this FAQ
and he no longer maintains the original version.]
A copy of most of the packages described below are also kept at
SAFIER, the SAnta Fe Instutute's Evolutionary computation Repository,
that can be entered via anonymous FTP at sfi.santafe.edu:/pub/EC (cf
Q15.3) Check this out!
You should also be aware that most Genetic Programming software is
archived by Jim McCoy <mccoy@ccwf.cc.utexas.edu>. Available via
anonymous FTP to ftp.cc.utexas.edu:/pub/genetic-programming directory
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 <gpc@ipld01.hac.com>.
A survey paper entitled "Genetic Algorithm Programming Environments"
will be published in IEEE Computer in the february/1994 issue.
Written by J.R. Filho, C. Alippi and P. Treleaven of the University
College, London, UK, it's avail. via 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. 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
recommendations regarding their quality.
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)
Issue 1.10 Posted: 20 December 1993 1
FAQ(3/3) ANSWERS FAQ(3/3)
Lang Programming Language; in parentheses: source code not included;
"TPas" = Think Pascal, "OPas" = MPW Object 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 (5) 995 pounds sterling (6)
single 3.500 DM, site license 10.000 DM (educational dicounts)
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 <jrs@media.mit.edu>
ESCaPaDE ES Unix C free Frank Hoffmeister <hoffmeister@
ls11.informatik.uni-dortmund.de>
Evolution GE, DOS C free Hans-Michael Voigt and
Machine ES Joachim Born
<voigt@max.fb10.tu-berlin.de>
GAC, GE Unix C free Bill Spears
GAL " Lisp " <spears@aic.nrl.navy.mil>
GAGA GE Unix C free Jon Crowcroft
<jon@cs.ucl.ac.uk>
GAucsd GE Unix C free Nici Schraudolph
<nici@cs.ucsd.edu>
GA GE, DOS (C++) free Mark Hughes
Workbench ED <mrh@camcon.co.uk>
Genesis GE, Unix, C free John Grefenstette
ED DOS <gref@aic.nrl.navy.mil>
GECO GE, Unix, Lisp free George P. W. Williams, Jr.
ED etc. <george@hsvaic.boeing.com>
GENEsYs GE Unix C free Thomas Baeck <baeck@
ls11.informatik.uni-dortmund.de>
GenET GE, Unix, C free Cezary Z. Janikow
ED etc. <janikow@radom.umsl.edu>
Issue 1.10 Posted: 20 December 1993 2
FAQ(3/3) ANSWERS FAQ(3/3)
Genie GE Mac TPas free Lance Chambers
<p_stampoul@fennel.cc.uwa.oz.au>
Genitor SS Unix C free Darrell Whitley
<whitley@cs.colostate.edu>
GENOCOP, GE Unix C free Zbigniew Michalewicz
Genetic-2/N <zbyszek@unccvax.uncc.edu>
GIGA GE Unix C free Joe Culberson
<joe@cs.ualberta.ca>
LibGA GE, Unix/DOS C free Art Corcoran
SS,ED NeXT/Amiga <corcoran@penguin.mcs.utulsa.edu>
mGA1.0 GE Unix Lisp free Robert E. Smith
SGA-C/Cube " nCube C " <rob@comec4.mh.ua.edu>
PARAGENESIS GE CM C* free Michael van Lent
<vanlent@cs.utk.edu>
PeGAsuS PA, Unix, ANSI-C free Dirk Schlierkamp-Voosen
ED etc. <dirk.schlierkamp-voosen.gmd.de>
PGA PA, Unix, C free Peter Ross
ED etc. <peter@aisb.ed.ac.uk>
Splicer GE Mac, C (1) Steve Bayer
X11 <bayer@galileo.jsc.nasa.gov>
WOLF SS Mac, C $20/ David Rogers
Unix free <drogers@riacs.edu>
=========================================================================
Classifier System Implementations:
=========================================================================
Name Type OS Lang Price Author/Contact
=========================================================================
CFS-C CF, Unix/DOS C free Rick Riolo
ED <rlr@merit.edu>
SCS-C CF, Unix/DOS C free Joerg Heitkoetter
ED Atari TOS <joke@ls11.informatik.uni-dortmund.de>
==========================================================================
Issue 1.10 Posted: 20 December 1993 3
FAQ(3/3) ANSWERS FAQ(3/3)
Commercial Packages:
=========================================================================
Name Type OS Lang Price Author/Contact
=========================================================================
EnGENEer OO, X11 C ? George Robbins,
GA Logica Cambridge Ltd.
EvoFrame/ OO, Mac, C++/ (6) Optimum Software
REALizer ES Win OPas <optimum@applelink.apple.com>
Evolver GE DOS, (C, $345 Phil Rybeck, Axcelis Inc.
Mac Pascal)
GAME OO, X11 C++ (4) Jose R. Filho
GA <zeluiz@cs.ucl.ac.uk>
MicroGA/ OO, Mac, C++ $249 Emergent Behavior, Inc.
Galapagos GA Win (3) <emergent@aol.com>
Omega ? DOS ? ? David Barrow, KiQ Ltd.
OOGA/ OO, Lisp $60/ Lawrence Davis and
GENESIS GE DOS C both John Grefenstette
<gref@aic.nrl.navy.mil>
PC/Beagle XP DOS ? (2) Richard Forsyth
XpertRule/XP DOS (TPas) (5) Attar Software
GenAsys <100166.1547@CompuServe.com>
XYpe SS Mac (C) $725 Ed Swartz, Virtual Image Inc.
=========================================================================
Under Development:
=========================================================================
Name Type OS Lang Price Author/Contact
=========================================================================
DGENESIS GE Unix C free Erick Cantu
<ecantu@itamvms1.bitnet>
JAZZ-C CF Unix C free Joerg Heitkoetter
<joke@ls11.informatik.uni-dortmund.de>
=========================================================================
Issue 1.10 Posted: 20 December 1993 4
FAQ(3/3) ANSWERS FAQ(3/3)
A20.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
via anonymous ftp from santafe.edu, directory "pub/misc/BUGS". Note
that it is unsupported software, copyrighted but freely
distributable.
Joshua R. Smith
Room E15-492
MIT Media Lab
20 Ames Street
Cambridge, MA 02139
Net: <jrs@media.mit.edu>
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
Issue 1.10 Posted: 20 December 1993 5
FAQ(3/3) ANSWERS FAQ(3/3)
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: <hoffmeister@ls11.informatik.uni-dortmund.de>
Fax: +49 231 755-2450
Evolution Machine:
The "Evolution Machine" (EM) was created by Hans-Michael Voigt,
Joachim Born and Jens Treptow. The authors developed the EM at the
Institute for Informatics and Computing Techniques of Berlin. At
present, Hans-Michael Voigt and Joachim Born are at the Technical
University of Berlin.
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).
Issue 1.10 Posted: 20 December 1993 6
FAQ(3/3) ANSWERS FAQ(3/3)
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 anonymous ftp from ftp-
bionik.fb10.tu-berlin.de (130.149.192.50) in the
"pub/software/Evolution-Machine" directory, which contains the
compressed files em_tc.exe (EM for Turbo C), em_tcp.exe (EM for Turbo
C++) and em_man.exe (the manual). Additionally, it exists the file
em-man.ps.Z (PostScript file of the manual, generated with the
standard Unix compress(1) program).
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).
We welcome bug reports, comments and sugestions, 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.
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>
Tel: +49 30-314-72-677
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.
Issue 1.10 Posted: 20 December 1993 7
FAQ(3/3) ANSWERS FAQ(3/3)
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 <spears@aic.nrl.navy.mil>
p.s.: We have also set up an anonymous FTP site:
ftp.aic.nrl.navy.mil. GAC, GAL, and 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; given sufficient interest it will be made available via
anonymous ftp.
Jon Crowcroft
Univeristy College London
Gower Street
London WCIE 6BT, UK
Net: <jon@cs.ucl.ac.uk>
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.
Nicol N. Schraudolph
The SALK Institute
Issue 1.10 Posted: 20 December 1993 8
FAQ(3/3) ANSWERS FAQ(3/3)
San Diego, La Jolla, CA, USA
Net: <nici@salk.edu>
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, as the WSMR-
SIMTEL20.Army.Mil site was closed down in October 93. Look for
"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: <mrh@camcon.co.uk>
GECO:
Genetic Evolution through Combination of Objects (GECO), version 2.0.
GECO 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(tm) file, and some simple examples are also provided to
illustrate its intended use.
GECO Version 2.00 is now available via anonymous ftp from
ftp.aic.nrl.navy.mil, in files "/pub/galist/src/ga/GECO-v2.0.tar.Z"
(Unix) or "/pub/galist/src/ga/GECO-v2.0.cpt.hqx" (Macintosh).
George P. W. Williams, Jr.
1334 Columbus City Rd.
Scottsboro, AL 35768
Net: <george@hsvaic.hv.boeing.com>
Tel: +1 (205) 461-2950
Fax: +1 (205) 461-2286
Issue 1.10 Posted: 20 December 1993 9
FAQ(3/3) ANSWERS FAQ(3/3)
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: <baeck@ls11.informatik.uni-dortmund.de>
Fax: +49 231 755-2450
GenET:
GenET Version 1.00 is now available via anonymous ftp from
radom.umsl.edu, as "/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.
GenET is a "generic" GA package. It is not generic in the normal
sense, which usually implies some standard (binary) representation
and its operators. 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. This
speeds up problem-specific GA applications by about 95% for
Issue 1.10 Posted: 20 December 1993 10
FAQ(3/3) ANSWERS FAQ(3/3)
researchers w/o extensive GA libraries and about 50% for those with
complete good libraries. The package provides some libraries of
representations and operators. The user can either create new
rep/opers, use the existing, or implement rep/operators along with
the problem. Problem is implemented by specifying only the
evaluation and initialization. Representations are defined by
functions to allocate storage and display CHROMOSOMEs. etc. All such
interfaces have standard definitions.
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 FP 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. This example nicely illustrates the power of the
generic mechanism for adapting the operators, which nicely allocates
the resources (high probabilities) to those operators that currently
show the best promise. 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 me evaluations
(especially bugs) and suggestions for future versions. Have fun.
Cezary Z. Janikow
Department of Math and CS, CCB319
St. Louis, MO 63121
Net: <janikow@radom.umsl.edu>
Tel: +1 (314) 553-6352
Fax: +1 (314) 553-5400
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
Issue 1.10 Posted: 20 December 1993 11
FAQ(3/3) ANSWERS FAQ(3/3)
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: <p_stampoul@fennel.cc.uwa.oz.au>
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, 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.
Thank you for your interest and good luck in searching your
hyperspace."
To receive GENITOR via anonymous ftp from Colorado State University
Computer Science Department follow these steps:
1. % mkdir Genitor
2. % cd Genitor
3. % ftp 129.82.102.183
4. <login:> anonymous
5. <password:> {your e-mail address for our information}
6. ftp> cd pub
7. ftp> binary
8. ftp> get GENITOR.tar
9. ftp> bye
The GENITOR.tar file is in tar format and can be restored in the
current directory using the following commands.
Issue 1.10 Posted: 20 December 1993 12
FAQ(3/3) ANSWERS FAQ(3/3)
10. % tar -xvf GENITOR.tar .
Note to SPARC-2 users: There is something strange about unix on on
sparc-2s. REMOVE the libraries /Genitor/lib/ga/libcsu***.a before
attempting to rebuild them for your machine. Somehow, the file is
not completely overwitten on this operating system. -- T.
Starkweather
Please direct all comments and questions to
<mathiask@cs.colostate.edu>. If these fail to work, contact:
L. Darrell Whitley
Dept. of Computer Science
Colorado State University
Fort Collins, CO 80523, USA
Net: <whitley@cs.colostate.edu>
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
(equalities and inequalities). Genetic-2 is an optimization package
for the linear transportation problem; Genetic-2N for the nonlinear
one.
Zbigniew Michalewicz
Dept. of Computer Science
University of North Carolina
Chappel-Hill, NC, USA
Net: <zbyszek@mosaic.uncc.edu>
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 [1].
References
[1] Genetic Invariance: A New Paradigm for GENETIC ALGORITHM Design
University of Alberta Technical Report TR92-02, June 1992
Issue 1.10 Posted: 20 December 1993 13
FAQ(3/3) ANSWERS FAQ(3/3)
[2] GIGA Program Description and Operation University of Alberta
Computing Science Technical Report TR92-06, June 1992
These can be obtained, along with the program, via anon. ftp to
ftp.cs.ualberta.ca in "pub/TechReports" in the subdirectories TR92-02
and TR92-06.
Alternatively, if you have gopher, try:
gopher gopher.cs.ualberta.ca
And follow the links to University of Alberta Technical Reports.
Joe Culberson
Department of Computer Science
University of Alberta, CA
Net: <joe@cs.ualberta.ca>
Tel: (403) 492-5401
LibGA:
LibGA Version 1.00 is now available via anonymous ftp from
ftp.aic.nrl.navy.mil, in the file "/pub/galist/src/ga/libga100.tar.Z"
or by email request to its author.
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 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.
I realize this is "yet another GA", but I hope it proves useful.
Art Corcoran
Net: <corcoran@penguin.mcs.utulsa.edu>
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
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
Issue 1.10 Posted: 20 December 1993 14
FAQ(3/3) ANSWERS FAQ(3/3)
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: <rob@comec4.mh.ua.edu>
Tel: +1 (205) 348-1618
Fax: +1 (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.
PARAGENESIS:
"I spent this past summer at the Naval Research Lab working with Ken
De Jong 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
Issue 1.10 Posted: 20 December 1993 15
FAQ(3/3) ANSWERS FAQ(3/3)
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. 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."
Michael van Lent
Computer Science Dept.
University of Tennessee
Knoxville TN 37996-1301, USA
Net: <vanlent@cs.utk.edu>
PeGAsuS:
PeGAsuS is a Programming Environment for Parallel Genetic
Algorithms developed at the German National Research Center for
Computer Science. In fact, it is a tool kit which can be used The
environment is written in ANSI-C and is available for many
different UNIX-based machines. It runs on MIMD parallel machines,
such as transputers, and distributed systems.
The User Interface consists of three parts: the PeGAsuS script
language, a graphical interface and a user library. The user library
has the same functionality of the PeGAsuS GA library. It allows the
user to define application specific functions that are not
provided by the system library. The script language is used to
specify the experiment. The user can use it to define the
application dependent data structures, attaches the genetic
operators to them and specifies the input/output interface.
Whereas the script language specifies the construction of a sub-
Issue 1.10 Posted: 20 December 1993 16
FAQ(3/3) ANSWERS FAQ(3/3)
population, The the execution order of the genetic operators,
manage communication between different processes and provide
input/output facilities. They build general frames for
simulating GAs, and can be considered as autonomous processes.
They interpret the PeGAsuS script, create appropriate data
structures, and describe the order of the frame functions. A "frame"
function controls the execution a base function. They prepare the
data representing the genetic material, and apply the genetic
operators to it, according to the script specification. 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 for Currently, PeGAsuS can be
compiled with the GNU C, RS/6000 C, ACE-C, and Alliant's FX/2800 C
compilers. It runs on SUN s and RS/6000 workstations, as well as on
the Alliant FX/28.
For more information contact:
Dirk Schlierkamp-Voosen
Research Group for Adative Systems
German National Research Center for
Computer Science
53731 Sankt Augustin, Germany
Net: <dirk.schlierkamp-voosen@gmd.de>
Tel: +49 2241 14 2466
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
consists of:
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
and it's easy to add your own problems (see below). CHROMOSOMEs are
represented as character arrays, so you are not (quite) stuck with
bit-string problem encodings.
Issue 1.10 Posted: 20 December 1993 17
FAQ(3/3) ANSWERS FAQ(3/3)
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!
Peter Ross
Department of AI
University of Edinburgh
80 South Bridge
Edinburgh EH1 1HN, UK
Net: <peter@aisb.ed.ac.uk>
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
(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
Issue 1.10 Posted: 20 December 1993 18
FAQ(3/3) ANSWERS FAQ(3/3)
Net: <bayer@galileo.jsc.nasa.gov>
Tel: +1 (404) 542-3265
Fax: +1 (706) 542-4807
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: <drogers@riacs.edu>
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; the CFS-C 2.0
mentioned in [SAB90] (e.g. "latent learning") will not be released;
instead an ANSIfied version of 1.0 (CFS-C 1.98j) is available from
SAFIER and the SyS ftp server.
CFS-C is available from SAFIER as:
sfi.santafe.edu:/pub/EC/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/CFS/src/cfsc-1.98j.tar.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.
Issue 1.10 Posted: 20 December 1993 19
FAQ(3/3) ANSWERS FAQ(3/3)
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 "Genetic Algorithms in Search, Optimization, and
Machine Learning", Addison-Wesley, Reading, MA, 1989.
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
and the other terms of the GPL, i.e. the GNU General Public License.
SCS-C v0.99j will be made 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.99j.tar.gz in directory "pub/LCS/src" contains the complete
software distribution; the documentation alone is available as scs-c-
doc.tar.gz 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: <joke@ls11.informatik.uni-dortmund.de>
Fax: +49 231 755-2450
A20.2) Commercial software packages?
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.
Issue 1.10 Posted: 20 December 1993 20
FAQ(3/3) ANSWERS FAQ(3/3)
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
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
Issue 1.10 Posted: 20 December 1993 21
FAQ(3/3) ANSWERS FAQ(3/3)
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:
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.
.PP For further information, current prices and orders, contact:
Wolfram Stebel
Optimum Software
Braunfelser Str. 26
35578 Wetzlar, Germany
Net: <optimum@applelink.apple.com>
Tel: +49 6441 25325
Fax: +49 6441 24818
Issue 1.10 Posted: 20 December 1993 22
FAQ(3/3) ANSWERS FAQ(3/3)
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
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 see the
directories under "papagena", e.g. "papagena/game/docs" contains all
the papers that have been produced over the course of the GAME
project, e.g. you'll find a little bit outdated draft of the GAME
DESIGN NOTES document, which explains some of the details of the
implementation. There are some other technical reports also. The
sources can also be obtained by ftp see "papagena/game/version2.01".
GAME is now in version 2.01 (the version distributed with the book
was 1.0). This version is still able to run only sequential GAs, but
version 3.0 is coming soon and 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.
Issue 1.10 Posted: 20 December 1993 23
FAQ(3/3) ANSWERS FAQ(3/3)
Please, feel free to use and distribute the software.
For more information contact:
Jose Luiz Ribeiro Filho
Department of Computer Science
University College London
Gower Street
London WC1E 6BT, UK
Net: <zeluiz@cs.ucl.ac.uk>
Tel: +44 (071) 387 7050 x 3701
Fax: +44 (071) 387 1397
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:
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: <emergent@aol.com>
Tel: +1 (415) 494-6763
MicroGA is distributed in Germany by Optimum Software (cf EvoFrame &
REALizer entries).
Issue 1.10 Posted: 20 December 1993 24
FAQ(3/3) ANSWERS FAQ(3/3)
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
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:
The Software Partnership (T.S.P.)
P.O. Box 991
Melrose, MA 02176, USA
Tel: +1 617 662 8991
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.
Issue 1.10 Posted: 20 December 1993 25
FAQ(3/3) ANSWERS FAQ(3/3)
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
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
Net: <100166.1547@CompuServe.com>
Tel: +44 942 608844
Fax: +44 942 601991
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:
Issue 1.10 Posted: 20 December 1993 26
FAQ(3/3) ANSWERS FAQ(3/3)
Ed Swartz
Virtual Image, Inc.
75 Sandy Pond Road #11
Ayer, MA 01432, USA
Tel: +1 (508) 772-4225
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 (Genetic 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 arbitrary levels of addressing for
GA manipulation (i.e., POPULATIONs can be broken down into arbitrary
substructures beyond INDIVIDUALs, CHROMOSOMEs, and GENEs, with
biological operators acting at all levels).
For more information contact: Jose Luiz Ribeiro Filho
<zeluiz@cs.ucl.ac.uk> (please refer to the section on GAME above,
that also lists the full affiliation/address).
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 <ecantu@babbage.rhon.itam.mx>.
A21) What are Gray codes, why to use them, how to efficiently implement
them?
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
Issue 1.10 Posted: 20 December 1993 27
FAQ(3/3) ANSWERS FAQ(3/3)
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 or 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 attrributed 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.
Issue 1.10 Posted: 20 December 1993 28
FAQ(3/3) ANSWERS FAQ(3/3)
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 */
}
}
Issue 1.10 Posted: 20 December 1993 29
FAQ(3/3) ANSWERS FAQ(3/3)
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).
A42) What is Life all about?
42
References
Issue 1.10 Posted: 20 December 1993 30
FAQ(3/3) ANSWERS FAQ(3/3)
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.
A42b) Is there a FAQ to this group?
Yes.
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. Commercial 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 <srctran@world.std.com> about patents on Artificial Neural
Networks (ANNs).
A99) A Glossary on EAs?
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.
Issue 1.10 Posted: 20 December 1993 31
FAQ(3/3) GLOSSARY FAQ(3/3)
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" [GOLDBERG89] 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]
CHROMOSOME:
Issue 1.10 Posted: 20 December 1993 32
FAQ(3/3) GLOSSARY FAQ(3/3)
(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.
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.
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 whereby 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 cell with a complete set of DIPLOID
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
Issue 1.10 Posted: 20 December 1993 33
FAQ(3/3) GLOSSARY FAQ(3/3)
Freudian slip of a Grandmaster. BTW: even the German
translation of this article has this "bug", although it's
well-hidden by the translator.]
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. 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 [GOLDBERG89] as a reason for the failure of GAs on
many tasks.
DIPLOID CHROMOSOME:
(biol) A CHROMOSOME which consists of a pair of homologous
chromosomes, i.e. two chromosomes containing the same GENEs in
the same sequence. In sexually reproducing SPECIES, the genes
in one of the chromosomes will have been inherited from the
father's GAMETE (sperm), while the genes in the other chromosome
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]
Issue 1.10 Posted: 20 December 1993 34
FAQ(3/3) GLOSSARY FAQ(3/3)
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.
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.
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.
ESS: See EVOLUTIONARILY STABLE 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, of which some varieties (3)
differ in FITNESS (reproductive success).
Issue 1.10 Posted: 20 December 1993 35
FAQ(3/3) GLOSSARY FAQ(3/3)
"Don't assume that all people who accept EVOLUTION are atheists"
--- Talk.origin FAQ
EVOLUTIONARILY STABLE STRATEGY:
A strategy that does well in a POPULATION dominated by the same
strategy. (cf Maynard Smith, 1974)
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.
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
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.
FUNCTION OPTIMIZATION:
For a function which takes a set of N input parameters, and
Issue 1.10 Posted: 20 December 1993 36
FAQ(3/3) GLOSSARY FAQ(3/3)
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.
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 HAPLOID CHROMOSOMEs.
GENE:
(EC) A subsection of a CHROMOSOME which (usually) encodes the
value of a single parameter.
(biol) A unit of heredity. May be defined in different ways for
different purposes. Molecular biologists sometimes use it in a
more abstract sense. Following Williams (cf Q10.7) `any
hereditary information for which there is a favorable or
unfavorable selection bias equal to several or many times its
rate of endogenous change.' cf CHROMOSOME.
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
Issue 1.10 Posted: 20 December 1993 37
FAQ(3/3) GLOSSARY FAQ(3/3)
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.
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.
GENOME:
The entire collection of GENEs (and hence CHROMOSOMEs) possessed
by an organism.
GP: See GENETIC PROGRAMMING.
H
HAPLOID CHROMOSOME:
(biol) A CHROMOSOME consisting of a single sequence of GENEs.
These are found in GAMETEs. cf DIPLOID CHROMOSOME.
In EC, it is usual for CHROMOSOMEs to be haploid.
I
INDIVIDUAL:
A single member of a POPULATION. In EC, each INDIVIDUAL
contains a CHROMOSOME 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 an 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:
Issue 1.10 Posted: 20 December 1993 38
FAQ(3/3) GLOSSARY FAQ(3/3)
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.
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.
O
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
Issue 1.10 Posted: 20 December 1993 39
FAQ(3/3) GLOSSARY FAQ(3/3)
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.
PERFORMANCE:
cf FITNESS.
PHYLOGENESIS:
Refers to a POPULATION of organisms. The life span of a
POPULATION of organisms from pre-historic times until today. cf
ONTOGENESIS.
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
Issue 1.10 Posted: 20 December 1993 40
FAQ(3/3) GLOSSARY FAQ(3/3)
categories: CROSSOVER, MUTATION and REORDERING operators.
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
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.
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
Issue 1.10 Posted: 20 December 1993 41
FAQ(3/3) GLOSSARY FAQ(3/3)
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
Issue 1.10 Posted: 20 December 1993 42
FAQ(3/3) GLOSSARY FAQ(3/3)
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
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
Issue 1.10 Posted: 20 December 1993 43
FAQ(3/3) GLOSSARY FAQ(3/3)
of real-valued parameters. FUNCTION OPTIMIZATION problems are
of this type. cf SEARCH SPACE, ORDER-BASED PROBLEM.
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 A11 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
Issue 1.10 Posted: 20 December 1993 44
FAQ(3/3) GLOSSARY FAQ(3/3)
(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.
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). 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). And Davika Seunarine
(Acadia Univ.) for smoothing out this and that.
and Everybody...
Last not least I'd like to thank Hans-Paul Schwefel, Thomas Baeck,
Frank Kursawe, Guenter Rudolph for their respective 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!
"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."
Issue 1.10 Posted: 20 December 1993 45
FAQ(3/3) GLOSSARY FAQ(3/3)
--- 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
Issue 1.10 Posted: 20 December 1993 46
FAQ(3/3) EPILOGUE FAQ(3/3)
you...!"
--- The Editor
"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
Issue 1.10 Posted: 20 December 1993 47
--
-joke
--
Joerg Heitkoetter
Systems Analysis Group "Why was I born with such
University of Dortmund, Germany contemporaries?"
<joke@ls11.informatik.uni-dortmund.de> -- Oscar Wilde
Technical Details
Message-ID:
<part3_757015572@lusty.informatik.uni-dortmund.de>Path:
arc1-ca.pugleaf.net!bloom-beacon.mit.edu!gatech!swrinde!cs.utexas.edu!uunet!Germany.EU.net!Informatik.Uni-Dortmund.DE!home!heitkoetReferences:
<part2_757015572@lusty.informatik.uni-dortmund.de>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!bloom-beacon.mit.edu!gatech!swrinde!cs.utexas.edu!uunet!Germany.EU.net!Informatik.Uni-Dortmund.DE!home!heitkoet
From: joke@ls11.informatik.uni-dortmund.de (Joerg Heitkoetter)
Newsgroups: comp.ai.genetic,comp.answers,news.answers
Subject: FAQ: comp.ai.genetic part 3/3 (A Guide to Frequently Asked Questions)
Supersedes: <part3_753815849@lusty.informatik.uni-dortmund.de>
Followup-To: comp.ai.genetic
Date: 27 Dec 1993 18:06:24 GMT
Organization: CS Department, University of Dortmund, Germany
Lines: 3115
Approved: news-answers-request@MIT.Edu
Message-ID: <part3_757015572@lusty.informatik.uni-dortmund.de>
References: <part2_757015572@lusty.informatik.uni-dortmund.de>
NNTP-Posting-Host: home.informatik.uni-dortmund.de
Summary: This is part 3 of a trilogy entitled "The Hitch-Hiker's Guide
to Evolutionary Computation". A monthly published list of Frequently
Asked Questions (and their answers) about Evolutionary Algorithms,
Life and Everything. It should be read by anyone who whishes to post
to the comp.ai.genetic newsgroup, preferably *before* posting.
Originator: joke@ls11.informatik.uni-dortmund.de (Joerg Heitkoetter)