Content deleted Content added
No edit summary |
→The Expansion and Compression Operators: Fixed link Tags: Mobile edit Mobile app edit Android app edit App section source |
||
| (25 intermediate revisions by 12 users not shown) | |||
Line 1:
{{Evolutionary algorithms}}
A '''schema''' ({{plural form}}: '''schemata''') is a template in [[computer science]] used in the field of [[genetic algorithm]]s
== Description ==
Line 11 ⟶ 12:
==Propagation of schema==
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
== The
{{cite
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 <math> \Sigma </math> denotes an alphabet, <math> \Sigma^l </math> denotes all words of length <math> l </math> over the alphabet <math> \Sigma </math>, <math> \Sigma_* </math> denotes the alphabet <math>\Sigma</math> with the extra symbol <math>*</math>. <math>\Sigma_*^l</math> denotes all schema of length <math> l </math> over the alphabet <math> \Sigma_* </math> as well as the empty schema <math> \epsilon_* </math>.
For any schema <math>s \in \Sigma^l_*</math> the following operator <math>{\uparrow}s</math>, called the <math>expansion</math> of <math>s</math>, which maps <math>s</math> to a subset of words in <math>\Sigma^l </math>:
<math display="block">{\uparrow}s := \{b \in \Sigma^l | b_i = s_i \mbox{ or } s_i = * \mbox{ for each } i \in \{1,...,l\}\} </math>
Where subscript <math>i</math> denotes the character at position <math>i</math> in a word or schema. When <math> s= \epsilon_*</math> then <math>{\uparrow}s = \emptyset</math>. More simply put, <math>{\uparrow}s</math> is the set of all words in <math>\Sigma^l</math> that can be made by exchanging the <math>*</math> symbols in <math>s</math> with symbols from <math>\Sigma</math>. For example, if <math>\Sigma=\{0,1\}</math>, <math>l=3</math> and <math>s=10*</math> then <math>{\uparrow}s=\{100,101\} </math>.
Conversely, for any <math>A \subseteq \Sigma^l</math> we define <math>{\downarrow}{A}</math>, called the <math>compression</math> of <math>A</math>, which maps <math>A</math> on to a schema <math>s\in \Sigma_*^l</math>:
<math display="block">{\downarrow}A:= s</math>
where <math>s</math> is a schema of length <math>l</math> such that the symbol at position <math>i</math> in <math>s</math> is determined in the following way: if <math>x_i = y_i</math> for all <math>x,y \in A</math> then <math>s_i = x_i</math> otherwise <math>s_i = *</math>. If <math>A = \emptyset</math> then <math>{\downarrow}A = \epsilon_*</math>. One can think of this operator as stacking up all the items in <math>A</math> and if all elements in a column are equivalent, the symbol at that position in <math>s</math> takes this value, otherwise there is a wild card symbol. For example, let <math>A = \{100,000,010\}</math> then <math>{\downarrow}A = **0</math>.
Schemata can be [[partially ordered]]. For any <math>a,b \in \Sigma^l_*</math> we say <math>a \leq b</math> if and only if <math>{\uparrow}a \subseteq {\uparrow}b</math>. It follows that <math>\leq</math> is a [[partial ordering]] on a set of schemata from the [[reflexive operator algebra|reflexivity]], [[Antisymmetric relation|antisymmetry]] and [[transitive relation|transitivity]] of the [[subset]] relation. For example, <math>\epsilon_* \leq 11 \leq 1* \leq **</math>.
This is because <math>{\uparrow}\epsilon_* \subseteq {\uparrow}11 \subseteq {\uparrow}1* \subseteq {\uparrow}** = \emptyset \subseteq \{11\} \subseteq \{11,10\} \subseteq \{11,10,01,00\}</math>.
The compression and expansion operators form a [[Galois connection]], where <math>\downarrow</math> is the lower adjoint and <math>\uparrow</math> the upper adjoint.<ref name="Fletcher"/>
== The Schematic Completion and The Schematic Lattice ==
[[File:Schematic Lattice.png|thumb|The Schematic lattice formed from the schematic completion on the set <math>A=\{111, 011, 001\}</math>. Here the schematic lattice <math>(\mathcal{S}(A),\leq)</math> is shown as a [[Hasse diagram]].
]]
For a set <math>A \subseteq \Sigma^l</math>, we call the process of calculating the compression on each subset of A, that is <math>\{{\downarrow}X | X \subseteq A\}</math>, the schematic completion of <math>A</math>, denoted <math>\mathcal{S}(A)</math>.<ref name="Fletcher"/>
For example, let <math>A = \{110, 100, 001, 000\}</math>. The schematic completion of <math>A</math>, results in the following set:
<math display="block">\mathcal{S}(A) =
\{001, 100, 000, 110, 00*, *00, 1*0, **0, *0*, ***, \epsilon_*\}</math>
The [[poset]] <math>(\mathcal{S}(A),\leq)</math> always forms a [[complete lattice]] called the schematic lattice.
The schematic lattice is similar to the concept lattice found in [[Formal concept analysis]].
{{clear}}
==See also==
*[[Holland's schema theorem]]
*[[Formal concept analysis]]
==References==
{{Reflist}}
{{Evolutionary computation}}
[[Category:Genetic algorithms]]
| |||