スキーマ定理を頭のすきーまに置いておきたい

スキーマ定理

こんにちは。ぬまです。今回は遺伝的アルゴリズム(GA)での探索をする際の基本原理であるスキーマ定理についてまとめたいと思います。
そもそもGAとはなんぞやという方はこちらを参照ください。
サルでもわかる遺伝的アルゴリズム - numa7pu’s diary

スキーマ定理とは

スキーマ定理でぐぐると以下の内容が記されていました。

遺伝アルゴリズムにおいてある遺伝子の特徴がどのように次の世代に遺伝していくかを示した定理. 遺伝子の部分列をスキーマといい, このスキーマをもつ遺伝子の数が遺伝演算によって次世代でどのように変化するかを確率的に示す事ができる.

わかりやすいですね。簡潔です。私もここまでまとめたいのですが、説明しがちなので、どゆこと？という人向けに説明します。

そもそもスキーマってなんやねん

スキーマとはGAにおける遺伝子の集団に保持される部分構造で0, 1, * で表される。*は0，1どちらでもよいという意味でワイルドカード記号ともdon't careとも呼ばれる。
具体的には、
H = * * 1 1
のスキーマについて考えると各個体0 0 1 1, 0 1 1 1, 1 0 1 1, 1 1 1 1がスキーマHに属するという。
すなわち、スキーマHがわかると集団の特徴がわかるということになる。
さらに、スキーマについて語るのに外せないのがスキーマの定義長とオーダーという概念。

スキーマの定義長

$\delta(* * 1 1)$ のように書き、左から見て最初の*以外の文字と最後の*以外の文字との距離である。
例えば
$\delta(* * 1 * 1 * ) = 5 - 3 = 2$
$\delta(* 0 * * * *) = 0$

スキーマのオーダー

$O(* * 1 1)$ のように書き、スキーマの0または1の数を表す。
例えば
$O(* * 1 * 1 *) = 2$
$O(* 0 * * * *) = 1$
これらを用いてスキーマ定理を紹介する。
現世代を $t$ 世代としたときのスキーマHの数を $m(H, t)$ として次世代にどう影響があるのか数式化する。
使われる変数を以下にまとめる。

変数

$n$	集団のサイズ
$f_1, f_2, \cdots, f_n$	各個体(遺伝子コード)の適応度
$f(ij{\cdots}k)$	文字列 $ij{\cdots}k$ の適応度
$f(H)$	スキーマ $H$ の適応度
$\bar{f}$	集団の平均適応度
$m(H, t)$	世代 $t$ におけるスキーマ $H$ に含まれる文字列の数
$l$	遺伝子の長さ
$\delta(H)$	スキーマ $H$ の定義長
$O(H)$	スキーマ $H$ のオーダ
$P_c$	交叉確率
$P_m$	突然変異確率

これらを用いて、次世代のスキーマHの数 $m(H, t+1)$ を交叉も突然変異もない場合、交叉のみ起こす場合、突然変異と交叉を起こす場合の３通りを考える。

スキーマ定理(メイン)

スキーマ定理を３通りから導出する。遺伝的アルゴリズムは遺伝子操作に交叉と突然変異があるため、スキーマの定理は最後の式となる。

交叉・突然変異がない場合

個体 $i$ は全個体の適応度の中に占める適応度の割合で次世代に残るので
$m(H, t+1) = m(H, t) \cdot n \cdot \frac{f(H)}{\sum{f_i}}$
$m(H, t+1) = m(H, t)\cdot\frac{f(H)}{\bar{f}}$
となる。

交叉のみの場合

定義長が長いと交叉が起きたときにスキーマが破壊されやすくなる。さらに、交叉点が $\delta(H)$ の中にあるときに破壊される。よって
$m(H, t+1) \geq m(H, t+1)\cdot\frac{f(H)}{\bar{f}} \cdot (1 - P_c \cdot \frac{\delta(H)}{l-1})$
となる。

突然変異・交叉がある場合

スキーマが破壊されるのはスキーマHの $O(H)$ 個の0または1 が突然変異を起こしたときであることがわかる。よって
$m(H, t+1) \geq m(H, t) \cdot\frac{f(H)}{\bar{f}} \cdot (1 - P_c \cdot \frac{\delta(H)}{l-1} - O(H) \cdot P_m)$
とわかる。これがスキーマ定理である。
これより、短くて低いオーダであり、かつ適応度が平均以上のスキーマが飛躍的に増大するということがわかる。

まとめ

いかがだったでしょうか？
難しかった人も簡単に理解ができた人もみなさんの頭のすきーまに残ってくれると嬉しいです。
今回はGAを語る上で大切な基本定理スキーマの定理を紹介しまとめた。面白い定理です。
それではまた。
参考文献
スキーマ定理とは何？ Weblio辞書
 http://mikilab.doshisha.ac.jp/dia/monthly/monthly03/20030602/personal/GA/01_mori.pdf