Glossary S - HHGT Evolutionary Computation (original) (raw)

S

SAFIER:

An [EVOLUTIONARY COMPUTATION](Q99%5FE.htm#EVOLUTIONARY COMPUTATION) FTPRepository, now defunct. Superceeded by ENCORE.

SCHEMA:

A pattern of GENEvalues 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 CHROMOSOMEcontains a great many schemata, the rate of SCHEMAprocessing in the POPULATIONis 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](Q99%5FS.htm#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 INDIVIDUALsto be evaluated. [SEARCH OPERATORS](Q99%5FS.htm#SEARCH OPERATORS)in [GENETIC ALGORITHM](Q99%5FG.htm#GENETIC ALGORITHM)sare typically based on CROSSOVERand point MUTATION.Search operators in [EVOLUTION STRATEGIE](Q99%5FE.htm#EVOLUTION STRATEGIE)sand [EVOLUTIONARY PROGRAMMING](Q99%5FE.htm#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 INDIVIDUALsin a POPULATIONare chosen for REPRODUCTION,typically on the basis of favoring individuals with higher FITNESS.

SELF-ADAPTATION:

The inclusion of a mechanism not only to evolve the [OBJECT VARIABLES](Q99%5FO.htm#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 INDIVIDUALsin a POPULATIONa non-zero probability of surviving into future GENERATIONs.See [HARD SELECTION](Q99%5FH.htm#HARD SELECTION).

SPECIATION:

(biol) The process whereby a new SPECIEScomes about. The most common cause of SPECIATIONis that of geographical isolation. If a SUB-POPULATIONof a single species is separated geographically from the main POPULATIONfor a sufficiently long time, their GENEswill diverge (either due to differences in SELECTIONpressures in different locations, or simply due to [GENETIC DRIFT](Q99%5FG.htm#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 EVOLUTIONwill produce superior INDIVIDUALswhich 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 MIGRATIONis 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](Q99%5FS.htm#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 OFFSPRINGsimilar 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 INDIVIDUALsto breed together. It is probably safest to use this term only in the context of algorithms which employ explicit SPECIATIONmechanisms.

(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 PARENTand its OFFSPRING.

STRATEGY VARIABLE:

Evolvable parameters that relate the distribution of OFFSPRINGfrom a PARENT.

SUB-POPULATION:

A POPULATIONmay be sub-divided into groups, known as SUB-POPULATIONs,where INDIVIDUALsmay 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 MIGRATIONconstraints: 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](Q99%5FP.htm#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.

[Glossary top level] [HHGTEC main contents page]