遺伝的アルゴリズム(Python)で障害物をジャンプ

# はじめに

障害物をジャンプでかわすミニゲーム、を遺伝的アルゴリズムでクリアさせてみました。

<!--
+ pygameで作られたマリオ:[Mario-Level-1](https://github.com/justinmeister/Mario-Level-1)
+ [マリオをある意味スーパープレイな遺伝的アルゴリズムとニューラルネットワーク学習のみで全自動クリアしてしまう「MarI/O」](https://gigazine.net/news/20150616-mari-o/)
<!--

<!--
本当はこんな感じで、マリオを遺伝的アルゴリズムで試したかったのですが、プログラム変更の手間や処理速度などの問題により、自作で検証用ゲームを作ることにしました。
-->

# ゲームの詳細

ルールは簡単で、操作は迫り来る障害物をジャンプで交わすだけです。

<blockquote class="twitter-tweet" data-lang="ja"><p lang="ja" dir="ltr">qiita資料 81GA <a href="https://t.co/RqHsxoe2AC">pic.twitter.com/RqHsxoe2AC</a></p>&mdash; 平野北斗 (@Default8058) <a href="https://twitter.com/Default8058/status/1023775916906835968?ref_src=twsrc%5Etfw">2018年7月30日</a></blockquote>
<script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

障害物の位置は固定しており、以下のようなマップになっています。

<img width="1637" alt="1.png" src="https://qiita-image-store.s3.amazonaws.com/0/247972/56854220-24a1-94c4-f611-494ff52835a0.png">


# 遺伝的アルゴリズム

遺伝的アルゴリズムとは、ランダムに初期値（遺伝子）を与えて、**選択・交叉・突然変異**という操作を繰り返すことで、**いつの間にか最適解（そうでない可能性もあり）が求まる**というものです。

簡単に言うと、強いものと弱いものがいる集団の中から、強いものが優先的に生き残っていくというものです。

まさに、生命を模倣したアルゴリズムっぽくないですか？

さらなる詳細は他の方に任せて、タメになった本・リンクを紹介しておきます。

+ 分かりやすい ー [【初心者向け】Re:ゼロから始める遺伝的アルゴリズム【人工知能】](https://qiita.com/Azunyan1111/items/975c67129d99de33dc21)
+ 分かりやすい ー [遺伝的アルゴリズムでオセロのAIを学習させてみた](https://www.youtube.com/watch?v=i2-N7nSapVk)
+ ガチ ー [遺伝的アルゴリズム - その理論と先端的手法 | 著者： 棟朝雅晴](https://www.amazon.co.jp/%E9%81%BA%E4%BC%9D%E7%9A%84%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0-%E3%81%9D%E3%81%AE%E7%90%86%E8%AB%96%E3%81%A8%E5%85%88%E7%AB%AF%E7%9A%84%E6%89%8B%E6%B3%95-%E6%A3%9F%E6%9C%9D-%E9%9B%85%E6%99%B4/dp/4627847815)

# 検証方法

**最初に**、遺伝的アルゴリズムを使うにあたって、データを**遺伝子**（コード）で表します。

今回の場合、１つの個体がゴールするまでに１０回の行動があります。

よって、以下の条件に従って長さ10の遺伝子（=[①, ②, ③, ④, ⑤, ⑥, ⑦, ⑧, ⑨, ⑩]）を作ります。

+ `ジャンプする: 1`
+ `ジャンプしない: ０`

<img width="1635" alt="2.png" src="https://qiita-image-store.s3.amazonaws.com/0/247972/45c89460-e3e2-95bd-80ea-11c41a9b2024.png">

例として、ある個体が上図のように動くと決めた場合の遺伝子は、

個体の遺伝子 = [0, 0, 1, 1, 0, 1, 0, 1, 0, 1]

となります。

**次に**、集団の中からどのように優れた(**適応度**が高い)個体を選択するかを決めます。

選択法は色々ありますが、今回は**トーナメント選択法**を用いました。

これは、現世代からランダムにn個の個体を取り出し、一番適応度が高い個体を１つ選び次世代の集団にコピーします。

次世代の個体数が現世代と同じN個になるまで、この操作を繰り返します。

**最後に**、個体の適応度を決めるための**評価関数**を設定します。

(実際、この評価関数の定義が難しい。。。)

今回の場合、進んだ距離をスコアとして使用します。

つまり、一番ゴールまで近づいた個体が優れていると定義します。

ここで一つ実験として、障害物がない場所(②, ⑤, ⑧)で無駄なジャンプをしないために、ジャンプの回数に比例したペナルティを与えます。

よって、

`適応度 = スコア　ー　(ペナルティ ×　ジャンプ回数)`

となります。

こうすることで、同じ距離まで進むことができる集団の中でも、無駄なジャンプをしなかった個体の適応度が高くなるようになります。

あとは、個体数や世代数、その他のパラメータを適当に決めて計算します。

# 結果

遺伝的アルゴリズムのプログラムは、[こちら](http://darden.hatenablog.com/entry/2017/03/29/213948)を参考にしました。

検証条件は以下の通りです。

+ 遺伝子の長さ : 10
+ 1世代あたりの個体数 : 4
+ 交叉率 : 0.5
+ 個体突然変異率 : 0.2
+ 遺伝子突然変異率(遺伝子１つに対しての突然変異率) : 0.3
+ 世代数 : 100

以下は、私の環境下での実行例です。

まずは、第０世代(ランダム初期値)の４個体ですが、全て①の障害物で終わりました。

<blockquote class="twitter-tweet" data-lang="ja"><p lang="ja" dir="ltr">qiita資料 0GA <a href="https://t.co/DE6gZQ9flK">pic.twitter.com/DE6gZQ9flK</a></p>&mdash; 平野北斗 (@Default8058) <a href="https://twitter.com/Default8058/status/1023774781810733057?ref_src=twsrc%5Etfw">2018年7月30日</a></blockquote>
<script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

---

次の第１世代で、早くも(交叉・突然変異によって)、①の障害物を超える個体が１つできました。

<blockquote class="twitter-tweet" data-lang="ja"><p lang="ja" dir="ltr">qiita資料 1GA <a href="https://t.co/vEqSb2A2hZ">pic.twitter.com/vEqSb2A2hZ</a></p>&mdash; 平野北斗 (@Default8058) <a href="https://twitter.com/Default8058/status/1023775741320683520?ref_src=twsrc%5Etfw">2018年7月30日</a></blockquote>
<script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

---

第３世代で、さらに適応度の高い個体ができましたが、選択においてランダムトーナメント法を用いたため、次世代に持ち越されませんでした。

<blockquote class="twitter-tweet" data-lang="ja"><p lang="ja" dir="ltr">qiita資料 3GA <a href="https://t.co/QsP8CMyzeX">pic.twitter.com/QsP8CMyzeX</a></p>&mdash; 平野北斗 (@Default8058) <a href="https://twitter.com/Default8058/status/1023775836556541953?ref_src=twsrc%5Etfw">2018年7月30日</a></blockquote>
<script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

---

そして、世代を重ねるに連れて遺伝子は進化し、第７０世代にはゴールできる個体ができました。

しかし、②において無駄なジャンプをしています。

<blockquote class="twitter-tweet" data-lang="ja"><p lang="ja" dir="ltr">qiita資料 70GA <a href="https://t.co/tB1Xf84Qig">pic.twitter.com/tB1Xf84Qig</a></p>&mdash; 平野北斗 (@Default8058) <a href="https://twitter.com/Default8058/status/1023775083095973888?ref_src=twsrc%5Etfw">2018年7月30日</a></blockquote>
<script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

---

そしてやっと、第81世代に無駄なジャンプをしない完璧な個体が出来上がりました。

<blockquote class="twitter-tweet" data-lang="ja"><p lang="ja" dir="ltr">qiita資料 81GA <a href="https://t.co/RqHsxoe2AC">pic.twitter.com/RqHsxoe2AC</a></p>&mdash; 平野北斗 (@Default8058) <a href="https://twitter.com/Default8058/status/1023775916906835968?ref_src=twsrc%5Etfw">2018年7月30日</a></blockquote>
<script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

実行プログラムと実行例における進化の過程のログファイルは、[Github](https://github.com/hokuto-HIRANO/GA_Game)に上げています。

# まとめ

遺伝的アルゴリズムは比較的簡単なアルゴリズムで試しやすいですが、数学的に収束条件がなく、ヒューリスティックな手法であることを理解しておかなければなりません。

また、初期値に依存しやすく、早く収束してしまい局所最適解に落ちやすいところも注意点です。

それを踏まえて様々な対処法が提案されており、有名なところでは、選択におけるトーナメント法を**ルーレット法**に変更することなどが上げられます。

ルーレット法では、個体の選択を適応度に応じた**確率**に基づいて行われます。

# 最後に

Pythonによるゲーム作成は初めてでしたが、「pygame」というライブラリを使うことで、簡単に作ることができました。

次は、迷路を自作して「Q学習」を試したいと思います。