2005-11-30

４　遺伝アルゴリズム(GA)の理論

アルゴリズム的内容
- スキーマ解析
- 最適解の発見確率
- 適応度関数の自己相関(適応度関数の最適解付近での様相と最適解探索)
集団遺伝学的内容
- 有限個体数がもたらす遺伝的浮動
スキーマ解析
- 個体を発生させて進化させていくと、個体が共有する特徴に着目するとその特徴の消長がシミュレートされる。スキーマの消長はそのスキーマに属する個体の適応度の総和により決まり、よりよいスキーマは個体数を増やしていくことにより、ますます子孫数を増やす仕組みになっており、指数関数的に子孫数を増やす。また、このスキーマは染色体上に並んでおり、そこに交叉を起こすというGAの原理から、局所的な評価をしながら、大域的に適応度を上げていく方法である。局所的に適応度が高い遺伝子配列はスキーマとして指数関数的に子孫を増やすことが示されており、スキーマ定理と呼ばれる。最適スキーマが進化の結果得られ、このスキーマが解であるとも言える。
最適解の発見確率
- GAは有限マルコフ連鎖である。マルコフ連鎖とは、ある状態の条件付き確率がその前の状態の条件つき確率になっている状態推移過程である。その中でも直前の状態にのみ依存し、それ以前の状態には依存しないものを有限マルコフ連鎖と呼ぶ。
- (有限)マルコフ連鎖においては、状態の推移条件により平衡状態に至ることが知られており、その平行状態は初期確率分布の与え方によらないことも知られている。このようなマルコフ連鎖の状態全体の平衡分布は、最適解以外にも正の確率を与えるので、マルコフ連鎖であるGAの解が最適解をもたらす確率は１に達しない
- マルコフ連鎖であるGAで最適解をもたらす確率を１にするためには、GAの最適解を示す固体(もしくは集団)とマルコフ連鎖で平衡状態に持ち込む集団とに乖離をもたせ、かつ、最適解への推移が一方向(最適解が推移集団に加わることはあっても抹消されることはないような推移条件)であるようにするのが１法である。たとえば最適解をマルコフ連鎖で推移させる集団の中でもっとも適応度の高いものとし、推移集団中でもっとも適応度の高い集団は確率１で子孫を残すものとすると、平衡集団中の最大適応度個体が最適解である確率が１に収束する
適応度関数の最適解付近での様相と最適解探索
- ある解とある解とがGAによってすぐに遷移するとき、この解同士は、｢解空間の中で近い」関係にあると考える。このような「解空間＝解分布平面」上に適応度関数をプロットすることで適応度関数の「景観」が形成される。「景観」が単純な山をなしていれば、GAにより最適解に到達することは容易だが、複数の峰の集まりであると、局所的最適解に到達してそこから脱することができなくなる。そこから脱出して最適解の探索を続け、最適解にいたるためには、「最適解付近」にいたったあと、その「周辺」を探索する必要があるが、その「探索範囲」がどれくらいかわかる必要がある。最適解付近の「景観」を特徴付ける指標として自己相関関数とその相関長というものを定義できる。適応度関数の相関長は、その相関長より遠位では適応度関数の値がランダムであり、それより近位では現在地点の値との相関が認められることを示す指標である。したがって、「仮に到達した解」から周辺を探索するにあたっては、適応度関数の相関長の格子で区分けされた小部分について「調べ｣るとよいだろうことに根拠が与えられる
有限個体数がもたらす遺伝的浮動
- 新規に生じた変異が中立であるとき、その変異は子孫を多く残したり、少なく残したりする。中立であるのでその多寡はランダムである。もしも集団個体数が無限であると、変異が残す子孫数は、ゼロではないので、消滅することはないが、個体数が有限である限り、子孫を残さない染色体が存在する。そのような確率は低くなく、実際、大多数の変異は、１代限りで、そして多くの変異が短期間のうちに消滅する。中には、野生型を駆逐してしまう変異も数は少ないが存在する。中立変異が一定の頻度で新生しているとすると、集団中に認められる中立変異の数は、集団個体数によらず、変異率によって決まることが知られている。

このように中立な変異も消長することは、GAにおいて変異に適応度を与えて最適解を求める方法において留意するべきポイントである