遺伝的アルゴリズム(しゃちょ〜)

遺伝的アルゴリズムといえば、「人間の遺伝子のようなものをコンピュータ内に持ち、それをどんどん進化させて・・・・」といった具合に、だいたいのイメージはつきますが、じゃぁ、具体的にどういう風にコンピュータ内で実現させるかというと、意外と簡単。
まず、何を進化させたいかを決めます。そのパラメータをa、b、c、dのように変数とします。例えば、2足歩行ロボットであれば、足の振りの振幅や、周期、他の関節との位相差などでも良いと思いますし、歩幅でも良いです。
これらのパラメータを1つの変数にまとめます。例えば、a、b、c、dが、それぞれ8bitの変数とすると、まとめた変数eは、32bitの変数ということになります。
e = (a<<24) + (b<<16) + (c<<8) + d
つまり、
a = 10101010(2進数)
b = 00001111(2進数)
c = 01010101(2進数)
d = 11110000(2進数)
だとすると、
e = 10101010000011110101010111110000(2進数)
という数字になります。これで、遺伝子を作ることが出来ました。このような(a,b,c,d)のパラメータセットを、最初にランダムで100個ぐらい作ります。すると、e[i](i=0,1,・・・99)は00000000000000000000000000000000(10進数で0)から、11111111111111111111111111111111(10進数で4,294,967,295)までの値のどれかを取ります。
次は、評価関数(どうなれば、良いのか)を決めます。例えば、2足歩行ロボットの歩行を獲得させたい場合は、「倒れたらNG」なので、頭の地面からの高さgを一定値以上に長い間保つというのでも良いと思います。
そうすると評価関数は、f = g x tという感じでも良いと思います。tは、頭の高さがgを保っていた時間になります。ただ、これだと、fの上限値が分からないので、普通は、正規化という0から1の間に収まるようにします。この場合、ロボットの身長を100cmとし、1回の試行時間を10秒とすると、fの最大値は、100 x 10 = 1000なので、
　　　g x t
f = -----------
　　　1000
としておけば、1以下になります。ロボットがジャンプしてしまうと頭の高さが100cmを超えるので、ジャンプしてしまったらNGとするなど、微妙な調整は必要です。たまに、シミュレーションでは、ロボットが空高く飛んでいってしまうことがありますので要注意です。
あとは、先ほど用意した100個のパラメータに対して、全てシミュレーションを行い、100回の試行結果の評価関数100個を計算します。

そして、fの値が高くなったeを数個(3個ぐらい)は「エリート」として、次の世代にそのままコピーします。残りには、交叉と突然変異をさせます。
ここは色々とやり方があるのですが、簡単なのは、適当に2つを取り出し、適当な所で分断し、入れ替える。といった方式です。例えば、
e[m] = 1110 0001 0000 1110 0110 0011 1111 0100
e[n] = 0001 0011 0111 1111 0000 1010 0010 1111
だとすると、適当な2箇所に線を引きます。
e[m] = 1110 0001 0000 | 1110 0110 0011 | 1111 0100
e[n] = 0001 0011 0111 | 1111 0000 1010 | 0010 1111
で、入れ替える。
e[m] = 1110 0001 0000 | 1111 0000 1010 | 1111 0100
e[n] = 0001 0011 0111 | 1110 0110 0011 | 0010 1111
です。真ん中の12bitを入れ替えてます。こうすると、新しい遺伝子が2個できます。これを交叉といいます。
突然変異は、だいたい5%ぐらいの確率で入れる場合が多いようですが、要は、適当に値をいれかえたり、ランダムにeを生成するなどです。
こうして、3個のエリート遺伝子、92個の交叉済み遺伝子、5個の突然変異遺伝子を、次の世代(第2世代)として、再度、100個の遺伝子に対してシミュレーションし、評価関数を求めて・・・といった具合に繰り返します。
これを、100世代ぐらいやると、殆どの遺伝子が、ある程度の評価値に落ち着いてきます(飽和)。
で、100世代目のエリート1個を取り出せば、進化した解が得られるという感じ。

ただ実際には、この方式では、全く「無」の状態から「歩行」を獲得させるのは無理です。以前のブログに書きましたが、第1世代なんて、100個のうち、どの遺伝子も、当然歩けません。歩けない者同士を交叉させても、やっぱり歩けない。時々、突然変異で生成された遺伝子が、1〜2歩ぐらい歩くけど、100世代ぐらいやっても全然駄目です。
なので、通常、第1世代の遺伝子を用意する際に、人間が、ある程度歩けそうなパラメータセットを意図的に作って、2個ぐらい混ぜておきます。すると、それはエリートとして生き残り、徐々にパラメータチューニングされていき、最終的に「準」最適解が出てきます。
ここで「準」と書いたのは、たいていの場合、このように事前に意図的なパラメータを入れると、最終的な解は、その近辺の局所解が出てくるからです。多分、歩行のような複雑なものは、局所解は、いろんなところにあるので、本当の最適解を求めるのは難しい。結局は、人間がある程度、最適解を知っていなければならないんですね。
さらに、評価関数も、「こうあって欲しい」は、人間が決めるので、この手の進化は、殆どパラメータチューニングの手法にしかならず、「誰も意図していなかった全く新しい歩行が創出される」ことは稀です。
人工生命の分野で、ロボットの形態を創出させるような場合は、GAを使うと、おもしろい解が得られる場合があります。例えば、10本のリンクを用意して、その接続方法を自由に変更でき、移動距離や移動速度を評価関数とすると、多足動物や、3足＋腕のような、いろんな形態が出来上がってきます。これは、おもしろい。