遺伝子アルゴリズム(GA)

遺伝子アルゴリズム(GA)は、生物の進化の過程を模倣して、問題の解を得ようとする手法である。最近では、人工知能(AI)の実現方法のひとつと考えられている。

遺伝子アルゴリズムでは、与えられた問題の解(解の候補)を生物の個体(遺伝子)に擬する。その複数の個体に対して、3種類の操作を繰り返しながら進化をさせる。進化を繰り返すうちに、個体=遺伝子=解の候補が、問題の望ましい解に近づいていくことを期待するのである。3つの操作とは

  1. 交叉(交配)
  2. 選択(自然淘汰)
  3. 突然変異

である。しかしながら、3つの操作の具体的な実現方法、そもそも解を遺伝子にどのように抽象化するかについては様々な方法がある。このため、ひとくちに遺伝子アルゴリズムと言っても、そのやり方は無限にあると言っても良い。

 遺伝子アルゴリズムが最もよく適用されるのは、「最適化問題」である。最適化問題とは、いくつかの変数で表される関数(これを目的関数とかコスト関数と呼ぶ)の値を最大にする(あるいは最小にする)変数の組を求める問題である。

例えば、生産ラインを共有する複数の製品に対して、その生産時間の割り振りを最適化する問題である。この場合、生産によって得られる利益が目的関数であり、各製品に割り振るに生産ラインの専有時間が変数である。

このように多くの変数が関与する問題の解法は、多変量解析と呼ばれる。多変量解析には従来から、重回帰分析、主成分分析、因子分析、クラスター分析など様々な方法がある。しかしながら、変数の数がたいへん多い場合、変数が離散的である場合、目的関数が連続的でない場合など、数学的な解析が困難な場合には、遺伝子アルゴリズムが有力な方法になる。

2次元の最適化問題

具体的な解放を例にして説明しよう。目的関数が下図のように与えられているとする。解は2次元の座標点である。一番高いピークの頂点を与える座標を求めたいのである。

onewell

人間ならば一目で解は分かるのだが、実はこの問題は意外に難しい。というのも、上図を描くには2500点で目的関数を計算する必要がある。相当なコストを払っているのである。さらに、この関数には主ピーク以外に小さいピークがいくつもある。そのため、このような問題でよく使われる最急降下線法などがうまく適用できないのである。

この問題は最も単純な2次元空間で解を探すように設定しているのだが、実際の問題ではもっと高次元になることが多い。

遺伝子

遺伝子として何を用いるかが重要である。今、解は2次元座標(x,y)で表される。従って、遺伝子上に2個の実数xとyを表現しなければならない。

実際の生物の遺伝子はDNAの2重らせんで表現される。2重らせんに成っているのは、ひとつは複写のため、もうひとつはエラー修正のためである。情報としては、2重のうち片方だけしか意味が無い。その片側はアデニン、グアニン、チミン、シトシンの4種類の塩基から選択される。すなわち、四値論理であり2bitの情報量である。しかし、遺伝子の単位が2bitである必然性は特に無い。1bitで良い。これはコンピュータに馴染む。

一番簡単には、浮動小数点実数のビット表現(IEEE754形式)をそのまま並べて遺伝子にすることが考えられる。この場合、元の実数が単精度なら遺伝子は8バイトになる。しかし、IEEE754の中身を調べると遺伝子アルゴリズムには具合が悪い。そこで、実数でなく整数を用いることにする。範囲が限られるなら(上図の2次元領域)整数でも十分である。

実際の計算はJavaを使った。Javaの整数は4バイト(32bit)である。これを遺伝子とした。遺伝子を上下に分けて、上部をx座標、下部をy座標に割り当てた(下図)。それぞれは16bitのshort型整数になる。これでも領域を66636分割できる精度がある。

waku

進化の論理

採用した進化の論理を次に示す。

  1. 最初にN個の個体(=遺伝子)をランダムに作り、最初の親世代とする
  2. N個から2個づつのペアを作る
  3. それぞれのペアは、4個づつ子供を作る
  4. 子供を作る際、2個の親の遺伝子をビットごとに比較し、ランダムにどちらかのビットを子供のビットとする(遺伝子の交叉)
  5. できた子供の遺伝子からランダムに選んだビットを反転させる(突然変異)
  6. 親世代を死なせる(自然死)。この時、適当な数だけ親を生存させる(遺伝子の複製)
  7. 残った個体から、与えられたルールに従い、N個だけを残して他を死なせる(自然淘汰)
  8. 与えられた条件を満たすまで、2から7を繰り返す

シミュレーションの過程

遺伝子アルゴリズムによるシミュレーションの過程を、http:/st/ga/に示す。WebGLを使っていて、途中経過を動画のように見ることができる。但し、WebGLはインターネットエクスプローラでは使えないため、Firefox、Google Chromeなど他のブラウザを使ってもらいたい。

最初、右図のように個体をランダムに初期配置する。これが第0世代であり、第1世代の親となる。

最適解は赤紫の円の中心である。

step0.s

第0世代から親ペア(赤玉)を選び、子供(赤玉の子供は水色玉。黄色玉は別の親ペアの子供)を作る。親ペアごとにこれを繰り返す。子供は第1世代である。

step1.s

第1世代の自然死、残った個体の自然淘汰を経て、最後に生き残った個体を親として第2世代が生まれる。

step2.s

第4世代の生き残り、最適解の周辺に集まっている。

step4.s

結果

ここで示した結果は、第4世代でほぼ最適解が得られた。この時、目的関数は80回計算した。これは収束が最も速い方の例である。収束の悪い場合も含めて平均すれば、遺伝子アルゴリズムで解を求める計算コスト(目的関数の計算回数)は、だいたい310回である。

ところで、計算コストはパラメータ(1世代の生き残り個体数、各ペアの生む子供の数、親世代の生き残り個体数、遺伝子に生ずる突然変異ビットの数)を調整すると、もう少し向上する。図の結果はパラメータが(8,4,1,1)であったが、パラメータを(8,4,2,2)にすると計算コストは170回になった。等間隔で計算する場合(上記の目的関数の図)は2500回であるので、遺伝子アルゴリズムでは14倍ほどのコストパーフォーマンスで解を求めることができた。

もっと変数が増えて高次元になるほど、遺伝子アルゴリズムが有効になると推察できる。4次元空間で同じ程度の精度を要求してみたところ、遺伝子アルゴリズム計算コストは35000回であった。等間隔の計算では625万回が必要であるから、コストパーフォーマンスは180倍である。

どこが人口知能なのか

では、遺伝子アルゴリズムのどの部分が人口知能なのか。上記のような最適化計算の場合、実際にプログラムで求める場合には、等間隔のメッシュで細かく計算するようなことはしない。始めに粗いメッシュで計算してみて解の場所を推定し、推定した領域で様々な方法を用いて解に近づける。これはプログラム的にはたいへん面倒な作業である。

それに比べて、遺伝子アルゴリズムを用いたプログラムは、コアの部分はどんな目的に対しても共通なのである。それでありながら、粗い計算から細かい計算まで自動的に求解が進む。いわば、人間が頭を使うかわりに、遺伝子アルゴリズムが同じようなことをやってくれる。

これが、遺伝子アルゴリズムの人口知能たる所以である。