NEATでCartPole問題を解く

はじめまして。モリカトロン株式会社でAIの研究をしている馬淵です。

最近ですが、ニューラルネットと遺伝的アルゴリズム(以下GA)を組み合わせた Neuro Evolution of Augmenting Topologies(以下NEAT)という手法で OpenAI gymのCartPole問題を解いていたので、この記事では備忘録も兼ねて簡単に解説していきたいと思います。

NEATとは

NEATは2002年頃に提案された手法で、ニューラルネットにおける構造と重みをGAを利用して問題に対し最適化する手法です。

・Evolving Neural Networks through Augmenting Topologies

誤差逆伝搬法による重みの学習や、GAを利用した重みの最適化はすでに存在していた時代ですが、ネットワーク構造の最適化に関しては議論が進んでいなかったようです。計算機処理能力の向上に伴い、深層学習が主流になった現代では若干マイナーな手法になってしまった印象を受けますが、Atariのゲームを攻略しようとしたり、python向けのライブラリが整備されたりなど、研究は今でも続けられています。

・HyperNEAT-GGP: A HyperNEAT-based Atari General Game Player

一般的に、OpenAI gymを解く手法として有名なものにDQNがありますが、DQNがQ学習にニューラルネットを利用しているのに対して、 NEATはニューラルネットのみで問題を解いています。そのため、方策といった概念が必要ありません。

また、NEATはGAの応用なのでGAに対して大まかに理解するために、先に以下の記事を読むことをお勧めします。

・遺伝的アルゴリズム （Genetic Algorithm）を始めよう！

全体の流れ

GAは世代ごとに遺伝子を交叉、変異させ、適合率が高い個体を残していくことで徐々に良い個体へ近づけていくいく手法です。 NEATの場合、ニューラルネットに対してGAを使いたいため、まずはニューラルネットを遺伝子配列で表現する必要があります。 様々な方法がありますが、今回はノードを表す遺伝子と、ノード間の接続関係を表す遺伝子を分けて表現する方法を採用しました。 ノードを表す遺伝子には

1. ノード番号(ID)
2. ノードの種類(入力ノード、出力ノード、隠れ層のノード)
3. 活性化関数の識別番号

の情報を配列の形で格納します。また、ノード間の接続関係を表す遺伝子は

1. 遺伝子ID
2. 入力元のノード番号
3. 出力先のノード番号
4. 重み
5. 接続が有効かどうか

を表現します。 これらの情報から、ノード間の入力、出力の関係を整理し、順伝搬時に対応するノードの活性化関数を参照することで遺伝子からニューラルネットを構築することが可能になります。あとは、得られたニューラルネットから適合率を計算して、普通のGAのアルゴリズムを適用するだけです。

よって、全体の流れとしては

1. 初期集団を作成する
2. 集団の遺伝子からニューラルネットを構築する
3. 得られたニューラルネットから適合率を計算する
4. 適合率が低い個体を淘汰する
5. 交叉と突然変異で新世代の集団を作成する
6. 一定の適合率になるまで2-5を繰り返す 

CartPoleでの初期集団の例

ここでの注意点として、初期集団には隠れ層がない単純なニューラルネットを採用したほうがよいです。理由として、NEATにおける変異がノードや接続の追加といったニューラルネットを現状より複雑にする操作しかないためです(そのせいで計算も重くなっていきます)。

ニューラルネットが複雑になればなるほど、交叉や変異による構造変化が小さくなり、適合率が上がりづらくなります。そのため、最初から複雑なニューラルネットを初期集団としてしまうと、最適な構造を持つニューラルネットが見つかりづらくなります。

NEATでCartPole 

今回はOpenAI gymのCartPoleに以下のような変更を施した環境で試してみました

1. ポールが下を向いても終了しない
2. ポールが下を向いた状態から開始する
3. 車体が画面外に出る、または1000step経過したら終了

