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 evolution as key elements in their design and implementation.
A variety of evolutionary algorithms have been proposed. The major ones
are: GENETIC ALGORITHMs, EVOLUTIONARY PROGRAMMING, EVOLUTION STRATEGIEs,
CLASSIFIER SYSTEM, and GENETIC PROGRAMMING. 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.
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 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.
Biological Processes behind Evolutionary Methods:
Terms
All living organisms consist of cells.
Each cell has the same set of one
or more chromosomes (strings
of DNA).
A chromosome can be conceptually divided into
genes
(fundamental blocks of DNA - also referred to as traits like
eye color).
The different possible settings of the trait (blue, green, or brown) are
called alleles.
Each gene is located at a particular
locus (position) on the
chromosome.
Many organisms have multiple chromosomes
in each cell.
The complete collection of chromosomes is called the organism's
genome.
A particular set of genes contained in a genome
is a genotype.
The genotype gives rise to the phenotype(physical
and mental characteristics) as the organism
develops.
Organisms whose chromosomes are arrayed in pairs are called
diploid and unpaired
are called haploid.
(In nature, most sexually reproducing species are diploid, including
homo sapiens.)
During sexual reproduction, recombination
(or crossover) occurs and genes are exchanged between pairs to form
a gamete
(a single chromosome) and then gametes
from th two parents pair up to create a full set of diploid chromosomes.
In haploid reproduction, genes are exchanged between two parents'
single-strand chromosomes.
Offsring are subject to mutation
in which a single nucleotides are exchanged from parent to offspring.
The fitness of
an organism is typically defined as the probability that the organism will
live to reproduce (viablility)
or as a function of the number of offspring the organism has (fertility).
Terms as used in GAs
Chromosomes
: a candidate solution to a problem often encoded as a bit string. (mostly
haploid reproduction in employed)
Genes : are either
single bits or short blocks of adjacent bits that encode a particular element
of the candidate solution. (parameter).
Allele : a bit
string (0 or 1).
Crossover : consists
of exchanging genetic information between two chromosomes of a haploid
pair.
Mutation occurs by
flipping the bit value of an allele at a particular randomly choosen
locus.
Genotype : of an individual in a GA is the configuration
of the bits in the individual's chromosome.
Phenotype : typically
not implemented.
Evolution is not a purposeful or directed process. There is no
evidence to support the assertion that the goal of evolution is to produce
Mankind nor any other species. In fact, the processes of nature are
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
- survival of the fittest.
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 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 poplutaion. 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.
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.
PSEUDO CODE Algorithm EA:
// 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.
What's Evolutionary Programming (EP)?
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 evolutionary
strategies, although the two approaches developed independently.
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.
"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).
EPs maintain 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 iterated 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.
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.
PSEUDO CODE Algorithm EP:
// 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.
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 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 evolutionary 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. 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 "Evolutions strategie und numerische
Optimierung".
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:
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 stepwise 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...
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:
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. 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.
ESs are capable of solving high dimensional, multimodal, nonlinear problems
subject to linear and/or nonlinear constraints. The objective function
can also 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 a finite elements method (FEM). ESs have been adapted to
vector optimization problem, 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.
What's a Classifier System (CFS)?
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. When Holland added a reinforcement component to
the overall design of a CFS that emphasized its ability to learn, the word
"learning" was prepended to the name, to make: "Learning
Classifier Systems". Today 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. This latter statement is really somewhat confusing, since Q-Learning
has no evolutionary component. Q-Learning is an equivolent replacement
of Holland's bucket-brigade algorithm, 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!
And the term "classifier system" is not used anymore.
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)", including other notions from machine
learning, connectionist learning, evolutionary robotics, etc.
Classifier systems 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,eg 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 The environment
can also mean something completely different (e.g. an infinite stream of
letters, time serieses, etc.).
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. (
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, 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. [This seemingly "random" behavior is not that random
at all; for more on instinctive, i.e., innate behavior of non-artificial
animals see]
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, 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 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:
// 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:
// 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.
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."