UnityとDEAP（遺伝的アルゴリズム）の連携

こんにちは、モリカトロン・プログラマのはっとりです。

このブログは「UnityとAx(Adaptive Experimentation Platform)の連携 - Morikatron Engineer Blog」の続編です。

はじめに
遺伝的アルゴリズム
DEAP
サンプルプログラム
動作環境など
ベイズ最適化と遺伝的アルゴリズムの比較
最後に

はじめに

前回はUnityとPythonでベイズ最適化のサンプルプログラムを作成しました。
今回は前回のサンプルプログラムに遺伝的アルゴリズムを追加します。

遺伝的アルゴリズム

遺伝的アルゴリズム（Genetic Algorithm、GA）は、遺伝子の選択、交配、突然変異といった生物の進化過程を模倣して、最適化問題の近似解を探索するアルゴリズムです。

今回、遺伝的アルゴリズムの実装にはDEAPというPythonパッケージを使用しました。

DEAP

DEAP（Distributed Evolutionary Algorithms in Python）は、Pythonで動作する進化計算フレームワークです。遺伝的アルゴリズム（GA）以外に、遺伝的プログラミング（GP）、進化戦略（ES）などのアルゴリズムが利用可能です。

DEAPの詳細は下記サイトを参照してください。
https://github.com/DEAP/deap

サンプルプログラム

前回作成したサンプルプログラムをベースに、クライアント側のUnity（WebGL）はそのままで、サーバー側の最適化アルゴリズムに遺伝的アルゴリズムを追加します。

具体的には以下の3種類のバリエーションを作成します。

シンプルGA（簡易版）
シンプルGA（フルスペック版）
実数値GA

※以下で紹介するソースコードはいずれもDEAP公式exampleをベースに筆者がコードを追加しています。

シンプルGA（簡易版）

最適化ループを包含した簡易版のAPIを使用します。ユーザーは必要最低限のコードで遺伝的アルゴリズムを始められます。

サンプルでは、単一のビット列をパラメータの数で分割し、対応する型・レンジ（実数・整数・択一・固定）に変換する手法を採っています。こうすることで、複数の型・レンジが混在するケースに対応可能としています。

現状は一つのパラメータを8ビットで表現しており、実数では8ビットの整数値（255）で分割した精度になりますが、ビット数を増やせばその分精度を上げることが可能です。

パラメータ定義の書式は前回使用したAx（ベイズ最適化のPythonパッケージ）のものを流用しています。

ソースコード
AxSample/booth_ga_short.py at master · morikatron/AxSample · GitHub
実行結果　※Booth Functionの最適解＝[1, 3]
- ベスト個体　　　　[1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1]
- ベストスコア　　　0.03460197523236275
- ベストパラメータ　[0.98039216, 3.09803922]

シンプルGA（フルスペック版）

遺伝的アルゴリズムの個々の構成要素（個体選択、フィッティング、交叉、突然変異など）に対応するAPIを使用してより細かなカスタマイズを行います。

このサンプルでは、デフォルトでは全個体選択ですが、選択個体数を指定するオプションを用意します。選択個体数を指定する場合は、DEF_SELECT_NUMの値を変更してください。

ソースコード
AxSample/booth_ga.py at master · morikatron/AxSample · GitHub
実行結果　※Booth Functionの最適解＝[1, 3]
- 選択個体数＝全個体
  - ベスト個体　　　　[1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0]
  - ベストスコア　　　0.0007689303020015359
  - ベストパラメータ　[0.98039216 3.01960784]
- 選択個体数＝2
  - ベスト個体　　　　[1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1]
  - ベストスコア　　　0.25605547428131104
  - ベストパラメータ　[0.82352941, 2.94117647]

実数値GA

ビット列の代わりに、実数値をそのまま遺伝子として使用します。

DEAPの実数値GAは、最適化対象パラメータは共通の型・レンジを持たないといけないという制約があるようなので、型・レンジが混在する最適化問題の場合だと前出のビット列を各種型・レンジに変換する手法の方が使い勝手が良いかもしれません。

ソースコード
AxSample/booth_ga_float.py at master · morikatron/AxSample · GitHub
実行結果　※Booth Functionの最適解＝[1, 3]
- ベスト個体　　　　[1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0]
- ベストスコア　　　0.0007689303020015359
- ベストパラメータ　[0.98039216, 3.01960784]

動作環境など

以下に書く内容以外は基本的に前回と同様になります。

GitHub

サンプルプログラムのリポジトリは前回と同じものを使用します。

GitHub - morikatron/AxSample: Unity～Ax連携サンプルプログラム

動作環境

deap 1.3.1

$ pip install deap

実行手順

適宜app.pyでOptimizerを切り替えてください。

【app.py 抜粋】

from booth_loop import Optimizer  # ベイズ最適化
# from booth_ga_short import Optimizer  # シンプルGA（簡易版）
# from booth_ga import Optimizer  # シンプルGA（フルスペック版）
# from booth_ga_float import Optimizer  # 実数値GA