Article View: comp.ai.genetic
Article #1FAQ: comp.ai.genetic part 1/3 (A Guide to Frequently Asked Questions)
From: Joerg Heitkoetter
Date: Mon, 27 Dec 1993 18:06
Date: Mon, 27 Dec 1993 18:06
2917 lines
113252 bytes
113252 bytes
Archive-name: ai-faq/genetic/part1
Last-Modified: 12/20/93
Issue: 1.10
FAQ(1/3) COMP.AI.GENETIC FAQ(1/3)
The
Hitch-Hiker's
Guide to
Evolutionary Computation
(FAQ in comp.ai.genetic)
edited by
Joerg Heitkoetter
c/o Systems Analysis Research Group, LSXI
Department of Computer Science
University of Dortmund
D-44221 Dortmund, Germany
<joke@ls11.informatik.uni-dortmund.de>
or <joke@santafe.edu>
(Usually FAQ means "Frequently Asked Questions,"
though it's sometimes referred to as
"Familiar Awkward Questions" ;-)
PLEASE, SEARCH THIS POSTING FIRST
IF YOU HAVE A QUESTION
and
DON'T POST ANSWERS TO FAQs:
POINT THE ASKER TO THIS POSTING
and
DON'T PANIC
Issue 1.10 Posted: 20 December 1993 1
FAQ(1/3) PREFACE FAQ(1/3)
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.
FAQ list
/F-A-Q list/ or /fak list/ [USENET] n. Syn FAQ, sense 2.
FAQL /fa'kl/ n. Syn. FAQ list.
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. See also FM, RTFAQ,
RTFB, RTFS, RTM, all of which mutated from RTFM, and compare
UTSL.
--- "The on-line hacker Jargon File, version 3.0, 29 July 1993",
available via anon. ftp to ftp.gnu.ai.mit.edu as
"/pub/gnu/jarg300.txt.gz"
PREFACE
This posting 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 those principles are
worth copying 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).
Issue 1.10 Posted: 20 December 1993 2
FAQ(1/3) PREFACE FAQ(1/3)
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, i.e. the "theory of evolution." The inspired algorithms are
thus termed Evolutionary Algorithms (EA).
Moreover, is this posting intended to introduce and help those, who
are just beginning to read this 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 are boring
to read again and again by comp.ai.genetic "old-timers."
You will see this posting popping up each month in the USENET
newsgroup comp.ai.genetic (including comp.answers, and news.answers,
where it should be locatable at any time).
CONTRIBUTIONS
Contributions, additions, corrections, cash, etc. are always welcome.
Send e-mail to the address above, if it is relevant, it will be
incorporated; if it is irrelevant it has even more chances to make in
into the next issue... (Please format your contribution
appropriately so it can just be dropped in. Unformatted contributions
however, won't be rejected.)
ARCHIVE SERVICE
This posting (like all other FAQs, i.e. the essence of the knowledge
floating through USENET) is available between postings on
rtfm.mit.edu in the directory "/pub/usenet/news.answers" as the files
ai-faq/genetic/part?. The FAQ may also be retrieved by e-mail from
<mail-server@rtfm.mit.edu>. Send a message to the mail-server with
"help" and "index" in the body on separate lines for more
information.
DISCLAIMER
This quarterly posting (i.e., 4 issues per year) 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 Systems Analysis Research Group,
neither as a whole, nor in part, they are just the editor's very own
collection of ideas, emerged over the past 28 years.
Issue 1.10 Posted: 20 December 1993 3
FAQ(1/3) PREFACE FAQ(1/3)
NOTE: some portions of this else rather dry guide are intended to be
satirical. If you do not recognize it as such, consult your local
doctor or a professional comedian.
HITCH-HIKING THE FAQNIVERSE
This guide is big. Really big. You just won't believe how hugely,
vastly, mindbogglingly big it is. That's why it has been split into a
trilogy, i.e. it can be pieced together from files "ai-
faq/genetic/part1", "ai-faq/genetic/part2", and "ai-
faq/genetic/part3".
Searching for answers
To find the answer of question number x, just search for the string
"Ax)" (so the answer to question "Q42:" is at "A42)")
What does, e.g. [ICGA85] mean?
Some books would be referenced again and again, that's why they got
this kind of "tag", that an experienced hitch-hiker will search for
to dissolve the riddle.
Why all this UPPERCASING in running text?
Some words are written in all uppercase letters, e.g. EVOLUTION, you
will find these reappearing in the Glossary (cf A99), with a ":" sign
appended, thus if you run on, say EC you can search for the string
"EC:" in the Glossary.
Other typographical conventions
A certain file on a certain FTP server will be specified in a certain
way: <ftp-site-name>:<the-complete-filename>, as e.g. in
ftp.certain.site:/pub/foo/bar.tar.gz
Referencing this Guide
If you want to reference this guide (although I have currently no
idea, why you should want to do this), I'd be insanely proud if it
looks like:
Heitkoetter, Joerg, ed. (1993) "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 in pub/usenet/news.answers/ai-faq/genetic/part?. ~90
pages. PostScript repositories: lumpi.informatik.uni-
dortmund.de:/pub/EA/docs/hhgtec-*.ps.gz,and
sfi.santafe.edu:/pub/EC/FAQ/hhgtec-*.ps.gz
Or simply call it "the Guide", or "HHGTEC" for acronymaniacs.
Obtaining a PostScript version
For innumerable reasons this guide is written using an ancient, good
old-fashioned UNIX text formatting utility, namely troff(1); better
Issue 1.10 Posted: 20 December 1993 4
FAQ(1/3) PREFACE FAQ(1/3)
to say the GNU version groff(1) and a hacked macro package based on
"tmac.an"; it's thus easy to generate ASCII (posted), TeX DVI (not
posted), and PostScript (ftpable) versions from a unique source. The
latter, looks really crisp (using boldface, italics, etc.), and thus
is available for those who prefer offline reading. Get file
"/pub/EA/docs/hhgtec-*.ps.gz" from the SyS ftp-server:
lumpi.informatik.uni-dortmund.de (129.217.36.140); or from within the
US you might try: ftp.santafe.edu and get file
"/pub/EC/FAQ/hhgtec-*.ps.gz".
"As a net is made up of a series of ties, so everything in
this world is connected by a series of ties. If anyone thinks
that the mesh of a net is an independent, isolated thing, he is
mistaken. It is called a net because it is made up of a series
of interconnected meshes, and each mesh has its place and
responsibility in relation to other meshes."
--- Buddha
The ZEN Puzzle
For some weird reason this guide contains some puzzles which can only
be solved by cautious readers who have (1) a certain amount of a
certain kind of humor, (2) a certain amount of patience and time, (3)
a certain amount of experience in ZEN navigation, and (4) a certain
amount of books of a certain author.
Usually, puzzles search either for certain answers (more often, ONE
answer) to a question; or, for the real smartasses, sometimes an
answer is presented, and a certain question is searched for. ZEN
puzzles are even more challenging: you have to come up with an answer
to a question, both of which are not explicitly, rather implicitly
stated somewhere in this FAQ. Thus, you are expected to give an
answer AND a question!
To give an impression what this is all about, consider the following,
submitted by Craig W. Reynolds. The correct question is: "Why is
Fisher's `improbability quote' (cf EPILOGUE) included in this FAQ?",
Craig's correct answer is: `This is a GREAT quotation, it sounds like
something directly out of a turn of the century Douglas Adams:
Natural selection: the original "Infinite Improbability Drive"' Got
the message? Well, this was easy and very obvious. The other puzzles
are more challenging...
However, all this is just for fun (mine and hopefully yours), there
is nothing like the $100 price, some big shots in computer science,
e.g. Don Knuth usually offer; all there is but a honorable
mentioning of the ZEN navigator, including the puzzle s/he solved.
It's thus like in real life: don't expect to make money from the time
being a scientist, it's all just for the fun of it...
Issue 1.10 Posted: 20 December 1993 5
FAQ(1/3) PREFACE FAQ(1/3)
Enjoy the trip!
Issue 1.10 Posted: 20 December 1993 6
FAQ(1/3) TABLE OF CONTENTS FAQ(1/3)
TABLE OF CONTENTS
ai-faq/genetic/part1
Q0: Hey, what about an Introduction to all this?
Q0.1 What's the precise of comp.ai.genetic?
Q0.2 How do I get started? What about Usenet documentation?
Q0.3 Blaah! Don't you have something more funny?
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)?
Q2: What can you do with EAs? What can't you do with them?
Q3: Who is or should be concerned with EAs?
Q4: How many Evolutionary Algorithms exist? Which?
Q4.1: What about Tierra, VENUS, PolyWorld, etc.?
ai-faq/genetic/part2
Q5: What about all this Optimization stuff?
Q10: Good introductory material about EAs?
Q10.1: Books for absolute beginners?
Q10.2: Textbooks?
Q10.3: The Classics?
Q10.4: Introductory Journal Articles?
Q10.5: Introductory Technical Reports?
Issue 1.10 Posted: 20 December 1993 7
FAQ(1/3) TABLE OF CONTENTS FAQ(1/3)
Q10.6: Not-quite-so-introductory Literature?
Q10.7: Biological Background Readings?
Q10.8: Electronic Bibliography Collections?
Q10.9: Videos?
Q10.10:CD-ROMs?
Q10.11:How do I get a copy of a dissertation?
Q11: Any journals and magazines about EAs?
Q12: The most important conferences concerned with EAs?
Q13: Evolutionary Computation Associations?
Q14: Where do I get technical reports on EAs from?
Q15: Other sources of information about EAs?
Q15.1: Electronic Digests?
Q15.2: Electronic Mailing Lists?
Q15.3: Electronic Access to Research Institutes?
Q15.4: Relevant Electronic News and FAQs?
Q15.5: What about all these Internet Services?
ai-faq/genetic/part3
Q20: Available EA software packages? FTP sites?
Q20.1: Free EA software packages?
Q20.2: Commercial EA software packages?
Q20.3: Software from current research projects?
Q21: What are Gray codes, why might I want to use them, and how do
I efficiently implement them? C Code, please?
Issue 1.10 Posted: 20 December 1993 8
FAQ(1/3) TABLE OF CONTENTS FAQ(1/3)
Q42: What is life all about?
Q42b: Is there a FAQ to this group?
Q98: What about Patents on EAs?
Q99: I don't get the message. What about a Glossary on EAs?
Issue 1.10 Posted: 20 December 1993 9
FAQ(1/3) ANSWERS FAQ(1/3)
A0) Hey, what about an Introduction to all this?
A0.1) What's the precise of comp.ai.genetic?
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).
A0.2) 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 don't want to read
any further; if you don't know what the hell this is all about,
proceed as follows: (1) carefully read the following paragraphs, (2)
read all the documents in news.announce.newusers before posting any
article to USENET. At least you should give the introductory stuff a
try, i.e. files "news-answers/introduction" and "news-answers/news-
newusers-intro". Both are survey articles, that provide a short and
easy way to get an overview of the interesting parts of the online
docs, and thus can help to prevent you from drowning in the megabytes
to read. Both can be received either by subscribing to news.answers,
or sending the following message to <mail-server@rtfm.mit.edu>:
send usenet/news.answers/introduction
send usenet/news.answers/news-newusers-intro
quit
Netiquette
"Usenet is a convention, in every sense of the word."
Although USENET is usually characterized as "an anarchy, with no laws
and no one in charge" there have "emerged" several rules over the
past years that shall facilitate life within newsgroups. Thus, you
will probably find the following types of articles:
1. Requests
Requests are articles of the form "I am looking for X" where X is
something public like a book, an article, a piece of software.
If multiple different answers can be expected, the person making the
request should prepare to make a summary of the answers he/she got
and announce to do so with a phrase like "Please e-mail, I'll
summarize" at the end of the posting.
The Subject line of the posting should then be something like
"Request: X"
Issue 1.10 Posted: 20 December 1993 10
FAQ(1/3) ANSWERS FAQ(1/3)
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:"
Issue 1.10 Posted: 20 December 1993 11
FAQ(1/3) ANSWERS FAQ(1/3)
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...
Thanx in advance for your patience!
A0.3) Blaah! Don't you have something more funny?
Yes. Let's face it. All these files are written by USENET
afficionados, and thus might offend beginners for some reasons, but
there is an alternative way: The EFF recently announced the following
in "EFFector Online Volume 5 No. 15, 8/20/1993" (A Publication of the
Electronic Frontier Foundation, ISSN 1062-9424), available via
Issue 1.10 Posted: 20 December 1993 12
FAQ(1/3) ANSWERS FAQ(1/3)
comp.org.eff.news:
Big Dummy's Guide to the Internet
"EFF is proud to announce that the Big Dummy's Guide to the Internet
is now available for free download from our ftp site. The Big
Dummy's Guide is a user guide for novices on all the Internet has to
offer.
The genesis of the Big Dummy's Guide was a few informal
conversations, which included Mitch Kapor of the Electronic Frontier
Foundation (EFF) and Steve Cisler of Apple Computers, in June of
1991. With the support of Apple Computers, EFF hired a writer (Adam
Gaffin) and actually took on the project in September of 1991.
The idea was to write a guide to the Internet for folks who had
little or no experience with network communications. The Guide is
currently posted to "the 'net" in ASCII and Hypercard (Mac) formats.
We have been giving it away on disk at conferences, and we hope to
have a print edition available for a nominal charge soon. We're
hoping to update this Guide on a regular basis, so please feel free
to send us your comments and corrections. Enjoy!"
The (original) Big Dummy's Guide to the Internet can be downloaded by
anonymous ftp from ftp.eff.org. The ASCII version is located at
/pub/Net_info/Big_Dummy/big-dummys-guide.txt . The Hypercard stack
is located at /pub/Net_info/Big_Dummy/big-dummys-guide.sea.hqx . The
Texinfo version (PostScript, TeXX DVI, HTML, GNU Info, ASCII) is
avail. at /pub/Net_info/Big_Dummy/Big_Dummys_Guide_Texi/* (cf
References of Q15)
A1) What are Evolutionary Algorithms (EAs)?
Evolutionary algorithms use computational models of evolutionary
processes as key elements in the design and implementation of
computer-based problem solving systems. A variety of evolutionary
computational models have been proposed. They 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, (GENETIC OPERATORS) such as
RECOMBINATION and MUTATION. Each INDIVIDUAL in the population
receives a measure of it's FITNESS in the ENVIRONMENT. REPRODUCTION
focuses attention on high fitness individuals, thus EXPLOITING the
available fitness information. Recombination and mutation perturb
those individuals, providing general heuristics for EXPLORATION.
Although simplistic from a biologist's viewpoint, these algorithms
Issue 1.10 Posted: 20 December 1993 13
FAQ(1/3) ANSWERS FAQ(1/3)
are sufficiently complex to provide robust and powerful ADAPTIVE
SEARCH mechanisms.
--- "An Overview of Evolutionary Computation" [ECML93], 442-459.
PSEUDO CODE
Algorithm EA is
// start with an initial time
t := 0;
// initialize a usually random population of individuals
initpopulation P (t);
// evaluate fitness of all initial individuals in population
evaluate P (t);
// test for termination criterion (time, fitness, etc.)
while not done do
// increase the time counter
t := t + 1;
// select sub-population for offspring production
P' := selectparents P (t);
// recombine the "genes" of selected parents
recombine P' (t);
// perturb the mated population stochastically
mutate P' (t);
// evaluate it's new fitness
evaluate P' (t);
// select the survivors from actual fitness
P := survive P,P' (t);
od
end EA.
A1.1) What's a Genetic Algorithm (GA)?
The GENETIC ALGORITHM is a model of MACHINE LEARNING which derives
its behavior from a metaphor of the processes 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 evolution.
We should note that EVOLUTION (in nature or anywhere else) is not a
purposive or directed process. That is, there is no evidence to
Issue 1.10 Posted: 20 December 1993 14
FAQ(1/3) ANSWERS FAQ(1/3)
support the assertion that the goal of evolution is to produce
Mankind. Indeed, the processes of nature seem to boil down to
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 our genetic information
(GENOME) is done in a way that admits sexual REPRODUCTION (such as by
budding) typically results in offspring that are genetically
identical to the parent. SEXUAL REPRODUCTION allows the creation of
genetically radically different offspring that are still of the same
general flavor (SPECIES).
At the molecular level what occurs (wild oversimplification alert!)
is that a pair of CHROMOSOMEs bump into one another, exchange chunks
of genetic information and drift apart. This is the RECOMBINATION
operation, which GA/GPers generally refer to as CROSSOVER because of
the way that genetic material crosses over from one chromosome to
another.
The CROSSOVER operation happens in an ENVIRONMENT where the selection
of who gets to mate is a function of the FITNESS of the INDIVIDUAL,
i.e. how good the individual is at competing in its environment.
Some GENETIC ALGORITHMs use a simple function of the fitness measure
to select individuals (probabilistically) to undergo genetic
operations such as crossover or 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. The two processes that most contribute
to EVOLUTION are crossover and fitness based selection/reproduction.
As it turns out, there are mathematical proofs that indicate that the
process of FITNESS proportionate REPRODUCTION is, in fact, near
optimal in some senses.
MUTATION also plays a role in this process, though it is not the
dominant role that is popularly believed to be the process of
EVOLUTION, i.e. random mutation and survival of the fittest. It
cannot be stressed too strongly that the GENETIC ALGORITHM (as a
simulation of a genetic process) is not a "random search" for a
solution to a problem (highly fit INDIVIDUAL). The genetic algorithm
uses stochastic processes, but the result is distinctly non-random
(better than random).
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.
Issue 1.10 Posted: 20 December 1993 15
FAQ(1/3) ANSWERS FAQ(1/3)
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);
Issue 1.10 Posted: 20 December 1993 16
FAQ(1/3) ANSWERS FAQ(1/3)
// recombine the "genes" of selected parents
recombine P' (t);
// perturb the mated population stochastically
mutate P' (t);
// evaluate it's new fitness
evaluate P' (t);
// select the survivors from actual fitness
P := survive P,P' (t);
od
end GA.
A1.2) What's Evolutionary Programming (EP)?
Introduction
Evolutionary Programming is a stochastic optimization strategy
similar to GENETIC ALGORITHMs, but which dispenses with both
"genomic" representations and with RECOMBINATION as a MUTATION
strategy.
Like GENETIC ALGORITHMs, the EP technique is useful for optimizing
problem solutions when other techniques like 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 the EP technique.
History
The 1966 book, "Artificial Intelligence Through Simulated Evolution"
by Fogel, Owens and Walsh is the landmark publication for
applications of the EP technique. In the work, automata were evolved
to predict symbol strings generated from Markov processes.
In 1992, the First Annual Conference on Evolutionary Programming was
held in La Jolla, CA. A second was held in 1993 and a third is
planned for 1994. The first conference attracted a diverse group of
academic, commericial and military researchers engaged in both
developing the theory of the EP technique and in applying EP to a
wide range of optimization problems.
Rather than list and analyze the sources in detail, I have included
several fundamental sources 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 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
Issue 1.10 Posted: 20 December 1993 17
FAQ(1/3) ANSWERS FAQ(1/3)
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.
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.
(3) Each offspring solution is assessed by computing it's FITNESS.
The N best solutions, or *stochastically* N of the best
solutions, are retained for the next POPULATION of solutions.
EP and GAs
There are two important ways in which the EP method differs from the
GA technique.
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 the EP approach, 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.
Second, the MUTATION operation simply changes aspects of the solution
according to a statistical distribution which weights minor
variations in offspring as highly probable and substantial variations
as increasingly unlikely 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 (see Sources, below ) in
which the variance of the mutation distribution is subject to
mutation by a fixed variance mutation operator and evolves along with
the solution.
Evolution and Sex: The Argumentative Side of EP
CROSSOVER as an abstraction of sexual RECOMBINATION has been
questioned on several fronts by the EP community.
Issue 1.10 Posted: 20 December 1993 18
FAQ(1/3) ANSWERS FAQ(1/3)
The strongest criticisms have been raised by Atmar (1992) in his
introductory papers in the first EP conference proceedings as well as
his substantially biological "On the Role of Males" in Animal
Behavior (1991). Atmar criticizes the use of terminology, indicating
that "crossing-over" is a process that occurs prior to sex during
meiotic cell division and its actual role in EVOLUTION is not clearly
understood. More than just simple semantics, he argues a reversal of
the common assumption that sex acts as an accelerator of diversity,
instead casting sex as a mechanism for expunging genetic defects from
the germline.
Atmar additionally argues that simplistic encodings of parameters for
optimization in GENETIC ALGORITHMs where one "trait" is equivalent to
one symbol pattern in the GENOME misrepresents the process of natural
selection and miscontrues cause and effect. He argues instead for
selection at the phenotypic level. He characterizes the EP approach
as being "top down" in that expressed variation at the level of the
phenotype is selected without concern for the representation at lower
levels, while the GA approach "celebrates" coding details potentially
to the exclusion of arriving at optimal solutions.
Several empirical evaluations of the value of CROSSOVER have been
reported, all of which suggest that the value of crossover is not
clear.
References
Some references to proceedings, books and journal articles which
provide an excellent introduction (by no means extensive) to the
field, include:
Fogel, LJ, Owens, AJ and Walsh, MJ (1966) "Artificial Intelligence
Through Simulated Evolution," John Wiley and Sons, NY. [primary]
Fogel, DB and Atmar, JW, (eds.) (1992) "Proceedings of the First
Annual Conference on Evolutionary Programming," Evolutionary
Programming Society, San Diego, CA. [primary]
Atmar, JW (1991) "On the Role of Males," Animal Behavior, Vol. 41,
pp. 195-205. [biological]
Ambati, BK, Ambati, J and Mokhtar, MM (1991) "Heuristic COMBINATORIAL
OPTIMIZATION by Simulated Darwinian EVOLUTION: A Polynomial Time
Algorithm for the Traveling Salesman Problem," Biological
Cybernetics, Vol. 65, pp 31-35. [mathematical]
Sebald, AV, Schlenzig, J and Fogel, DB (1991) "Minimax Design of CMAC
Neural Controllers Using Evolutionary Programming," Proc. of the 25th
Asilomar Conf. on Signals, Systems and Computers, Chen, RR (ed.),
Pacific Grove, CA, pp 551-555. [practical]
Issue 1.10 Posted: 20 December 1993 19
FAQ(1/3) ANSWERS FAQ(1/3)
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
// increase the time counter
t := t + 1;
// perturb the whole population stochastically
P' := mutate P (t);
// evaluate it's new fitness
evaluate P' (t);
// select the survivors from actual fitness
P := survive P,P' (t);
od
end EP.
It should be pointed out that EP does not use any CROSSOVER as a
GENETIC OPERATOR.
A1.3) What's an Evolution Strategy (ES)? [preliminary]
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."
Issue 1.10 Posted: 20 December 1993 20
FAQ(1/3) ANSWERS FAQ(1/3)
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 my, 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
Issue 1.10 Posted: 20 December 1993 21
FAQ(1/3) ANSWERS FAQ(1/3)
(select
(cond (plus-strategy?
(union (mutate
(recombine population))
population))
(comma-strategy?
(mutate
(recombine population))))))))
However, dealing with ES is sometimes seen as "strong tobacco," for
it takes a decent amount of PROBABILITY THEORY and applied STATISTICS
to understand the inner workings of an ES, while it navigates through
the hyperspace of the usually n-dimensional problem space, by
throwing hyperelipses into the deep...
Luckily, this medium doesn't allow for much mathematical ballyhoo;
the author therefore has to come up with a simple but brilliantly
intriguing explanation to save the reader from falling asleep during
the rest of this section, so here we go:
Imagine a black box. A large black box. As large as, say for example,
a Coca-Cola vending machine. Now, [..] (to be continued)
A single INDIVIDUAL of the ES' POPULATION consists of the following
GENOTYPE representing a point in the SEARCH SPACE:
OBJECT VARIABLES
Real-valued x_i have to be tuned by RECOMBINATION and MUTATION
such that an objective function reaches its global optimum.
Referring to the metaphor mentioned previously, the x_i
represent the regulators of the alien Coka-Cola vending machine.
STRATEGY VARIABLES
Real-valued s_i (usually denoted by a lowercase sigma) or mean
STEPSIZES determine the mutability of the x_i. They represent
the STANDARD DEVIATION of a (0, s_i) GAUSSIAN DISTRIBUTION (GD)
being added to each x_i as an undirected MUTATION. With an
EXPECTANCY VALUE of 0 the parents will produce offsprings
similar to themselves on average. In order to make a doubling
and a halving of a stepsize equally probable, the s_i mutate
LOG-NORMALLY, distributed, i.e. exp(GD), from generation to
GENERATION. These stepsizes hide the INTERNAL MODEL the
POPULATION has made of its ENVIRONMENT, i.e. a SELF-ADAPTATION
of the stepsizes has replaced the exogenous control of the (1+1)
ES.
This concept works because selection sooner or later prefers those
INDIVIDUALs having built a good model of the objective function, thus
producing better offspring. Hence, LEARNING takes place on two
levels: (1) at the genotypic, i.e. the object and strategy variable
level and (2) at the phenotypic level, i.e. the FITNESS level.
Issue 1.10 Posted: 20 December 1993 22
FAQ(1/3) ANSWERS FAQ(1/3)
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 a
permanent adaptation of the stepsizes can 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 pure 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
being 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.
Issue 1.10 Posted: 20 December 1993 23
FAQ(1/3) ANSWERS FAQ(1/3)
ESs prove to be successful when compared to other iterative methods
on a large number of test problems (Schwefel 77). They are adaptable
to nearly all sorts of problems in optimization, because they need
very little information about the problem, esp. no derivatives of the
objective function. For a list of some 300 applications of EAs, see
the SyS-2/92 report (cf Q14). ESs are capable of solving high
dimensional, multimodal, nonlinear problems subject to linear and/or
nonlinear constraints. The objective function can also, e.g. be the
result of a SIMULATION, it does not have to be given in a closed
form. This also holds for the constraints which may represent the
outcome of, e.g. a finite elements method (FEM). ESs have been
adapted to VECTOR OPTIMIZATION problems (Kursawe 92), and they can
also serve as a heuristic for NP-complete combinatorial problems like
the TRAVELLING SALESMAN problem or problems with a noisy or changing
response surface.
References
Kursawe, F. (1992) "Evolution strategies for vector optimization",
Taipei, National Chiao Tung University, 187-193.
Kursawe, F. (1994) "Evolution strategies: Simple models of natural
processes?", Revue Internationale de Systemique, France (to appear).
Rechenberg, I. (1973) "Evolutionsstrategie: Optimierung technischer
Systeme nach Prinzipien der biologischen Evolution", Stuttgart:
Fromman-Holzboog.
Schwefel, H.-P. (1977) "Numerische Optimierung von Computermodellen
mittels der Evolutionsstrategie", Basel: Birkhaeuser.
Schwefel, H.-P. (1987) "Collective Phaenomena in Evolutionary
Systems", 31st Annu. Meet. Inter'l Soc. for General System Research,
Budapest, 1025-1033.
A1.4) What's a Classifier System (CFS)? [preliminary]
The name of the Game
First, a word on naming conventions is due, for no other paradigm of
EC has undergone more changes to it's name space than the thread
we're currently talking about. 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, thus, the word "learning" was prepended to the name to
stress the MACHINE LEARNING notion of the then called "Learning
Classifier Systems" abbrv. with 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 SAFIER as
Issue 1.10 Posted: 20 December 1993 24
FAQ(1/3) ANSWERS FAQ(1/3)
sfi.santafe.edu:/pub/EC/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].
On Schema Processors and ANIMATS
So, to get back to the question above, "What are CFSs?", we first
might answer, "Well, there are many interpretations of Holland's
ideas...what do you like to know in particular?" And then we'd start
with a recitation from [HOLLAND75,92], and explain all the schema
processors, the broadcast language, etc. But, we will take a more
comprehensive, and intuitive way to understand what classifier
systems are all about.
The easiest road to explore the very nature of classifier systems, is
to take the ANIMAT (ANIMAl + roboT = ANIMAT) "lane" devised by Booker
(1982) and later studied extensively by Wilson (1985), who also
coined the term for this approach. Work continues on ANIMATs but is
often regarded as ARTIFICIAL LIFE rather than EVOLUTIONARY
COMPUTATION. This thread of research has even its own conference
series: "Simulation of Adaptive Behavior (SAB)" (cf Q12), including
other notions from machine learning, connectionist learning,
evolutionary robotics, etc. [NB: the latter is obvious, if an ANIMAT
lives in a digital microcosm, it can be put into the real world by
implantation into an autonomous robot vehicle, that has
sensors/detectors (camera eyes, whiskers, etc.) and effectors
(wheels, robot arms, etc.); so all what'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
adopt their behavior toward a changing environment, as is explained
below in greater detail.
Holland envisioned a cognitive system capable of classification the
ongoings in its environment, and then react to these ongoings
appropriately. So what does it need to build such a system?
Obviously, we need (1) an environment; (2) receptors that tell our
system about the ongoings; (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
Issue 1.10 Posted: 20 December 1993 25
FAQ(1/3) ANSWERS FAQ(1/3)
that contains "food" and "poison". And the GOFER itself, that walks
across this grid and tries (a) to learn to distinguish between these
two items, and (b) survive well fed.
Much the same for Wilson's animat, called "*". Yes, it's just an
asterisk, and a "Kafka-esque naming policy" is one of the sign posts
of the whole field; e.g. the first implementation by Holland and
Reitmann 1978 was called CS-1, cognitive system 1; Smith' 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 what's left are the messages floating through the black box.
They should also be simple strings of zeroes and ones, and are to be
Issue 1.10 Posted: 20 December 1993 26
FAQ(1/3) ANSWERS FAQ(1/3)
kept in a data structure, we call "the message list".
With all this given, we can imagine the ongoings 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 ongoings appropriately.
What does it need to be a frog?
Let's take a look at the behavior emitted by Kermit. It lives in its
digital microwilderness where it moves around randomly. [NB: This
seemingly "random" behavior is not that random at all; for more on
instinctive, i.e., innate behavior of non-artificial animals see,
e.g. Tinbergen (1951)]
Whenever a small flying object appears, that has no stripes, Kermit
should eat it, because it's very likely a spicy fly, or other flying
insect. If it has stripes, the insect is better left alone, because
Kermit better don't 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
Issue 1.10 Posted: 20 December 1993 27
FAQ(1/3) ANSWERS FAQ(1/3)
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;
Issue 1.10 Posted: 20 December 1993 28
FAQ(1/3) ANSWERS FAQ(1/3)
// 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);
Issue 1.10 Posted: 20 December 1993 29
FAQ(1/3) ANSWERS FAQ(1/3)
// 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 SAFIER as: sfi.santafe.edu:/pub/EC/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 SAFIER as:
sfi.santafe.edu:/pub/EC/CFS/papers/lcs92-2.ps.gz
Issue 1.10 Posted: 20 December 1993 30
FAQ(1/3) ANSWERS FAQ(1/3)
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 SAFIER as:
sfi.santafe.edu:/pub/EC/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 given 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.
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. & 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.
Issue 1.10 Posted: 20 December 1993 31
FAQ(1/3) ANSWERS FAQ(1/3)
Post, E.L. (1943) "Formal reductions of the general combinatorial
decision problem" American Journal of Mathematics, 65, 197-268.
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
[ICGA95], 16-23.
A1.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.
A2) What can EAs do for you? What can't they do?
In principle, EAs can compute any computable function, i.e.
everything a normal digital computer can do.
Issue 1.10 Posted: 20 December 1993 32
FAQ(1/3) ANSWERS FAQ(1/3)
EAs are especially bad suited for problems that are already known how
to solve, unless these problems are intended to serve as BENCHMARK
PROGRAMS. Special purpose algorithms, i.e. algorithms that have a
certain amount of PROBLEM DOMAIN KNOWLEDGE hard coded in them, will
usually outperform EAs, so there is no BLACK MAGIC in EC. EAs should
be used when there is no other known problem solving strategy, and
the problem domain is NP-complete. That's where EAs come into play:
heuristically finding solutions where all else fails.
Following is an incomplete (sic!) list of successful EA
applications:
TIMETABLING
Another thing that has been addressed quite successfully with GAs is
timetabling. A very common manifestation of this kind of problem is
the timetabling of exams or classes in Universities, etc. 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.
Issue 1.10 Posted: 20 December 1993 33
FAQ(1/3) ANSWERS FAQ(1/3)
References
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, (to appear).
Fang, H.-L. (1992) "Investigating GAs for scheduling", MSc
Dissertation, University of Edinburgh Dept. of ARTIFICIAL
INTELLIGENCE, Edinburgh, UK.
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)
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
Issue 1.10 Posted: 20 December 1993 34
FAQ(1/3) ANSWERS FAQ(1/3)
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)."
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.
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."
Issue 1.10 Posted: 20 December 1993 35
FAQ(1/3) ANSWERS FAQ(1/3)
--- 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 to gwdu03.gwdg.de in directory
"pub/msdos/reports/wi", file "earef.eps".
Boulding, K.E. (1991) "What is evolutionary economics?", Journal of
Evolutionary Economics, 1, 9-17.
FURTHER APPLICATION(S)
[..]
References
[..]
A3) 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.
Issue 1.10 Posted: 20 December 1993 36
FAQ(1/3) ANSWERS FAQ(1/3)
Physicists
Use EC hardware, e.g. Hillis' (Thinking Machine Corp.'s) Connection
Machine to model real world problems which include thousands of
variables, that run "naturally" in parallel, and thus can be modelled
more easily and esp. "faster" on a parallel machine, than on a
serial "PC" one.
Biologists
In fact many working biologists are hostile to modeling, but an
entire community of POPULATION Biologists arose with the
'evolutionary synthesis' of the 1930's created by the polymaths R.A.
Fisher, J.B.S. Haldane, and S. Wright. Wright's 'shifting balance'
theory (balancing drift and selection in small POPULATIONS thereby
avoiding local optima) is of current interest to both biologists and
ECers -- populations are naturally parallel.
A good exposition of current POPULATION Biology modeling is J.
Maynard Smith's text Evolutionary Genetics. Richard Dawkin's Selfish
Gene and Extended Phenotype are unparalleled (sic!) prose expositions
of evolutionary processes. Rob Collins' papers are excellent
parallel GA models of evolutionary processes (available in ICGA91 and
by ftp from ftp.cognet.ucla.edu "/pub/alife/papers").
As fundamental motivation, consider Fisher's comment: "No practical
biologist interested in [e.g.] sexual REPRODUCTION would be led to
work out the detailed consequences experienced by organisms having
three or more sexes; yet what else should [s/]he do if [s/]he wishes
to understand why the sexes are, in fact, always two?" (Three sexes
would make for even weirder grammar, [s/]he said...)
Philosophers
and some other really curious people may also be interested in EC for
various reasons.
A4) 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 to hybrid experiments, i.e. there
exist pieces of software that reside in some researchers computer,
that have been described in papers of proceedings volumes, and may
someday prove useful on a certain task. To stay in EA slang, we
should think of these evolving strands as BUILDING BLOCKs, that when
recombined someday, will produce new offspring and give birth to new
EA paradigm(s).
Promising Rookies
Issue 1.10 Posted: 20 December 1993 37
FAQ(1/3) ANSWERS FAQ(1/3)
As far as "solving complex function and COMBINATORIAL OPTIMIZATION
tasks" is concerned, Davis work on real-valued representations and
adaptive operators should be mentioned (Davis 89). Moreover Whitley's
GENITOR system incorporating ranking and "steady state" mechanism
(Whitley 89), Goldberg's "messy GAs", involves adaptive
representations (Goldberg 91), and Eshelman's CHC algorithm (Eshelman
91).
For "the design of robust learning systems", i.e. the field
characterized by CFS, Holland's (1986) classifier system, with it's
state-of-the-art implementation CFS-C (Riolo 88), we should note
recent developments in SAMUEL (Grefenstette 89), GABIL (De Jong &
Spears 91), and GIL (Janikow 91).
References
Davis, L. (1989) "Adapting operator probabilities in genetic
algorithms", [ICGA89], 60-69.
Whitley, D. et al. (1989) "The GENITOR algorithm and selection
pressure: why rank-based allocation of reproductive trials is best",
[ICGA89], 116-121.
Goldberg, D. et al. (1991) "Don't worry, be messy", [ICGA91], 24-30.
Eshelman, L.J. et al. (1991) "Preventing premature convergence in
Genetic Algorithms by preventing incest", [ICGA91], 115-122.
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.
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.
Grefenstette, J.J. (1989) "A system for learning control strategies
with genetic algorithms", [ICGA89], 183-190.
De Jong K.A. & Spears W. (1991) "Learning concept classification
rules using genetic algorithms". Proc. 12th IJCAI, 651-656, Sydney,
Australia: 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.
Issue 1.10 Posted: 20 December 1993 38
FAQ(1/3) ANSWERS FAQ(1/3)
A4.1) What about Tierra, VENUS, etc.?
None of these are Evolutionary Algorithms, but all of them use the
evolutionary methaphora 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 characterize 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
Issue 1.10 Posted: 20 December 1993 39
FAQ(1/3) ANSWERS FAQ(1/3)
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)
Further Reseach on Tierra?
This (future) project involves inoculating the process of EVOLUTION
into an artificial medium. Self-replicating machine code algorithms
(``creatures'') are run on computers in which MUTATIONs occur in the
form of bit flips. The result is evolution by natural selection. The
project encompasses both biological and computational goals: To study
the PROCESS of evolution in detail, through analysis of sequences of
events and genetic changes. To observe the envelopes of evolutionary
possibilities, both under identical and very different conditions. To
understand what factors affect the shapes of phylogenetic trees. To
understand what are the elements of evolvability in genetic
languages. To understand what elements are required for an evolving
system to spontaneously increase in diversity and complexity, as in
the transition from single celled to multi-cellular life. To
experiment with the control of evolution of machine code algorithms,
for the purpose of breeding programs to do useful work. This work
will lead to a greater understanding of the process of evolution, and
to the possible forms that life may take on throughout the universe.
In addition, it may provide a means (through evolution) of developing
the software of the future, particularly software for massively
parallel computers.
--- "A Proposal: Evolution of Digital Organisms" by Tom Ray (1992)
How to get Tierra?
The Tierra V4.1 source code; and the source code, and DOS executables
of all tools is available now. Please note that the source code in
the ftp site and the source code provided on disk will each compile
and run on either DOS or UNIX platforms. It is exactly the same
source code in either case. The DOS executables are available only
on disk, and can not be freely distributed.
If you purchase this program on disk, thank you for your support. If
you obtain the source code through the net or friends, we invite you
to contribute an amount that represents the program's worth to you.
You may make a check in US dollars payable to Virtual Life, and mail
Issue 1.10 Posted: 20 December 1993 40
FAQ(1/3) ANSWERS FAQ(1/3)
the check to the address listed below.
Tierra by FTP?
If you use the software, be sure to pick up new versions from the ftp
site. The source in the ftp site will be replaced on an occassional
basis.
The complete source code and documentation (but not executables) is
available by anonymous ftp at:
tierra.slhs.udel.edu [128.175.41.34] and
life.slhs.udel.edu [128.175.41.33]
in the directories: almond/, beagle/, doc/, and tierra/.
To get it, ftp to tierra or life, log in as user "anonymous" and give
your email address (eg. tom@udel.edu) as a password. Be sure to
transfer binaries in binary mode (it is safe to transfer everything
in binary mode). Each directory contains a compressed tar file
(filename.tar.Z) and a SRC directory that contains all the files in
raw ascii format. You can just pick up the .tar.Z files, and they
will expand into the complete directory structure with the following
commands (Unix only):
uncompress tierra.tar.Z
tar oxvf tierra.tar
Tierra by snail mail?
The source code, documentation and the beagle.exe file can be
distributed freely, however, the executables (the .exe files in DOS)
are for sale and cannot be freely distributed (with the exeception of
beagle.exe).
If you do not have ftp access you may obtain everything on DOS disks
by making a check for $50 (US dollars drawn on a US bank) payable to
Virtual Life. $20 for upgrade from earlier version (please specify
your serial number and version number). Specify 3.5" 720K, or 3.5"
1.4Mb, or 5.25" 360K, or 5.25" 1.2Mb disks. Send the check to the
following address:
Virtual Life
25631 Jorgensen Rd.
Newman, CA 95360
The DOS disks contain everything but ALmond (ALmond can be provided
on disk by request, but it only runs on a Unix platform). The disks
include DOS executables, source code and documentation. The DOS
disks include an easy installation program. This is the same source
code available in the ftp site. If you have ftp access and a
compiler, there is no need to buy the disks.
Issue 1.10 Posted: 20 December 1993 41
FAQ(1/3) ANSWERS FAQ(1/3)
References
Ray, T. S. (1991) "Is it alive, or is it GA?" Proceedings of the
1991 International Conference on Genetic Algorithms, Eds. Belew, R.
K., and L. B. Booker, San Mateo, CA: Morgan Kaufmann, 527--534.
Ray, T. S. (1991) "An approach to the synthesis of life."
Artificial Life II, Santa Fe Institute Studies in the Sciences of
Complexity, vol. XI, Eds. C. Langton, C. Taylor, J. D. Farmer, & S.
Rasmussen, Redwood City, CA: Addison-Wesley, 371--408.
Ray, T. S. (1991) "Population dynamics of digital organisms."
Artificial Life II Video Proceedings, Ed. C. G. Langton, Redwood
City, CA: Addison Wesley.
Ray, T. S. (1991) "Evolution and optimization of digital
organisms." Scientific Excellence in Supercomputing: The IBM 1990
Contest Prize Papers, Eds. Keith R. Billingsley, Ed Derohanes, Hilton
Brown, III. Athens, GA, 30602, The Baldwin Press, The University of
Georgia.
Ray, T. S. (1992) "Evolution, ecology and optimization of digital
organisms." Santa Fe Institute working paper 92-08-042.
Ray, T. S. "Evolution, complexity, entropy, and artificial reality."
submitted Physica D. Avail. as
"tierra.slhs.udel.edu:/doc/PhysicaD.tex"
Ray, T. S. (1993) "An evolutionary approach to synthetic biology,
Zen and the art of creating life. Artificial Life 1(1): (in press).
Avail. as "tierra.slhs.udel.edu:/doc/Zen.tex"
VENUS
Steen Rasmussen's (et al.) VENUS I+II "coreworlds" as described in
[ALIFEII] and [LEVY92], are inspired by A.K. Dewdney's well-known
article (Dewdney 1984). Dewdney proposed a game called "Core Wars",
in which hackers create computer programs that battle for control of
a computer's "core" memory (Strack 93). Since computer programs are
just patterns of information, a successful program in core wars is
one that replicates its pattern within the memory, so that eventually
most of the memory contains its pattern rather than that of the
competing program.
VENUS is a modification of Core Wars in which the Computer programs
can mutate, thus the pseudo assembler code creatures of VENUS evolve
steadily. Furthermore each memory location is endowed with
"resources" which, like sunshine are added at a steady state. A
program must have sufficient resources in the regions of memory it
occupies in order to execute. The input of resources determines
whether the VENUS ecosystem is a "jungle" or a "desert." In jungle
ENVIRONMENTs, Rasmussen et al. observe the spontaneous emergence of
Issue 1.10 Posted: 20 December 1993 42
FAQ(1/3) ANSWERS FAQ(1/3)
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 as file
"pub/usenet/news.answers/games/corewar-faq.Z".
PolyWorld
Larry Yaeger's PolyWorld as described in [ALIFEIII] and [LEVY92] is
available via anonymous ftp from ftp.apple.com in directory
"/pub/polyworld".
"The subdirectories in this "polyworld" area contain the source code
for the PolyWorld ecological simulator, designed and written by Larry
Yaeger, and Copyright 1990, 1991, 1992 by Apple Computer.
PostScript versions of my Artificial Life III technical paper have
now been added to the directory. These should be directly printable
from most machines. Because some unix systems' "lpr" commands cannot
handle very large files (ours at least), I have split the paper into
Yaeger.ALife3.1.ps and Yaeger.ALife3.2.ps. These files can be ftp-ed
in "ascii" mode. For unix users I have also included compressed
versions of both these files (indicated by the .Z suffix), but have
left the uncompressed versions around for people connecting from non-
unix systems. I have not generated PostScript versions of the
images, because they are color and the resulting files are much too
large to store, retrieve, or print. Accordingly, though I have
removed a Word-formatted version of the textual body of the paper
that used to be here, I have left a Word-formatted version of the
color images. If you wish to acquire it, you will need to use the
binary transfer mode to move it to first your unix host and then to a
Macintosh (unless Word on a PC can read it - I don't know), and you
may need to do something nasty like use ResEdit to set the file type
and creator to match those of a standard Word document (Type = WDBN,
Creator = MSWD). [..]"
Issue 1.10 Posted: 20 December 1993 43
FAQ(1/3) ANSWERS FAQ(1/3)
--- from the README by Larry Yaeger <larryy@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
Issue 1.10 Posted: 20 December 1993 44
--
-joke
--
Joerg Heitkoetter
Systems Analysis Group "Why was I born with such
University of Dortmund, Germany contemporaries?"
<joke@ls11.informatik.uni-dortmund.de> -- Oscar Wilde
Technical Details
Message-ID:
<part1_757015572@lusty.informatik.uni-dortmund.de>Path:
arc1-ca.pugleaf.net!bloom-beacon.mit.edu!usc.edu!cs.utexas.edu!uunet!Germany.EU.net!Informatik.Uni-Dortmund.DE!home!heitkoetReferences:
<NEWS_757015572@lusty.informatik.uni-dortmund.de>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!bloom-beacon.mit.edu!usc.edu!cs.utexas.edu!uunet!Germany.EU.net!Informatik.Uni-Dortmund.DE!home!heitkoet
From: joke@ls11.informatik.uni-dortmund.de (Joerg Heitkoetter)
Newsgroups: comp.ai.genetic,comp.answers,news.answers
Subject: FAQ: comp.ai.genetic part 1/3 (A Guide to Frequently Asked Questions)
Supersedes: <part1_753815849@lusty.informatik.uni-dortmund.de>
Followup-To: comp.ai.genetic
Date: 27 Dec 1993 18:06:17 GMT
Organization: CS Department, University of Dortmund, Germany
Lines: 2917
Approved: news-answers-request@MIT.Edu
Message-ID: <part1_757015572@lusty.informatik.uni-dortmund.de>
References: <NEWS_757015572@lusty.informatik.uni-dortmund.de>
NNTP-Posting-Host: home.informatik.uni-dortmund.de
Summary: This is part 1 of a trilogy entitled "The Hitch-Hiker's Guide
to Evolutionary Computation". A monthly published list of Frequently
Asked Questions (and their answers) about Evolutionary Algorithms,
Life and Everything. It should be read by anyone who whishes to post
to the comp.ai.genetic newsgroup, preferably *before* posting.
Originator: joke@ls11.informatik.uni-dortmund.de (Joerg Heitkoetter)