## Evolutionary Computation Glossary

Go to entries beginning with R

## S

### SAFIER:

An EVOLUTIONARY COMPUTATION FTP Repository, now defunct. Superceeded by ENCORE.

### SCHEMA:

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.

### SCHEMA THEOREM:

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.

### SEARCH SPACE:

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.

### SEARCH OPERATORS:

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.

### SELECTION:

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.

### SIMULATION:

The act of modeling a natural process.

### SOFT SELECTION:

The mechanism which allows inferior INDIVIDUALs in a POPULATION a non-zero probability of surviving into future GENERATIONs. See HARD SELECTION.

### SPECIATION:

(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.

### SPECIES:

(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

### STANDARD DEVIATION:

A measurement for the spread of a set of data; a measurement for the variation of a random variable.

### STATISTICS:

Descriptive measures of data; a field of mathematics that uses probability theory to gain insight into systems' behavior.

### STEPSIZE:

Typically, the average distance in the appropriate space between a PARENT and its OFFSPRING.

### STRATEGY VARIABLE:

Evolvable parameters that relate the distribution of OFFSPRING from a PARENT.

### SUB-POPULATION:

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.

### SUMMERSCHOOL:

(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.