ホランドのスキーマ定理

ホランドのスキーマ定理は遺伝的アルゴリズムの基本定理とも呼ばれ、^[1]進化ダイナミクスの方程式を粗視化することで得られる不等式です。スキーマ定理によれば、平均以上の適応度を持つ短く低次のスキーマの頻度は、世代が進むにつれて指数関数的に増加します。この定理は1970 年代にジョン・ホランドによって提唱されました。当初は遺伝的アルゴリズムの威力を説明する基礎として広く受け入れられていました。しかし、この解釈は^[2]でレビューされたいくつかの出版物で批判されており、そこではスキーマ定理はスキーマ指標関数をマクロ的な測定値とするプライス方程式の特殊なケースであることが示されています。

スキーマは、特定の文字列位置で類似性を持つ文字列のサブセットを識別するテンプレートです。スキーマはシリンダー セットの特殊なケースであり、したがって位相空間を形成します。

長さ 6 のバイナリ文字列を考えてみましょう。スキーマは、1*10*1位置 1、3、6 に 1、位置 4 に 0 がある長さ 6 のすべての文字列のセットを表します。* はワイルドカードシンボルで、位置 2 と 5 の値は 1 または 0 のいずれかになります。スキーマの順序 はテンプレート内の固定位置の数として定義され、定義長は最初の特定の位置と最後の特定の位置の間の距離です。の順序は4 で、定義長は 5 です。スキーマの適合度は、スキーマに一致するすべての文字列の平均適合度です。文字列の適合度は、問題固有の評価関数によって計算された、エンコードされた問題解決の値の尺度です。遺伝的アルゴリズムの確立された方法と遺伝的演算子を使用すると、スキーマ定理では、平均以上の適合度を持つ短く低次のスキーマが、次の世代で指数関数的に増加すると述べられています。方程式で表すと次のようになります。 ${\displaystyle o(H)}$ ${\displaystyle \delta (H)}$1*10*1

${\displaystyle \operatorname {E} (m(H,t+1))\geq {m(H,t)f(H) \over a_{t}}[1-p].}$

ここで、 は世代 におけるスキーマ に属する文字列の数、はスキーマ の観測された平均適応度、は世代 における観測された平均適応度です。破壊の確率は、交差または突然変異によってスキーマ が破壊される確率です。 という仮定の下では、次のように表すことができます。 ${\displaystyle m(H,t)}$${\displaystyle H}$${\displaystyle t}$${\displaystyle f(H)}$${\displaystyle H}$${\displaystyle a_{t}}$${\displaystyle t}$${\displaystyle p}$${\displaystyle H}$${\displaystyle p_{m}\ll 1}$

${\displaystyle p={\delta (H) \over l-1}p_{c}+o(H)p_{m}}$

ここで、はスキーマの順序、はコードの長さ、は突然変異の確率、は交差の確率です。したがって、定義長が短いスキーマは、混乱する可能性が低くなります。スキーマ定理が等式ではなく不等式である理由については、よく誤解されています。 答えは実際には簡単です。定理は、スキーマに属する文字列が、前の世代ではに属していなかった単一の文字列の突然変異 (または 2 つの文字列の再結合) によって「最初から」作成される、小さいながらもゼロではない確率を無視しています。 さらに、 の式は明らかに悲観的です。交配相手によっては、 の最初と最後の固定位置の間で交差点が選択されても、再結合によってスキームが混乱しない場合があります。 ${\displaystyle o(H)}$${\displaystyle l}$${\displaystyle p_{m}}$${\displaystyle p_{c}}$${\displaystyle \delta (H)}$
${\displaystyle H}$${\displaystyle H}$${\displaystyle p}$${\displaystyle H}$

スキーマ定理は、遺伝的アルゴリズムが無限に大きい集団を維持するという仮定の下で成り立つが、必ずしも（有限の）実践に引き継がれるわけではない。初期集団のサンプリング誤差により、遺伝的アルゴリズムは選択的優位性を持たないスキーマに収束する可能性がある。これは特に、関数が複数のピークを持つ可能性があるマルチモーダル最適化で発生する。集団は、他のピークを無視して、ピークの1つを好むように移動する可能性がある。 ^[3]

スキーマ定理が遺伝的アルゴリズムの威力を説明できない理由は、それがすべての問題インスタンスに当てはまり、遺伝的アルゴリズムのパフォーマンスが低い問題と遺伝的アルゴリズムのパフォーマンスが高い問題を区別できないためです。

• J. Holland, Adaptation in Natural and Artificial Systems、MIT Press、1992年再版（初版は1975年）。
• J. Holland、「Hidden Order: How Adaptation Builds Complexity」、Helix Books、1996 年。