遺伝的アルゴリズムxニューラルネットワーク（NeuroEvolution）でOpen AI Gymの二足歩行ロボを歩かせた話

どうも、オリィ研究所（http://orylab.com/） の ryo_grid こと神林です。

今回は以前試してなかなかうまくいかなかったOpen AI Gymの二足歩行ロボの強化学習へ再チャレンジした話と、その中で知ったNEAT(NeuroEvolution of Augmenting Topologies)という手法について書きたいと思います。

# 前回のお話
DQN(Deep Q-learning Network)という、強化学習の手法を使って二足歩行ロボを歩かせようとしました。
結果として、学習自体は成されましたが、まともに歩くというところまではいくことができませんでした。

[PythonでAIシミュレーションプラットフォームOpen AI Gym を利用して遊ぶ (DQN編)](http://qiita.com/ryo_grid/items/94f3a95d1e8d2ccddd6a)

# 再チャレンジ
どうにか歩かせることができないかとネットの海をさまよっていたところ、stefanopalmieri氏という方が同じ課題に取り組んだと思われるコードを発見したので、プログラムをお借りして（パラメータをいじったり、多少のコードの修正は加えた）、実行してみました。

https://gist.github.com/stefanopalmieri/2efec0e09c14de06fb93fbb91e18a93a

結果、ある程度歩く動作をさせることができました。
途中で転んでしまったりしてゴールには到達していませんが、確かに歩行動作を学習しています。
歩行方法に関する知識はまったく与えていないのに、このような振る舞いをするのだから強化学習というのは不思議ですね。
学習させた結果はこちら↓。歩いている様子の動画に加えて、ソースコードとコンフィグファイル、実行方法も載せておきました。

https://gym.openai.com/evaluations/eval_wzmU0dtQCeoz2dWyhsD5Q
<blockquote class="twitter-tweet" data-lang="ja"><p lang="und" dir="ltr"><a href="https://t.co/HpXL6yMDuZ">pic.twitter.com/HpXL6yMDuZ</a></p>&mdash; ホクソryo_grid@86世代 (@ryo_grid) <a href="https://twitter.com/ryo_grid/status/817261578332446721">2017年1月6日</a></blockquote>
<script async src="//platform.twitter.com/widgets.js" charset="utf-8"></script>

# neat-python
上記で利用させてもらったプログラムでは、[neat-python](http://neat-python.readthedocs.io/en/latest/)というpythonの強化学習ライブラリが利用されています。
バージョンは0.8を利用しました。
最初はニート？とクエスチョンマークが出ましたが、調べてみると NEAT という強化学習の一手法であることが分かりました。
で、他人のプログラムを実行してみました、だけでは残念な感じなので、今回はこの手法について簡単に解説してみます。

# Neuroevolution
遺伝的アルゴリズムでニューラルネットワークの結合重みやトポロジ（各層間の接続関係）の最適化を行う手法です。
一般的な手法ですとニューラルネットワークの結合重みはバックプロパゲーション（誤差逆伝播法）という手法で更新されますが、そこのところを遺伝的アルゴリズムで行います。
そして、今回利用したNEATという手法では、さらにトポロジも遺伝的ネットワークで最適化してしまうという大胆なことを行います。

その他、詳しくは wikipedia にも解説があるのでそちらをご参照下さい。

[Neuroevolution](https://ja.wikipedia.org/wiki/Neuroevolution)

# NEAT (NeuroEvolution of Augmenting Topologies)
論文はこちら(久しぶりに英語論文を読みました...)
[Evolving Neural Networks through Augmenting Topologies](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.28.5457&rep=rep1&type=pdf)

2001年に提案された手法で、ニューラルネットワークの重みとトポロジを遺伝的アルゴリズムで最適化します。なんだか、最先端な感じがするNEATですが、16年前には開発されていた手法なんですね。
当時は、Neuroevolutionにおいて、トポロジの最適化まで踏み込むことについて有効性が定かではなかったそうですが、NEATはそれが有効であることを示しました。

トポロジの最適化は小さな構造から徐々に増大させていきながら行われます。タイトルにあるAugmenting(増大する)というのは、このことを指しています。詳細は論文をご参照ください。

さて、2013年にはDQNという手法でアタリのゲームをプレイするAIが生み出されたことが一躍話題となりましたが、その後、同種の試みはNEATを用いても行われているようです。

[A Neuroevolution Approach to General Atari Game Playing](https://pdfs.semanticscholar.org/2897/b921f734bc7083f263717ba2217257d3e661.pdf)

また、Neuroevolution界(?)では、実用面でNEATおよびその亜種がデファクトになっているようで、ライブラリもneat-python以外にも多数開発されているようです。

[MultiNEAT(C++)](http://multineat.com/)
[SharpNEAT(C#)](http://sharpneat.sourceforge.net/)
[JNEAT(Java)](http://nn.cs.utexas.edu/?jneat)

なお、DQNとNEATはどちらもニューラルネットワークを使いますが、DQNはあくまでQ学習で、その枠組みの中にニューラルネットワークを取り込んだものであるのに対して、NEATはざっくりと言ってしまえばただのニューラルネットワークで、その最適化の方法が特殊なだけであると言えます。

ここらへんの微妙な違いは、DQNという手法についての理解を必要とするので、↓の記事などを読んでみてください。

[DQNの生い立ち　＋　Deep Q-NetworkをChainerで書いた](http://qiita.com/Ugo-Nama/items/08c6a5f6a571335972d5)

neat-pythonを使ってみた印象としては、強化学習のコード自体は直感的に書けるので良い感じなのですが、ニューラルネットワークあるあるで、チューニングパラメータがたくさんあるので、そこらへんが大変そうだなと思いました。
ただ、適当にやってもそれなりにワークするのか、パラメータセンシティブなのかはもっと、使いこんでみないと分からないです。


```text:walker.config
# The `Types` section specifies which classes should be used for various
# tasks in the NEAT algorithm.  If you use a non-default class here, you
# must register it with your Config instance before loading the config file.
[Types]
stagnation_type      = DefaultStagnation
reproduction_type    = DefaultReproduction

[phenotype]
input_nodes          = 24
hidden_nodes         = 0
output_nodes         = 4
initial_connection   = fs_neat
max_weight           = 10
min_weight           = -10
feedforward          = 0
activation_functions = tanh sigmoid relu identity
weight_stdev         = 3

[genetic]
pop_size                = 400
max_fitness_threshold   = 130
prob_add_conn           = 0.3
prob_add_node           = 0.1
prob_delete_conn        = 0.05
prob_delete_node        = 0.03
prob_mutate_bias        = 0.00109
bias_mutation_power     = 0.01
prob_mutate_response    = 0.01
response_mutation_power = 0.01
prob_mutate_weight      = 0.3
prob_replace_weight     = 0.03
weight_mutation_power   = 0.1
prob_mutate_activation  = 0.01
prob_toggle_link        = 0.0138
reset_on_extinction     = 1

[genotype compatibility]
compatibility_threshold = 3
excess_coefficient      = 1.0
disjoint_coefficient    = 1.0
weight_coefficient      = 0.4

[DefaultStagnation]
species_fitness_func = mean
max_stagnation       = 5

[DefaultReproduction]
elitism              = 3
survival_threshold   = 0.2
```

以上です。