はじめに
前回の投稿Pythonで実数値遺伝的アルゴリズムの性能を評価してみるの投稿の課題の一つであったBLX-α以外の交叉法としてUNDXの実装を行いました。
UNDXとは
実数値GAの交叉に親を3つ用いる(BLX-αは2つ)ようにした手法で、変数間の依存関係に強い手法とされています。
なお、世代交代時に子との入れ替えの対象となる親は2つだけです。
詳細は以下の論文を参照してください。
実数値GAのフロンティア
単峰性正規分布交叉を用いた実数値遺伝的アルゴリズムによる光学系の最適化
実装
githubに置いています。
https://github.com/SwitchBladeJW/RCGA
評価方法
前回と同様のベンチマーク関数を用いて、BLX-αとUNDXの性能を評価しました。
世代交代モデルはMGGを用いています。 致死個体に対する対応は前回から変更しています。
- 世代交代数：2個体(エリート選択：1個体、ルーレット選択：1個体)
- 致死個体(任意のパラメータが探索範囲を超えた個体) への対応：評価対象から外す
交叉のパラメータは以下の通りです。
- BLX-α(α=0.5)
- UNDX(α=0.5、β=0.35)
Rastrigin関数
- 多峰性関数
- 探索範囲：-5.12～5.12
- 大域的最適解 ： = 0 , (x[i] = 0)
- 2次元のグラフ
2次元
- 最大世代数：100世代
- 集団数：30個体
- 生成子個体数: 60個体/世代
- 初期集団の分布：-5.12～-2.0(次元数が少ないので、最適解を外して分布させています)
個体の分布表示です。青が集団、赤が最良個体です。加えて、親の選択と子の生成も表示するようにしています。
プロットの凡例です。
| 交叉法 | プロット |
|---|---|
| BLX-α |  |
| UNDX |  |
特徴としては、BLX-αは選択された親に対して、X軸・Y軸方向に長方形で子が分布します。
親1と2をつなぐ直線の周辺に楕円形に子が分布します。
RosenBrock関数
- 単峰性関数
- 探索範囲：-2.048～2.048
- 大域的最適解 ： =0 、(x[i] = 1)
- 2次元のグラフ
20次元
- 最大世代数：100000世代
- 集団数：50個体
- 生成子個体数: 200個体/世代
UNDXでは30000世代で最適解を求めることができていますが、BLX-αでは100000世代でも最適解を求めることができていません。RosenBrock関数は変数間の依存関係がある関数なので、UNDXが有効に働いていると思われます。
Schwefel関数
- 多峰性関数
- 探索範囲：-512～512
- 大域的最適解 ： ≒0 、(x[i] = 420.9687)
- 2次元のグラフ
10次元
- 最大世代数：30000世代
- 集団数：300個体
- 生成子個体数: 200個体/世代
前回、致死個体の対処方法を「探索範囲を超えたパラメータを限界値に設定する」にしていて、BLX-αで局所解にはまっていましたが、致死個体の対処方法を変更することで改善されました。
BLX-αとUNDXとも最適解を求めることができていますが、BLX-αの方が早く収束しています。すべてに万能な手法はないってことですね。
学習時間に関して
ColaboratoryでRosenBrock関数20次元100000世代の学習時間の計測を行いました。
()内は致死固体を除いた評価回数(評価関数を使った回数)です。致死個体がなければ、1世代につき202回です。
| 環境 | BLX-α | UNDX |
|---|---|---|
| Colaboratory(CPU) | 40分(20186185回) | 37分(20193164回) |
| Colaboratory(GPU) | 40分(20186482回) | 35分(20193868回) |
※2019.07.06時点での時間です。
- 一般的にはUNDXの方が計算コストが大きいのですが、UNDXの方が処理が早く終わっていました。UNDXの方はforループを完全に排除して作ることができたので、その辺りが聞いてるのかなと思います。pythonでforループは鬼門ですね。
- CPUとGPUの処理速度がほとんど変わりませんでした。GPUに適したコーディングにしないとあまり恩恵はないかもしれません。