What's new in the FAQ?
David Beasley
Issue: 9.1
Hello, and welcome to the new edition of the comp.ai.genetic FAQ,
"The Hitch-Hiker's Guide to Evolutionary Computation".
As usual, here's a description of the differences in content between
this and the previous version. There are no major changes. Details of
minor changes are given below.
The last edition was posted on September 20 2000. There was no December
edition. The next edition is due out on June 20th, 2001. Every second
monday, a reminder is posted to comp.ai.genetic and telling people how
to pick up copies on the net.
As always, if you have information which could usefully go into the
guide, send it to me at the address below. (NOTE: Do NOT send any
email to the cs.cf.ac.uk address: it will be ignored.) Please include
in the Subject line: HHGTEC. If you find any information is
inaccurate, please let me know (if possible, with the _accurate_
information). All contributions/help welcome.
If you have any questions which you'd like to be answered in the FAQ,
post them to the newsgroup first. If any sensible answers are
forthcoming, let me know, and I'll include the information in the FAQ.
The ASCII version of the FAQ comes in 6 parts, with the following broad
categories:
1. Intro to the FAQ and the newsgroup 24k
2. Descriptions of different types of EAs 56k
3. Practice and theory 55k
4. References and information sources 81k
5. EA software packages 93k
6. Other topics and glossary 74k
CHANGES
Q1.4 Added link to Alwyn Barry's site on Learning Classifier Systems (thanks
to Tim Kovacs)
Q2 Added the Framsticks Alife project (thanks to Maciej Komosinski)
Q4 Added link to page on Memetic Algorithms (thanks to Pablo Moscato)
Q4.1 Updated FTP address for Larry Yaegers Polyworld (thanks to
Tim Tyler)
Q5 Updated reference to the Linear-Programming-FAQ (thanks to John Gregory)
Q10.2 Added book: "Intelligence through Simulated Evolution: Forty Years of
Evolutionary Programming"
Q10.8 Added details of the Learning Classifier System Bibliography (thanks to
Tim Kovacs)
Q15.2 Added details of a Classifier Systems mailing list. (thanks to Tim Kovacs)
Q20 Ease - updated URL (thanks to Joe Sprave)
Q20.2 Added new Commercial GA package: optiGA
Q22 Fixed typo in heading (thanks to Albert Rogers).
AVAILABILITY
The HTML version is available from various places, including:
Germany: EUnet Deutschland GmbH:
http://surf.de.uu.net/encore/www/
Spain: The University of Oviedo:
http://www.etsimo.uniovi.es/ftp/pub/EC/FAQ/www/
UK: The University of Birmingham
http://www.cs.bham.ac.uk/Mirrors/ftp.de.uu.net/EC/clife/www/
USA: The Santa Fe Institute:
http://alife.santafe.edu/~joke/encore/www/
Hong Kong: The Chinese University of Hong Kong:
http://www.cs.cuhk.hk/pub/EC/FAQ/www/top.htm
David Beasley, Bath, UK __o
david....@iee.org \<,
-comp.ai.genetic FAQ Editor- ___________________()/ ()___
--
David Beasley
Last-Modified: 4/12/01
Issue: 9.1
Important note: Do NOT send email to the cs.cf.ac.uk address above: it will
be ignored. Corrections and other correspondence should be sent to
david....@iee.org
The
Hitch-Hiker's
Guide to
Evolutionary Computation
(FAQ for comp.ai.genetic)
edited by
Joerg Heitkoetter
UUnet Deutschland GmbH
Sebrathweg 20
D-44149 Dortmund, Germany
<jo...@de.uu.net>
or <jo...@santafe.edu>
and
David Beasley
ingenta ltd
BUCS Building,
University of Bath,
Bath, United Kingdom BA2 7AY
<david....@iee.org>
PLEASE:
Search this document first if you have a question
and
If someone posts a question to the newsgroup which is answered in here
DON'T POST THE ANSWER TO THE NEWSGROUP:
POINT THE ASKER TO THIS FAQ
and finally
DON'T PANIC!
Copyright (c) 1993-2001 by Joerg Heitkoetter and David Beasley, all
rights reserved.
This FAQ may be posted to any USENET newsgroup, on-line service, or
BBS as long as it is posted in its entirety and includes this
copyright statement. This FAQ may not be distributed for financial
gain. This FAQ may not be included in commercial collections or
compilations without express permission from the author.
FAQ /F-A-Q/ or /fak/ [USENET] n. 1. A Frequently Asked Question.
2. A compendium of accumulated lore, posted periodically to
high-volume newsgroups in an attempt to forestall such
questions. Some people prefer the term `FAQ list' or `FAQL'
/fa'kl/, reserving `FAQ' for sense 1.
RTFAQ
/R-T-F-A-Q/ [USENET: primarily written, by analogy with RTFM]
imp. Abbrev. for `Read the FAQ!', an exhortation that the person
addressed ought to read the newsgroup's FAQ list before posting
questions.
RTFM /R-T-F-M/ [UNIX] imp. Acronym for `Read The Fucking Manual'. 1.
Used by gurus to brush off questions they consider trivial or
annoying. Compare Don't do that, then! 2. Used when reporting
a problem to indicate that you aren't just asking out of
randomness. "No, I can't figure out how to interface UNIX to my
toaster, and yes, I have RTFM." Unlike sense 1, this use is
considered polite. ...
--- "The on-line hacker Jargon File, version 3.0, 29 July
1993"
PREFACE
This guide is intended to help, provide basic information, and serve
as a first straw for individuals, i.e. uninitiated hitch-hikers, who
are stranded in the mindboggling universe of Evolutionary Computation
(EC); that in turn is only a small footpath to an even more
mindboggling scientific universe, that, incorporating Fuzzy Systems,
and Artificial Neural Networks, is sometimes referred to as
Computational Intelligence (CI); that in turn is only part of an even
more advanced scientific universe of mindparalysing complexity, that
incorporating Artificial Life, Fractal Geometry, and other Complex
Systems Sciences might someday be referred to as Natural Computation
(NC).
Over the course of the past years, GLOBAL OPTIMIZATION algorithms
imitating certain principles of nature have proved their usefulness
in various domains of applications. Especially worth copying are
those principles where nature has found "stable islands" in a
"turbulent ocean" of solution possibilities. Such phenomena can be
found in annealing processes, central nervous systems and biological
EVOLUTION, which in turn have lead to the following OPTIMIZATION
methods: Simulated Annealing (SA), Artificial Neural Networks (ANNs)
and the field of Evolutionary Computation (EC).
EC may currently be characterized by the following pathways: Genetic
Algorithms (GA), Evolutionary Programming (EP), Evolution Strategies
(ES), Classifier Systems (CFS), Genetic Programming (GP), and several
other problem solving strategies, that are based upon biological
observations, that date back to Charles Darwin's discoveries in the
19th century: the means of natural selection and the survival of the
fittest, and theories of evolution. The inspired algorithms are thus
termed Evolutionary Algorithms (EA).
Moreover, this guide is intended to help those who are just beginning
to read the comp.ai.genetic newsgroup, and those who are new "on"
USENET. It shall help to avoid lengthy discussions of questions that
usually arise for beginners of one or the other kind, and which are
boring to read again and again by comp.ai.genetic "old-timers."
You will see this guide popping up periodically in the Usenet
newsgroup comp.ai.genetic (and also comp.answers , and news.answers ,
where it should be locatable at any time).
ORIGIN
This guide was produced by Joerg Heitkoetter (known as Joke) in early
1993, using material from many sources (see Acknowledgements ), mixed
with his own brand of humour. Towards the end of 1993, Joerg handed
over editorial responsibility to David Beasley . He reorganised the
guide in various ways, and generally attempted to inject his own
brand of orderliness. Thus, any jokes are the work of Joke. The
mundane bits are David's responsibility.
The guide is kept up to date, as far as possible, and new versions
are issued several times a year. However, we do rely on useful
information being sent to us for inclusion in the guide (we dont
always have time to read comp.ai.genetic , for example).
Contributions, additions, corrections, cash, etc. are therefore
always welcome. Send e-mail to the address at the beginning of the
guide.
DISCLAIMER
This periodic posting is not meant to discuss any topic exhaustively,
but should be thought of as a list of reference pointers, instead.
This posting is provided on an "as is" basis, NO WARRANTY whatsoever
is expressed or implied, especially, NO WARRANTY that the information
contained herein is up-to-date, correct or useful in any way,
although all this is intended.
Moreover, please note that the opinions expressed herein do not
necessarily reflect those of the editors' institutions or employers,
neither as a whole, nor in part. They are just the amalgamation of
the editors' collections of ideas, and contributions gleaned from
other sources.
NOTE: some portions of this otherwise rather dry guide are intended
to be satirical. If you do not recognize it as such, consult your
local doctor or a professional comedian.
HOW TO USE THIS GUIDE
HITCH-HIKING THE FAQNIVERSE
This guide is big. Really big. You just won't believe how hugely,
vastly, mindbogglingly big it is. That's why it has been split into a
"trilogy" -- which, like all successful trilogies, eventually ends up
consisting of more than three parts.
Searching for answers
To find the answer of question number x, just search for the string
"Qx:". (So the answer to question 42 is at "Q42:"!)
What does [xxxx99] mean?
Some books are referenced again and again, that's why they have this
kind of "tag", that an experienced hitch-hiker will search for in the
list of books (see Q10 and Q12 and other places) to dissolve the
riddle. Here, they have a ":" appended, thus you can search for the
string "[ICGA85]:" for example.
Why all this UPPERCASING in running text?
Words written in all uppercase letters are cross-references to
entries in the Glossary (see Q99). Again, they have a ":" appended,
thus if you find, say EVOLUTION, you can search for the string
"EVOLUTION:" in the Glossary.
FTP and HTTP naming conventions
A file available on an FTP server will be specified as: <ftp-site-
name>/<the-complete-filename> So for example, the file bar.tar.gz in
the directory /pub/foo on the ftp server ftp.certain.site would be
specified as: ftp.certain.site/pub/foo/bar.tar.gz
A specification ending with a "/" is a reference to a whole
directory, e.g. ftp.certain.site/pub/foo/
HTTP files are specified in a similar way, but with the prefix:
http://
WHERE TO FIND THIS GUIDE
Between postings to comp.ai.genetic , this FAQ is available on the
World Wide Web. Get it from any ENCORE site (See Q15.3). The
following Encore sites can be accessed by HTTP. If you use the one
closest to you, you should get the best speed of service. (Note,
however, that some sites are not always up to date. The guide is
normally issued every 3 months.)
o UUnet Deutschland GmbH (Germany) (definitive location):
http://surf.de.uu.net/encore/www/
o The Chinese University of Hong Kong (China):
http://www.cs.cuhk.hk/pub/EC/FAQ/www/top.htm
o Ecole Polytechnique (France):
http://www.eark.polytechnique.fr/EC/FAQ/www/top.htm
o The University of Oviedo (Spain):
http://www.etsimo.uniovi.es/ftp/pub/EC/FAQ/www/
o The University of Birmingham (UK)
http://www.cs.bham.ac.uk/Mirrors/ftp.de.uu.net/EC/clife/www/
o The Santa Fe Institute (USA):
http://alife.santafe.edu/~joke/encore/www/
Other Encore sites can be accessed by FTP, and the FAQ can be found
in the file FAQ/www/top.htm or something similar. The FAQ is also
available in plain text format on Encore, and from
rtfm.mit.edu/pub/usenet/news.answers/ai-faq/genetic/ as the files:
part1 to part6. The FAQ may also be retrieved by e-mail from <mail-
ser...@rtfm.mit.edu>. Send a message to the mail-server with "help"
and "index" in the body on separate lines for more information.
A PostScript version is also available. This looks really crisp
(using boldface, italics, etc.), and is available for those who
prefer offline reading. Get it from Encore in file FAQ/hhgtec.ps.gz
(the plain text versions are in the same directory too).
"As a net is made up of a series of ties, so everything in this
world is connected by a series of ties. If anyone thinks that the
mesh of a net is an independent, isolated thing, he is mistaken. It
is called a net because it is made up of a series of interconnected
meshes, and each mesh has its place and
responsibility in relation to other meshes."
--- Buddha
Referencing this Guide
If you want to reference this guide it should look like:
Heitkoetter, Joerg and Beasley, David, eds. (2001) "The Hitch-
Hiker's Guide to Evolutionary Computation: A list of Frequently Asked
Questions (FAQ)", USENET: comp.ai.genetic. Available via anonymous
FTP from rtfm.mit.edu/pub/usenet/news.answers/ai-faq/genetic/ About
110 pages.
Or simply call it "the Guide", or "HHGTEC" for acronymaniacs.
The ZEN Puzzle
For some weird reason this guide contains some puzzles which can only
be solved by cautious readers who have (1) a certain amount of a
certain kind of humor, (2) a certain amount of patience and time, (3)
a certain amount of experience in ZEN NAVIGATION, and (4) a certain
amount of books of a certain author.
Usually, puzzles search either for certain answers (more often, ONE
answer) to a question; or, for the real smartasses, sometimes an
answer is presented, and a certain question is searched for. ZEN
puzzles are even more challenging: you have to come up with an answer
to a question, both of which are not explicitly, rather implicitly
stated somewhere in this FAQ. Thus, you are expected to give an
answer AND a question!
To give an impression what this is all about, consider the following,
submitted by Craig W. Reynolds. The correct question is: "Why is
Fisher's `improbability quote' (cf EPILOGUE ) included in this FAQ?",
Craig's correct answer is: `This is a GREAT quotation, it sounds like
something directly out of a turn of the century Douglas Adams:
Natural Selection:
the original "Infinite Improbability Drive"' Got the message? Well,
this was easy and very obvious. The other puzzles are more
challenging...
However, all this is just for fun (mine and hopefully yours), there
is nothing like the $100 price, some big shots in computer science,
e.g. Don Knuth usually offer; all there is but a honorable
mentioning of the ZEN navigator, including the puzzle s/he solved.
It's thus like in real life: don't expect to make money from your
time being a scientist, it's all just for the fun of it...
Enjoy the trip!
TABLE OF CONTENTS
Part1
Q0: How about an introduction to comp.ai.genetic?
Part2
Q1: What are Evolutionary Algorithms (EAs)?
Q1.1: What's a Genetic Algorithm (GA)?
Q1.2: What's Evolutionary Programming (EP)?
Q1.3: What's an Evolution Strategy (ES)?
Q1.4: What's a Classifier System (CFS)?
Q1.5: What's Genetic Programming (GP)?
Part3
Q2: What applications of EAs are there?
Q3: Who is concerned with EAs?
Q4: How many EAs exist? Which?
Q4.1: What about Alife systems, like Tierra and VENUS?
Q5: What about all this Optimization stuff?
Part4
Q10: What introductory material on EAs is there?
Q10.1: Suitable background reading for beginners?
Q10.2: Textbooks on EC?
Q10.3: The Classics?
Q10.4: Introductory Journal Articles?
Q10.5: Introductory Technical Reports?
Q10.6: Not-quite-so-introductory Literature?
Q10.7: Biological Background Readings?
Q10.8: On-line bibliography collections?
Q10.9: Videos?
Q10.10: CD-ROMs?
Q10.11: How do I get a copy of a dissertation?
Q11: What EC related journals and magazines are there?
Q12: What are the important conferences/proceedings on EC?
Q13: What Evolutionary Computation Associations exist?
Q14: What Technical Reports are available?
Q15: What information is available over the net?
Q15.1: What digests are there?
Q15.2: What mailing lists are there?
Q15.3: What online information repositories are there?
Q15.4: What relevant newsgroups and FAQs are there?
Q15.5: What about all these Internet Services?
Part5
Q20: What EA software packages are available?
Q20.1: Free software packages?
Q20.2: Commercial software packages?
Q20.3: Current research projects?
Part6
Q21: What are Gray codes, and why are they used?
Q22: What test data is available?
Q42: What is Life all about?
Q42b: Is there a FAQ to this group?
Q98: Are there any patents on EAs?
Q99: A Glossary on EAs?
----------------------------------------------------------------------
Subject: Q0: How about an introduction to comp.ai.genetic?
Certainly. See below.
What is comp.ai.genetic all about?
The newsgroup comp.ai.genetic is intended as a forum for people who
want to use or explore the capabilities of Genetic Algorithms (GA),
Evolutionary Programming (EP), Evolution Strategies (ES), Classifier
Systems (CFS), Genetic Programming (GP), and some other, less well-
known problem solving algorithms that are more or less loosely
coupled to the field of Evolutionary Computation (EC).
How do I get started? What about USENET documentation?
The following guidelines present the essentials of the USENET online
documentation, that is posted each month to news.announce.newusers
If you are already familiar with "netiquette" you can skip to the end
of this answer; if you don't know what the hell this is all about,
proceed as follows: (1) carefully read the following paragraphs, (2)
read all the documents in news.announce.newusers before posting any
article to USENET. At least you should give the introductory stuff a
try, i.e. files "news-answers/introduction" and "news-answers/news-
newusers-intro". Both are survey articles, that provide a short and
easy way to get an overview of the interesting parts of the online
docs, and thus can help to prevent you from drowning in the megabytes
to read. Both can be received either by subscribing to news.answers ,
or sending the following message to <mail-...@rtfm.mit.edu>:
send usenet/news.answers/introduction
send usenet/news.answers/news-newusers-intro
quit
Netiquette
"Usenet is a convention, in every sense of the word."
Although USENET is usually characterized as "an anarchy, with no laws
and no one in charge" there have "emerged" several rules over the
past years that shall facilitate life within newsgroups. Thus, you
will probably find the following types of articles:
1. Requests
Requests are articles of the form "I am looking for X" where X is
something public like a book, an article, a piece of software.
If multiple different answers can be expected, the person making the
request should prepare to make a summary of the answers he/she got
and announce to do so with a phrase like "Please e-mail, I'll
summarize" at the end of the posting.
The Subject line of the posting should then be something like
"Request: X"
2. Questions
As opposed to requests, questions are concerned with something so
specific that general interest cannot readily be assumed. If the
poster thinks that the topic is of some general interest, he/she
should announce a summary (see above).
The Subject line of the posting should be something like "Question:
this-and-that" (Q: this-and-that) or have the form of a question
(i.e., end with a question mark)
3. Answers
These are reactions to questions or requests. As a rule of thumb
articles of type "answer" should be rare. Ideally, in most cases
either the answer is too specific to be of general interest (and
should thus be e-mailed to the poster) or a summary was announced
with the question or request (and answers should thus be e-mailed to
the poster).
The subject lines of answers are automatically adjusted by the news
software.
4. Summaries
In all cases of requests or questions the answers for which can be
assumed to be of some general interest, the poster of the request or
question shall summarize the answers he/she received. Such a summary
should be announced in the original posting of the question or
request with a phrase like "Please answer by e-mail, I'll summarize"
In such a case answers should NOT be posted to the newsgroup but
instead be mailed to the poster who collects and reviews them. After
about 10 to 20 days from the original posting, its poster should make
the summary of answers and post it to the net.
Some care should be invested into a summary:
a) simple concatenation of all the answers might not be enough;
instead redundancies, irrelevances, verbosities and errors should
be filtered out (as good as possible),
b) the answers shall be separated clearly
c) the contributors of the individual answers shall be identifiable
unless they requested to remain anonymous [eds note: yes, that
happens])
d) the summary shall start with the "quintessence" of the answers, as
seen by the original poster
e) A summary should, when posted, clearly be indicated to be one by
giving it a Subject line starting with "Summary:"
Note that a good summary is pure gold for the rest of the newsgroup
community, so summary work will be most appreciated by all of us.
(Good summaries are more valuable than any moderator!)
5. Announcements
Some articles never need any public reaction. These are called
announcements (for instance for a workshop, conference or the
availability of some technical report or software system).
Announcements should be clearly indicated to be such by giving them a
subject line of the form "Announcement: this-and-that", or "ust "A:
this-and-that".
Due to common practice, conference announcements usually carry a
"CFP:" in their subject line, i.e. "call for papers" (or: "call for
participation").
6. Reports
Sometimes people spontaneously want to report something to the
newsgroup. This might be special experiences with some software,
results of own experiments or conceptual work, or especially
interesting information from somewhere else.
Reports should be clearly indicated to be such by giving them a
subject line of the form "Report: this-and-that"
7. Discussions
An especially valuable possibility of USENET is of course that of
discussing a certain topic with hundreds of potential participants.
All traffic in the newsgroup that can not be subsumed under one of
the above categories should belong to a discussion.
If somebody explicitly wants to start a discussion, he/she can do so
by giving the posting a subject line of the form "Start discussion:
this-and-that" (People who react on this, please remove the "Start
discussion: " label from the subject line of your replies)
It is quite difficult to keep a discussion from drifting into chaos,
but, unfortunately, as many other newsgroups show there seems to be
no secure way to avoid this. On the other hand, comp.ai.genetic has
not had many problems with this effect, yet, so let's just go and
hope...
Thanks in advance for your patience!
The Internet
For information on internet services, see Q15.5.
------------------------------
Copyright (c) 1993-2000 by J. Heitkoetter and D. Beasley, all rights
reserved.
This FAQ may be posted to any USENET newsgroup, on-line service, or
BBS as long as it is posted in its entirety and includes this
copyright statement. This FAQ may not be distributed for financial
gain. This FAQ may not be included in commercial collections or
compilations without express permission from the author.
End of ai-faq/genetic/part1
***************************
--
David Beasley
Last-Modified: 4/12/01
Issue: 9.1
Important note: Do NOT send email to the cs.cf.ac.uk address above: it will
be ignored. Corrections and other correspondence should be sent to
david....@iee.org
TABLE OF CONTENTS OF PART 2
Q1: What are Evolutionary Algorithms (EAs)?
Q1.1: What's a Genetic Algorithm (GA)?
Q1.2: What's Evolutionary Programming (EP)?
Q1.3: What's an Evolution Strategy (ES)?
Q1.4: What's a Classifier System (CFS)?
Q1.5: What's Genetic Programming (GP)?
----------------------------------------------------------------------
Subject: Q1: What are Evolutionary Algorithms (EAs)?
Evolutionary algorithm is an umbrella term used to describe computer-
based problem solving systems which use computational models of some
of the known mechanisms of EVOLUTION as key elements in their design
and implementation. A variety of EVOLUTIONARY ALGORITHMs have been
proposed. The major ones are: GENETIC ALGORITHMs (see Q1.1),
EVOLUTIONARY PROGRAMMING (see Q1.2), EVOLUTION STRATEGIEs (see Q1.3),
CLASSIFIER SYSTEMs (see Q1.4), and GENETIC PROGRAMMING (see Q1.5).
They all share a common conceptual base of simulating the evolution
of INDIVIDUAL structures via processes of SELECTION, MUTATION, and
REPRODUCTION. The processes depend on the perceived PERFORMANCE of
the individual structures as defined by an ENVIRONMENT.
More precisely, EAs maintain a POPULATION of structures, that evolve
according to rules of selection and other operators, that are
referred to as "search operators", (or GENETIC OPERATORs), such as
RECOMBINATION and mutation. Each individual in the population
receives a measure of its FITNESS in the environment. Reproduction
focuses attention on high fitness individuals, thus exploiting (cf.
EXPLOITATION) the available fitness information. Recombination and
mutation perturb those individuals, providing general heuristics for
EXPLORATION. Although simplistic from a biologist's viewpoint, these
algorithms are sufficiently complex to provide robust and powerful
adaptive search mechanisms.
--- "An Overview of Evolutionary Computation" [ECML93], 442-459.
BIOLOGICAL BASIS
To understand EAs, it is necessary to have some appreciation of the
biological processes on which they are based.
Firstly, we should note that EVOLUTION (in nature or anywhere else)
is not a purposive or directed process. That is, there is no
evidence to support the assertion that the goal of evolution is to
produce Mankind. Indeed, the processes of nature seem to boil down to
a haphazard GENERATION of biologically diverse organisms. Some of
evolution is determined by natural SELECTION or different INDIVIDUALs
competing for resources in the ENVIRONMENT. Some are better than
others. Those that are better are more likely to survive and
propagate their genetic material.
In nature, we see that the encoding for genetic information (GENOME)
is done in a way that admits asexual REPRODUCTION. Asexual
reproduction typically results in OFFSPRING that are genetically
identical to the PARENT. (Large numbers of organisms reproduce
asexually; this includes most bacteria which some biologists hold to
be the most successful SPECIES known.)
Sexual reproduction allows some shuffing of CHROMOSOMEs, producing
offspring that contain a combination of information from each parent.
At the molecular level what occurs (wild oversimplification alert!)
is that a pair of almost identical chromosomes bump into one another,
exchange chunks of genetic information and drift apart. This is the
RECOMBINATION operation, which is often referred to as CROSSOVER
because of the way that biologists have observed strands of
chromosomes crossing over during the exchange.
Recombination happens in an environment where the selection of who
gets to mate is largely a function of the FITNESS of the individual,
i.e. how good the individual is at competing in its environment. Some
"luck" (random effect) is usually involved too. Some EAs use a simple
function of the fitness measure to select individuals
(probabilistically) to undergo genetic operations such as crossover
or asexual reproduction (the propagation of genetic material
unaltered). This is fitness-proportionate selection. Other
implementations use a model in which certain randomly selected
individuals in a subgroup compete and the fittest is selected. This
is called tournament selection and is the form of selection we see in
nature when stags rut to vie for the privilege of mating with a herd
of hinds.
Much EA research has assumed that the two processes that most
contribute to evolution are crossover and fitness based
selection/reproduction. Evolution, by definition, absolutely
requires diversity in order to work. In nature, an important source
of diversity is MUTATION. In an EA, a large amount of diversity is
usually introduced at the start of the algorithm, by randomising the
GENEs in the POPULATION. The importance of mutation, which
introduces further diversity while the algorithm is running,
therefore continues to be a matter of debate. Some refer to it as a
background operator, simply replacing some of the original diversity
which may have been lost, while others view it as playing the
dominant role in the evolutionary process.
It cannot be stressed too strongly that an EVOLUTIONARY ALGORITHM (as
a SIMULATION of a genetic process) is not a random search for a
solution to a problem (highly fit individual). EAs use stochastic
processes, but the result is distinctly non-random (better than
random).
PSEUDO CODE
Algorithm EA is
// start with an initial time
t := 0;
// initialize a usually random population of individuals
initpopulation P (t);
// evaluate fitness of all initial individuals in population
evaluate P (t);
// test for termination criterion (time, fitness, etc.)
while not done do
// increase the time counter
t := t + 1;
// select sub-population for offspring production
P' := selectparents P (t);
// recombine the "genes" of selected parents
recombine P' (t);
// perturb the mated population stochastically
mutate P' (t);
// evaluate its new fitness
evaluate P' (t);
// select the survivors from actual fitness
P := survive P,P' (t);
od
end EA.
------------------------------
Subject: Q1.1: What's a Genetic Algorithm (GA)?
The GENETIC ALGORITHM is a model of machine learning which derives
its behavior from a metaphor of some of the mechanisms of EVOLUTION
in nature. This is done by the creation within a machine of a
POPULATION of INDIVIDUALs represented by CHROMOSOMEs, in essence a
set of character strings that are analogous to the base-4 chromosomes
that we see in our own DNA. The individuals in the population then
go through a process of simulated "evolution".
Genetic algorithms are used for a number of different application
areas. An example of this would be multidimensional OPTIMIZATION
problems in which the character string of the chromosome can be used
to encode the values for the different parameters being optimized.
In practice, therefore, we can implement this genetic model of
computation by having arrays of bits or characters to represent the
chromosomes. Simple bit manipulation operations allow the
implementation of CROSSOVER, MUTATION and other operations. Although
a substantial amount of research has been performed on variable-
length strings and other structures, the majority of work with
genetic algorithms is focussed on fixed-length character strings. We
should focus on both this aspect of fixed-lengthness and the need to
encode the representation of the solution being sought as a character
string, since these are crucial aspects that distinguish GENETIC
PROGRAMMING, which does not have a fixed length representation and
there is typically no encoding of the problem.
When the genetic algorithm is implemented it is usually done in a
manner that involves the following cycle: Evaluate the FITNESS of
all of the individuals in the population. Create a new population by
performing operations such as crossover, fitness-proportionate
REPRODUCTION and mutation on the individuals whose fitness has just
been measured. Discard the old population and iterate using the new
population.
One iteration of this loop is referred to as a GENERATION. There is
no theoretical reason for this as an implementation model. Indeed,
we do not see this punctuated behavior in populations in nature as a
whole, but it is a convenient implementation model.
The first generation (generation 0) of this process operates on a
population of randomly generated individuals. From there on, the
genetic operations, in concert with the fitness measure, operate to
improve the population.
PSEUDO CODE
Algorithm GA is
// start with an initial time
t := 0;
// initialize a usually random population of individuals
initpopulation P (t);
// evaluate fitness of all initial individuals of population
evaluate P (t);
// test for termination criterion (time, fitness, etc.)
while not done do
// increase the time counter
t := t + 1;
// select a sub-population for offspring production
P' := selectparents P (t);
// recombine the "genes" of selected parents
recombine P' (t);
// perturb the mated population stochastically
mutate P' (t);
// evaluate its new fitness
evaluate P' (t);
// select the survivors from actual fitness
P := survive P,P' (t);
od
end GA.
------------------------------
Subject: Q1.2: What's Evolutionary Programming (EP)?
Introduction
EVOLUTIONARY PROGRAMMING, originally conceived by Lawrence J. Fogel
in 1960, is a stochastic OPTIMIZATION strategy similar to GENETIC
ALGORITHMs, but instead places emphasis on the behavioral linkage
between PARENTs and their OFFSPRING, rather than seeking to emulate
specific GENETIC OPERATORs as observed in nature. Evolutionary
programming is similar to EVOLUTION STRATEGIEs, although the two
approaches developed independently (see below).
Like both ES and GAs, EP is a useful method of optimization when
other techniques such as gradient descent or direct, analytical
discovery are not possible. Combinatoric and real-valued FUNCTION
OPTIMIZATION in which the optimization surface or FITNESS landscape
is "rugged", possessing many locally optimal solutions, are well
suited for evolutionary programming.
History
The 1966 book, "Artificial Intelligence Through Simulated Evolution"
by Fogel, Owens and Walsh is the landmark publication for EP
applications, although many other papers appear earlier in the
literature. In the book, finite state automata were evolved to
predict symbol strings generated from Markov processes and non-
stationary time series. Such evolutionary prediction was motivated
by a recognition that prediction is a keystone to intelligent
behavior (defined in terms of adaptive behavior, in that the
intelligent organism must anticipate events in order to adapt
behavior in light of a goal).
In 1992, the First Annual Conference on evolutionary programming was
held in La Jolla, CA. Further conferences have been held annually
(See Q12). The conferences attract a diverse group of academic,
commercial and military researchers engaged in both developing the
theory of the EP technique and in applying EP to a wide range of
optimization problems, both in engineering and biology.
Rather than list and analyze the sources in detail, several
fundamental sources are listed below which should serve as good
pointers to the entire body of work in the field.
The Process
For EP, like GAs, there is an underlying assumption that a fitness
landscape can be characterized in terms of variables, and that there
is an optimum solution (or multiple such optima) in terms of those
variables. For example, if one were trying to find the shortest path
in a Traveling Salesman Problem, each solution would be a path. The
length of the path could be expressed as a number, which would serve
as the solution's fitness. The fitness landscape for this problem
could be characterized as a hypersurface proportional to the path
lengths in a space of possible paths. The goal would be to find the
globally shortest path in that space, or more practically, to find
very short tours very quickly.
The basic EP method involves 3 steps (Repeat until a threshold for
iteration is exceeded or an adequate solution is obtained):
(1) Choose an initial POPULATION of trial solutions at random. The
number of solutions in a population is highly relevant to the
speed of optimization, but no definite answers are available as
to how many solutions are appropriate (other than >1) and how
many solutions are just wasteful.
(2) Each solution is replicated into a new population. Each of
these offspring solutions are mutated according to a
distribution of MUTATION types, ranging from minor to extreme
with a continuum of mutation types between. The severity of
mutation is judged on the basis of the functional change imposed
on the parents.
(3) Each offspring solution is assessed by computing its fitness.
Typically, a stochastic tournament is held to determine N
solutions to be retained for the population of solutions,
although this is occasionally performed deterministically.
There is no requirement that the population size be held
constant, however, nor that only a single offspring be generated
from each parent.
It should be pointed out that EP typically does not use any CROSSOVER
as a genetic operator.
EP and GAs
There are two important ways in which EP differs from GAs.
First, there is no constraint on the representation. The typical GA
approach involves encoding the problem solutions as a string of
representative tokens, the GENOME. In EP, the representation follows
from the problem. A neural network can be represented in the same
manner as it is implemented, for example, because the mutation
operation does not demand a linear encoding. (In this case, for a
fixed topology, real- valued weights could be coded directly as their
real values and mutation operates by perturbing a weight vector with
a zero mean multivariate Gaussian perturbation. For variable
topologies, the architecture is also perturbed, often using Poisson
distributed additions and deletions.)
Second, the mutation operation simply changes aspects of the solution
according to a statistical distribution which weights minor
variations in the behavior of the offspring as highly probable and
substantial variations as increasingly unlikely. Further, the
severity of mutations is often reduced as the global optimum is
approached. There is a certain tautology here: if the global optimum
is not already known, how can the spread of the mutation operation be
damped as the solutions approach it? Several techniques have been
proposed and implemented which address this difficulty, the most
widely studied being the "Meta-Evolutionary" technique in which the
variance of the mutation distribution is subject to mutation by a
fixed variance mutation operator and evolves along with the solution.
EP and ES
The first communication between the evolutionary programming and
EVOLUTION STRATEGY groups occurred in early 1992, just prior to the
first annual EP conference. Despite their independent development
over 30 years, they share many similarities. When implemented to
solve real-valued function optimization problems, both typically
operate on the real values themselves (rather than any coding of the
real values as is often done in GAs). Multivariate zero mean Gaussian
mutations are applied to each parent in a population and a SELECTION
mechanism is applied to determine which solutions to remove (i.e.,
"cull") from the population. The similarities extend to the use of
self-adaptive methods for determining the appropriate mutations to
use -- methods in which each parent carries not only a potential
solution to the problem at hand, but also information on how it will
distribute new trials (offspring). Most of the theoretical results on
convergence (both asymptotic and velocity) developed for ES or EP
also apply directly to the other.
The main differences between ES and EP are:
1. Selection: EP typically uses stochastic selection via a
tournament. Each trial solution in the population faces
competition against a preselected number of opponents and
receives a "win" if it is at least as good as its opponent in
each encounter. Selection then eliminates those solutions with
the least wins. In contrast, ES typically uses deterministic
selection in which the worst solutions are purged from the
population based directly on their function evaluation.
2. RECOMBINATION: EP is an abstraction of EVOLUTION at the level of
reproductive populations (i.e., SPECIES) and thus no
recombination mechanisms are typically used because
recombination does not occur between species (by definition: see
Mayr's biological species concept). In contrast, ES is an
abstraction of evolution at the level of INDIVIDUAL behavior.
When self-adaptive information is incorporated this is purely
genetic information (as opposed to phenotypic) and thus some
forms of recombination are reasonable and many forms of
recombination have been implemented within ES. Again, the
effectiveness of such operators depends on the problem at hand.
References
Some references which provide an excellent introduction (by no means
extensive) to the field, include:
Artificial Intelligence Through Simulated Evolution [Fogel66]
(primary)
Fogel DB (1995) "Evolutionary Computation: Toward a New Philosophy of
Machine Intelligence," IEEE Press, Piscataway, NJ.
Proceeding of the first [EP92], second [EP93] and third [EP94] Annual
Conference on Evolutionary Programming (primary) (See Q12).
PSEUDO CODE
Algorithm EP is
// start with an initial time
t := 0;
// initialize a usually random population of individuals
initpopulation P (t);
// evaluate fitness of all initial individuals of population
evaluate P (t);
// test for termination criterion (time, fitness, etc.)
while not done do
// perturb the whole population stochastically
P'(t) := mutate P (t);
// evaluate its new fitness
evaluate P' (t);
// stochastically select the survivors from actual fitness
P(t+1) := survive P(t),P'(t);
// increase the time counter
t := t + 1;
od
end EP.
[Eds note: An extended version of this introduction is available from
ENCORE (see Q15.3) in /FAQ/supplements/what-is-ep ]
------------------------------
Subject: Q1.3: What's an Evolution Strategy (ES)?
In 1963 two students at the Technical University of Berlin (TUB) met
and were soon to collaborate on experiments which used the wind
tunnel of the Institute of Flow Engineering. During the search for
the optimal shapes of bodies in a flow, which was then a matter of
laborious intuitive experimentation, the idea was conceived of
proceeding strategically. However, attempts with the coordinate and
simple gradient strategies (cf Q5) were unsuccessful. Then one of
the students, Ingo Rechenberg, now Professor of Bionics and
Evolutionary Engineering, hit upon the idea of trying random changes
in the parameters defining the shape, following the example of
natural MUTATIONs. The EVOLUTION STRATEGY was born. A third
student, Peter Bienert, joined them and started the construction of
an automatic experimenter, which would work according to the simple
rules of mutation and SELECTION. The second student, Hans-Paul
Schwefel, set about testing the efficiency of the new methods with
the help of a Zuse Z23 computer; for there were plenty of objections
to these "random strategies."
In spite of an occasional lack of financial support, the Evolutionary
Engineering Group which had been formed held firmly together. Ingo
Rechenberg received his doctorate in 1970 (Rechenberg 73). It
contains the theory of the two membered EVOLUTION strategy and a
first proposal for a multimembered strategy which in the nomenclature
introduced here is of the (m+1) type. In the same year financial
support from the Deutsche Forschungsgemeinschaft (DFG, Germany's
National Science Foundation) enabled the work, that was concluded, at
least temporarily, in 1974 with the thesis "Evolutionsstrategie und
numerische Optimierung" (Schwefel 77).
Thus, EVOLUTION STRATEGIEs were invented to solve technical
OPTIMIZATION problems (TOPs) like e.g. constructing an optimal
flashing nozzle, and until recently ES were only known to civil
engineering folks, as an alternative to standard solutions. Usually
no closed form analytical objective function is available for TOPs
and hence, no applicable optimization method exists, but the
engineer's intuition.
The first attempts to imitate principles of organic evolution on a
computer still resembled the iterative optimization methods known up
to that time (cf Q5): In a two-membered or (1+1) ES, one PARENT
generates one OFFSPRING per GENERATION by applying NORMALLY
DISTRIBUTED mutations, i.e. smaller steps occur more likely than big
ones, until a child performs better than its ancestor and takes its
place. Because of this simple structure, theoretical results for
STEPSIZE control and CONVERGENCE VELOCITY could be derived. The ratio
between successful and all mutations should come to 1/5: the so-
called 1/5 SUCCESS RULE was discovered. This first algorithm, using
mutation only, has then been enhanced to a (m+1) strategy which
incorporated RECOMBINATION due to several, i.e. m parents being
available. The mutation scheme and the exogenous stepsize control
were taken across unchanged from (1+1) ESs.
Schwefel later generalized these strategies to the multimembered ES
now denoted by (m+l) and (m,l) which imitates the following basic
principles of organic evolution: a POPULATION, leading to the
possibility of recombination with random mating, mutation and
selection. These strategies are termed PLUS STRATEGY and COMMA
STRATEGY, respectively: in the plus case, the parental generation is
taken into account during selection, while in the comma case only the
offspring undergoes selection, and the parents die off. m (usually a
lowercase mu, denotes the population size, and l, usually a lowercase
lambda denotes the number of offspring generated per generation). Or
to put it in an utterly insignificant and hopelessly outdated
language:
(define (Evolution-strategy population)
(if (terminate? population)
population
(evolution-strategy
(select
(cond (plus-strategy?
(union (mutate
(recombine population))
population))
(comma-strategy?
(mutate
(recombine population))))))))
However, dealing with ES is sometimes seen as "strong tobacco," for
it takes a decent amount of probability theory and applied STATISTICS
to understand the inner workings of an ES, while it navigates through
the hyperspace of the usually n-dimensional problem space, by
throwing hyperelipses into the deep...
Luckily, this medium doesn't allow for much mathematical ballyhoo;
the author therefore has to come up with a simple but brilliantly
intriguing explanation to save the reader from falling asleep during
the rest of this section, so here we go:
Imagine a black box. A large black box. As large as, say for example,
a Coca-Cola vending machine. Now, [..] (to be continued)
A single INDIVIDUAL of the ES' population consists of the following
GENOTYPE representing a point in the SEARCH SPACE:
OBJECT VARIABLES
Real-valued x_i have to be tuned by recombination and mutation
such that an objective function reaches its global optimum.
Referring to the metaphor mentioned previously, the x_i
represent the regulators of the alien Coka-Cola vending machine.
STRATEGY VARIABLEs
Real-valued s_i (usually denoted by a lowercase sigma) or mean
stepsizes determine the mutability of the x_i. They represent
the STANDARD DEVIATION of a (0, s_i) GAUSSIAN DISTRIBUTION (GD)
being added to each x_i as an undirected mutation. With an
"expectancy value" of 0 the parents will produce offspring
similar to themselves on average. In order to make a doubling
and a halving of a stepsize equally probable, the s_i mutate
log-normally, distributed, i.e. exp(GD), from generation to
generation. These stepsizes hide the internal model the
population has made of its ENVIRONMENT, i.e. a SELF-ADAPTATION
of the stepsizes has replaced the exogenous control of the (1+1)
ES.
This concept works because selection sooner or later prefers
those individuals having built a good model of the objective
function, thus producing better offspring. Hence, learning takes
place on two levels: (1) at the genotypic, i.e. the object and
strategy variable level and (2) at the phenotypic level, i.e.
the FITNESS level.
Depending on an individual's x_i, the resulting objective
function value f(x), where x denotes the vector of objective
variables, serves as the PHENOTYPE (fitness) in the selection
step. In a plus strategy, the m best of all (m+l) individuals
survive to become the parents of the next generation. Using the
comma variant, selection takes place only among the l offspring.
The second scheme is more realistic and therefore more
successful, because no individual may survive forever, which
could at least theoretically occur using the plus variant.
Untypical for conventional optimization algorithms and lavish at
first sight, a comma strategy allowing intermediate
deterioration performs better! Only by forgetting highly fit
individuals can a permanent adaptation of the stepsizes take
place and avoid long stagnation phases due to misadapted s_i's.
This means that these individuals have built an internal model
that is no longer appropriate for further progress, and thus
should better be discarded.
By choosing a certain ratio m/l, one can determine the
convergence property of the evolution strategy: If one wants a
fast, but local convergence, one should choose a small HARD
SELECTION, ratio, e.g. (5,100), but looking for the global
optimum, one should favour a softer selection (15,100).
Self-adaptation within ESs depends on the following agents
(Schwefel 87):
Randomness: One cannot model mutation
as a purely random process. This would mean that a child is
completely independent of its parents.
Population size: The population has to be sufficiently large. Not
only
the current best should be allowed to reproduce, but a set of
good individuals. Biologists have coined the term "requisite
variety" to mean the genetic variety necessary to prevent a
SPECIES from becoming poorer and poorer genetically and
eventually dying out.
COOPERATION:
In order to exploit the effects of a population (m > 1), the
individuals should recombine their knowledge with that of others
(cooperate) because one cannot expect the knowledge to
accumulate in the best individual only.
Deterioration: In order to allow better internal models (stepsizes)
to provide better progress in the future, one should accept
deterioration from one generation to the next. A limited life-
span in nature is not a sign of failure, but an important means
of preventing a species from freezing genetically.
ESs prove to be successful when compared to other iterative
methods on a large number of test problems (Schwefel 77). They
are adaptable to nearly all sorts of problems in optimization,
because they need very little information about the problem,
especially no derivatives of the objective function. For a list
of some 300 applications of EAs, see the SyS-2/92 report (cf
Q14). ESs are capable of solving high dimensional, multimodal,
nonlinear problems subject to linear and/or nonlinear
constraints. The objective function can also, e.g. be the
result of a SIMULATION, it does not have to be given in a closed
form. This also holds for the constraints which may represent
the outcome of, e.g. a finite elements method (FEM). ESs have
been adapted to VECTOR OPTIMIZATION problems (Kursawe 92), and
they can also serve as a heuristic for NP-complete combinatorial
problems like the TRAVELLING SALESMAN PROBLEM or problems with a
noisy or changing response surface.
References
Kursawe, F. (1992) " Evolution strategies for vector
optimization", Taipei, National Chiao Tung University, 187-193.
Kursawe, F. (1994) " Evolution strategies: Simple models of
natural processes?", Revue Internationale de Systemique, France
(to appear).
Rechenberg, I. (1973) "Evolutionsstrategie: Optimierung
technischer Systeme nach Prinzipien der biologischen Evolution",
Stuttgart: Fromman-Holzboog.
Schwefel, H.-P. (1977) "Numerische Optimierung von
Computermodellen mittels der Evolutionsstrategie", Basel:
Birkhaeuser.
Schwefel, H.-P. (1987) "Collective Phaenomena in Evolutionary
Systems", 31st Annu. Meet. Inter'l Soc. for General System
Research, Budapest, 1025-1033.
------------------------------
Subject: Q1.4: What's a Classifier System (CFS)?
The name of the Game
First, a word on naming conventions is due, for no other paradigm of
EC has undergone more changes to its name space than this one.
Initially, Holland called his cognitive models "Classifier Systems"
abbrv. with CS, and sometimes CFS, as can be found in [GOLD89].
Whence Riolo came into play in 1986 and Holland added a reinforcement
component to the overall design of a CFS, that emphasized its ability
to learn. So, the word "learning" was prepended to the name, to make:
"Learning Classifier Systems" (abbrv. to LCS). On October 6-9, 1992
the "1st Inter'l Workshop on Learning Classifier Systems" took place
at the NASA Johnson Space Center, Houston, TX. A summary of this
"summit" of all leading researchers in LCS can be found on ENCORE
(See Q15.3) in file CFS/papers/lcs92.ps.gz
Today, the story continues, LCSs are sometimes subsumed under a "new"
machine learning paradigm called "Evolutionary Reinforcement
Learning" or ERL for short, incorporating LCSs, "Q-Learning", devised
by Watkins (1989), and a paradigm of the same name, devised by Ackley
and Littman [ALIFEIII].
And then, this latter statement is really somewhat confusing, as
Marco Dorigo has pointed out in a letter to editors of this guide,
since Q-Learning has no evolutionary component. So please let the
Senior Editor explain: When I wrote this part of the guide, I just
had in mind that Q-Learning would make for a pretty good replacement
of Holland's bucket-brigade algorithm, so I used this litte
speculation to see what comes out of it; in early December 95, almost
two years later, it has finally caught Marco's attention. But
meanwhile, I have been proven right: Wilson has suggested to use Q-
Learning in CLASSIFIER SYSTEM (Wilson 1994) and Dorigo & Bersini
(1994) have shown that Q-Learning and the bucket-brigade are truly
equivalent concepts.
We would therefore be allowed to call a CFS that uses Q-Learning for
rule discovery, rather than a bucket-brigade, a Q-CFS, Q-LCS, or Q-
CS; in any case would the result be subsumed under the term ERL, even
if Q-Learning itself is not an EVOLUTIONARY ALGORITHM!
Interestingly, Wilson called his system ZCS (apparantly no "Q"
inside), while Dorigo & Bersini called their system a D-Max-VSCS, or
"discounted max very simple classifier system" (and if you know Q-
Learning at least the D-Max part of the name will remind you of that
algorithm). The latter paper can be found on Encore (see Q15.3) in
file CFS/papers/sab94.ps.gz
And by the way in [HOLLAND95] the term "classifier system" is not
used anymore. You cannot find it in the index. Its a gone! Holland
now stresses the adaptive component of his invention, and simply
calls the resulting systems adaptive agents. These agents are then
implemented within the framework of his recent invention called ECHO.
(See http://www.santafe.edu/projects/echo for more.)
Alwyn Barry's LCS Web has a great deal of information on LCS. See:
http://www.csm.uwe.ac.uk/~ambarry/LCSWEB/
On Schema Processors and ANIMATS
So, to get back to the question above, "What are CFSs?", we first
might answer, "Well, there are many interpretations of Holland's
ideas...what do you like to know in particular?" And then we'd start
with a recitation from [HOLLAND75], [HOLLAND92], and explain all the
SCHEMA processors, the broadcast language, etc. But, we will take a
more comprehensive, and intuitive way to understand what CLASSIFIER
SYSTEMs are all about.
The easiest road to explore the very nature of classifier systems, is
to take the animat (ANIMAl + ROBOT = ANIMAT) "lane" devised by Booker
(1982) and later studied extensively by Wilson (1985), who also
coined the term for this approach. Work continues on animats but is
often regarded as ARTIFICIAL LIFE rather than EVOLUTIONARY
COMPUTATION. This thread of research has even its own conference
series: "Simulation of Adaptive Behavior (SAB)" (cf Q12), including
other notions from machine learning, connectionist learning,
evolutionary robotics, etc. [NB: the latter is obvious, if an animat
lives in a digital microcosm, it can be put into the real world by
implantation into an autonomous robot vehicle, that has
sensors/detectors (camera eyes, whiskers, etc.) and effectors
(wheels, robot arms, etc.); so all that's needed is to use our
algorithm as the "brain" of this vehicle, connecting the hardware
parts with the software learning component. For a fascinating intro
to the field see, e.g. Braitenberg (1984)]
classifier systems, however, are yet another offspring of John
Holland's aforementioned book, and can be seen as one of the early
applications of GAs, for CFSs use this EVOLUTIONARY ALGORITHM to
adapt their behavior toward a changing ENVIRONMENT, as is explained
below in greater detail.
Holland envisioned a cognitive system capable of classifying the
goings on in its environment, and then reacting to these goings on
appropriately. So what is needed to build such a system? Obviously,
we need (1) an environment; (2) receptors that tell our system about
the goings on; (3) effectors, that let our system manipulate its
environment; and (4) the system itself, conveniently a "black box" in
this first approach, that has (2) and (3) attached to it, and "lives"
in (1).
In the animat approach, (1) usually is an artificially created
digital world, e.g. in Booker's Gofer system, a 2 dimensional grid
that contains "food" and "poison". And the Gofer itself, that walks
across this grid and tries (a) to learn to distinguish between these
two items, and (b) survive well fed.
Much the same for Wilson's animat, called "*". Yes, its just an
asterisk, and a "Kafka-esque naming policy" is one of the sign posts
of the whole field; e.g. the first implementation by Holland and
Reitmann 1978 was called CS-1, (cognitive system 1); Smith's Poker
player LS-1 (1980) followed this "convention". Riolo's 1988 LCS
implementations on top of his CFS-C library (cf Q20), were dubbed
FSW-1 (Finite State World 1), and LETSEQ-1 (LETter SEQuence predictor
1).
So from the latter paragraph we can conclude that environment can
also mean something completely different (e.g. an infinite stream of
letters, time serieses, etc.) than in the animat approach, but
anyway; we'll stick to it, and go on.
Imagine a very simple animat, e.g. a simplified model of a frog.
Now, we know that frogs live in (a) Muppet Shows, or (b) little
ponds; so we chose the latter as our demo environment (1); and the
former for a non-Kafka-esque name of our model, so let's dub it
"Kermit".
Kermit has eyes, i.e. sensorial input detectors (2); hands and legs,
i.e. environment-manipulating effectors (3); is a spicy-fly-
detecting-and-eating device, i.e. a frog (4); so we got all the 4
pieces needed.
Inside the Black Box
The most primitive "black box" we can think of is a computer. It has
inputs (2), and outputs (3), and a message passing system inbetween,
that converts (i.e., computes), certain input messages into output
messages, according to a set of rules, usually called the "program"
of that computer. From the theory of computer science, we now borrow
the simplest of all program structures, that is something called
"production system" or PS for short. A PS has been shown to be
computationally complete by Post (1943), that's why it is sometimes
called a "Post System", and later by Minsky (1967). Although it
merely consists of a set of if-then rules, it still resembles a full-
fledged computer.
We now term a single "if-then" rule a "classifier", and choose a
representation that makes it easy to manipulate these, for example by
encoding them into binary strings. We then term the set of
classifiers, a "classifier population", and immediately know how to
breed new rules for our system: just use a GA to generate new
rules/classifiers from the current POPULATION!
All that's left are the messages floating through the black box.
They should also be simple strings of zeroes and ones, and are to be
kept in a data structure, we call "the message list".
With all this given, we can imagine the goings on inside the black
box as follows: The input interface (2) generates messages, i.e., 0/1
strings, that are written on the message list. Then these messages
are matched against the condition-part of all classifiers, to find
out which actions are to be triggered. The message list is then
emptied, and the encoded actions, themselves just messages, are
posted to the message list. Then, the output interface (3) checks
the message list for messages concerning the effectors. And the cycle
restarts.
Note, that it is possible in this set-up to have "internal messages",
because the message list is not emptied after (3) has checked; thus,
the input interface messages are added to the initially empty list.
(cf Algorithm CFS, LCS below)
The general idea of the CFS is to start from scratch, i.e., from
tabula rasa (without any knowledge) using a randomly generated
classifier population, and let the system learn its program by
induction, (cf Holland et al. 1986), this reduces the input stream to
recurrent input patterns, that must be repeated over and over again,
to enable the animat to classify its current situation/context and
react on the goings on appropriately.
What does it need to be a frog?
Let's take a look at the behavior emitted by Kermit. It lives in its
digital microwilderness where it moves around randomly. [NB: This
seemingly "random" behavior is not that random at all; for more on
instinctive, i.e., innate behavior of non-artificial animals see,
e.g. Tinbergen (1951)]
Whenever a small flying object appears, that has no stripes, Kermit
should eat it, because its very likely a spicy fly, or other flying
insect. If it has stripes, the insect is better left alone, because
Kermit had better not bother with wasps, hornets, or bees. If Kermit
encounters a large, looming object, it immediately uses its effectors
to jump away, as far as possible.
So, part of these behavior patterns within the "pond world", in AI
sometimes called a "frame," from traditional knowledge representation
techniques, Rich (1983), can be expressed in a set of "if <condition>
then <action>" rules, as follows:
IF small, flying object to the left THEN send @
IF small, flying object to the right THEN send %
IF small, flying object centered THEN send $
IF large, looming object THEN send !
IF no large, looming object THEN send *
IF * and @ THEN move head 15 degrees left
IF * and % THEN move head 15 degrees right
IF * and $ THEN move in direction head pointing
IF ! THEN move rapidly away from direction head pointing
Now, this set of rules has to be encoded for use within a CLASSIFIER
SYSTEM. A possible encoding of the above rule set in CFS-C (Riolo)
classifier terminology. The condition part consists of two
conditions, that are combined with a logical AND, thus must be met
both to trigger the associated action. This structure needs a NOT
operation, (so we get NAND, and know from hardware design, that we
can build any computer solely with NANDs), in CFS-C this is denoted
by the `~' prefix character (rule #5).
IF THEN
0000, 00 00 00 00
0000, 00 01 00 01
0000, 00 10 00 10
1111, 01 ## 11 11
~1111, 01 ## 10 00
1000, 00 00 01 00
1000, 00 01 01 01
1000, 00 10 01 10
1111, ## ## 01 11
Obviously, string `0000' denotes small, and `00' in the fist part of
the second column, denotes flying. The last two bits of column #2
encode the direction of the object approaching, where `00' means
left, `01' means right, etc.
In rule #4 a the "don't care symbol" `#' is used, that matches `1'
and `0', i.e., the position of the large, looming object, is
completely arbitrary. A simple fact, that can save Kermit's
(artificial) life.
PSEUDO CODE (Non-Learning CFS)
Algorithm CFS is
// start with an initial time
t := 0;
// an initially empty message list
initMessageList ML (t);
// and a randomly generated population of classifiers
initClassifierPopulation P (t);
// test for cycle termination criterion (time, fitness, etc.)
while not done do
// increase the time counter
t := t + 1;
// 1. detectors check whether input messages are present
ML := readDetectors (t);
// 2. compare ML to the classifiers and save matches
ML' := matchClassifiers ML,P (t);
// 3. process new messages through output interface
ML := sendEffectors ML' (t);
od
end CFS.
To convert the previous, non-learning CFS into a learning CLASSIFIER
SYSTEM, LCS, as has been proposed in Holland (1986), it takes two
steps:
(1) the major cycle has to be changed such that the activation of
each classifier depends on some additional parameter, that can
be modified as a result of experience, i.e. reinforcement from
the ENVIRONMENT;
(2) and/or change the contents of the classifier list, i.e.,
generate new classifiers/rules, by removing, adding, or
combining condition/action-parts of existing classifiers.
The algorithm thus changes accordingly:
PSEUDO CODE (Learning CFS)
Algorithm LCS is
// start with an initial time
t := 0;
// an initially empty message list
initMessageList ML (t);
// and a randomly generated population of classifiers
initClassifierPopulation P (t);
// test for cycle termination criterion (time, fitness, etc.)
while not done do
// increase the time counter
t := t + 1;
// 1. detectors check whether input messages are present
ML := readDetectors (t);
// 2. compare ML to the classifiers and save matches
ML' := matchClassifiers ML,P (t);
// 3. highest bidding classifier(s) collected in ML' wins the
// "race" and post the(ir) message(s)
ML' := selectMatchingClassifiers ML',P (t);
// 4. tax bidding classifiers, reduce their strength
ML' := taxPostingClassifiers ML',P (t);
// 5. effectors check new message list for output msgs
ML := sendEffectors ML' (t);
// 6. receive payoff from environment (REINFORCEMENT)
C := receivePayoff (t);
// 7. distribute payoff/credit to classifiers (e.g. BBA)
P' := distributeCredit C,P (t);
// 8. Eventually (depending on t), an EA (usually a GA) is
// applied to the classifier population
if criterion then
P := generateNewRules P' (t);
else
P := P'
od
end LCS.
What's the problem with CFSs?
Just to list the currently known problems that come with CFSs, would
take some additional pages; therefore only some interesting papers
dealing with unresolved riddles are listed; probably the best paper
containing most of these is the aforementioned summary of the LCS
Workshop:
Smith, R.E. (1992) "A report on the first Inter'l Workshop on LCSs"
avail. from ENCORE (See Q15.3) in file CFS/papers/lcs92.ps.gz
Other noteworthy critiques on LCSs include:
Wilson, S.W. (1987) "Classifier Systems and the Animat Problem"
Machine Learning, 2.
Wilson, S.W. (1988) "Bid Competition and Specificity Reconsidered"
Complex Systems, 2(5):705-723.
Wilson, S.W. & Goldberg, D.E. (1989) "A critical review of classifier
systems" [ICGA89], 244-255.
Goldberg, D.E., Horn, J. & Deb, K. (1992) "What makes a problem hard
for a classifier system?" (containing the Goldberg citation below)
is also available from Encore (See Q15.3) in file
CFS/papers/lcs92-2.ps.gz
Dorigo, M. (1993) "Genetic and Non-genetic Operators in ALECSYS"
Evolutionary Computation, 1(2):151-164. The technical report, the
journal article is based on is avail. from Encore (See Q15.3) in file
CFS/papers/icsi92.ps.gz
Smith, R.E. Forrest, S. & Perelson, A.S. (1993) "Searching for
Diverse, Cooperative POPULATIONs with Genetic Algorithms"
Evolutionary Computation, 1(2):127-149.
Conclusions?
Generally speaking: "There's much to do in CFS research!"
No other notion of EC provides more space to explore and if you are
interested in a PhD in the field, you might want to take a closer
look at CFS. However, be warned!, to quote Goldberg: "classifier
systems are a quagmire---a glorious, wondrous, and inventing
quagmire, but a quagmire nonetheless."
References
Booker, L.B. (1982) "Intelligent behavior as an adaption to the task
environment" PhD Dissertation, Univ. of Michigan, Logic of Computers
Group, Ann Arbor, MI.
Braitenberg, V. (1984) "Vehicles: Experiments in Synthetic
Psychology" Boston, MA: MIT Press.
Dorigo M. & H. Bersini (1994). "A Comparison of Q-Learning and
Classifier Systems." Proceedings of From Animals to Animats, Third
International Conference on SIMULATION of Adaptive Behavior (SAB94),
Brighton, UK, D.Cliff, P.Husbands, J.-A.Meyer and S.W.Wilson (Eds.),
MIT Press, 248-255.
http://iridia.ulb.ac.be/dorigo/dorigo/conferences/IC.11-SAB94.ps.gz
Holland, J.H. (1986) "Escaping Brittleness: The possibilities of
general-purpose learning algorithms applied to parallel rule-based
systems". In: R.S. Michalski, J.G. Carbonell & T.M. Mitchell (eds),
Machine Learning: An Artificial Intelligence approach, Vol II,
593-623, Los Altos, CA: Morgan Kaufman.
Holland, J.H., et al. (1986) "Induction: Processes of Inference,
Learning, and Discovery", Cambridge, MA: MIT Press.
Holland, J.H. (1992) "Adaptation in natural and artificial systems"
Boston, MA: MIT Press.
Holland, J.H. (1995) "Hidden Order: How adaptation builds complexity"
Reading, MA: Addison-Wesley. [HOLLAND95]:
Holland, J.H. & Reitman, J.S. (1978) "Cognitive Systems based on
Adaptive Algorithms" In D.A. Waterman & F.Hayes-Roth, (eds) Pattern-
directed inference systems. NY: Academic Press.
Minsky, M.L. (1961) "Steps toward Artificial Intelligence"
Proceedings IRE, 49, 8-30. Reprinted in E.A. Feigenbaum & J. Feldman
(eds) Computers and Thought, 406-450, NY: McGraw-Hill, 1963.
Minsky, M.L. (1967) "Computation: Finite and Infinite Machines"
Englewood Cliffs, NJ: Prentice-Hall.
Post, Emil L. (1943) "Formal reductions of the general combinatorial
decision problem" American Journal of Mathematics, 65, 197-215.
Rich, E. (1983) "Artificial Intelligence" NY: McGraw-Hill.
Tinbergen, N. (1951) "The Study of Instinct" NY: Oxford Univ. Press.
Watkins, C. (1989) "Learning from Delayed Rewards" PhD Dissertation,
Department of Psychology, Cambridge Univ., UK.
Wilson, S.W. (1985) "Knowledge growth in an artificial animal" in
[ICGA85], 16-23.
Wilson, S.W. (1994) "ZCS: a zeroth level classifier system" in EC
2(1), 1-18.
------------------------------
Subject: Q1.5: What's Genetic Programming (GP)?
GENETIC PROGRAMMING is the extension of the genetic model of learning
into the space of programs. That is, the objects that constitute the
POPULATION are not fixed-length character strings that encode
possible solutions to the problem at hand, they are programs that,
when executed, "are" the candidate solutions to the problem. These
programs are expressed in genetic programming as parse trees, rather
than as lines of code. Thus, for example, the simple program "a + b
* c" would be represented as:
+
/ \
a *
/ \
b c
or, to be precise, as suitable data structures linked together to
achieve this effect. Because this is a very simple thing to do in the
programming language Lisp, many GPers tend to use Lisp. However, this
is simply an implementation detail. There are straightforward methods
to implement GP using a non-Lisp programming environment.
The programs in the population are composed of elements from the
FUNCTION SET and the TERMINAL SET, which are typically fixed sets of
symbols selected to be appropriate to the solution of problems in the
domain of interest.
In GP the CROSSOVER operation is implemented by taking randomly
selected subtrees in the INDIVIDUALs (selected according to FITNESS)
and exchanging them.
It should be pointed out that GP usually does not use any MUTATION as
a GENETIC OPERATOR.
More information is available in the GP mailing list FAQ. (See
Q15.2) and from http://smi-web.stanford.edu/people/koza/
------------------------------
Copyright (c) 1993-2000 by J. Heitkoetter and D. Beasley, all rights
reserved.
This FAQ may be posted to any USENET newsgroup, on-line service, or
BBS as long as it is posted in its entirety and includes this
copyright statement. This FAQ may not be distributed for financial
gain. This FAQ may not be included in commercial collections or
compilations without express permission from the author.
End of ai-faq/genetic/part2
***************************
--
David Beasley
Last-Modified: 4/12/01
Issue: 9.1
Important note: Do NOT send email to the cs.cf.ac.uk address above: it will
be ignored. Corrections and other correspondence should be sent to
david....@iee.org
TABLE OF CONTENTS OF PART 3
Q2: What applications of EAs are there?
Q3: Who is concerned with EAs?
Q4: How many EAs exist? Which?
Q4.1: What about Alife systems, like Tierra and VENUS?
Q5: What about all this Optimization stuff?
----------------------------------------------------------------------
Subject: Q2: What applications of EAs are there?
In principle, EAs can compute any computable function, i.e.
everything a normal digital computer can do.
But EAs are especially badly suited for problems where efficient ways
of solving them are already known, (unless these problems are
intended to serve as benchmarks). Special purpose algorithms, i.e.
algorithms that have a certain amount of problem domain knowledge
hard coded into them, will usually outperform EAs, so there is no
black magic in EC. EAs should be used when there is no other known
problem solving strategy, and the problem domain is NP-complete.
That's where EAs come into play: heuristically finding solutions
where all else fails.
Following is an incomplete (sic!) list of successful EA
applications:
ARTIFICIAL LIFE
ARTIFICIAL LIFE (ALIFE) systems attempt to simulate the kind of
behaviour exhibited by real, living creatures. Not all Artificial
Life systems employ EVOLUTIONARY ALGORITHMs (see Q4.1).
Framsticks
Framsticks is a three-dimensional life SIMULATION project. Both the
physical structure of creatures and their control systems are
evolved. Evolutionary algorithms are used with SELECTION, CROSSOVER
and MUTATION. Finite element methods are used for simulation. Both
spontaneous and directed EVOLUTIONs are possible.
This system uses the standard EA framework to evolve 3D agents
equipped with neural networks. It has proved to be an attractive tool
for people who want to learn about the way evolutionary OPTIMIZATION
techniques work.
This is shareware, but all the evolutionary features are available
free. The project is open, and developers can take part in it, and
also conduct their own experiments (i.e. using their own GENETIC
OPERATORs). There are links to the scientific papers on the web
page, as well as the detailed program documentation. The software is
quite general and can be used to study a range of problems, including
coevolution of body and brain.
For more details, see: http://www.frams.poznan.pl/
BIOCOMPUTING
Biocomputing, or Bioinformatics, is the field of biology dedicated to
the automatic analysis of experimental data (mostly sequencing data).
Several approaches to specific biocomputing problems have been
described that involve the use of GA, GP and simulated annealing.
General information about biocomputing (software, databases, misc.)
can be found on the server of the European Bioinformatics Institute:
http://www.ebi.ac.uk/ebi_home.html ENCORE has a good selection of
pointers related to this subject. VSCN provides a detailed online
course on bioinformatics: http://www.techfak.uni-
bielefeld.de/bcd/Curric/welcome.html
There are three main domains to which GA have been applied in
Bioinformatics: protein folding, RNA folding, sequence alignment.
Protein Folding
Proteins are one of the essential components of any form of life.
They are made of twenty different types of amino acid. These amino
acids are chained together in order to form the protein that can
contain from a few to several thousands residues. In most of the
cases, the properties and the function of a protein are a result of
its three dimensional structure. It seems that in many cases this
structure is a direct consequence of the sequence. Unfortunately, it
is still very difficult/impossible to deduce the three dimensional
structure, knowing only the sequence. A part of the VSCN on-line
bioinformatics course is dedicated to the use of GAs in Protein
Folding Prediction. It contains an extensive bibliography and a
detailed presentation of the subject with LOTS of explanations and
on-line papers. The URL is: http://www.techfak.uni-
bielefeld.de/bcd/Curric/ProtEn/contents.html
Koza [KOZA92] gives one example of GP applied to Protein Folding.
Davis [DAVIS91] gives an example of DNA conformation prediction (a
closely related problem) in his Handbook of GAs.
RNA Folding
Describing the tertiary structure of an RNA molecule, is about as
hard as for a protein, but describing the intermediate structure
(secondary structure) is somehow easier because RNA molecules are
using the same pairing rules as DNA, (Watson and Crick base pairing).
There exist deterministic algorithms that given a set of constraints
(rules), compute the more stable structure, but: (a) their time and
memory requirement increase quadratically or more with the length of
the sequences, and (b) they require simplified rules. Lots of effort
has recently been put into applying GAs to this problem, and several
papers can be found (on-line if your institute subscribes to these
journals):
A genetic Algorithm Based Molecular Modelling Technique For RNA Stem-
loop Structures H. Ogata, Y. Akiyama and M Kanehisa, Nucleic Acid
Research, 1995, vol 23,3 419-426
An Annealing Mutation Operator in the GA for RNA folding B.A Shapiro
and J. C. Wu, CABIOS, 1996, vol 12, 3, 171-180
The computer Simulation of RNA Folding Pathway Using a Genetic
Algorithm A.P. Gultyaev, F.D.H van Batenburg and C. W. A. Pleij in
Journal of Molecular Biology, 1995, vol 250 37-51
Simulated Annealing has also been applied successfully to this
problem:
Description of RNA folding by SA M. Schmitz and G. Steger in Journal
of Molecular Biology, 1995, 255, 245-266
Sequence Alignments
Sequence Alignment is another important problem of Bioinformatics.
The aim is to align together several related sequences (from two to
hundreds) given a cost function. For the most widely used cost
functions, the problem has been shown to be NP-complete. Several
attempts have been made using SA:
Multiple Sequence Alignment Using SA J. Kim, Sakti Pramanik and M.J.
Chung, CABIOS, 1994, vol 10, 4, 419-426
Multiple Sequence Alignment by Parallel SA M. Isshikawa, T. Koya and
al, CABIOS, 1993,vol 9, 3, 267-273
SAM, software which uses Hidden Markov Models for Multiple Sequence
Alignment, can use SA to train the model. Several papers have been
published on SAM. The software, documentation and an extensive
bibliography can be found in:
http://www.cse.ucsc.edu/research/compbio/sam.html
More recently, various software using different methods like Gibbs
sampling or GAs has been developed:
A Gibbs Sampling Strategy for Multiple Alignment C.E. Lawrence, S. F.
Altschull and al, Science, October 1993, vol 262, 208-214
SAGA: Sequence Alignment by Genetic Algorithm C. Notredame and D.G.
Higgins, Nucleic Acid Research, 1995, vol 24, 8,
1515-1524
A beta release of SAGA (along with the paper) is available on the
European Bioinformatics Institute anonymous FTP server:
ftp.ebi.ac.uk/pub/software/unix/saga.tar.Z
CELLULAR PROGRAMMING: Evolution of Parallel Cellular Machines
Nature abounds in systems involving the actions of simple, locally-
interacting components, that give rise to coordinated global
behavior. These collective systems have evolved by means of natural
SELECTION to exhibit striking problem-solving capacities, while
functioning within a complex, dynamic ENVIRONMENT. Employing simple
yet versatile parallel cellular models, coupled with EVOLUTIONARY
COMPUTATION techniques, cellular programming is an approach for
constructing man-made systems that exhibit characteristics such as
those manifest by their natural counterparts.
Parallel cellular machines hold potential both scientifically, as
vehicles for studying phenomena of interest in areas such as complex
adaptive systems and ARTIFICIAL LIFE, as well as practically,
enabling the construction of novel systems, endowed with
evolutionary, reproductive, regenerative, and learning capabilities.
Web site: http://lslwww.epfl.ch/~moshes/cp.html
References:
Sipper, M. (1997) "Evolution of Parallel Cellular Machines: The
Cellular Programming Approach", Springer-Verlag, Heidelberg.
Sipper, M. (1996) "Co-evolving Non-Uniform Cellular Automata to
Perform Computations", Physica D, 92, 193-208.
Sipper, M. and Ruppin, E. (1997) "Co-evolving architectures for
cellular machines", Physica D, 99, 428-441.
Sipper, M. and Tomassini, M. (1996) "Generating Parallel Random
Number Generators By Cellular Programming", International Journal of
Modern Physics C, 7(2), 181-190.
Sipper, M. (1997) "Evolving Uniform and Non-uniform Cellular Automata
Networks", in Annual Reviews of Computational Physics, D. Stauffer
(ed)
Evolvable Hardware
The idea of evolving machines, whose origins can be traced to the
cybernetics movement of the 1940s and the 1950s, has recently
resurged in the form of the nascent field of bio-inspired systems and
evolvable hardware. The field draws on ideas from the EVOLUTIONARY
COMPUTATION domain as well as on novel hardware innovations.
Recently, the term evolware has been used to describe such evolving
ware, with current implementations centering on hardware, while
raising the possibility of using other forms in the future, such as
bioware. The inaugural workshop, Towards Evolvable Hardware, took
place in Lausanne, in October 1995, followed by the First
International Conference on Evolvable Systems: From Biology to
Hardware (ICES96) held in Japan, in October 1996. Another major event
in the field, ICES98, was held in Lausanne, Switzerland, in September
1998.
References:
Sipper, M. et al (1997) "A Phylogenetic, Ontogenetic, and Epigenetic
View of Bio-Inspired Hardware Systems", IEEE Transactions on
Evolutionary Computation, 1(1).
Sanchez, E. and Tomassini, M. (eds) (1996) "Towards Evolvable
Hardware", Springer-Verlag, Lecture Notes in Computer Science, 1062.
Higuchi, T. et al (1997) "Proceedings of First International
Conference on Evolvable Systems: From Biology to Hardware (ICES96)",
Springer-Verlag, Lecture Notes in Computer Science.
GAME PLAYING
GAs can be used to evolve behaviors for playing games. Work in
evolutionary GAME THEORY typically surrounds the EVOLUTION of a
POPULATION of players who meet randomly to play a game in which they
each must adopt one of a limited number of moves. (Maynard-Smith
1982). Let's suppose it is just two moves, X and Y. The players
receive a reward, analogous to Darwinian FITNESS, depending on which
combination of moves occurs and which move they adopted. In more
complicated models there may be several players and several moves.
The players iterate such a game a series of times, and then move on
to a new partner. At the end of all such moves, the players will have
a cumulative payoff, their fitness. This fitness can then be used to
generate a new population.
The real key in using a GA is to come up with an encoding to
represent player's strategies, one that is amenable to CROSSOVER and
to MUTATION. Possibilities are to suppose at each iteration a player
adopts X with some probability (and Y with one minus such). A player
can thus be represented as a real number, or a bit-string suitably
interpreted as a probability
An alternative characterisation is to model the players as Finite
State Machines, or Finite Automata (FA). These can be though of as a
simple flow chart governing behaviour in the "next" play of the game
depending upon previous plays. For example:
100 Play X
110 If opponent plays X go to 100
120 Play Y
130 If opponent plays X go to 100 else go to 120
represents a strategy that does whatever its opponent did last, and
begins by playing X, known as "Tit-For-Tat." (Axelrod 1982). Such
machines can readily be encoded as bit-strings. Consider the encoding
"1 0 1 0 0 1" to represent TFT. The first three bits, "1 0 1" are
state 0. The first bit, "1" is interpreted as "Play X." The second
bit, "0" is interpreted as "if opponent plays X go to state 1," the
third bit, "1", is interpreted as "if the opponent plays Y, go to
state 1." State 1 has a similar interpretation. Crossing over such
bit-strings always yields valid strategies.
SIMULATIONs in the Prisoner's dilemma have been undertaken (Axelrod
1987, Fogel 1993, Miller 1989) of these machines.
Alternative representations of game players include CLASSIFIER
SYSTEMs (Marimon, McGrattan and Sargent 1990, [GOLD89]), and Neural-
networks (Fogel and Harrald 1994), though not necessarily with a GA.
(Fogel 1993), and Fogel and Harrald 1994 use an Evolutionary
Program). Chellapilla and Fogel (1999) have evolved a neural network
which can play checkers (draughts) at near expert level.
Other methods of evolving a population can be found in Lindgren 1991,
Glance and Huberman 1993 and elsewhere.
A GA for playing the game "Mastermind" has been produced. See
http://kal-el.ugr.es/mastermind
References.
Axelrod, R. (1987) ``The Evolution of Strategies in the Repeated
Prisoner's Dilemma,'' in [DAVIS91]
Axelrod, R (?) ``The Complexity of Cooperation'' (See the web site,
which includes code to implement tournaments:
http://pscs.physics.lsa.umich.edu/Software/ComplexCoop.html )
Chellapilla, K. and Fogel, D.B. (1999) ``Evolution, neural networks,
games, and intelligence'' , Proc. IEEE, Sept., pp. 1471-1496.
Miller, J.H. (1989) ``The Coevolution of Automata in the Repeated
Prisoner's Dilemma'' Santa Fe Institute Working Paper 89-003.
Marimon, Ramon, Ellen McGrattan and Thomas J. Sargent (1990) ``Money
as a Medium of Exchange in an Economy with Artificially Intelligent
Agents'' Journal of Economic Dynamics and Control 14, pp. 329--373.
Maynard-Smith, (1982) Evolution and the Theory of Games, CUP.
Lindgren, K. (1991) ``Evolutionary Phenomena in Simple Dynamics,'' in
[ALIFEI].
Holland, J.H and John Miller (1990) ``Artificially Adaptive Agents in
Economic Theory,'' American Economic Review: Papers and Proceedings
of the 103rd Annual Meeting of the American Economics Association:
365--370.
Huberman, Bernado, and Natalie S. Glance (1993) "Diversity and
Collective Action" in H. Haken and A. Mikhailov (eds.)
Interdisciplinary Approaches to Nonlinear Systems, Springer.
Fogel (1993) "Evolving Behavior in the Iterated Prisoner's Dilemma"
Evolutionary Computation 1:1, 77-97
Fogel, D.B. and Harrald, P. (1994) ``Evolving Complex Behaviour in
the Iterated Prisoner's Dilemma,'' Proceedings of the Fourth Annual
Meetings of the Evolutionary Programming Society, L.J. Fogel and A.W.
Sebald eds., World Science Press.
Lindgren, K. and Nordahl, M.G. "Cooperation and Community Structure
in Artificial Ecosystems", Artificial Life, vol 1:1&2, 15-38
Stanley, E.A., Ashlock, D. and Tesfatsion, L. (1994) "Iterated
Prisoners Dilemma with Choice and Refusal of Partners in [ALIFEIII]
131-178
JOB-SHOP SCHEDULING
The Job-Shop Scheduling Problem (JSSP) is a very difficult NP-
complete problem which, so far, seems best addressed by sophisticated
branch and bound search techniques. GA researchers, however, are
continuing to make progress on it. (Davis 85) started off GA
research on the JSSP, (Whitley 89) reports on using the edge
RECOMBINATION operator (designed initially for the TSP) on JSSPs too.
More recent work includes (Nakano 91),(Yamada & Nakano 92), (Fang et
al. 93). The latter three report increasingly better results on
using GAs on fairly large benchmark JSSPs (from Muth & Thompson 63);
neither consistently outperform branch & bound search yet, but seem
well on the way. A crucial aspect of such work (as with any GA
application) is the method used to encode schedules. An important
aspect of some of the recent work on this is that better results have
been obtained by rejecting the conventional wisdom of using binary
representations (as in (Nakano 91)) in favor of more direct
encodings. In (Yamada & Nakano 92), for example, a GENOME directly
encodes operation completion times, while in (Fang et al. 93) genomes
represent implicit instructions for building a schedule. The success
of these latter techniques, especially since their applications are
very important in industry, should eventually spawn advances in GA
theory.
Concerning the point of using GAs at all on hard job-shop scheduling
problems, the same goes here as suggested above for `Timetabling':
The GA approach enables relatively arbitrary constraints and
objectives to be incorporated painlessly into a single OPTIMIZATION
method. It is unlikely that GAs will outperform specialized
knowledge-based and/or conventional OR-based approaches to such
problems in terms of raw solution quality, however GAs offer much
greater simplicity and flexibility, and so, for example, may be the
best method for quick high-quality solutions, rather than finding the
best possible solution at any cost. Also, of course, hybrid methods
will have a lot to offer, and GAs are far easier to parallelize than
typical knowledge-based/OR methods.
Similar to the JSSP is the Open Shop Scheduling Problem (OSSP).
(Fang et al. 93) reports an initial attempt at using GAs for this.
Ongoing results from the same source shows reliable achievement of
results within less than 0.23% of optimal on moderately large OSSPs
(so far, up to 20x20), including an improvement on the previously
best known solution for a benchmark 10x10 OSSP. A simpler form of job
shop problem is the Flow-Shop Sequencing problem; recent successful
work on applying GAs to this includes (Reeves 93)."
Other scheduling problems
In contrast to job shop scheduling some maintenance scheduling
problems consider which activities to schedule within a planned
maintenance period, rather than seeking to minimise the total time
taken by the activities. The constraints on which parts may be taken
out of service for maintenance at particular times may be very
complex, particularly as they will in general interact. Some initial
work is given in (Langdon, 1995).
References
Davis, L. (1985) "Job-Shop Scheduling with Genetic Algorithms",
[ICGA85], 136-140.
Muth, J.F. & Thompson, G.L. (1963) "Industrial Scheduling". Prentice
Hall, Englewood Cliffs, NJ, 1963.
Nakano, R. (1991) "Conventional Genetic Algorithms for Job-Shop
Problems", [ICGA91], 474-479.
Reeves, C.R. (1993) "A Genetic Algorithm for Flowshop Sequencing",
Coventry Polytechnic Working Paper, Coventry, UK.
Whitley, D., Starkweather, T. & D'Ann Fuquay (1989) "Scheduling
Problems and Traveling Salesmen: The Genetic Edge Recombination
Operator", [ICGA89], 133-140.
Fang, H.-L., Ross, P., & Corne D. (1993) "A Promising Genetic
Algorithm Approach to Job-Shop Scheduling, Rescheduling & Open-Shop
Scheduling Problems", [ICGA93], 375-382.
Yamada, T. & Nakano, R. (1992) "A Genetic Algorithm Applicable to
Large-Scale Job-Shop Problems", [PPSN92], 281-290.
Langdon, W.B. (1995) "Scheduling Planned Maintenance of the (UK)
National Grid", cs.ucl.ac.uk/genetic/papers/grid_aisb-95.ps
MANAGEMENT SCIENCES
"Applications of EA in management science and closely related fields
like organizational ecology is a domain that has been covered by some
EA researchers - with considerable bias towards scheduling problems.
Since I believe that EA have considerable potential for applications
outside the rather narrow domain of scheduling and related
combinatorial problems, I started collecting references about the
status quo of EA-applications in management science. This report
intends to make available my findings to other researchers in the
field. It is a short overview and lists some 230 references to
current as well as finished research projects. [..]
"At the end of the paper, a questionnaire has been incorporated that
may be used for this purpose. Other comments are also appreciated."
--- from the Introduction of (Nissen 93)
References
Nissen, V. (1993) "Evolutionary Algorithms in Management Science: An
Overview and List of References", Papers on Economics and Evolution,
edited by the European Study Group for Evolutionary Economics. This
report is also avail. via anon. FTP from
ftp.gwdg.de/pub/msdos/reports/wi/earef.eps
Boulding, K.E. (1991) "What is evolutionary economics?", Journal of
Evolutionary Economics, 1, 9-17.
NON-LINEAR FILTERING
New connections between GENETIC ALGORITHMs and Non Linear Filtering
Theory have been established. GAs have already been successfully
applied to a large class of non-linear filtering problems such as
RADAR / SONAR/ GPS signal processing. This relatively new branch of
GA application has also lead to new results on the convergence of
GAs: large deviations, fluctuations...
Some preprints and references on this topic are available in the web
page: http://www-sv.cict.fr/lsp/Delmoral/index.html
The new results also points out some natural connections between:
genetic type algorithms, information theory, non-linear filtering
theory, interacting and branching particle systems.
TIMETABLING
This has been addressed quite successfully with GAs. A very common
manifestation of this kind of problem is the timetabling of exams or
classes in Universities, etc.
The first application of GAs to the timetabling problem was to build
the schedule of the teachers in an Italian high school. The
research, conducted at the Department of Electronics and Information
of Politecnico di Milano, Italy, showed that a GA was as good as Tabu
Search, and better than simulated annealing, at finding teacher
schedules satisfying a number of hard and soft constraints. The
software package developed is now in current use in some high schools
in Milano. (Colorni et al 1990)
At the Department of Artificial Intelligence, University of
Edinburgh, timetabling the MSc exams is now done using a GA (Corne et
al. 93, Fang 92). An example of the use of GAs for timetabling
classes is (Abramson & Abela 1991).
In the exam timetabling case, the FITNESS function for a GENOME
representing a timetable involves computing degrees of punishment for
various problems with the timetable, such as clashes, instances of
students having to take consecutive exams, instances of students
having (eg) three or more exams in one day, the degree to which
heavily-subscribed exams occur late in the timetable (which makes
marking harder), overall length of timetable, etc. The modular nature
of the fitness function has the key to the main potential strength of
using GAs for this sort of thing as opposed to using conventional
search and/or constraint programming methods. The power of the GA
approach is the ease with which it can handle arbitrary kinds of
constraints and objectives; all such things can be handled as
weighted components of the fitness function, making it easy to adapt
the GA to the particular requirements of a very wide range of
possible overall objectives . Very few other timetabling methods, for
example, deal with such objectives at all, which shows how difficult
it is (without GAs) to graft the capacity to handle arbitrary
objectives onto the basic "find shortest- length timetable with no
clashes" requirement. The proper way to weight/handle different
objectives in the fitness function in relation to the general GA
dynamics remains, however, an important research problem!
GAs thus offer a combination of simplicity, flexibility & speed which
competes very favorably with other approaches, but are unlikely to
outperform knowledge-based (etc) methods if the best possible
solution is required at any cost. Even then, however, hybridisation
may yield the best of both worlds; also, the ease (if the hardware is
available!) of implementing GAs in parallel enhances the possibility
of using them for good, fast solutions to very hard timetabling and
similar problems.
References
Abramson & Abela (1991) "A Parallel Genetic Algorithm for Solving the
School Timetabling Problem", Technical Report, Division of I.T.,
C.S.I.R.O, April 1991. (Division of Information Technology,
C.S.I.R.O., c/o Dept. of Communication & Electronic Engineering,
Royal Melbourne Institute of Technology, PO BOX 2476V, Melbourne
3001, Australia)
Colorni A., M. Dorigo & V. Maniezzo (1990). Genetic Algorithms And
Highly Constrained Problems: The Time-Table Case. Proceedings of the
First International Workshop on Parallel Problem Solving from Nature,
Dortmund, Germany, Lecture Notes in Computer Science 496, Springer-
Verlag, 55-59.
http://iridia.ulb.ac.be/dorigo/dorigo/conferences/IC.01-PPSN1.ps.gz
Colorni A., M. Dorigo & V. Maniezzo (1990). Genetic Algorithms: A
New Approach to the Time-Table Problem. NATO ASI Series, Vol.F 82,
COMBINATORIAL OPTIMIZATION, (Ed. M.Akguel and others), Springer-
Verlag, 235-239.
http://iridia.ulb.ac.be/dorigo/dorigo/conferences/IC.02-NATOASI90.ps.gz
Colorni A., M. Dorigo & V. Maniezzo (1990). A Genetic Algorithm to
Solve the Timetable Problem. Technical Report No. 90-060,
Politecnico di Milano, Italy.
http://iridia.ulb.ac.be/dorigo/dorigo/tec.reps/TR.01-TTP.ps.gz
Corne, D. Fang, H.-L. & Mellish, C. (1993) "Solving the Modular Exam
Scheduling Problem with Genetic Algorithms". Proc. of 6th Int'l
Conf. on Industrial and Engineering Applications of Artificial
Intelligence & Expert Systems, ISAI.
Fang, H.-L. (1992) "Investigating GAs for scheduling", MSc
Dissertation, University of Edinburgh Dept. of Artificial
Intelligence, Edinburgh, UK.
------------------------------
Subject: Q3: Who is concerned with EAs?
EVOLUTIONARY COMPUTATION attracts researchers and people of quite
dissimilar disciplines, i.e. EC is a interdisciplinary research
field:
Computer scientists
Want to find out about the properties of sub-symbolic information
processing with EAs and about learning, i.e. adaptive systems in
general.
They also build the hardware necessary to enable future EAs
(precursors are already beginning to emerge) to huge real world
problems, i.e. the term "massively parallel computation" [HILLIS92],
springs to mind.
Engineers
Of many kinds want to exploit the capabilities of EAs on many areas
to solve their application, esp. OPTIMIZATION problems.
Roboticists
Want to build MOBOTs (MOBile ROBOTs, i.e. R2D2's and #5's cousins)
that navigate through uncertain ENVIRONMENTs, without using built-in
"maps". The MOBOTS thus have to adapt to their surroundings, and
learn what they can do "move-through-door" and what they can't "move-
through-wall" on their own by "trial-and-error".
Cognitive scientists
Might view CFS as a possible apparatus to describe models of thinking
and cognitive systems.
Physicists
Use EC hardware, e.g. Hillis' (Thinking Machine Corp.'s) Connection
Machine to model real world problems which include thousands of
variables, that run "naturally" in parallel, and thus can be modelled
more easily and esp. "faster" on a parallel machine, than on a
serial "PC" one.
Biologists
Are finding EAs useful when it comes to protein folding and other
such bio-computational problems (see Q2).
EAs can also be used to model the behaviour of real POPULATIONs of
organisms. Some biologists are hostile to modeling, but an entire
community of Population Biologists arose with the 'evolutionary
synthesis' of the 1930's created by the polymaths R.A. Fisher, J.B.S.
Haldane, and S. Wright. Wright's SELECTION in small populations,
thereby avoiding local optima) is of current interest to both
biologists and ECers -- populations are naturally parallel.
A good exposition of current population Biology modeling is J.
Maynard Smith's text Evolutionary Genetics. Richard Dawkin's Selfish
Gene and Extended Phenotype are unparalleled (sic!) prose expositions
of evolutionary processes. Rob Collins' papers are excellent
parallel GA models of evolutionary processes (available in [ICGA91]
and by FTP from ftp.cognet.ucla.edu/pub/alife/papers/ ).
As fundamental motivation, consider Fisher's comment: "No practical
biologist interested in (e.g.) sexual REPRODUCTION would be led to
work out the detailed consequences experienced by organisms having
three or more sexes; yet what else should [s/]he do if [s/]he wishes
to understand why the sexes are, in fact, always
two?" (Three sexes would make for even weirder grammar, [s/]he
said...)
Chemists
And in particular biochemists and molecular chemists, are interested
in problems such as the conformational analysis of molecular clusters
and related problems in molecular sciences. The application of GAs
to molecular systems has opened an interesting area of research and
the number of chemists involved in it increases day-by-day.
Some typical research topics include:
o protein folding; o conformational analysis and energy
minimization; o docking algorithms for drug-design; o solvent site
prediction in macromolecules;
Several papers have been published in journals such as Journal of
Computational Chemistry and Journal of Computer-Aided Design.
Some interesting WWW sites related to the applications of GAs to
chemistry (or molecular science in general) include:
o http://garage.cps.msu.edu/projects/biochem/biochem.html about GAs
in biochemistry (water site prediction, drug-design and protein
folding); o
http://www.tc.cornell.edu/Edu/SPUR/SPUR94/Main/John.html about the
application of GAs to the search of conformational energy minima;
o http://cmp.ameslab.gov/cmp/CMP_Theory/gsa/gen2.html By using a
GA in combiation with a Tight-binding model, David Deaven and Kai-
Ming Ho founded fullerene cages (including C60) starting from
random coordinates.
See also Q2 for applications in biocomputing.
Philosophers
and some other really curious people may also be interested in EC for
various reasons.
------------------------------
Subject: Q4: How many EAs exist? Which?
The All Stars
There are currently 3 main paradigms in EA research: GENETIC
ALGORITHMs, EVOLUTIONARY PROGRAMMING, and EVOLUTION STRATEGIEs.
CLASSIFIER SYSTEMs and GENETIC PROGRAMMING are OFFSPRING of the GA
community. Besides this leading crop, there are numerous other
different approaches, alongside hybrid experiments, i.e. there exist
pieces of software residing in some researchers computers, that have
been described in papers in conference proceedings, and may someday
prove useful on certain tasks. To stay in EA slang, we should think
of these evolving strands as BUILDING BLOCKs, that when recombined
someday, will produce new offspring and give birth to new EA
paradigm(s).
One such interesting offspring is the Memetic Algorithm. This is a
hybrid evolutionary algorithm, which makes use of local search
operators. For details, see
http://www.densis.fee.unicamp.br/~moscato/memetic_home.html
Promising Rookies
As far as "solving complex function and COMBINATORIAL OPTIMIZATION
tasks" is concerned, Davis' work on real-valued representations and
adaptive operators should be mentioned (Davis 89). Moreover Whitley's
Genitor system incorporating ranking and "steady state" mechanism
(Whitley 89), Goldberg's "messy GAs", involves adaptive
representations (Goldberg 91), and Eshelman's CHC algorithm (Eshelman
91). For real FUNCTION OPTIMIZATION, Differential EVOLUTION seems
hard to beat in terms of convergence speed as well as simplicity:
With just three control variables, tuning is particularly easy to do.
For "the design of robust learning systems", i.e. the field
characterized by CFS, Holland's (1986) CLASSIFIER SYSTEM, with its
state-of-the-art implementation CFS-C (Riolo 88), we should note
developments in SAMUEL (Grefenstette 89), GABIL (De Jong & Spears
91), and GIL (Janikow 91).
References
Davis, L. (1989) "Adapting operator probabilities in genetic
algorithms", [ICGA89], 60-69.
De Jong K.A. & Spears W. (1991) "Learning concept classification
rules using genetic algorithms". Proc. 12th IJCAI, 651-656, Sydney,
Australia: Morgan Kaufmann.
Dorigo M. & E. Sirtori (1991)."ALECSYS: A Parallel Laboratory for
Learning Classifier Systems". Proceedings of the Fourth International
Conference on Genetic Algorithms, San Diego, California, R.K.Belew
and L.B.Booker (Eds.), Morgan Kaufmann, 296-302.
Dorigo M. (1995). "ALECSYS and the AutonoMouse: Learning to Control a
Real Robot by Distributed Classifier Systems". Machine Learning, 19,
3, 209-240.
Eshelman, L.J. et al. (1991) "Preventing premature convergence in
genetic algorithms by preventing incest", [ICGA91], 115-122.
Goldberg, D. et al. (1991) "Don't worry, be messy", [ICGA91], 24-30.
Grefenstette, J.J. (1989) "A system for learning control strategies
with genetic algorithms", [ICGA89], 183-190.
Holland, J.H. (1986) "Escaping brittleness: The possibilities of
general-purpose learning algorithms applied to parallel rule-based
systems". In R. Michalski, J. Carbonell, T. Mitchell (eds), Machine
Learning: An Artificial Intelligence Approach. Los Altos: Morgan
Kaufmann.
Janikow C. (1991) "Inductive learning of decision rules from
attribute-based examples: A knowledge-intensive Genetic Algorithm
approach". TR91-030, The University of North Carolina at Chapel Hill,
Dept. of Computer Science, Chapel Hill, NC.
Riolo, R.L. (1988) "CFS-C: A package of domain independent
subroutines for implementing classifier systems in arbitrary, user-
defined environments". Logic of computers group, Division of
computer science and engineering, University of Michigan.
Whitley, D. et al. (1989) "The GENITOR algorithm and selection
pressure: why rank-based allocation of reproductive trials is best",
[ICGA89], 116-121.
------------------------------
Subject: Q4.1: What about Alife systems, like Tierra and VENUS?
None of these are EVOLUTIONARY ALGORITHMs, but all of them use the
evolutionary metaphor as their "playing field".
Tierra
Synthetic organisms have been created based on a computer metaphor of
organic life in which CPU time is the ``energy'' resource and memory
is the ``material'' resource. Memory is organized into informational
patterns that exploit CPU time for self-replication. MUTATION
generates new forms, and EVOLUTION proceeds by natural SELECTION as
different GENOTYPEs compete for CPU time and memory space.
Observation of nature shows that evolution by natural selection is
capable of both OPTIMIZATION and creativity. Artificial models of
evolution have demonstrated the optimizing ability of evolution, as
exemplified by the field of GENETIC ALGORITHMs. The creative aspects
of evolution have been more elusive to model. The difficulty derives
in part from a tendency of models to specify the meaning of the
``genome'' of the evolving entities, precluding new meanings from
emerging. I will present a natural model of evolution demonstrating
both optimization and creativity, in which the GENOME consists of
sequences of executable machine code.
From a single rudimentary ancestral ``creature'', very quickly there
evolve parasites, which are not able to replicate in isolation
because they lack a large portion of the genome. However, these
parasites search for the missing information, and if they locate it
in a nearby creature, parasitize the information from the neighboring
genome, thereby effecting their own replication.
In some runs, hosts evolve immunity to attack by parasites. When
immune hosts appear, they often increase in frequency, devastating
the parasite POPULATIONs. In some runs where the community comes to
be dominated by immune hosts, parasites evolve that are resistant to
immunity.
Hosts sometimes evolve a response to parasites that goes beyond
immunity, to actual (facultative) hyper-parasitism. The hyper-
parasite deceives the parasite causing the parasite to devote its
energetic resources to replication of the hyper-parastie genome.
This drives the parasites to extinction. Evolving in the absence of
parasites, hyper-parasites completely dominate the community,
resulting in a relatively uniform community characterized by a high
degree of relationship between INDIVIDUALs. Under these
circumstances, sociality evolves, in the form of creatures which can
only replicate in aggregations.
The cooperative behavior of the social hyper-parasites makes them
vulnerable to a new class of parasites. These cheaters, hyper-hyper-
parasites, insert themselves between cooperating social individuals,
deceiving the social creatures, causing them to replicate the genomes
of the cheaters.
The only genetic change imposed on the simulator is random bit flips
in the machine code of the creatures. However, it turns out that
parasites are very sloppy replicators. They cause significant
RECOMBINATION and rearrangement of the genomes. This spontaneous
sexuality is a powerful force for evolutionary change in the system.
One of the most interesting aspects of this instance of life is that
the bulk of the evolution is based on adaptation to the biotic
ENVIRONMENT rather than the physical environment. It is co-evolution
that drives the system.
--- "Tierra announcement" by Tom Ray (1991)
How to get Tierra?
Tierra is available (source and executables, for Unix and NT) from
alife.santafe.edu/pub/SOFTWARE/Tierra
.
Related work
David Bennett <d...@pfxcorp.com> reported in March 2000: Much new work
has been done in Tierra since 1993. Thomas Ray
<tr...@mail.nhn.ou.edu> is now working in Japan. I have been using
another similar system called Avida. It has some advantages, and a
significant body of research results. The contact for Avida is
<av...@krl.caltech.edu>.
References
Ray, T. S. (1991) "Is it alive, or is it GA?" in [ICGA91], 527--534.
Ray, T. S. (1991) "An approach to the synthesis of life." in
[ALIFEII], 371--408.
Ray, T. S. (1991) "Population dynamics of digital organisms." in
[ALIFEII].
Ray, T. S. (1991) "Evolution and optimization of digital
organisms." Scientific Excellence in Supercomputing: The IBM 1990
Contest Prize Papers, Eds. Keith R. Billingsley, Ed Derohanes, Hilton
Brown, III. Athens, GA, 30602, The Baldwin Press, The University of
Georgia.
Ray, T. S. (1992) "Evolution, ecology and optimization of digital
organisms." Santa Fe Institute working paper 92-08-042.
Ray, T. S. "Evolution, complexity, entropy, and artificial reality."
submitted Physica D.
Ray, T. S. (1993) "An evolutionary approach to synthetic biology,
Zen and the art of creating life. Artificial Life 1(1).
VENUS
Steen Rasmussen's (et al.) VENUS I+II "coreworlds" as described in
[ALIFEII] and [LEVY92], are inspired by A.K. Dewdney's well-known
article (Dewdney 1984). Dewdney proposed a game called "Core Wars",
in which hackers create computer programs that battle for control of
a computer's "core" memory (Strack 93). Since computer programs are
just patterns of information, a successful program in core wars is
one that replicates its pattern within the memory, so that eventually
most of the memory contains its pattern rather than that of the
competing program.
VENUS is a modification of Core Wars in which the Computer programs
can mutate, thus the pseudo assembler code creatures of VENUS evolve
steadily. Furthermore each memory location is endowed with
"resources" which, like sunshine are added at a steady state. A
program must have sufficient resources in the regions of memory it
occupies in order to execute. The input of resources determines
whether the VENUS ecosystem is a "jungle" or a "desert." In jungle
ENVIRONMENTs, Rasmussen et al. observe the spontaneous emergence of
primitive "copy/split" organisms starting from (structured) random
initial conditions.
--- [ALIFEII], p.821
Dewdney, A.K. (1984) "Computer Recreations: In the Game called Core
War Hostile Programs Engage in a Battle of Bits", Sci. Amer. 250(5),
14-22.
Farmer & Belin (1992) "Artificial Life: The Coming Evolution",
[ALIFEII], 815-840.
Rasmussen, et al. (1990) "The Coreworld: Emergence and Evolution of
Cooperative Structures in a Computational Chemistry", [FORREST90],
111-134.
Rasmussen, et al. (1992) "Dynamics of Programmable Matter",
[ALIFEII], 211-254.
Strack (1993) "Core War Frequently Asked Questions (
rec.games.corewar FAQ)" Avail. by anon. FTP from
rtfm.mit.edu/pub/usenet/news.answers/games/corewar-faq.Z
PolyWorld
Larry Yaeger's PolyWorld as described in [ALIFEIII] and [LEVY92] is
available via anonymous FTP from
alife.santafe.edu/pub/SOFTWARE/Polyworld/
"The subdirectories in this "polyworld" area contain the source code
for the PolyWorld ecological simulator, designed and written by Larry
Yaeger, and Copyright 1990, 1991, 1992 by Apple Computer.
PostScript versions of my ARTIFICIAL LIFE III technical paper have
now been added to the directory. These should be directly printable
from most machines. Because some unix systems' "lpr" commands cannot
handle very large files (ours at least), I have split the paper into
Yaeger.ALife3.1.ps and Yaeger.ALife3.2.ps. These files can be ftp-ed
in "ascii" mode. For unix users I have also included compressed
versions of both these files (indicated by the .Z suffix), but have
left the uncompressed versions around for people connecting from non-
unix systems. I have not generated PostScript versions of the
images, because they are color and the resulting files are much too
large to store, retrieve, or print. Accordingly, though I have
removed a Word-formatted version of the textual body of the paper
that used to be here, I have left a Word-formatted version of the
color images. If you wish to acquire it, you will need to use the
binary transfer mode to move it to first your unix host and then to a
Macintosh (unless Word on a PC can read it - I don't know), and you
may need to do something nasty like use ResEdit to set the file type
and creator to match those of a standard Word document (Type = WDBN,
Creator = MSWD). [..]"
--- from the README by Larry Yaeger <lar...@apple.com>
General Alife repositories?
Also, all of the following FTP sites carry ALIFE related info:
ftp.cognet.ucla.edu/pub/alife/ ,
life.anu.edu.au/pub/complex_systems/alife/ ,
ftp.cogs.susx.ac.uk/pub/reports/csrp/ , xyz.lanl.gov/nlin-sys/ ,
alife.santafe.edu/pub/ .
------------------------------
Subject: Q5: What about all this Optimization stuff?
Just think of an OPTIMIZATION problem as a black box. A large black
box. As large as, for example, a Coca-Cola vending machine. Now, we
don't know anything about the inner workings of this box, but see,
that there are some regulators to play with, and of course we know,
that we want to have a bottle of the real thing...
Putting this everyday problem into a mathematical model, we proceed
as follows:
(1) we label all the regulators with x and a number starting from 1;
the result is a vector x, i.e. (x_1,...,x_n), where n is the
number of visible regulators.
(2) we must find an objective function, in this case it's obvious, we
want to get k bottles of the real thing, where k is equal to 1.
[some might want a "greater or equal" here, but we restricted
ourselves to the visible regulators (we all know that sometimes a
"kick in the right place" gets use more than 1, but I have no
idea how to put this mathematically...)]
(3) thus, in the language some mathematicians prefer to speak in:
f(x) = k = 1. So, what we have here is a maximization problem
presented in a form we know from some boring calculus lessons,
and we also know that there at least a dozen utterly
uninteresting techniques to solve problems presented this way...
What can we do in order to solve this problem?
We can either try to gain more knowledge or exploit what we already
know about the interior of the black box. If the objective function
turns out to be smooth and differentiable, analytical methods will
produce the exact solution.
If this turns out to be impossible, we might resort to the brute
force method of enumerating the entire SEARCH SPACE. But with the
number of possibilities growing exponentially in n, the number of
dimensions (inputs), this method becomes infeasible even for low-
dimensional spaces.
Consequently, mathematicians have developed theories for certain
kinds of problems leading to specialized OPTIMIZATION procedures.
These algorithms perform well if the black box fulfils their
respective prerequisites. For example, Dantzig's simplex algorithm
(Dantzig 66) probably represents the best known multidimensional
method capable of efficiently finding the global optimum of a linear,
hence convex, objective function in a search space limited by linear
constraints. (A USENET FAQ on linear programming is maintained by
Professor Robert Fourer <4...@iems.nwu.edu> (and "nonlinear-
programming-faq") that is posted monthly to sci.op-research and is
mostly interesting to read. It is also available from http://www-
unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.html )
Gradient strategies are no longer tied to these linear worlds, but
they smooth their world by exploiting the objective function's first
partial derivatives one has to supply in advance. Therefore, these
algorithms rely on a locally linear internal model of the black box.
Newton strategies additionally require the second partial
derivatives, thus building a quadratic internal model. Quasi-Newton,
conjugate gradient and variable metric strategies approximate this
information during the search.
The deterministic strategies mentioned so far cannot cope with
deteriorations, so the search will stop if anticipated improvements
no longer occur. In a multimodal ENVIRONMENT these algorithms move
"uphill" from their respective starting points. Hence, they can only
converge to the next local optimum.
Newton-Raphson-methods might even diverge if a discrepancy between
their internal assumptions and reality occurs. But of course, these
methods turn out to be superior if a given task matches their
requirements. Not relying on derivatives, polyeder strategy, pattern
search and rotating coordinate search should also be mentioned here
because they represent robust non-linear optimization algorithms
(Schwefel 81).
Dealing with technical optimization problems, one will rarely be able
to write down the objective function in a closed form. We often need
a SIMULATION model in order to grasp reality. In general, one cannot
even expect these models to behave smoothly. Consequently,
derivatives do not exist. That is why optimization algorithms that
can successfully deal with black box-type situations have been
developed. The increasing applicability is of course paid for by a
loss of "convergence velocity," compared to algorithms specially
designed for the given problem. Furthermore, the guarantee to find
the global optimum no longer exists!
But why turn to nature when looking for more powerful algorithms?
In the attempt to create tools for various purposes, mankind has
copied, more often instinctively than geniously, solutions invented
by nature. Nowadays, one can prove in some cases that certain forms
or structures are not only well adapted to their ENVIRONMENT but have
even reached the optimum (Rosen 67). This is due to the fact that the
laws of nature have remained stable during the last 3.5 billion
years. For instance, at branching points the measured ratio of the
diameters in a system of blood-vessels comes close to the theoretical
optimum provided by the laws of fluid dynamics (2^-1/3). This, of
course, only represents a limited, engineering point of view on
nature. In general, nature performs adaptation, not optimization.
The idea to imitate basic principles of natural processes for optimum
seeking procedures emerged more than three decades ago (cf Q10.3).
Although these algorithms have proven to be robust and direct
OPTIMIZATION tools, it is only in the last five years that they have
caught the researchers' attention. This is due to the fact that many
people still look at organic EVOLUTION as a giantsized game of dice,
thus ignoring the fact that this model of evolution cannot have
worked: a human germ-cell comprises approximately 50,000 GENEs, each
of which consists of about 300 triplets of nucleic bases. Although
the four existing bases only encode 20 different amino acids,
20^15,000,000, ie circa 10^19,500,000 different GENOTYPEs had to be
tested in only circa 10^17 seconds, the age of our planet. So, simply
rolling the dice could not have produced the diversity of today's
complex living systems.
Accordingly, taking random samples from the high-dimensional
parameter space of an objective function in order to hit the global
optimum must fail (Monte-Carlo search). But by looking at organic
evolution as a cumulative, highly parallel sieving process, the
results of which pass on slightly modified into the next sieve, the
amazing diversity and efficiency on earth no longer appears
miraculous. When building a model, the point is to isolate the main
mechanisms which have led to today's world and which have been
subjected to evolution themselves. Inevitably, nature has come up
with a mechanism allowing INDIVIDUALs of one SPECIES to exchange
parts of their genetic information (RECOMBINATION or CROSSOVER), thus
being able to meet changing environmental conditions in a better way.
Dantzig, G.B. (1966) "Lineare Programmierung und Erweiterungen",
Berlin: Springer. (Linear programming and extensions)
Kursawe, F. (1994) " Evolution strategies: Simple models of natural
processes?", Revue Internationale de Systemique, France (to appear).
Rosen, R. (1967) "Optimality Principles in Biologie", London:
Butterworth.
Schwefel, H.-P. (1981) "Numerical Optimization of Computer Models",
Chichester: Wiley.
------------------------------
Copyright (c) 1993-2000 by J. Heitkoetter and D. Beasley, all rights
reserved.
This FAQ may be posted to any USENET newsgroup, on-line service, or
BBS as long as it is posted in its entirety and includes this
copyright statement. This FAQ may not be distributed for financial
gain. This FAQ may not be included in commercial collections or
compilations without express permission from the author.
End of ai-faq/genetic/part3
***************************
--