モチベ

遺伝的アルゴリズムにおける積み木仮説とスキーマ定理の関係性について興味が沸いたので、調べた結果について簡単にまとめた

内容

GAはあまり数学的分析が進んでいないが、積み木仮説とスキーマ定理を用いてその挙動を説明することができる

ここでは積み木仮説とスキーマ定理によるGAの挙動の説明を試みる

積み木仮説は最適解に近い良好な解はその部分構造(積み木)が組み合わさることで生成されるという仮説

この積み木仮説の1手法にスキーマがある

スキーマとは個体の構成要素である遺伝子の部分集合のことである

遺伝子長5で値に{0, 1}をとる遺伝子のスキーマの例をあげると[1, 0, 1, * , *]のようなものが考えられる

この時 * はワイルドカード記号を示し、{0, 1}のどちらにも一致するものと考える

そのため例のスキーマは[1, 0, 1, 0, 0], [1, 0, 1, 0, 1], [1, 0, 1, 1, 0], [1, 0, 1, 1, 1]の4遺伝子から構成される遺伝子の部分集合となる

スキーマは実体の他に定義長とオーダーという属性をもつ

定義長：遺伝子を左から見て * 以外の値と最後の * 以外の値のビット位置の距離

オーダー：* 以外の値の数

例の[1, 0, 1, * , *]は定義長が2、オーダーが3のスキーマになる

このスキーマを利用して、前の世代から次の世代にどれだけ特定のスキーマが生き残るかを検討するのがスキーマ定理（なので、GAには深く関わりのある定理）

単純なGAを例として、特定のスキーマが次世代にどれだけ生き残るかを考える

変数の定義は下記

<\div>

まず、ベースラインとして交叉や突然変異がない場合を考える

GAのアルゴリズムでは適合率に応じて次世代に残るHを決定するため、次世代に残るHの件数m(H, t+1)はm(H, t) の関数として表せる。適合率の比率により次世代に残る件数が決まるとすると下記のように表せる

<\div>

続いて交叉を考慮に加えた場合を考える

交叉では定義長の間に交叉点が入ることによりスキーマが壊れるため、スキーマが壊れない場合を考える

スキーマが壊れる場合とは、長さlのうち、切断可能な位置はl-1箇所でそのうち定義長δ(H)無いで切断された場合になる

そのため、ランダムに選択された切断位置から表現を失うようなHが発生する確率PはP＝δ(H)/(l-1)と表せる。これに交叉が発生する確率p_cの考慮を加えると、表現を失うようなHが発生する確率P_c＝p_c*δ(H)/(l-1)と表せる

これらの結果から、スキーマが壊れない場合の確率は1-P_c＝1-p_c*δ(H)/(l-1)と表せることがわかる。これを交叉考慮前の式に掛け合わせることで、交叉を考慮したm(H, t+1)を求めることができる

<\div>

※不等号となるのは同じスキーマ H に含まれる値が交叉をしてもスキーマが破壊されることがないなどの場合があるため

最後に突然変異を考慮に加えた場合を考える

交叉と同様に突然変異により、スキーマが壊れない場合を考える

スキーマ中の * 以外の要素に突然変異が起きない場合、スキーマは壊れない

これをオーダーO(H)と突然変異率p_mを用いて表すとスキーマが壊れない確率P=(1-P_m)**O(H)と表せる

P_mは通常小さい値なのでPを近似するとP≈ 1-O(H)P_mと表せる

これを交叉考慮の式に加えると下記のようになる

<\div>

この式で表されるm(H, t+1)とm(H, t)の関係性をスキーマ定理という

これを単純なGAに当てはめた時、 p_c >> p_a、δ(H) > O(H) のため式内のO(H)⋅pmはほとんど無視できる

そのため、下記の条件を満たすスキーマHの件数は指数関数的に増大していくことがわかる

これらの条件を満たすスキーマは * 以外の値が部分的に固まっており、適合度が高いスキーマになっている

これは共通点の少ない適合度の高いスキーマが探索対象に増えていくことを示しており、GAにおいて解の探索(適合度の高い解を探すこと)が進むことを示している