Schema (genetic algorithms): Difference between revisions

Revision as of 20:54, 15 June 2017

Revision as of 13:37, 10 November 2017

Line 1:

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]].<ref name="Holland1">{{cite book |title=Adaptation in Natural and Artificial Systems|year=1992|edition=reprint|publisher=The MIT Press|author=Holland, John Henry |isbn=9780472084609 |url=https://books.google.com/books/about/Adaptation_in_natural_and_artificial_sys.html?id=JE5RAAAAMAAJ |deadurl=no |accessdate=22 April 2014}}</ref>

== Description ==

Line 31:

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 [[reflexivity]]{{disambiguation needed|date=June 2017}}, [[antisymmetry]] and [[transitivity]]{{disambiguation needed|date=June 2017}} 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>.

Line 45:

The [[poset]] <math>(\mathcal{S}(A),\leq)</math> always forms a [[complete lattice]] called 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]].

]]