Schema (genetic algorithms): Difference between revisions

Revision as of 11:14, 24 May 2017

Latest revision as of 16:47, 6 August 2025

(18 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 that identifies a [[subset]] of strings with similarities at certain string positions. Schemata are a special case of [[cylinder set]]s;, andforming soa form[[Base (topology)|basis]] for a [[topologicalproduct spacetopology]] on strings.<ref name="Holland1">{{cite book |title=Adaptation in Natural and Artificial Systems|year=1992|edition=reprint|publisher=The MIT Press|author=Holland, John Henry |ISBNisbn=9780472084609 |URLurl=https://books.google.com/books/about/Adaptation_in_natural_and_artificial_sys.html?id=JE5RAAAAMAAJ |deadurl=no |accessdate=22 April 2014}}</ref> In other words, schemata can be used to generate a [[Topological space|topology]] on a space of strings.

== 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 don'tdo not have to be) children of parents who matched it.

== 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|urlclass=https://arxivcs.org/pdf/1705.04536.pdfNE }} </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 27 ⟶ 28:

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

{{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[[File:Schematic aLattice.png|thumb|The setSchematic <math>A \subseteq \Sigma^l</math>,lattice weformed callfrom the processschematic ofcompletion calculatingon the compression on each subset of A, that isset <math>A=\{{\downarrow}X111, |011, X \subseteq A001\}</math>,. Here the schematic completion of <math>A</math>, denotedlattice <math>(\mathcal{S}(A),\leq)</math>.<ref nameis =shown as a [[Hasse diagram]]. "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 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>\Sigma^l = \{1,0\}^3</math> and <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) =

Line 47 ⟶ 48:

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]].

]]

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

Line 60:

{{Reflist}}

{{Evolutionary computation}}

[[Category:Genetic algorithms]]

[[Category:Genetic programming]]

{{bioinformatics-stub}}

{{compu-AI-stub}}

{{comp-sci-stub}}