Evolutionary Computation Glossary
Go to entries beginning with R
An
EVOLUTIONARY COMPUTATION
FTP
Repository, now defunct. Superceeded by
ENCORE.
A pattern of
GENE
values in a
CHROMOSOME,
which may include `dont care' states. Thus in a binary chromosome, each
SCHEMA
(plural schemata) can be specified by a string of the same length as the chromosome, with each
character one of {0, 1, #}. A particular chromosome is said to `contain' a particular schema if it
matches the schema (e.g. chromosome 01101 matches schema #1#0#).
The `order' of a schema is the number of non-dont-care positions specified, while the `defining
length' is the distance between the furthest two non-dont-care positions. Thus #1##0# is of order 2
and defining length 3.
Theorem devised by Holland [HOLLAND92] to explain the behaviour of
GAs.
In essence, it says that a GA gives exponentially increasing reproductive trials to above average
schemata. Because each
CHROMOSOME
contains a great many schemata, the rate of
SCHEMA
processing in the
POPULATION
is very high, leading to a phenomenon known as implicit parallelism. This gives a GA with a
population of size N a speedup by a factor of N cubed, compared to a random search.
If the solution to a task can be represented by
a set of N real-valued parameters, then the job of finding this solution can be thought of as a
search in an N-dimensional space. This is referred to simply as the
SEARCH SPACE.
More generally, if the solution to a task can be represented using a representation scheme, R, then
the search space is the set of all possible configurations which may be represented in R.
Processes used to generate new
INDIVIDUALs
to be evaluated.
SEARCH OPERATORS
in
GENETIC ALGORITHMs
are typically based on
CROSSOVER
and point
MUTATION.
Search operators in
EVOLUTION STRATEGIEs
and
EVOLUTIONARY PROGRAMMING
typically follow from the representation of a solution and often involve Gaussian or lognormal
perturbations when applied to real-valued vectors.
The process by which some
INDIVIDUALs
in a
POPULATION
are chosen for
REPRODUCTION,
typically on the basis of favoring individuals with higher
FITNESS.
The inclusion of a mechanism not only to
evolve the
OBJECT VARIABLES
of a solution, but simultaneously to evolve information on how each solution will generate new
OFFSPRING.
The act of modeling a natural process.
The mechanism which allows inferior
INDIVIDUALs
in a
POPULATION
a non-zero probability of surviving into future
GENERATIONs.
See
HARD SELECTION.
(biol) The process whereby a new
SPECIES
comes about. The most common cause of
SPECIATION
is that of geographical isolation. If a
SUB-POPULATION
of a single species is separated geographically from the main
POPULATION
for a sufficiently long time, their
GENEs
will diverge (either due to differences in
SELECTION
pressures in different locations, or simply due to
GENETIC DRIFT).
Eventually, genetic differences will be so great that members of the sub-population must be
considered as belonging to a different (and new) species.
Speciation is very important in evolutionary biology. Small sub-populations can evolve much more
rapidly than a large population (because genetic changes don't take long to become fixed in the
population). Sometimes, this
EVOLUTION
will produce superior
INDIVIDUALs
which can outcompete, and eventually replace the species of the original, main population.
(EC)
Techniques analogous to geographical isolation are used in a number of
GAs.
Typically, the population is divided into sub-populations, and individuals are only allowed to mate
with others in the same sub-population. (A small amount of
MIGRATION
is performed.)
This produces many sub-populations which differ in their characteristics, and may be referred to as
different "species". This technique can be useful for finding multiple solutions to a problem, or
simply maintaining diversity in the
SEARCH SPACE.
Most biology/genetics textbooks contain information on speciation. A more detailed account can be
found in "Genetics, Speciation and the Founder Principle", L.V. Giddings, K.Y. Kaneshiro and
W.W. Anderson (Eds.), Oxford University Press 1989.
(biol) There is no universally-agreed firm definition of
a
SPECIES.
A species may be roughly defined as a collection of living creatures, having similar
characteristics, which can breed together to produce viable
OFFSPRING
similar to their
PARENTs.
Members of one species occupy the same ecological
NICHE.
(Members of different species may occupy the same, or different niches.)
(EC)
In EC the definition of "species" is less clear, since generally it is always possible for a pair
INDIVIDUALs
to breed together. It is probably safest to use this term only in the context of algorithms which
employ explicit
SPECIATION
mechanisms.
(biol) The existence of different species allows different ecological niches to be exploited.
Furthermore, the existence of a variety of different species itself creates new niches, thus
allowing room for further species. Thus nature bootstraps itself into almost limitless complexity
and diversity.
Conversely, the domination of one, or a small number of species reduces the number of viable
niches, leads to a decline in diversity, and a reduction in the ability to cope with new situations.
"Give any one species too much rope, and they'll fuck it up"
--- Roger Waters, "Amused to Death", 1992
A measurement for the spread of a
set of data; a measurement for the variation of a random variable.
Descriptive measures of data; a field of
mathematics that uses probability theory to gain insight into systems' behavior.
Typically, the average distance in the appropriate
space between a
PARENT
and its
OFFSPRING.
Evolvable parameters that relate the
distribution of
OFFSPRING
from a
PARENT.
A
POPULATION
may be sub-divided into groups, known as
SUB-POPULATIONs,
where
INDIVIDUALs
may only mate with others in the same group. (This technique might be chosen for parallel
processors). Such sub-divisions may markedly influence the evolutionary dynamics of a population
(e.g. Wright's 'shifting balance' model). Sub-populations may be defined by various
MIGRATION
constraints: islands with limited arbitrary migration; stepping-stones with migration to neighboring
islands; isolation-by-distance in which each individual mates only with near neighbors. cf
PANMICTIC POPULATION,
SPECIATION.
(USA) One of the most interesting things in the
US educational system: class work during the summer break.
Go to entries beginning with T
Go to entries beginning with:
1,
A,
B,
C,
D,
E,
F,
G,
H,
I,
L,
M,
N,
O,
P,
R,
S,
T,
U,
V,
Z.
[Glossary top level]
[HHGTEC main contents page]
Mistakes in this page?
Hitch Hiker's Guide to Evolutionary Computation,
Issue 7.4, released 18 January 2000
Copyright © 1993-2000 by J. Heitkötter and
D. Beasley, all rights reserved.