スキーマ（遺伝的アルゴリズム）

スキーマ（複数形：schemata ）は、遺伝的アルゴリズムの分野で用いられるコンピュータサイエンスのテンプレートであり、特定の文字列位置における類似性を持つ文字列のサブセットを識別する。スキーマはシリンダー集合の特殊なケースであり、文字列上の積位相の基礎を形成する。^[1]つまり、スキーマは文字列空間上の位相を生成するために使用できる。

説明

例えば、長さが6のバイナリ文字列を考えてみましょう。スキーマ1**0*1は、長さが6で、1番目と6番目の位置が1、4番目の位置が0であるすべての単語の集合を表します。*はワイルドカード記号で、位置2、3、5は1または0のいずれかの値を持つことができます。スキーマの順序はテンプレート内の固定位置の数として定義され、定義長 は最初の特定の位置と最後の特定の位置の間の距離です。1**0*1の順序は3で、定義長は5です。スキーマの適合度は、スキーマに一致するすべての文字列の平均適合度です。文字列の適合度は、問題固有の評価関数によって計算される、エンコードされた問題解決の値の尺度です。 ${\displaystyle \delta (H)}$

長さ

スキーマの長さは、スキーマ内のノードの総数として定義されます。また、一致するプログラム内のノードの数と等しくなります。^[2] ${\displaystyle H}$ ${\displaystyle N(H)}$ ${\displaystyle N(H)}$ ${\displaystyle H}$

混乱

スキーマHに一致する個体の子供がスキーマHに一致しない場合、そのスキーマは破壊されたと言われる。^[2]

スキーマの伝播

遺伝的アルゴリズムや遺伝的プログラミングなどの進化的コンピューティングにおいて、伝播とは、ある世代の特性が次の世代に継承されることを指します。例えば、あるスキーマは、現世代の個体がそれに一致し、次の世代の個体もそれに一致する場合、伝播されます。次の世代の個体は、そのスキーマに一致した親の子供である場合もありますが、必ずしもそうである必要はありません。

拡張演算子と圧縮演算子

最近、スキーマは順序理論を用いて研究されている。^[3]

スキーマには、拡張と圧縮という2つの基本演算子が定義されています。拡張は、スキーマをそれが表す単語の集合にマッピングし、圧縮は、単語の集合をスキーマにマッピングします。

以下の定義では、 はアルファベット を表し、はアルファベット 上の長さのすべての単語 を表し、は追加の記号 が付いたアルファベット を表します。はアルファベット 上の長さのすべてのスキーマと空のスキーマを表します。 ${\displaystyle \Sigma }$ ${\displaystyle \Sigma ^{l}}$ ${\displaystyle l}$ ${\displaystyle \Sigma }$ ${\displaystyle \Sigma _{*}}$ ${\displaystyle \Sigma }$ ${\displaystyle *}$ ${\displaystyle \Sigma _{*}^{l}}$ ${\displaystyle l}$ ${\displaystyle \Sigma _{*}}$ ${\displaystyle \epsilon _{*}}$

任意のスキーマに対して、 と呼ばれる 次の演算子はの単語のサブセットにマッピングされます。 ${\displaystyle s\in \Sigma _{*}^{l}}$ ${\displaystyle {\uparrow }s}$ ${\displaystyle expansion}$ ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle \Sigma ^{l}}$

$${\displaystyle {\uparrow }s:=\{b\in \Sigma ^{l}|b_{i}=s_{i}{\mbox{ or }}s_{i}=*{\mbox{ for each }}i\in \{1,...,l\}\}}$$

ここで、添え字は単語またはスキーマ内の位置にある文字を表します。のとき、となります。もっと簡単に言うと、は の記号を の記号と交換することで作成できる内のすべての単語の集合です。例えば、 のとき、となります。 ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle s=\epsilon _{*}}$ ${\displaystyle {\uparrow }s=\emptyset }$ ${\displaystyle {\uparrow }s}$ ${\displaystyle \Sigma ^{l}}$ ${\displaystyle *}$ ${\displaystyle s}$ ${\displaystyle \Sigma }$ ${\displaystyle \Sigma =\{0,1\}}$ ${\displaystyle l=3}$ ${\displaystyle s=10*}$ ${\displaystyle {\uparrow }s=\{100,101\}}$

