『 遺伝的アルゴリズムで歩行動作獲得への道 ～１歩目～ 』
2009 年 10 月 29 日
僕の大好きな、「マッチ箱の脳」という本があります。
人工知能についてとってもおもしろく解説してあるこの本を書いたのは、「がんばれ森川君2号」や「アストロノーカ」などの人工知能が組み込まれたゲームを作ったすごい人です。
僕はアストロノーカしかやったこと無いのですが、人工知能が自然にゲームに組み込まれていてすごいなあと当時思ってました。中ではすっごい難しいことをやっているのに。その影響か、僕も人工知能を組みたいと思ってこれまで何度もチャレンジしては挫折してきましたが、懲りずにまたチャレンジすることにしました。
てなわけで、シャクトリムシに歩き方を学習させようと思います。昔は全部自分で作ろうとして失敗したけど、今は高速なAS3や物理エンジンライブラリもあるし、やってみよーGOGO！というわけで今はこんな感じ。
ちなみに、まだ人工知能を組み込んでいないので、どれだけ待ってもうまく歩けません。クリックでカメラを切り替えるなどという、見た目な機能ばかり付けています。さいさき不安です。
まず、シャクトリムシの歩行について考えてみます。人工知能を組むときは、何を学習させるのかが一番大事なので、ここを見極めます。
いくつかの棒状のパーツが繋がった体をシャクトリムシと見立てます。体の繋ぎ目である関節を適当に動かすと、シャクトリムシがウニョウニョ動きます。でもこれだけだと、ただ暴れているだけで全然前へ進みません。前へ歩かせるためには、全ての関節が連携しながら動く必要があります。じゃあ、どのタイミングで、どのくらいの速さで、どれくらいの力で動かせば、もっとも前へ進めるのか。人が手動で調整しても良いのですが、関節の数が増えたら大変だし、途中で重力の大きさとか、少しでも変えるとまた最初から調整というのはちょっと。。。
なので、その辺をシャクトリムシ自身に学習してもらいます。問題を簡単にするために、0.5秒ごとに各関節の速度が決められた数値に切り替わるようにして、それを8回繰り返します。その8回の切り替わりをまとめて、1回の歩行動作のサイクルとします。関節は5個あるので、一体のシャクトリムシの歩行方法を決定するために、8×5=40のパラメータを必要とします。とりあえず、当面はこの40個のパラメータを学習していきます。そのうち形状の進化もさせたいので、そしたらまた別のパラメータにしなければならないのですが。
学習方法は、分かりやすくて学習過程が楽しい遺伝的アルゴリズム（Genetic Algorithm、以下GA）を使っていくことにします。
さてここからは、GAをちょっとでも分かってもらえればということで、GAの概要を書いておきます。うろ覚えな上に下手にドラマチックにしようとしたので、正確ではないと思いますが、興味のある方は何かの足しになるかも知れません。多分本当はもっとドラマチックなんです、きっと。それに、僕もこれ以上のことは分からずにやっているので大丈夫なはずです（何が）。本気で勉強したい人にはこのサイトがおすすめです。
準備編
適当な数のシャクトリムシを作ります。
このとき、シャクトリムシの関節の動き方（どんなタイミングで、どんな速度で、どんな力で動かすのか）をランダムに決定し、パラメータとして持たせておきます。このパラメータを生物のそれぞれの個性になぞらえてシャクトリムシの染色体と呼びます。同じ染色体を持ったシャクトリムシは、全く同じ動きをするわけです。で、色んな個性をもったシャクトリムシをひとまとめにして世代と呼ぶことにします。
激闘編
世代ができたところで、次はどいつが一番優秀なシャクトリムシなのかを見極めます。何をもって優秀なのかは色々意見がありますが、とりあえず全員を歩かせてみて、一定時間内に一番遠くまで歩いたシャクトリムシを優勝とします。歩かせた後は成績順にソートでもしておきましょう。
愛憎編 ～淘汰～
競争すれば優秀なやつも出てくるし、落ちこぼれも出てきます。手を繋いでみんなで一等賞なんてこの世界には存在しません。しょせんこの世は弱肉強食、弱いシャクトリムシは生存競争に負けて死んでしまいます。この弱肉強食の世界をGAでは淘汰（選択）という処理でおこないます。
GAとは、何百世代も世代交代しながら、だんだんと優秀なシャクトリムシを作っていくという仕組みです。弱いシャクトリムシは次の世代に自分の子孫を残せず、捨てられます。どのシャクトリムシを、どれくらいの数だけ淘汰させるのかを決める方法もたくさんあって、単純にランキング最下位から選んだり、確率的に選んだり色々です。
愛憎編 ～交叉～
生存競争に敗れるシャクトリ虫もいれば、生き残るシャクトリ虫もいます。そして、次世代に向けてシャクトリ虫をさらに進化させるべく、生き残ったシャクトリ虫の優秀な染色体をかけあわせて、もっと優秀な染色体をつくりだす処理を交叉といいます。
生き残ったシャクトリ虫の中から、何らかの方法（ランキングの上位からだったり、ランダムだったり色々あります）で2匹の親を選びます。選ばれた親は交配し、2匹の子供を作ります。この子供は、生き残った親の染色体から生まれるので、そこそこ優秀なシャクトリ虫だと予想されます。たまに親の良くない部分を引き継いだ子供も生まれますが。交叉の方法もそれこそたくさんあって、親の遺伝子をある1点で入れ替える一点交叉だったり、二点交叉だったり、解きたい問題によって良い方法は違ってきます。結構バクチなのがアレですが、これでひとまず次世代に希望をもたせることができました。
そうそう、淘汰しすぎた場合はランダムな染色体を持った新入りを追加したり交配したり、増えすぎた場合は多めに淘汰させるなどして、今の世代と次世代とでシャクトリ虫の総数が同じになるようにするのを忘れずに。いつの間にか絶滅しちゃったりとか寂しいから。
愛憎編 ～突然変異～
次世代の卵もそろい、愛憎編もそろそろ終幕です。が、最後にちょっと味付けします。というのも、淘汰と交叉だけを繰り返していくと秀才はだんだんと多くなっていくのですが、壁をぶち破る天才は生まれにくいのです。このままだと、やがてそこそこ優秀な染色体にみんな同化し、進化が止まってしまいます。
そこで、染色体のどこか一部分を、極めて低い確率で全く別の値に書き換えてしまいます。これを突然変異と呼びます。突然変異のおかげで進化が停滞せずに、常にチャレンジャーな世代を生み出すことができます。突然変異をさせすぎると、副作用としてせっかくこれまで培ってきた優秀な染色体の情報が壊されてしまうので注意です。
歴史はちょっとだけ進んで繰り返す
そして、次世代はまた激闘編へと進み、だんだんとシャクトリムシは歩行動作を獲得していくのでした。
