FAQ: comp.ai.genetic part 2/6 (A Guide to Frequently Asked Questions)
From: David.Beasley@cs.cf.ac.uk (David Beasley)
Newsgroups: comp.ai.genetic,comp.answers,news.answers
Subject: FAQ: comp.ai.genetic part 2/6 (A Guide to Frequently Asked Questions)
Supersedes: <part2_866739275@cs.cf.ac.uk>
Followup-To: comp.ai.genetic
Date: 8 Oct 1997 11:39:04 GMT
Organization: Posted through the Joint Cardiff Computing Service, Wales, UK
Expires: 10 Jan 1998 11:39:01 GMT
Message-ID: <part2_876310741@cs.cf.ac.uk>
References: <part1_876310741@cs.cf.ac.uk>
Summary: This is part 2 of a <trilogy> entitled "The Hitch-Hiker's Guide
to Evolutionary Computation". A periodically published list of Frequently
Asked Questions (and their answers) about Evolutionary Algorithms,
Life and Everything. It should be read by anyone who whishes to post
to the comp.ai.genetic newsgroup, preferably *before* posting.
Archive-name: ai-faq/genetic/part2
Last-Modified: 10/8/97
Issue: 5.3
TABLE OF CONTENTS OF PART 2
Q1: What are Evolutionary Algorithms (EAs)?
Q1.1: What's a Genetic Algorithm (GA)?
Q1.2: What's Evolutionary Programming (EP)?
Q1.3: What's an Evolution Strategy (ES)?
Q1.4: What's a Classifier System (CFS)?
Q1.5: What's Genetic Programming (GP)?
----------------------------------------------------------------------
Subject: Q1: What are Evolutionary Algorithms (EAs)?
Evolutionary algorithm is an umbrella term used to describe computer-
based problem solving systems which use computational models of some
of the known mechanisms of EVOLUTION as key elements in their design
and implementation. A variety of evolutionary algorithms have been
proposed. The major ones are: GENETIC ALGORITHMs (see Q1.1),
EVOLUTIONARY PROGRAMMING (see Q1.2), EVOLUTION STRATEGIEs (see Q1.3),
CLASSIFIER SYSTEMs (see Q1.4), and GENETIC PROGRAMMING (see Q1.5).
They all share a common conceptual base of simulating the evolution
of INDIVIDUAL structures via processes of SELECTION, MUTATION, and
REPRODUCTION. The processes depend on the perceived PERFORMANCE of
the individual structures as defined by an ENVIRONMENT.
More precisely, EAs maintain a POPULATION of structures, that evolve
according to rules of selection and other operators, that are
referred to as "search operators", (or GENETIC OPERATORs), such as
RECOMBINATION and mutation. Each individual in the population
receives a measure of it's FITNESS in the environment. Reproduction
focuses attention on high fitness individuals, thus exploiting (cf.
EXPLOITATION) the available fitness information. Recombination and
mutation perturb those individuals, providing general heuristics for
EXPLORATION. Although simplistic from a biologist's viewpoint, these
algorithms are sufficiently complex to provide robust and powerful
adaptive search mechanisms.
--- "An Overview of Evolutionary Computation" [ECML93], 442-459.
BIOLOGICAL BASIS
To understand EAs, it is necessary to have some appreciation of the
biological processes on which they are based.
Firstly, we should note that EVOLUTION (in nature or anywhere else)
is not a purposive or directed process. That is, there is no
evidence to support the assertion that the goal of evolution is to
produce Mankind. Indeed, the processes of nature seem to boil down to
a haphazard GENERATION of biologically diverse organisms. Some of
evolution is determined by natural SELECTION or different INDIVIDUALs
competing for resources in the ENVIRONMENT. Some are better than
others. Those that are better are more likely to survive and
propagate their genetic material.
In nature, we see that the encoding for genetic information (GENOME)
is done in a way that admits asexual REPRODUCTION. Asexual
reproduction typically results in OFFSPRING that are genetically
identical to the PARENT. (Large numbers of organisms reproduce
asexually; this includes most bacteria which some biologists hold to
be the most successful SPECIES known.)
Sexual reproduction allows some shuffing of CHROMOSOMEs, producing
offspring that contain a combination of information from each parent.
At the molecular level what occurs (wild oversimplification alert!)
is that a pair of almost identical chromosomes bump into one another,
exchange chunks of genetic information and drift apart. This is the
RECOMBINATION operation, which is often referred to as CROSSOVER
because of the way that biologists have observed strands of
chromosomes crossing over during the exchange.
Recombination happens in an environment where the selection of who
gets to mate is largely a function of the FITNESS of the individual,
i.e. how good the individual is at competing in its environment. Some
"luck" (random effect) is usually involved too. Some EAs use a simple
function of the fitness measure to select individuals
(probabilistically) to undergo genetic operations such as crossover
or asexual reproduction (the propagation of genetic material
unaltered). This is fitness-proportionate selection. Other
implementations use a model in which certain randomly selected
individuals in a subgroup compete and the fittest is selected. This
is called tournament selection and is the form of selection we see in
nature when stags rut to vie for the privilege of mating with a herd
of hinds.
Much EA research has assumed that the two processes that most
contribute to evolution are crossover and fitness based
selection/reproduction. 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.
Evolution, by definition, absolutely requires diversity in order to
work. In nature, an important source of diversity is MUTATION. In
an EA, a large amount of diversity is usually introduced at the start
of the algorithm, by randomising the GENEs in the POPULATION. The
importance of mutation, which introduces further diversity while the
algorithm is running, therefore continues to be a matter of debate.
Some refer to it as a background operator, simply replacing some of
the original diversity which has been lost, while others view it as
playing the dominant role in the evolutionary process.
It cannot be stressed too strongly that an evolutionary algorithm (as
a SIMULATION of a genetic process) is not a random search for a
solution to a problem (highly fit individual). EAs use stochastic
processes, but the result is distinctly non-random (better than
random).
PSEUDO CODE
Algorithm EA is
// start with an initial time
t := 0;
// initialize a usually random population of individuals
initpopulation P (t);
// evaluate fitness of all initial individuals in population
evaluate P (t);
// test for termination criterion (time, fitness, etc.)
while not done do
// increase the time counter
t := t + 1;
// select sub-population for offspring production
P' := selectparents P (t);
// recombine the "genes" of selected parents
recombine P' (t);
// perturb the mated population stochastically
mutate P' (t);
// evaluate it's new fitness
evaluate P' (t);
// select the survivors from actual fitness
P := survive P,P' (t);
od
end EA.
------------------------------
Subject: Q1.1: What's a Genetic Algorithm (GA)?
The GENETIC ALGORITHM is a model of machine learning which derives
its behavior from a metaphor of some of the mechanisms of EVOLUTION
in nature. This is done by the creation within a machine of a
POPULATION of INDIVIDUALs represented by CHROMOSOMEs, in essence a
set of character strings that are analogous to the base-4 chromosomes
that we see in our own DNA. The individuals in the population then
go through a process of simulated "evolution".
Genetic algorithms are used for a number of different application
areas. An example of this would be multidimensional OPTIMIZATION
problems in which the character string of the chromosome can be used
to encode the values for the different parameters being optimized.
In practice, therefore, we can implement this genetic model of
computation by having arrays of bits or characters to represent the
chromosomes. Simple bit manipulation operations allow the
implementation of CROSSOVER, MUTATION and other operations. Although
a substantial amount of research has been performed on variable-
length strings and other structures, the majority of work with
genetic algorithms is focussed on fixed-length character strings. We
should focus on both this aspect of fixed-lengthness and the need to
encode the representation of the solution being sought as a character
string, since these are crucial aspects that distinguish GENETIC
PROGRAMMING, which does not have a fixed length representation and
there is typically no encoding of the problem.
When the genetic algorithm is implemented it is usually done in a
manner that involves the following cycle: Evaluate the FITNESS of
all of the individuals in the population. Create a new population by
performing operations such as crossover, fitness-proportionate
REPRODUCTION and mutation on the individuals whose fitness has just
been measured. Discard the old population and iterate using the new
population.
One iteration of this loop is referred to as a GENERATION. There is
no theoretical reason for this as an implementation model. Indeed,
we do not see this punctuated behavior in populations in nature as a
whole, but it is a convenient implementation model.
The first generation (generation 0) of this process operates on a
population of randomly generated individuals. From there on, the
genetic operations, in concert with the fitness measure, operate to
improve the population.
PSEUDO CODE
Algorithm GA is
// start with an initial time
t := 0;
// initialize a usually random population of individuals
initpopulation P (t);
// evaluate fitness of all initial individuals of population
evaluate P (t);
// test for termination criterion (time, fitness, etc.)
while not done do
// increase the time counter
t := t + 1;
// select a sub-population for offspring production
P' := selectparents P (t);
// recombine the "genes" of selected parents
recombine P' (t);
// perturb the mated population stochastically
mutate P' (t);
// evaluate it's new fitness
evaluate P' (t);
// select the survivors from actual fitness
P := survive P,P' (t);
od
end GA.
------------------------------
Subject: Q1.2: What's Evolutionary Programming (EP)?
Introduction
EVOLUTIONARY PROGRAMMING, originally conceived by Lawrence J. Fogel
in 1960, is a stochastic OPTIMIZATION strategy similar to GENETIC
ALGORITHMs, but instead places emphasis on the behavioral linkage
between PARENTs and their OFFSPRING, rather than seeking to emulate
specific GENETIC OPERATORS as observed in nature. Evolutionary
programming is similar to EVOLUTION STRATEGIES, although the two
approaches developed independently (see below).
Like both ES and GAs, EP is a useful method of optimization when
other techniques such as gradient descent or direct, analytical
discovery are not possible. Combinatoric and real-valued FUNCTION
OPTIMIZATION in which the optimization surface or FITNESS landscape
is "rugged", possessing many locally optimal solutions, are well
suited for evolutionary programming.
History
The 1966 book, "Artificial Intelligence Through Simulated Evolution"
by Fogel, Owens and Walsh is the landmark publication for EP
applications, although many other papers appear earlier in the
literature. In the book, finite state automata were evolved to
predict symbol strings generated from Markov processes and non-
stationary time series. Such evolutionary prediction was motivated
by a recognition that prediction is a keystone to intelligent
behavior (defined in terms of adaptive behavior, in that the
intelligent organism must anticipate events in order to adapt
behavior in light of a goal).
In 1992, the First Annual Conference on evolutionary programming was
held in La Jolla, CA. Further conferences have been held annually
(See Q12). The conferences attract a diverse group of academic,
commercial and military researchers engaged in both developing the
theory of the EP technique and in applying EP to a wide range of
optimization problems, both in engineering and biology.
Rather than list and analyze the sources in detail, several
fundamental sources are listed below which should serve as good
pointers to the entire body of work in the field.
The Process
For EP, like GAs, there is an underlying assumption that a fitness
landscape can be characterized in terms of variables, and that there
is an optimum solution (or multiple such optima) in terms of those
variables. For example, if one were trying to find the shortest path
in a Traveling Salesman Problem, each solution would be a path. The
length of the path could be expressed as a number, which would serve
as the solution's fitness. The fitness landscape for this problem
could be characterized as a hypersurface proportional to the path
lengths in a space of possible paths. The goal would be to find the
globally shortest path in that space, or more practically, to find
very short tours very quickly.
The basic EP method involves 3 steps (Repeat until a threshold for
iteration is exceeded or an adequate solution is obtained):
(1) Choose an initial POPULATION of trial solutions at random. The
number of solutions in a population is highly relevant to the
speed of optimization, but no definite answers are available as
to how many solutions are appropriate (other than >1) and how
many solutions are just wasteful.
(2) Each solution is replicated into a new population. Each of
these offspring solutions are mutated according to a
distribution of MUTATION types, ranging from minor to extreme
with a continuum of mutation types between. The severity of
MUTATION is judged on the basis of the functional change imposed
on the parents.
(3) Each offspring solution is assessed by computing it's fitness.
Typically, a stochastic tournament is held to determine N
solutions to be retained for the population of solutions,
although this is occasionally performed deterministically.
There is no requirement that the population size be held
constant, however, nor that only a single offspring be generated
from each parent.
It should be pointed out that EP typically does not use any CROSSOVER
as a GENETIC OPERATOR.
EP and GAs
There are two important ways in which EP differs from GAs.
First, there is no constraint on the representation. The typical GA
approach involves encoding the problem solutions as a string of
representative tokens, the GENOME. In EP, the representation follows
from the problem. A neural network can be represented in the same
manner as it is implemented, for example, because the mutation
operation does not demand a linear encoding. (In this case, for a
fixed topology, real- valued weights could be coded directly as their
real values and mutation operates by perturbing a weight vector with
a zero mean multivariate Gaussian perturbation. For variable
topologies, the architecture is also perturbed, often using Poisson
distributed additions and deletions.)
Second, the mutation operation simply changes aspects of the solution
according to a statistical distribution which weights minor
variations in the behavior of the offspring as highly probable and
substantial variations as increasingly unlikely. Further, the
severity of mutations is often reduced as the global optimum is
approached. There is a certain tautology here: if the global optimum
is not already known, how can the spread of the mutation operation be
damped as the solutions approach it? Several techniques have been
proposed and implemented which address this difficulty, the most
widely studied being the "Meta-Evolutionary" technique in which the
variance of the mutation distribution is subject to mutation by a
fixed variance mutation operator and evolves along with the solution.
EP and ES
The first communication between the evolutionary programming and
EVOLUTION STRATEGY groups occurred in early 1992, just prior to the
first annual EP conference. Despite their independent development
over 30 years, they share many similarities. When implemented to
solve real-valued function optimization problems, both typically
operate on the real values themselves (rather than any coding of the
real values as is often done in GAs). Multivariate zero mean Gaussian
mutations are applied to each parent in a population and a SELECTION
mechanism is applied to determine which solutions to remove (i.e.,
"cull") from the population. The similarities extend to the use of
self-adaptive methods for determining the appropriate mutations to
use -- methods in which each parent carries not only a potential
solution to the problem at hand, but also information on how it will
distribute new trials (offspring). Most of the theoretical results on
convergence (both asymptotic and velocity) developed for ES or EP
also apply directly to the other.
The main differences between ES and EP are:
1. Selection: EP typically uses stochastic selection via a
tournament. Each trial solution in the population faces
competition against a preselected number of opponents and
receives a "win" if it is at least as good as its opponent in
each encounter. Selection then eliminates those solutions with
the least wins. In contrast, ES typically uses deterministic
selection in which the worst solutions are purged from the
population based directly on their function evaluation.
2. RECOMBINATION: EP is an abstraction of EVOLUTION at the level of
reproductive populations (i.e., SPECIES) and thus no
recombination mechanisms are typically used because
recombination does not occur between species (by definition: see
Mayr's biological species concept). In contrast, ES is an
abstraction of evolution at the level of INDIVIDUAL behavior.
When self-adaptive information is incorporated this is purely
genetic information (as opposed to phenotypic) and thus some
forms of recombination are reasonable and many forms of
recombination have been implemented within ES. Again, the
effectiveness of such operators depends on the problem at hand.
References
Some references which provide an excellent introduction (by no means
extensive) to the field, include:
Artificial Intelligence Through Simulated Evolution [Fogel66]
(primary)
Fogel DB (1995) "Evolutionary Computation: Toward a New Philosophy of
Machine Intelligence," IEEE Press, Piscataway, NJ.
Proceeding of the first [EP92], second [EP93] and third [EP94] Annual
Conference on Evolutionary Programming (primary) (See Q12).
PSEUDO CODE
Algorithm EP is
// start with an initial time
t := 0;
// initialize a usually random population of individuals
initpopulation P (t);
// evaluate fitness of all initial individuals of population
evaluate P (t);
// test for termination criterion (time, fitness, etc.)
while not done do
// perturb the whole population stochastically
P'(t) := mutate P (t);
// evaluate it's new fitness
evaluate P' (t);
// stochastically select the survivors from actual fitness
P(t+1) := survive P(t),P'(t);
// increase the time counter
t := t + 1;
od
end EP.
[Eds note: An extended version of this introduction is available from
ENCORE (see Q15.3) in /FAQ/supplements/what-is-ep ]
------------------------------
Subject: Q1.3: What's an Evolution Strategy (ES)?
In 1963 two students at the Technical University of Berlin (TUB) met
and were soon to collaborate on experiments which used the wind
tunnel of the Institute of Flow Engineering. During the search for
the optimal shapes of bodies in a flow, which was then a matter of
laborious intuitive experimentation, the idea was conceived of
proceeding strategically. However, attempts with the coordinate and
simple gradient strategies (cf Q5) were unsuccessful. Then one of
the students, Ingo Rechenberg, now Professor of Bionics and
Evolutionary Engineering, hit upon the idea of trying random changes
in the parameters defining the shape, following the example of
natural MUTATIONs. The EVOLUTION STRATEGY was born. A third
student, Peter Bienert, joined them and started the construction of
an automatic experimenter, which would work according to the simple
rules of mutation and SELECTION. The second student, Hans-Paul
Schwefel, set about testing the efficiency of the new methods with
the help of a Zuse Z23 computer; for there were plenty of objections
to these "random strategies."
In spite of an occasional lack of financial support, the Evolutionary
Engineering Group which had been formed held firmly together. Ingo
Rechenberg received his doctorate in 1970 (Rechenberg 73). It
contains the theory of the two membered EVOLUTION strategy and a
first proposal for a multimembered strategy which in the nomenclature
introduced here is of the (m+1) type. In the same year financial
support from the Deutsche Forschungsgemeinschaft (DFG, Germany's
National Science Foundation) enabled the work, that was concluded, at
least temporarily, in 1974 with the thesis "Evolutionsstrategie und
numerische Optimierung" (Schwefel 77).
Thus, EVOLUTION STRATEGIEs were invented to solve technical
OPTIMIZATION problems (TOPs) like e.g. constructing an optimal
flashing nozzle, and until recently ES were only known to civil
engineering folks, as an alternative to standard solutions. Usually
no closed form analytical objective function is available for TOPs
and hence, no applicable optimization method exists, but the
engineer's intuition.
The first attempts to imitate principles of organic evolution on a
computer still resembled the iterative optimization methods known up
to that time (cf Q5): In a two-membered or (1+1) ES, one PARENT
generates one OFFSPRING per GENERATION by applying NORMALLY
DISTRIBUTED mutations, i.e. smaller steps occur more likely than big
ones, until a child performs better than its ancestor and takes its
place. Because of this simple structure, theoretical results for
STEPSIZE control and CONVERGENCE VELOCITY could be derived. The ratio
between successful and all mutations should come to 1/5: the so-
called 1/5 SUCCESS RULE was discovered. This first algorithm, using
mutation only, has then been enhanced to a (m+1) strategy which
incorporated RECOMBINATION due to several, i.e. m parents being
available. The mutation scheme and the exogenous stepsize control
were taken across unchanged from (1+1) ESs.
Schwefel later generalized these strategies to the multimembered ES
now denoted by (m+l) and (m,l) which imitates the following basic
principles of organic evolution: a POPULATION, leading to the
possibility of recombination with random mating, mutation and
selection. These strategies are termed PLUS STRATEGY and COMMA
STRATEGY, respectively: in the plus case, the parental generation is
taken into account during selection, while in the comma case only the
offspring undergoes selection, and the parents die off. m (usually a
lowercase mu, denotes the population size, and l, usually a lowercase
lambda denotes the number of offspring generated per generation). Or
to put it in an utterly insignificant and hopelessly outdated
language:
(define (Evolution-strategy population)
(if (terminate? population)
population
(evolution-strategy
(select
(cond (plus-strategy?
(union (mutate
(recombine population))
population))
(comma-strategy?
(mutate
(recombine population))))))))
However, dealing with ES is sometimes seen as "strong tobacco," for
it takes a decent amount of probability theory and applied STATISTICS
to understand the inner workings of an ES, while it navigates through
the hyperspace of the usually n-dimensional problem space, by
throwing hyperelipses into the deep...
Luckily, this medium doesn't allow for much mathematical ballyhoo;
the author therefore has to come up with a simple but brilliantly
intriguing explanation to save the reader from falling asleep during
the rest of this section, so here we go:
Imagine a black box. A large black box. As large as, say for example,
a Coca-Cola vending machine. Now, [..] (to be continued)
A single INDIVIDUAL of the ES' population consists of the following
GENOTYPE representing a point in the SEARCH SPACE:
OBJECT VARIABLES
Real-valued x_i have to be tuned by recombination and mutation
such that an objective function reaches its global optimum.
Referring to the metaphor mentioned previously, the x_i
represent the regulators of the alien Coka-Cola vending machine.
STRATEGY VARIABLEs
Real-valued s_i (usually denoted by a lowercase sigma) or mean
stepsizes determine the mutability of the x_i. They represent
the STANDARD DEVIATION of a (0, s_i) GAUSSIAN DISTRIBUTION (GD)
being added to each x_i as an undirected mutation. With an
"expectancy value" of 0 the parents will produce offspring
similar to themselves on average. In order to make a doubling
and a halving of a stepsize equally probable, the s_i mutate
log-normally, distributed, i.e. exp(GD), from generation to
generation. These stepsizes hide the internal model the
population has made of its ENVIRONMENT, i.e. a SELF-ADAPTATION
of the stepsizes has replaced the exogenous control of the (1+1)
ES.
This concept works because selection sooner or later prefers
those individuals having built a good model of the objective
function, thus producing better offspring. Hence, learning takes
place on two levels: (1) at the genotypic, i.e. the object and
strategy variable level and (2) at the phenotypic level, i.e.
the FITNESS level.
Depending on an individual's x_i, the resulting objective
function value f(x), where x denotes the vector of objective
variables, serves as the PHENOTYPE (fitness) in the selection
step. In a plus strategy, the m best of all (m+l) individuals
survive to become the parents of the next generation. Using the
comma variant, selection takes place only among the l offspring.
The second scheme is more realistic and therefore more
successful, because no individual may survive forever, which
could at least theoretically occur using the plus variant.
Untypical for conventional optimization algorithms and lavish at
first sight, a comma strategy allowing intermediate
deterioration performs better! Only by forgetting highly fit
individuals can a permanent adaptation of the stepsizes take
place and avoid long stagnation phases due to misadapted s_i's.
This means that these individuals have built an internal model
that is no longer appropriate for further progress, and thus
should better be discarded.
By choosing a certain ratio m/l, one can determine the
convergence property of the evolution strategy: If one wants a
fast, but local convergence, one should choose a small HARD
SELECTION, ratio, e.g. (5,100), but looking for the global
optimum, one should favour a softer selection (15,100).
Self-adaptation within ESs depends on the following agents
(Schwefel 87):
Randomness: One cannot model mutation
as a purely random process. This would mean that a child is
completely independent of its parents.
Population size: The population has to be sufficiently large. Not
only
the current best should be allowed to reproduce, but a set of
good individuals. Biologists have coined the term "requisite
variety" to mean the genetic variety necessary to prevent a
SPECIES from becoming poorer and poorer genetically and
eventually dying out.
COOPERATION:
In order to exploit the effects of a population (m > 1), the
individuals should recombine their knowledge with that of others
(cooperate) because one cannot expect the knowledge to
accumulate in the best individual only.
Deterioration: In order to allow better internal models (stepsizes)
to provide better progress in the future, one should accept
deterioration from one generation to the next. A limited life-
span in nature is not a sign of failure, but an important means
of preventing a species from freezing genetically.
ESs prove to be successful when compared to other iterative
methods on a large number of test problems (Schwefel 77). They
are adaptable to nearly all sorts of problems in optimization,
because they need very little information about the problem,
especially no derivatives of the objective function. For a list
of some 300 applications of EAs, see the SyS-2/92 report (cf
Q14). ESs are capable of solving high dimensional, multimodal,
nonlinear problems subject to linear and/or nonlinear
constraints. The objective function can also, e.g. be the
result of a SIMULATION, it does not have to be given in a closed
form. This also holds for the constraints which may represent
the outcome of, e.g. a finite elements method (FEM). ESs have
been adapted to VECTOR OPTIMIZATION problems (Kursawe 92), and
they can also serve as a heuristic for NP-complete combinatorial
problems like the TRAVELLING SALESMAN PROBLEM or problems with a
noisy or changing response surface.
References
Kursawe, F. (1992) " Evolution strategies for vector
optimization", Taipei, National Chiao Tung University, 187-193.
Kursawe, F. (1994) " Evolution strategies: Simple models of
natural processes?", Revue Internationale de Systemique, France
(to appear).
Rechenberg, I. (1973) "Evolutionsstrategie: Optimierung
technischer Systeme nach Prinzipien der biologischen Evolution",
Stuttgart: Fromman-Holzboog.
Schwefel, H.-P. (1977) "Numerische Optimierung von
Computermodellen mittels der Evolutionsstrategie", Basel:
Birkhaeuser.
Schwefel, H.-P. (1987) "Collective Phaenomena in Evolutionary
Systems", 31st Annu. Meet. Inter'l Soc. for General System
Research, Budapest, 1025-1033.
------------------------------
Subject: Q1.4: What's a Classifier System (CFS)?
The name of the Game
First, a word on naming conventions is due, for no other paradigm of
EC has undergone more changes to it's name space than this one.
Initially, Holland called his cognitive models "Classifier Systems"
abbrv. with CS, and sometimes CFS, as can be found in [GOLD89].
Whence Riolo came into play in 1986 and Holland added a reinforcement
component to the overall design of a CFS, that emphasized its ability
to learn. So, the word "learning" was prepended to the name, to make:
"Learning Classifier Systems" (abbrv. to LCS). On October 6-9, 1992
the "1st Inter'l Workshop on Learning Classifier Systems" took place
at the NASA Johnson Space Center, Houston, TX. A summary of this
"summit" of all leading researchers in LCS can be found on ENCORE
(See Q15.3) in file CFS/papers/lcs92.ps.gz
Today, the story continues, LCSs are sometimes subsumed under a "new"
machine learning paradigm called "Evolutionary Reinforcement
Learning" or ERL for short, incorporating LCSs, "Q-Learning", devised
by Watkins (1989), and a paradigm of the same name, devised by Ackley
and Littman [ALIFEIII].
And then, this latter statement is really somewhat confusing, as
Marco Dorigo has pointed out in a letter to editors of this guide,
since Q-Learning has no evolutionary component. So please let the
Senior Editor explain: When I wrote this part of the guide, I just
had in mind that Q-Learning would make for a pretty good replacement
of Holland's bucket-brigade algorithm, so I used this litte
speculation to see what comes out of it; in early December 95, almost
two years later, it has finally caught Marco's attention. But
meanwhile, I have been proven right: Wilson has suggested to use Q-
Learning in CLASSIFIER SYSTEM (Wilson 1994) and Dorigo & Bersini
(1994) have shown that Q-Learning and the bucket-brigade are truly
equivalent concepts.
We would therefore be allowed to call a CFS that uses Q-Learning for
rule discovery, rather than a bucket-brigade, a Q-CFS, Q-LCS, or Q-
CS; in any case would the result be subsumed under the term ERL, even
if Q-Learning itself is not an evolutionary algorithm!
Interestingly, Wilson called his system ZCS (apparantly no "Q"
inside), while Dorigo & Bersini called their system a D-Max-VSCS, or
"discounted max very simple classifier system" (and if you know Q-
Learning at least the D-Max part of the name will remind you of that
algorithm). The latter paper can be found on Encore (see Q15.3) in
file CFS/papers/sab94.ps.gz
And by the way in [HOLLAND95] the term "classifier system" is not
used anymore. You cannot find it in the index. It's a gone! Holland
now stresses the adaptive component of his invention, and simply
calls the resulting systems adaptive agents. These agents are then
implemented within the framework of his recent invention called ECHO.
(See http://alife.santafe.edu/alife/software/echo.html for more.)
On Schema Processors and ANIMATS
So, to get back to the question above, "What are CFSs?", we first
might answer, "Well, there are many interpretations of Holland's
ideas...what do you like to know in particular?" And then we'd start
with a recitation from [HOLLAND75], [HOLLAND92], and explain all the
SCHEMA processors, the broadcast language, etc. But, we will take a
more comprehensive, and intuitive way to understand what CLASSIFIER
SYSTEMs are all about.
The easiest road to explore the very nature of classifier systems, is
to take the animat (ANIMAl + ROBOT = ANIMAT) "lane" devised by Booker
(1982) and later studied extensively by Wilson (1985), who also
coined the term for this approach. Work continues on animats but is
often regarded as ARTIFICIAL LIFE rather than EVOLUTIONARY
COMPUTATION. This thread of research has even its own conference
series: "Simulation of Adaptive Behavior (SAB)" (cf Q12), including
other notions from machine learning, connectionist learning,
evolutionary robotics, etc. [NB: the latter is obvious, if an animat
lives in a digital microcosm, it can be put into the real world by
implantation into an autonomous robot vehicle, that has
sensors/detectors (camera eyes, whiskers, etc.) and effectors
(wheels, robot arms, etc.); so all that's needed is to use our
algorithm as the "brain" of this vehicle, connecting the hardware
parts with the software learning component. For a fascinating intro
to the field see, e.g. Braitenberg (1984)]
classifier systems, however, are yet another offspring of John
Holland's aforementioned book, and can be seen as one of the early
applications of GAs, for CFSs use this evolutionary algorithm to
adapt their behavior toward a changing ENVIRONMENT, as is explained
below in greater detail.
Holland envisioned a cognitive system capable of classifying the
goings on in its environment, and then reacting to these goings on
appropriately. So what is needed to build such a system? Obviously,
we need (1) an environment; (2) receptors that tell our system about
the goings on; (3) effectors, that let our system manipulate its
environment; and (4) the system itself, conveniently a "black box" in
this first approach, that has (2) and (3) attached to it, and "lives"
in (1).
In the animat approach, (1) usually is an artificially created
digital world, e.g. in Booker's Gofer system, a 2 dimensional grid
that contains "food" and "poison". And the Gofer itself, that walks
across this grid and tries (a) to learn to distinguish between these
two items, and (b) survive well fed.
Much the same for Wilson's animat, called "*". Yes, 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's Poker
player LS-1 (1980) followed this "convention". Riolo's 1988 LCS
implementations on top of his CFS-C library (cf Q20), were dubbed
FSW-1 (Finite State World 1), and LETSEQ-1 (LETter SEQuence predictor
1).
So from the latter paragraph we can conclude that environment can
also mean something completely different (e.g. an infinite stream of
letters, time serieses, etc.) than in the animat approach, but
anyway; we'll stick to it, and go on.
Imagine a very simple animat, e.g. a simplified model of a frog.
Now, we know that frogs live in (a) Muppet Shows, or (b) little
ponds; so we chose the latter as our demo environment (1); and the
former for a non-Kafka-esque name of our model, so let's dub it
"Kermit".
Kermit has eyes, i.e. sensorial input detectors (2); hands and legs,
i.e. environment-manipulating effectors (3); is a spicy-fly-
detecting-and-eating device, i.e. a frog (4); so we got all the 4
pieces needed.
Inside the Black Box
The most primitive "black box" we can think of is a computer. It has
inputs (2), and outputs (3), and a message passing system inbetween,
that converts (i.e., computes), certain input messages into output
messages, according to a set of rules, usually called the "program"
of that computer. From the theory of computer science, we now borrow
the simplest of all program structures, that is something called
"production system" or PS for short. A PS has been shown to be
computationally complete by Post (1943), that's why it is sometimes
called a "Post System", and later by Minsky (1967). Although it
merely consists of a set of if-then rules, it still resembles a full-
fledged computer.
We now term a single "if-then" rule a "classifier", and choose a
representation that makes it easy to manipulate these, for example by
encoding them into binary strings. We then term the set of
classifiers, a "classifier population", and immediately know how to
breed new rules for our system: just use a GA to generate new
rules/classifiers from the current POPULATION!
All that's left are the messages floating through the black box.
They should also be simple strings of zeroes and ones, and are to be
kept in a data structure, we call "the message list".
With all this given, we can imagine the goings on inside the black
box as follows: The input interface (2) generates messages, i.e., 0/1
strings, that are written on the message list. Then these messages
are matched against the condition-part of all classifiers, to find
out which actions are to be triggered. The message list is then
emptied, and the encoded actions, themselves just messages, are
posted to the message list. Then, the output interface (3) checks
the message list for messages concerning the effectors. And the cycle
restarts.
Note, that it is possible in this set-up to have "internal messages",
because the message list is not emptied after (3) has checked; thus,
the input interface messages are added to the initially empty list.
(cf Algorithm CFS, LCS below)
The general idea of the CFS is to start from scratch, i.e., from
tabula rasa (without any knowledge) using a randomly generated
classifier population, and let the system learn its program by
induction, (cf Holland et al. 1986), this reduces the input stream to
recurrent input patterns, that must be repeated over and over again,
to enable the animat to classify its current situation/context and
react on the goings on appropriately.
What does it need to be a frog?
Let's take a look at the behavior emitted by Kermit. It lives in its
digital microwilderness where it moves around randomly. [NB: This
seemingly "random" behavior is not that random at all; for more on
instinctive, i.e., innate behavior of non-artificial animals see,
e.g. Tinbergen (1951)]
Whenever a small flying object appears, that has no stripes, Kermit
should eat it, because it's very likely a spicy fly, or other flying
insect. If it has stripes, the insect is better left alone, because
Kermit had better not bother with wasps, hornets, or bees. If Kermit
encounters a large, looming object, it immediately uses its effectors
to jump away, as far as possible.
So, part of these behavior patterns within the "pond world", in AI
sometimes called a "frame," from traditional knowledge representation
techniques, Rich (1983), can be expressed in a set of "if <condition>
then <action>" rules, as follows:
IF small, flying object to the left THEN send @
IF small, flying object to the right THEN send %
IF small, flying object centered THEN send $
IF large, looming object THEN send !
IF no large, looming object THEN send *
IF * and @ THEN move head 15 degrees left
IF * and % THEN move head 15 degrees right
IF * and $ THEN move in direction head pointing
IF ! THEN move rapidly away from direction head pointing
Now, this set of rules has to be encoded for use within a CLASSIFIER
SYSTEM. A possible encoding of the above rule set in CFS-C (Riolo)
classifier terminology. The condition part consists of two
conditions, that are combined with a logical AND, thus must be met
both to trigger the associated action. This structure needs a NOT
operation, (so we get NAND, and know from hardware design, that we
can build any computer solely with NANDs), in CFS-C this is denoted
by the `~' prefix character (rule #5).
IF THEN
0000, 00 00 00 00
0000, 00 01 00 01
0000, 00 10 00 10
1111, 01 ## 11 11
~1111, 01 ## 10 00
1000, 00 00 01 00
1000, 00 01 01 01
1000, 00 10 01 10
1111, ## ## 01 11
Obviously, string `0000' denotes small, and `00' in the fist part of
the second column, denotes flying. The last two bits of column #2
encode the direction of the object approaching, where `00' means
left, `01' means right, etc.
In rule #4 a the "don't care symbol" `#' is used, that matches `1'
and `0', i.e., the position of the large, looming object, is
completely arbitrary. A simple fact, that can save Kermit's
(artificial) life.
PSEUDO CODE (Non-Learning CFS)
Algorithm CFS is
// start with an initial time
t := 0;
// an initially empty message list
initMessageList ML (t);
// and a randomly generated population of classifiers
initClassifierPopulation P (t);
// test for cycle termination criterion (time, fitness, etc.)
while not done do
// increase the time counter
t := t + 1;
// 1. detectors check whether input messages are present
ML := readDetectors (t);
// 2. compare ML to the classifiers and save matches
ML' := matchClassifiers ML,P (t);
// 3. process new messages through output interface
ML := sendEffectors ML' (t);
od
end CFS.
To convert the previous, non-learning CFS into a learning CLASSIFIER
SYSTEM, LCS, as has been proposed in Holland (1986), it takes two
steps:
(1) the major cycle has to be changed such that the activation of
each classifier depends on some additional parameter, that can
be modified as a result of experience, i.e. reinforcement from
the ENVIRONMENT;
(2) and/or change the contents of the classifier list, i.e.,
generate new classifiers/rules, by removing, adding, or
combining condition/action-parts of existing classifiers.
The algorithm thus changes accordingly:
PSEUDO CODE (Learning CFS)
Algorithm LCS is
// start with an initial time
t := 0;
// an initially empty message list
initMessageList ML (t);
// and a randomly generated population of classifiers
initClassifierPopulation P (t);
// test for cycle termination criterion (time, fitness, etc.)
while not done do
// increase the time counter
t := t + 1;
// 1. detectors check whether input messages are present
ML := readDetectors (t);
// 2. compare ML to the classifiers and save matches
ML' := matchClassifiers ML,P (t);
// 3. highest bidding classifier(s) collected in ML' wins the
// "race" and post the(ir) message(s)
ML' := selectMatchingClassifiers ML',P (t);
// 4. tax bidding classifiers, reduce their strength
ML' := taxPostingClassifiers ML',P (t);
// 5. effectors check new message list for output msgs
ML := sendEffectors ML' (t);
// 6. receive payoff from environment (REINFORCEMENT)
C := receivePayoff (t);
// 7. distribute payoff/credit to classifiers (e.g. BBA)
P' := distributeCredit C,P (t);
// 8. Eventually (depending on t), an EA (usually a GA) is
// applied to the classifier population
if criterion then
P := generateNewRules P' (t);
else
P := P'
od
end LCS.
What's the problem with CFSs?
Just to list the currently known problems that come with CFSs, would
take some additional pages; therefore only some interesting papers
dealing with unresolved riddles are listed; probably the best paper
containing most of these is the aforementioned summary of the LCS
Workshop:
Smith, R.E. (1992) "A report on the first Inter'l Workshop on LCSs"
avail. from ENCORE (See Q15.3) in file CFS/papers/lcs92.ps.gz
Other noteworthy critiques on LCSs include:
Wilson, S.W. (1987) "Classifier Systems and the Animat Problem"
Machine Learning, 2.
Wilson, S.W. (1988) "Bid Competition and Specificity Reconsidered"
Complex Systems, 2(5):705-723.
Wilson, S.W. & Goldberg, D.E. (1989) "A critical review of classifier
systems" [ICGA89], 244-255.
Goldberg, D.E., Horn, J. & Deb, K. (1992) "What makes a problem hard
for a classifier system?" (containing the Goldberg citation below)
is also available from Encore (See Q15.3) in file
CFS/papers/lcs92-2.ps.gz
Dorigo, M. (1993) "Genetic and Non-genetic Operators in ALECSYS"
Evolutionary Computation, 1(2):151-164. The technical report, the
journal article is based on is avail. from Encore (See Q15.3) in file
CFS/papers/icsi92.ps.gz
Smith, R.E. Forrest, S. & Perelson, A.S. (1993) "Searching for
Diverse, Cooperative POPULATIONs with Genetic Algorithms"
Evolutionary Computation, 1(2):127-149.
Conclusions?
Generally speaking: "There's much to do in CFS research!"
No other notion of EC provides more space to explore and if you are
interested in a PhD in the field, you might want to take a closer
look at CFS. However, be warned!, to quote Goldberg: "classifier
systems are a quagmire---a glorious, wondrous, and inventing
quagmire, but a quagmire nonetheless."
References
Booker, L.B. (1982) "Intelligent behavior as an adaption to the task
environment" PhD Dissertation, Univ. of Michigan, Logic of Computers
Group, Ann Arbor, MI.
Braitenberg, V. (1984) "Vehicles: Experiments in Synthetic
Psychology" Boston, MA: MIT Press.
Dorigo M. & H. Bersini (1994). "A Comparison of Q-Learning and
Classifier Systems." Proceedings of From Animals to Animats, Third
International Conference on SIMULATION of Adaptive Behavior (SAB94),
Brighton, UK, D.Cliff, P.Husbands, J.-A.Meyer and S.W.Wilson (Eds.),
MIT Press, 248-255.
http://iridia.ulb.ac.be/dorigo/dorigo/conferences/IC.11-SAB94.ps.gz
Holland, J.H. (1986) "Escaping Brittleness: The possibilities of
general-purpose learning algorithms applied to parallel rule-based
systems". In: R.S. Michalski, J.G. Carbonell & T.M. Mitchell (eds),
Machine Learning: An Artificial Intelligence approach, Vol II,
593-623, Los Altos, CA: Morgan Kaufman.
Holland, J.H., et al. (1986) "Induction: Processes of Inference,
Learning, and Discovery", Cambridge, MA: MIT Press.
Holland, J.H. (1992) "Adaptation in natural and artificial systems"
Boston, MA: MIT Press.
Holland, J.H. (1995) "Hidden Order: How adaptation builds complexity"
Reading, MA: Addison-Wesley. [HOLLAND95]:
Holland, J.H. & Reitman, J.S. (1978) "Cognitive Systems based on
Adaptive Algorithms" In D.A. Waterman & F.Hayes-Roth, (eds) Pattern-
directed inference systems. NY: Academic Press.
Minsky, M.L. (1961) "Steps toward Artificial Intelligence"
Proceedings IRE, 49, 8-30. Reprinted in E.A. Feigenbaum & J. Feldman
(eds) Computers and Thought, 406-450, NY: McGraw-Hill, 1963.
Minsky, M.L. (1967) "Computation: Finite and Infinite Machines"
Englewood Cliffs, NJ: Prentice-Hall.
Post, Emil L. (1943) "Formal reductions of the general combinatorial
decision problem" American Journal of Mathematics, 65, 197-215.
Rich, E. (1983) "Artificial Intelligence" NY: McGraw-Hill.
Tinbergen, N. (1951) "The Study of Instinct" NY: Oxford Univ. Press.
Watkins, C. (1989) "Learning from Delayed Rewards" PhD Dissertation,
Department of Psychology, Cambridge Univ., UK.
Wilson, S.W. (1985) "Knowledge growth in an artificial animal" in
[ICGA85], 16-23.
Wilson, S.W. (1994) "ZCS: a zeroth level classifier system" in EC
2(1), 1-18.
------------------------------
Subject: Q1.5: What's Genetic Programming (GP)?
GENETIC PROGRAMMING is the extension of the genetic model of learning
into the space of programs. That is, the objects that constitute the
POPULATION are not fixed-length character strings that encode
possible solutions to the problem at hand, they are programs that,
when executed, "are" the candidate solutions to the problem. These
programs are expressed in genetic programming as parse trees, rather
than as lines of code. Thus, for example, the simple program "a + b
* c" would be represented as:
+
/ \
a *
/ \
b c
or, to be precise, as suitable data structures linked together to
achieve this effect. Because this is a very simple thing to do in the
programming language Lisp, many GPers tend to use Lisp. However, this
is simply an implementation detail. There are straightforward methods
to implement GP using a non-Lisp programming environment.
The programs in the population are composed of elements from the
FUNCTION SET and the TERMINAL SET, which are typically fixed sets of
symbols selected to be appropriate to the solution of problems in the
domain of interest.
In GP the CROSSOVER operation is implemented by taking randomly
selected subtrees in the INDIVIDUALs (selected according to FITNESS)
and exchanging them.
It should be pointed out that GP usually does not use any MUTATION as
a GENETIC OPERATOR.
More information is available in the GP mailing list FAQ. (See
Q15.2) and from http://www-cs-faculty.stanford.edu/~koza/
------------------------------
Copyright (c) 1993-1997 by J. Heitkoetter and D. Beasley, all rights
reserved.
This FAQ may be posted to any USENET newsgroup, on-line service, or
BBS as long as it is posted in its entirety and includes this
copyright statement. This FAQ may not be distributed for financial
gain. This FAQ may not be included in commercial collections or
compilations without express permission from the author.
End of ai-faq/genetic/part2
***************************
[
By Archive-name
| By Author
| By Category
| By Newsgroup
]
[
Home |
Latest Updates |
Archive Stats |
Search |
Usenet References |
Help
]
Send corrections/additions to the FAQ Maintainer:
Last Update December 18 1997 @ 02:12 AM faq-admin@faqs.org