今回エンジニアブロクを担当する小瀬です。
先日、将棋のAIが現役のプロ棋士に勝つなど、なかなか話題を集めている人工知能ですが今回はGA（Genetic algorithm、遺伝的アルゴリズム）と呼ばれる手法で謎の生物に歩行学習をさせてみようかと思います。
■GAとは？
GA（遺伝的アルゴリズム）についてザックリと説明すると、ランダムで与えられた数値、アルゴリズムを用いて徐々に学習・遺伝させながら解を求めていく進化的アルゴリズムの一種です。
今回のケースでは、４本足を持ったモデルに関節の回転パラメータ等をランダムで与え、より効率よく歩けるよう学習させていきます。本来は決まった解の無い問題の最適解を探したり、ロジックそのものをランダムで組み換えより高度なアルゴリズムを自動で生成させたりなど、複雑なシチュエーションで利用される事が多いのかなと思います。
■進化(学習)のしくみ
それでは、実際にどのように進化させていくのか簡単に説明していきます。
◇０．初期生成
GAの解説などではあまり触れられませんが、一番初めの個体は完全にランダムで生成してしまいます。一般的には、一度に大量の個体を生成してしまったほうが効率が良いですがパフォーマンスや時間との兼ね合いで適度な数（N体）の個体を生成します。
◇１．淘汰
それぞれの個体を動作させ、求める解に基づいてスコアを算出し優秀な個体を選別します。選別する手法としてはスコアの高いエリートから順番に選択する方法や、スコアの高いものの確率を上げその中からランダムで選択する方法などがあります。
◇２．交叉
生き残った個体からランダムに２つの個体を選び、それぞれの要素を交叉させていきます。このフェイズは空間内の個体が最大数（N体）になるまで繰り返します。
交叉の方法としては、上図のように個体Ａと個体Ｂを選びそれぞれの個体からパラメータを受け継ぎ新しい個体Ｘを生成します。このＡとＢのパラメータを区切る方法によって２点交叉、一様交叉など様々な方法があります。
◇３．突然変異
交叉した個体の中を一定確率で突然変異を起こさせます（簡単に言ってしまえば一部のパラメータをランダムに変えたりします）。どの程度の頻度で突然変異するかによって結果は大きく変わってきますが、突然変異を無くしてしまうと「進化の袋小路」に陥り、途中で進化が止まってしまうことがあります。
◇４．繰り返し
この１〜３までのプロセスを望む結果が得られるまでひたすら繰り返していきます。求める解によっては非常に時間がかかる事もあります。
■歩行学習
今回は、４本足のモデルを用意し、Unity上でRigidbodyやCharactorJoint等を設定することで簡単に物理演算を行えるよう設定しています。
上記の０〜４の各プロセスについて簡単に説明すると、体と４本の足、それぞれ２箇所の関節を持ち、各関節にランダムで回転値（厳密には２〜５点の回転各をそれぞれ順番に補間しながらループ）を与えられた個体が５０体生成されます。
それらの個体が、自らの手足の動きと物理演算によって移動して行くため、その結果として最もZ方向に進んだ個体により高いスコアを付けます。この際、移動中ににひっくり返ってしまったり、後ろ方向を向いてしまった個体にはペナルティとしてマイナス点を与えています。
計算されたスコアの中から上位１０個体を選出し、それぞれ関節の回転角を交叉させて新しい個体を生成、そのうち２０体は突然変異として１〜２箇所の関節にランダム値を与えています。
こういった計算を何百世代と繰り返し、より効率よく移動できるよう学習させて行きました。
■学習結果
第１世代目ではほとんど前に進むことも出来ず、その場でウネウネしているだけで回転してしまっている個体もいます。
３８０世代目の個体となると、完璧とは言えなくとも這うように歩くようになります。このように何世代も学習を重ねていくことでより良い結果を得ることが出来ます。
今回は、関節の回転角、脚の質量などを遺伝させ変化させてみましたが、脚を移動させる際の力の強度や脚そのものの大きさ等を変えてみるのも面白いかもしれません。
（ただ、残念なことに色々と設定を変更してみたものの、RigidbodyやJoinの作成の仕方が悪いのか、Unityの物理エンジンの精度の問題なのか分かりませが、同じパラメータの個体であっても実行する度に結果が微妙に異なり、２０００世代ほど遺伝させてみてもあまり効率的な進化が行われていないようでした。この辺りの問題が解決すると、より良い結果が得られたのではないかなと思います。）
■まとめ
GA自体の考え方は難しくはないと思いますし、こういったシンプルなものであれば実装方法は非常に簡単でかなり面白い結果が得られる手法だと思います。望む結果を得るためには、スコアの計算方法や個体のパラメータ設定など色々と調整が必要な部分もありますが、AIに興味のある方は一度試してみてはいかがでしょうか？
■おまけ
煩雑なコードではありますが、今回作成したUnityプロジェクトをアップロードしておきます。
GAWalker.zip
Assetフォルダの中にSceneファイルが１つあるので、そのシーンをロードして実行すると勝手に遺伝が始まります。また、２０世代毎にExportフォルダ以下に自動的に各パラメータが保存されるため、GenManagerのインスペクタにある「Import」からロードすることも可能です。