Schema (genetic algorithms)
Encyclopedia
A schema is a template in computer science
used in the field of genetic algorithm
s that identifies a subset
of strings with similarities at certain string positions. Schemata are a special case of cylinder set
s; and so form a topological space
.
symbol, which means that positions 2, 3 and 5 can have a value of either 1 or 0. The order of a schema is defined as the number of fixed positions in the template, while the defining length
is the distance between the first and last specific positions. The order of 1**0*1 is 3 and its defining length is 5. The fitness of a schema is the average fitness of all strings matching the schema. The fitness of a string is a measure of the value of the encoded problem solution, as computed by a problem-specific evaluation function.
, called 
, is defined as the total number of nodes in the schema. 
is also equal to the number of nodes in the programs matching 
.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
used in the field of genetic algorithm
Genetic algorithm
A genetic algorithm is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems...
s that identifies a subset
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
of strings with similarities at certain string positions. Schemata are a special case of cylinder set
Cylinder set
In mathematics, a cylinder set is the natural open set of a product topology. Cylinder sets are particularly useful in providing the base of the natural topology of the product of a countable number of copies of a set...
s; and so form a topological space
Topological space
Topological spaces are mathematical structures that allow the formal definition of concepts such as convergence, connectedness, and continuity. They appear in virtually every branch of modern mathematics and are a central unifying notion...
.
Description
For example, consider binary strings of length 6. The schema 1**0*1 describes the set of all words of length 6 with 1's at positions 1 and 6 and a 0 at position 4. The * is a wildcardWildcard character
-Telecommunication:In telecommunications, a wildcard character is a character that may be substituted for any of a defined subset of all possible characters....
symbol, which means that positions 2, 3 and 5 can have a value of either 1 or 0. The order of a schema is defined as the number of fixed positions in the template, while the defining length
Defining length
In genetic algorithms and genetic programming defining length L is the maximum distance between two defining symbols in schema H...
is the distance between the first and last specific positions. The order of 1**0*1 is 3 and its defining length is 5. The fitness of a schema is the average fitness of all strings matching the schema. The fitness of a string is a measure of the value of the encoded problem solution, as computed by a problem-specific evaluation function.Length
The length of a schema, called , is defined as the total number of nodes in the schema. is also equal to the number of nodes in the programs matching .