 | This article may be too technical for most readers to understand. (August 2011) |
遺伝的アルゴリズムの分野において、スキーマ（複数形：スキーマ）は、潜在的な解のサブセットを表すテンプレートです。これらのテンプレートでは、特定の位置には固定記号（例：0または1）を使用し、その他の位置にはワイルドカードまたは「don't care」記号（多くの場合、#または*）を使用します
スキーマの定義長（L(H)と表記）は、テンプレート内の最も外側の固定位置間の距離を測定する。スキーマ定理によれば、定義長が短いスキーマは、交叉という遺伝的演算子によって破壊される可能性が低い。[1] [2]その結果、短いスキーマはより堅牢であると考えられ、次世代に伝播される可能性が高くなる。[3]
遺伝的プログラミングでは、解は多くの場合木として表現されますが、定義長さはスキーマH内のすべての非ワイルドカードシンボルを含む最小の木片のリンクの数です。[4]
例
定義長は、最初の固定記号の位置から最後の固定記号の位置を引いて計算されます。長さ5の文字列に1から始まるインデックスを使用すると、次のようになります。
- スキーマ `1##0#` では、最初の固定シンボル (`1`) が位置 1 にあり、最後の固定シンボル (`0`) が位置 4 にあります。定義長は 4 − 1 = 3 です。
- スキーマ `00##0` では、最初の固定シンボルは位置 1 にあり、最後の固定シンボルは位置 5 にあります。定義長は 5 − 1 = 4 です。
- スキーマ `##0##` には、位置 3 に固定シンボルが 1 つだけあります。最初と最後の固定位置は同じなので、定義長は 3 − 3 = 0 です。
参考文献
- ^ トーマス・ベック（2018年10月3日）『進化的計算1：基本アルゴリズムと演算子』CRC Press. ISBN 978-1-351-98942-8。
- ^ ポリ、リカルド、ラングドン、ウィリアム・B. (1998年9月1日). 「一点交差と点突然変異を用いた遺伝的プログラミングのためのスキーマ理論」 .進化計算. 6 (3): 231–252 . doi :10.1162/evco.1998.6.3.231. ISSN 1063-6560
- ^ 「遺伝的プログラミングの基礎」UCL UK . 2010年7月13日閲覧。
- ^ ラングドン、ウィリアム・B.、ポリ、リカルド（2013年3月9日）。遺伝的プログラミングの基礎。シュプリンガー・サイエンス＆ビジネス・メディア。ISBN 978-3-662-04726-2。
 | このコンピュータサイエンスの記事はスタブです。記事を拡張することでWikipediaに貢献できます |
