Schema (genetic algorithms): Difference between revisions

Revision as of 18:36, 11 June 2017

Revision as of 20:54, 15 June 2017

Line 15:

== The Expansion and Compression Operators ==

Recently schema have been studied using [[order theory]].<ref name = "Fletcher">

{{cite journalarxiv |author=Jack McKay Fletcher and Thomas Wennkers | year=2017 |title=A natural approach to studying schema processing |journaleprint=arXiv preprint arXiv:1705.04536|url=https://arxiv.org/pdf/1705.04536.pdf}} </ref>

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.

Line 29:

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

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"/>

{{cite journal |author=Jack McKay Fletcher and Thomas Wennkers| year=2017 |title=A natural approach to studying schema processing |journal=arXiv preprint arXiv:1705.04536|url=https://arxiv.org/pdf/1705.04536.pdf}} </ref>

== The Schematic Completion and The Schematic Lattice ==

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"/>

{{cite journal |author=Jack McKay Fletcher and Thomas Wennkers| year=2017 |title=A natural approach to studying schema processing |journal=arXiv preprint arXiv:1705.04536|url=https://arxiv.org/pdf/1705.04536.pdf}} </ref>

For example, let <math>A = \{110, 100, 001, 000\}</math>. The schematic completion of <math>A</math>, results in the following set:

Line 47 ⟶ 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 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]].

]]

Line 62 ⟶ 60:

[[Category:Genetic algorithms]]

[[Category:Genetic programming]]

{{bioinformatics-stub}}

{{compu-AI-stub}}

{{comp-sci-stub}}