はじめに
障害物をジャンプでかわすミニゲーム、を遺伝的アルゴリズムでクリアさせてみました。
ゲームの詳細
ルールは簡単で、操作は迫り来る障害物をジャンプで交わすだけです。
qiita資料 81GA pic.twitter.com/RqHsxoe2AC
— 平野北斗 (@Default8058) 2018年7月30日
障害物の位置は固定しており、以下のようなマップになっています。
遺伝的アルゴリズム
遺伝的アルゴリズムとは、ランダムに初期値（遺伝子）を与えて、選択・交叉・突然変異という操作を繰り返すことで、いつの間にか最適解（そうでない可能性もあり）が求まるというものです。
簡単に言うと、強いものと弱いものがいる集団の中から、強いものが優先的に生き残っていくというものです。
まさに、生命を模倣したアルゴリズムっぽくないですか？
さらなる詳細は他の方に任せて、タメになった本・リンクを紹介しておきます。
- 分かりやすい ー 【初心者向け】Re:ゼロから始める遺伝的アルゴリズム【人工知能】
- 分かりやすい ー 遺伝的アルゴリズムでオセロのAIを学習させてみた
- ガチ ー 遺伝的アルゴリズム - その理論と先端的手法 | 著者： 棟朝雅晴
検証方法
最初に、遺伝的アルゴリズムを使うにあたって、データを遺伝子（コード）で表します。
今回の場合、１つの個体がゴールするまでに１０回の行動があります。
よって、以下の条件に従って長さ10の遺伝子（=[①, ②, ③, ④, ⑤, ⑥, ⑦, ⑧, ⑨, ⑩]）を作ります。
ジャンプする: 1ジャンプしない: ０
例として、ある個体が上図のように動くと決めた場合の遺伝子は、
個体の遺伝子 = [0, 0, 1, 1, 0, 1, 0, 1, 0, 1]
となります。
次に、集団の中からどのように優れた(適応度が高い)個体を選択するかを決めます。
選択法は色々ありますが、今回はトーナメント選択法を用いました。
これは、現世代からランダムにn個の個体を取り出し、一番適応度が高い個体を１つ選び次世代の集団にコピーします。
次世代の個体数が現世代と同じN個になるまで、この操作を繰り返します。
最後に、個体の適応度を決めるための評価関数を設定します。
(実際、この評価関数の定義が難しい。。。)
今回の場合、進んだ距離をスコアとして使用します。
つまり、一番ゴールまで近づいた個体が優れていると定義します。
ここで一つ実験として、障害物がない場所(②, ⑤, ⑧)で無駄なジャンプをしないために、ジャンプの回数に比例したペナルティを与えます。
よって、
適応度 = スコア ー (ペナルティ × ジャンプ回数)
となります。
こうすることで、同じ距離まで進むことができる集団の中でも、無駄なジャンプをしなかった個体の適応度が高くなるようになります。
あとは、個体数や世代数、その他のパラメータを適当に決めて計算します。
結果
遺伝的アルゴリズムのプログラムは、こちらを参考にしました。
検証条件は以下の通りです。
- 遺伝子の長さ : 10
- 1世代あたりの個体数 : 4
- 交叉率 : 0.5
- 個体突然変異率 : 0.2
- 遺伝子突然変異率(遺伝子１つに対しての突然変異率) : 0.3
- 世代数 : 100
以下は、私の環境下での実行例です。
まずは、第０世代(ランダム初期値)の４個体ですが、全て①の障害物で終わりました。
qiita資料 0GA pic.twitter.com/DE6gZQ9flK
— 平野北斗 (@Default8058) 2018年7月30日
次の第１世代で、早くも(交叉・突然変異によって)、①の障害物を超える個体が１つできました。
qiita資料 1GA pic.twitter.com/vEqSb2A2hZ
— 平野北斗 (@Default8058) 2018年7月30日
第３世代で、さらに適応度の高い個体ができましたが、選択においてランダムトーナメント法を用いたため、次世代に持ち越されませんでした。
qiita資料 3GA pic.twitter.com/QsP8CMyzeX
— 平野北斗 (@Default8058) 2018年7月30日
そして、世代を重ねるに連れて遺伝子は進化し、第７０世代にはゴールできる個体ができました。
しかし、②において無駄なジャンプをしています。
qiita資料 70GA pic.twitter.com/tB1Xf84Qig
— 平野北斗 (@Default8058) 2018年7月30日
そしてやっと、第81世代に無駄なジャンプをしない完璧な個体が出来上がりました。
qiita資料 81GA pic.twitter.com/RqHsxoe2AC
— 平野北斗 (@Default8058) 2018年7月30日
実行プログラムと実行例における進化の過程のログファイルは、Githubに上げています。
まとめ
遺伝的アルゴリズムは比較的簡単なアルゴリズムで試しやすいですが、数学的に収束条件がなく、ヒューリスティックな手法であることを理解しておかなければなりません。
また、初期値に依存しやすく、早く収束してしまい局所最適解に落ちやすいところも注意点です。
それを踏まえて様々な対処法が提案されており、有名なところでは、選択におけるトーナメント法をルーレット法に変更することなどが上げられます。
ルーレット法では、個体の選択を適応度に応じた確率に基づいて行われます。
最後に
Pythonによるゲーム作成は初めてでしたが、「pygame」というライブラリを使うことで、簡単に作ることができました。
次は、迷路を自作して「Q学習」を試したいと思います。