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

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

例えば、長さ6のバイナリ文字列を考えてみましょう。スキーマ1**0*1は、長さ6のすべての単語のうち、1番目と6番目の位置に1があり、4番目の位置に0がある単語の集合を表します。*はワイルドカード記号であり、2番目、3番目、5番目の位置には1または0のどちらの値も取ることができます。スキーマの順序はテンプレート内の固定位置の数として定義され、定義長は${\displaystyle \delta (H)}$は、最初と最後の特定の位置間の距離です。1**0*1 のオーダーは 3 で、定義長は 5 です。スキーマの適合度は、スキーマに一致するすべての文字列の平均適合度です。文字列の適合度は、特定の問題用に設計されたルールを使用して計算された、それが表すソリューションの良さを示す数値スコアです。

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

近年、スキーマは順序理論を用いて研究されている。^{[ 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 展開}$の${\displaystyle s}$マッピング${\displaystyle s}$単語のサブセットに$\displaystyle \Sigma ^{l}}$:

$${\displaystyle {\uparrow }s:=\{b\in \Sigma ^{l}|b_{i}=s_{i}{\mbox{ または }}s_{i}=*{\mbox{ 各 }}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 圧縮}$の${\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\}}$。

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

セットの場合$\displaystyle A\subseteq \Sigma ^{l}}$A の各部分集合に対する圧縮を計算するプロセスを、${\displaystyle \{{\downarrow }X|X\subseteq A\}}$、概略図の完成${\displaystyle A}$、と表記される$\displaystyle {\mathcal {S}}(A)}$[ ^{3 ]​}

例えば、${\displaystyle A=\{110,100,001,000\}}$. 概略図の完成${\displaystyle A}$結果として、以下のセットが得られます。 $${\displaystyle {\mathcal {S}}(A)=\{001,100,000,110,00*,*00,1*0,**0,*0*,***,\epsilon _{*}\}}$$

ポセット​${\displaystyle ({\mathcal {S}}(A),\leq )}$常に、概略格子と呼ばれる完全な格子を形成する。

この図式格子は、形式概念分析 に見られる概念格子と類似している。

• ホランドの図式定理
• 形式概念分析