A schema (: schemata) is a template in computer science used in the field of genetic algorithms that identifies a subset of strings with similarities at certain string positions. Schemata are a special case of cylinder sets, forming a basis for a product topology on strings.[1] In other words, schemata can be used to generate a topology on a space of strings.
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 the first and sixth positions and a 0 at the fourth position. The * is a wildcard 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
\delta(H)
The length of a schema
H
N(H)
N(H)
H
If the child of an individual that matches schema H does not itself match H, the schema is said to have been disrupted.
In evolutionary computing such as genetic algorithms and genetic programming, propagation refers to the inheritance of characteristics of one generation by the next. For example, a schema is propagated if individuals in the current generation match it and so do those in the next generation. Those in the next generation may be (but do not have to be) children of parents who matched it.
Recently schema have been studied using order theory.[3]
Two basic operators are defined for schema: expansion and compression. The expansion maps a schema onto a set of words which it represents, while the compression maps a set of words on to a schema.
In the following definitions
\Sigma
\Sigmal
l
\Sigma
\Sigma*
\Sigma
*
l | |
\Sigma | |
* |
l
\Sigma*
\epsilon*
s\in
l | |
\Sigma | |
* |
{\uparrow}s
expansion
s
s
\Sigmal
Where subscript
i
i
s=\epsilon*
{\uparrow}s=\emptyset
{\uparrow}s
\Sigmal
*
s
\Sigma
\Sigma=\{0,1\}
l=3
s=10*
{\uparrow}s=\{100,101\}
Conversely, for any
A\subseteq\Sigmal
{\downarrow}{A}
compression
A
A
s\in
l | |
\Sigma | |
* |
s
l
i
s
xi=yi
x,y\inA
si=xi
si=*
A=\emptyset
{\downarrow}A=\epsilon*
A
s
A=\{100,000,010\}
{\downarrow}A=**0
Schemata can be partially ordered. For any
a,b\in
l | |
\Sigma | |
* |
a\leqb
{\uparrow}a\subseteq{\uparrow}b
\leq
\epsilon*\leq11\leq1*\leq**
{\uparrow}\epsilon*\subseteq{\uparrow}11\subseteq{\uparrow}1*\subseteq{\uparrow}**=\emptyset\subseteq\{11\}\subseteq\{11,10\}\subseteq\{11,10,01,00\}
The compression and expansion operators form a Galois connection, where
\downarrow
\uparrow
For a set
A\subseteq\Sigmal
\{{\downarrow}X|X\subseteqA\}
A
l{S}(A)
For example, let
A=\{110,100,001,000\}
A
(l{S}(A),\leq)
The schematic lattice is similar to the concept lattice found in Formal concept analysis.