遺伝的アルゴリズム

GA

ゼミで発表しなければならない。
進化論的計算手法の2章を簡単にまとめる。ここも参考


GAで扱う情報は、PTYPEとGTYPEの二層構造からなる。

GTYPE
遺伝子コードとも言う。細胞内の染色体に相当する。遺伝子型のアナロジー。低レベル局所規則の集合。GAのオペレータの操作対象になる。
PTYPE
表現型(発現型)。GTYPEの環境内での発達に伴う大域的な行動や構造の発現を表す。

環環境に応じて、PTYPEから適合度(fitness value)が決まる。
適合度は高い程良いものとする。

GAのGTYPEを一次元のビット列、それをバイナリ表現で変換したものをPTYPEとする。
遺伝子座とは、染色体上の遺伝子の場所を指す。
例えば、010というGTYPEは、

  • 1番目の遺伝子座の遺伝子 ⇒ 0
  • 2番目の遺伝子座の遺伝子 ⇒ 1
  • 3番目の遺伝子座の遺伝子 ⇒ 0

などとなる。

GAの基本的なしくみ

  1. 何匹かの犬が存在し、集団を構成する(世代tの犬)。
  2. 犬は各々遺伝子コードをを有し、それが発現したPTYPEに応じて適合度が決まっている。
  3. 犬は生殖活動を行い、世代t+1の子孫を作り出す。
  4. 生殖の際には、適合度の大きものほど多くの子孫を作りやすく、低いものほど死滅しやすい。
  5. この結果、次の世代t+1では、各個体の適合度は前の世代よりも良いことが期待される。
  6. 同様にして、t+2,t+3と繰り返していき、集団全体が段々良くなっていく。

GAのオペレータ

突然変異

「b」が「B」に突然変異する。

a b c d e f ⇒ a B c d e f
逆位

3番目から5番目の遺伝子座の遺伝子が「|c|d|e|」から「|e|d|c|」に逆位している。

a b c d e f ⇒ a b e d c f
交叉

3番目の前のところで交叉している(つまり、「b」と「c」の間)。

a b c d e f
1 2 3 4 5 6

↓

a b 3 4 5 6
1 2 c d e f

これは交叉点が一つなので一点交叉(1X)と呼ばれる。
交叉点が複数あったならば、複数点(n点)交叉(nX)、
任意個の交叉点を取れる交叉法ならば、一様交叉(UX)と呼ばれる。
一様交叉は、0,1からなるビット列のマスクを用いて実現する。
二つの親をA,Bとし、作るべき子をa,bとすると、

  1. マスクにランダムに0,1の文字列を発生させる。
  2. aの遺伝子は、対応するマスクが1のときは親Aから受け継ぎ、0のときは、親bから受け継ぐ。
  3. bの遺伝子は、対応するマスクが0のときは親Aから受け継ぎ、1のときは、親bから受け継ぐ。

GAにおける選択

適合度の大きいものほど多産で、小さいものほど死に易いように選びたい。

  • ルーレット方式
  • トーナメント方式
  • エリート戦略
ルーレット方式

適合度に比例したルーレット(重み付けルーレット)を作り、そのルーレットを回して当たった場所の個体を選択する。
例えば、

f1 f2 f3 f4 f5
1.0 2.0 0.5 3.0 3.5

という場合を考えると、重み付けルーレットでの選択を次のように考える。
f1+f2+f3+f4+f5=10.0
よって、0から10までの乱数を一様に発生する。
そして、下記の規則に当てはめて選択する。
乱数が0.0から1.0 ⇒ f1の個体を選択する。
乱数が1.0から3.0 ⇒ f1の個体を選択する。
乱数が3.0から3.5 ⇒ f1の個体を選択する。
乱数が3.5から6.5 ⇒ f1の個体を選択する。
乱数が6.5から10.0 ⇒ f1の個体を選択する。

トーナメント方式

集団の中から個体をある個体数だけランダムに選びだし、その中で最も適合度の高いものを選択する。
この過程を集団数が得られるまで繰り返す。

エリート戦略

適合度の高い個体のいくつかを、そのまま次の世代に残す手法。
適合度の高い個体が偶然選択されずに死滅することを防ぐことができる。

GAの基本的な流れ

GTYPEの集合{g_t(i)}をある世代tにおける個体群とする。
各々のg_t(i)の表現型p_t(i)に対して、環境内における適合度f_t(i)が決定される。

  1. GTYPEオペレータを適合度の大きなGTYPEに適用。
  2. その結果生成されたGTYPEを適合度の小さなGTYPEと置き換える。
  3. 次の世代(t+1)のGTYPEの集合{g_t+1(i)}が生成される。
  4. その後は、この過程を繰り返す。

簡単にまとめると、

  1. ランダムに初期世代の集団を生成する。
  2. 現在の集団の各個体に対して適合度を計算する。
  3. 現在の集団から適合度に比例する確率分布を用いて個体を選び出す。
  4. 選び出された個体にGAオペレータを適用させて、次の世代の集団を生成する。
  5. 2に戻る。

最適値探索

例えば、ある範囲(探索空間)の中の最大値を探すとき、「最大値を正しく、そして、早くみつけられるか」が重要。
そして、これが失敗するとき、「最適値でない解を見つけ出して終わった」ということ。
このように、探索手法が悪いと極大値を見つけだして終わってしまう。
最適値探索は山を登ることに例えられ、探索空間内の標高地図を適合度ランドスケープと呼ぶ。

最適値探索において、単純な方法に局所的山登り法がある。

  1. 自分の周りを見て、上り勾配が一番大きいとこりに一歩進む。
  2. これを周りに上り勾配がなくなるまで繰り返す。

これは自分のすぐ周りしか見ていないため、局所解に陥りやすい欠点がある。
この局所的山登り法は以下のようなものがある。

最急勾配山登り法
  1. 一つの出発点をランダムに選び、この地点を「頂上」とする。
  2. 周囲を見てその高さを記録する。
  3. もし周囲のどこかが「現頂上」よりも高ければその地点を「現頂上」に変更し、2へ戻る。
  4. もし高さに増加が無いならば、今までの最高頂上より「現頂上」が高いならばそれを保存し、1へ戻る。
  5. 決められた時間が経過したならば、見つかった頂上を返す。
逐次勾配山登り法
  1. 一つの出発点をランダムに選び、この地点を「頂上」とする。
  2. 時計周りで北から周囲を見ていく。ある場所が「現頂上」よりも高いならば、それを「現頂上」とする。そして、再び時計回りで「現頂上」の周囲を見ていくが、このとき先の頂上で「現頂上」が見つかった次の方向から見始める。
  3. もし高さに増加が無いならば、今までの最高頂上より「現頂上」が高いならばそれを保存し、1へ戻る。
  4. 決められた時間が経過したならば、見つかった頂上を返す。
ランダム突然変異山登り法
  1. 一つの出発点をランダムに選ぶ。この点を「最高評価解」と呼ぶ。
  2. 周囲の点をランダムに選ぶ。この点が現在の「最高評価解」よりも高いならば、それを新しい「最高評価解」とする。
  3. 最適な点が見つかるか、定められた時間が経過するまで2へ戻る。
  4. 「最高評価解」を返す。