また、報酬を(画面中央にどれだけ近いか)×(棒がどれだけ上を向いているか)で計算(最大1)して、エピソード終了時の報酬の和を適合率として進化させました。そのため、適合率の最大値は900前後になります。

ちなみにですがNEATを扱う場合、適合率の計算の部分は並列処理で行うことを推奨します。私の環境ではCartPole問題を1世代192の個体、1024世代、適合率の計算で平均をとるために1個体につき2回計算させましたが、並列処理を使わなかった場合、12時間ほどかかりました。(192×1024回×2回分のCartPoleをやっているので当然といえば当然ですね…)

それでは、世代ごとにニューラルネットの構造と挙動がどうなっているか見ていきます。

結果

・第1世代

初期集団で最も成績が良かった個体。適合率240.94

入力ノードと出力ノードをランダムな重みでつなぎ合わせているだけなので当然良い結果にはなりません。左右に揺らすだけの挙動を見せます。画面外に出て終了しない個体が選ばれていることが分かります。

・第512世代

512世代目までで最も成績が良かった個体。適合率538.78

ポールを回転させることを習得していることが分かります。ポールを上向きにした方がよいことを理解し始めているようです(ポールを上向きに維持する方法が分かっていないようですが…)。また、ニューラルネットも加速度にsigmoid関数を適用してから出力ノードに流すようになっています。ノード数自体は512世代経過しても変化が少ないですが、ノード間の重みは変化しています。

・1024世代

1024世代目までで最も成績が良かった個体。適合率806.38

不安定な場面もありますがポールを上向きにしつつ倒れないようにしています。ニューラルネットの構造も初期集団と比較すると大きく変化しました。

各世代ごとの適合率の中央値、最大値および最高適合率の推移をグラフにすると以下のようになります。DQNが大量のパラメータを必要とするのに対し、単純なネットワークでこれほど高いスコアを出せるのは驚きですね。

各世代ごとの適合率の推移

また、GAを利用している性質上、交叉や変異における操作をランダムで行うため、やり直しをするたびに出力される結果やニューラルネットの構造は違ったものになります。以下は同じパラメータを使ってもう一度計算させた場合の最高適合率を出した個体です。

別バージョンの1024世代目で最も成績が良かった個体。適合率737.06

ニューラルネットの構造や挙動が違っていることが分かります。このように進化計算をするたびに結果が変化するため、目標とする適合率に到達できない可能性があり注意が必要となります。

まとめ

NEATをつかって強化学習の枠組みの問題が解けることができました。DQNと比較するとメリットとしてはニューラルネットのパラメータ数が少ないことが挙げられます。ただし、これはCartPoleの場合であり、別の問題(例えばAtari 2600などの画像を入力とする場合)は変わってくる可能性があります。

また、デメリットとしては計算に時間がかかる、結果が不安定で目標とする適合率が得られない可能性がある、といったものが挙げられます。前者は並列処理をすることで回避することができますが、後者は何度もやり直す以外に方法がないように考えられます。

個人的なやってみた感想としては、少なくとも現代の計算機の場合、DQNなどの強化学習や誤差逆伝搬法を利用して目的を達成できるならばそちらを利用すれば良いように思えます。

ただし、今後の計算機の能力、特に並列処理の発展によっては使える場面も増えてくると考えられます。マルコフ過程が必要なく、適合率の与え方さえ定義すれば、勝手にニューラルネットを構築してくれるため、非常に楽です。

今後の発展に期待しましょう。

(おまけ)

NEATによる計算を同じ条件で10回ほど行い、最も適合率が高い個体を選出したところ以下のようになりました。素晴らしい性能になっています。

最も成績が良かった個体。適合率851.09

参考文献

本記事は以下の文献、コードを参考にしました

• brain-tokyo-workshop/WANNRelease/prettyNEAT at master · google/brain-tokyo-workshop · GitHub

  (実装時に参考にしたコード) 

• 遺伝的アルゴリズム （Genetic Algorithm）を始めよう！

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