schema (genetic algorithms)

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 $\backslash delta(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.

The length of a schema $H$, called $N(H)$, is defined as the total number of nodes in the schema. $N(H)$ is also equal to the number of nodes in the programs matching $H$.{{cite web|title=Foundations of Genetic Programming|url=http://www.cs.ucl.ac.uk/staff/W.Langdon/FOGP/|publisher=UCL UK|accessdate=13 July 2010}}

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.

{{cite arXiv |author=Jack McKay Fletcher and Thomas Wennkers |year=2017 |title=A natural approach to studying schema processing |eprint=1705.04536|class=cs.NE }}

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 $\backslash Sigma$ denotes an alphabet, $\backslash Sigma^l$ denotes all words of length $l$ over the alphabet $\backslash Sigma$, $\backslash Sigma\_*$ denotes the alphabet $\backslash Sigma$ with the extra symbol $*$. $\backslash Sigma\_*^l$ denotes all schema of length $l$ over the alphabet $\backslash Sigma\_*$ as well as the empty schema $\backslash epsilon\_*$.

For any schema $s\; \backslash in\; \backslash Sigma^l\_*$ the following operator $\{\backslash uparrow\}s$, called the $expansion$ of $s$, which maps $s$ to a subset of words in $\backslash Sigma^l$:

$$\{\backslash uparrow\}s\; :=\; \backslash \{b\; \backslash in\; \backslash Sigma^l\; |\; b\_i\; =\; s\_i\; \backslash mbox\{\; or\; \}\; s\_i\; =\; *\; \backslash mbox\{\; for\; each\; \}\; i\; \backslash in\; \backslash \{1,...,l\backslash \}\backslash \}$$

Where subscript $i$ denotes the character at position $i$ in a word or schema. When $s=\; \backslash epsilon\_*$ then $\{\backslash uparrow\}s\; =\; \backslash emptyset$. More simply put, $\{\backslash uparrow\}s$ is the set of all words in $\backslash Sigma^l$ that can be made by exchanging the $*$ symbols in $s$ with symbols from $\backslash Sigma$. For example, if $\backslash Sigma=\backslash \{0,1\backslash \}$, $l=3$ and $s=10*$ then $\{\backslash uparrow\}s=\backslash \{100,101\backslash \}$.

Conversely, for any $A\; \backslash subseteq\; \backslash Sigma^l$ we define $\{\backslash downarrow\}\{A\}$, called the $compression$ of $A$, which maps $A$ on to a schema $s\backslash in\; \backslash Sigma\_*^l$:

$$\{\backslash downarrow\}A:=\; s$$

where $s$ is a schema of length $l$ such that the symbol at position $i$ in $s$ is determined in the following way: if $x\_i\; =\; y\_i$ for all $x,y\; \backslash in\; A$ then $s\_i\; =\; x\_i$ otherwise $s\_i\; =\; *$. If $A\; =\; \backslash emptyset$ then $\{\backslash downarrow\}A\; =\; \backslash epsilon\_*$. One can think of this operator as stacking up all the items in $A$ and if all elements in a column are equivalent, the symbol at that position in $s$ takes this value, otherwise there is a wild card symbol. For example, let $A\; =\; \backslash \{100,000,010\backslash \}$ then $\{\backslash downarrow\}A\; =\; **0$.

Schemata can be partially ordered. For any $a,b\; \backslash in\; \backslash Sigma^l\_*$ we say $a\; \backslash leq\; b$ if and only if $\{\backslash uparrow\}a\; \backslash subseteq\; \{\backslash uparrow\}b$. It follows that $\backslash leq$ is a partial ordering on a set of schemata from the reflexivity, antisymmetry and transitivity of the subset relation. For example, $\backslash epsilon\_*\; \backslash leq\; 11\; \backslash leq\; 1*\; \backslash leq\; **$.

This is because $\{\backslash uparrow\}\backslash epsilon\_*\; \backslash subseteq\; \{\backslash uparrow\}11\; \backslash subseteq\; \{\backslash uparrow\}1*\; \backslash subseteq\; \{\backslash uparrow\}**\; =\; \backslash emptyset\; \backslash subseteq\; \backslash \{11\backslash \}\; \backslash subseteq\; \backslash \{11,10\backslash \}\; \backslash subseteq\; \backslash \{11,10,01,00\backslash \}$.

The compression and expansion operators form a Galois connection, where $\backslash downarrow$ is the lower adjoint and $\backslash uparrow$ the upper adjoint.

File:Schematic Lattice.png.

]]

For a set $A\; \backslash subseteq\; \backslash Sigma^l$, we call the process of calculating the compression on each subset of A, that is $\backslash \{\{\backslash downarrow\}X\; |\; X\; \backslash subseteq\; A\backslash \}$, the schematic completion of $A$, denoted $\backslash mathcal\{S\}(A)$.

For example, let $A\; =\; \backslash \{110,\; 100,\; 001,\; 000\backslash \}$. The schematic completion of $A$, results in the following set:

$$\backslash mathcal\{S\}(A)\; =$$

\{001, 100, 000, 110, 00*, *00, 1*0, **0, *0*, ***, \epsilon_*\}

The poset $(\backslash mathcal\{S\}(A),\backslash leq)$ always forms a complete lattice called the schematic lattice.

The schematic lattice is similar to the concept lattice found in Formal concept analysis.

{{clear}}

• Holland's schema theorem
• Formal concept analysis

{{Reflist}}

{{Evolutionary computation}}

Category:Genetic algorithms