逆に、任意の に対してを定義します。これはのと呼ばれ、スキーマ にマッピングされます。ここでは長さ のスキーマであり、 の位置にあるシンボルは次のように決定されます。すべて に対してであれば 、それ以外の場合は。 であれば。この演算子は のすべての項目を積み重ねるものと考えることができ、列のすべての要素が同等であれば のその位置にあるシンボルはこの値を取り、そうでない場合はワイルドカードシンボルになります。例えば、の場合、 となります。 ${\displaystyle A\subseteq \Sigma ^{l}}$ ${\displaystyle {\downarrow }{A}}$ ${\displaystyle compression}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle s\in \Sigma _{*}^{l}}$ $${\displaystyle {\downarrow }A:=s}$$ ${\displaystyle s}$ ${\displaystyle l}$ ${\displaystyle i}$ ${\displaystyle s}$ ${\displaystyle x_{i}=y_{i}}$ ${\displaystyle x,y\in A}$ ${\displaystyle s_{i}=x_{i}}$ ${\displaystyle s_{i}=*}$ ${\displaystyle A=\emptyset }$ ${\displaystyle {\downarrow }A=\epsilon _{*}}$ ${\displaystyle A}$ ${\displaystyle s}$ ${\displaystyle A=\{100,000,010\}}$ ${\displaystyle {\downarrow }A=**0}$

スキーマは半順序付けが可能です。任意の に対して、 が である必要十分条件となります。部分集合関係の反射性、反対称性、推移性から、 はスキーマ集合上の半順序付けとなります。例えば、 です。これは だからです。 ${\displaystyle a,b\in \Sigma _{*}^{l}}$ ${\displaystyle a\leq b}$ ${\displaystyle {\uparrow }a\subseteq {\uparrow }b}$ ${\displaystyle \leq }$ ${\displaystyle \epsilon _{*}\leq 11\leq 1*\leq **}$ ${\displaystyle {\uparrow }\epsilon _{*}\subseteq {\uparrow }11\subseteq {\uparrow }1*\subseteq {\uparrow }**=\emptyset \subseteq \{11\}\subseteq \{11,10\}\subseteq \{11,10,01,00\}}$

圧縮演算子と展開演算子はガロア接続を形成し、ここでは下側随伴演算子、 は上側随伴演算子である。^[3] ${\displaystyle \downarrow }$ ${\displaystyle \uparrow }$

概略的完成と概略的格子

集合 上の図式的完成から形成される図式的格子。ここでは、図式的格子はハッセ図として示されている。 ${\displaystyle A=\{111,011,001\}}$ ${\displaystyle ({\mathcal {S}}(A),\leq )}$

集合 に対して、A の各部分集合上の圧縮、つまり を計算するプロセスをの概略的完成と呼び、 と表記する。^[3] ${\displaystyle A\subseteq \Sigma ^{l}}$ ${\displaystyle \{{\downarrow }X|X\subseteq A\}}$ ${\displaystyle A}$ ${\displaystyle {\mathcal {S}}(A)}$

たとえば、 とします。 を図式的に完成させると、次の集合が得られます。 ${\displaystyle A=\{110,100,001,000\}}$ ${\displaystyle A}$ $${\displaystyle {\mathcal {S}}(A)=\{001,100,000,110,00*,*00,1*0,**0,*0*,***,\epsilon _{*}\}}$$

posetは 常に、概略格子と呼ばれる 完全な格子を形成します。 ${\displaystyle ({\mathcal {S}}(A),\leq )}$

図式的格子は、形式的概念分析で使用されている概念格子に似ています。

参照

• ホランドのスキーマ定理
• 形式概念分析

参考文献

1. ホランド、ジョン・ヘンリー (1992). 『自然システムと人工システムにおける適応』（復刻版）. MIT 出版. ISBN 9780472084609. 2014年4月22日閲覧。
2. 「遺伝的プログラミングの基礎」UCL UK . 2010年7月13日閲覧。
3. Jack McKay FletcherとThomas Wennkers (2017). 「スキーマ処理を研究するための自然なアプローチ」arXiv : 1705.04536 [cs.NE].

Retrieved from "https://en.wikipedia.org/w/index.php?title=Schema_(genetic_algorithms)&oldid=1304538298"