ホランドのスキーマ定理：原理・例・意義

スキーマと例

スキーマ（複数形：schemata）は、いくつかの位置に値を指定し、残りの位置では任意の値を許すことで、文字列の部分集合に一致するテンプレートである。二進表現では、一般にワイルドカード「*」を「どちらでもよい」を示す記号として用いる。たとえば長さ4の文字列に対するスキーマ 1*0* は 1000、1001、1100、1101 に一致する。つまり第1位置は1、第3位置は0でなければならず、第2と第4は0でも1でもよい。形式的には、スキーマは円筒集合の特別な場合であり、文字列空間上の位相における基本開集合として扱うこともできる。この見方については円筒集合の議論を参照。

スキーマの典型的な特徴

• 次数 o(H): スキーマのうち固定された（ワイルドカードでない）位置の数。
• 定義長 d(H): 最初の固定位置と最後の固定位置の間の距離（交叉による破壊に関係する）。
• 出現数 m(H,t): 世代 t において、そのスキーマに一致する集団中の文字列数。

定理の非形式的な記述

スキーマ定理は、選択・交叉・突然変異の後、次世代におけるスキーマの出現数の期待値について下限を与える。言い換えると、あるスキーマが平均以上の適応度を持つなら、それは次世代でより多くのコピーを生み出す傾向がある。ただし、その期待値は交叉や突然変異が固定位置を壊す確率によって減少する。したがってこの定理は、相対的適応度と破壊確率（交叉・突然変異）を結びつけ、スキーマの短期的な伝播を予測する。

解釈、構成ブロック仮説、限界

ホランドはこの定理を用いて、「構成ブロック仮説」を動機づけた。すなわち、遺伝的アルゴリズムは、短く、次数が低く、適応度の高いスキーマを組み合わせることで、高品質な解を構成するという考えである。しかし、この定理を大域最適化の保証と読むべきではない。これは力学の厳密な予測ではなく期待値の下限を与えるものであり、比例選択と単純な遺伝子操作を仮定している。批判としては、遺伝子間の連鎖、エピスタシス、有限集団における確率的効果、表現形式の問題などが、単純な外挿を成り立たなくすることが指摘されてきた。より新しい解析では、スキーマ指標を測定量として用いると、スキーマ定理はより一般的な進化の会計、たとえばPrice方程式の特定の場合として理解できることが示されている。これにより、この結果はアルゴリズムの能力を完全に説明するものというより、帳簿的な記述として捉え直される。

歴史、用途、注目すべき点

ジョン・ホランドは、適応システムを理解する計画の一部として、1970年代にスキーマの概念と定理を導入した。関連研究についてはジョン・ホランドを参照。この定理は、教育的にも直感的にも今なお有用であり、短く重要なパターンを保つ遺伝子操作がなぜ有利になりうるのかを説明する。実際には、現代の進化計算では、固定的な交叉・突然変異を補完または置き換えるために、連鎖学習、問題特化型再結合、集団ベースの統計が用いられることが多く、これは定理の限界に対処するためである。スキーマを文字列の部分集合、あるいは円筒集合として捉える概念は、アルゴリズムの考え方と数学的構造とも結びつく。スキーマは、研究者がマクロな統計量を追跡できる検索空間の部分集合を特定する。

わかりやすい入門やさらに技術的な解説については、一般的な遺伝的アルゴリズムの資料や、スキーマ定理をPrice方程式および集団遺伝学の形式化と関連づけるレビューを参照するとよい。スキーマ定理は、選択と変異がパターン頻度をどのように形作るかについての簡潔で歴史的に重要な命題であるが、現代の進化的アルゴリズムを考える際には、より詳細な解析ツールや実証的手法と併用するのが望ましい。