前置き
遺伝的アルゴリズムはパラメータの調整や組み合わせ最適化のような非常に単純な例で紹介されることが多いですが、少しの工夫でアルゴリズムやプログラムの自動生成が可能になります。
前提知識
遺伝的アルゴリズム
変異、遺伝、淘汰などによる生物の進化の考えに基づいた探索アルゴリズムです。
遺伝子型
突然変異や交叉のような遺伝的操作を行う対象となる型です。
表現型
適応度の評価対象となる遺伝子型から発現した個体です。
様々な遺伝的アルゴリズム
遺伝的プログラミング
遺伝子型が木構造
遺伝的ネットワークプログラミング
遺伝子型がネットワーク構造
Graph Structured Program Evolution (GRAPE)
遺伝子型が一次元配列
表現型がグラフ構造
ループが必要なアルゴリズムも表現でき、高い確率で階乗やフィボナッチを求めるプログラムを自動生成できます。
実際に動かせるデモ
対象問題
強化学習のシミュレーション環境である OpenAI Gym の簡単な問題を GRAPE を使用して解いてみました。
Cart Pole
上に乗っている Pole が倒れないように Cart を動かしてバランスを取るという問題です。
初期状態はある程度ランダムなため、ある程度汎用的に対応可能なアルゴリズムが必要です。
下の画像は実際に獲得したアルゴリズムの動作です。
この自動生成されたアルゴリズムをPythonで実行可能なように吐き出したものは以下です。
この吐き出す処理も実装しているためプログラムコードの生成が自動化されていると言えます。
Mountain Car
Car を動かして右の山に登るという問題です。
こちらも初期条件はある程度ランダムです。
下の画像は実際に獲得したアルゴリズムの動作です。
この自動生成されたアルゴリズムをPythonで実行可能なように吐き出したものは以下です。
まとめ
最近発表された AutoML-Zero も進化的アルゴリズムによりアルゴリズム自体を自動で構築するものでした。
今後は機械学習も含めて完全に人間の手を離れて自動でアルゴリズムやプログラミングの作成を行うという研究がより盛んに行われると考えられます。
個体表現や遺伝子操作に関してより一般的な遺伝的アルゴリズムに則っているGRAPEを拡張してAutoML-Zeroを実装したところ、現時点でおおよそ期待通りの結果が得られています。
前置きに述べたとおり遺伝的アルゴリズムはパラメータの最適化や数値の組み合わせ最適化を解くだけのものではありません。
進化と学習は両立するものであり、進化により得た新しい構造を学習で最大限活かすという関係を実用的なレベルで再現したのが AutoML-Zero だと考えており、遺伝的アルゴリズムはこの進化の部分に大いに活用することができると信じています。
この方面での研究・開発を行っている方の参考になれば幸いです。