realcodedgeneticalgorithm

Transcript

1. 実数値遺伝的アルゴリズム Real-Coded Genetic Algorithm 大阪府立大学 工学研究科 清水 悠生
2. 2 はじめに ✓ 実数値遺伝的アルゴリズムでよく使われる 手法の紹介をします（単目的最適化がメイン） ✓ 数学的な話はあまりしません（文献見て） ✓ 本記事で紹介するアルゴリズムは 全てGitHubで実装しています（python) ✓ https://github.com/yshimizu12/RealCodedGeneticAlgorithm
3. 3 実数値遺伝的アルゴリズムの概要 ✓ 実数値ベクトルを遺伝子型とする進化計算法を実数値 遺伝的アルゴリズム(GA: Genetic Algorithm)と呼ぶ ✓ 通常のGAとは異なり実数値ベクトルを操作する ✓ 実数値GAの枠組みは下記のとおり 初期集団の 乱数生成 親個体群の 複製選択 実数値交叉 による 子個体群の 生成 次の集団の 生存選択 集団 親 子 次の集団 満たさなければ戻る 停止条件を 満たせば終了
4. 4 世代交代モデル ✓ 実数値GAの枠組みの中の複製選択と生存選択を合わせて 世代交代モデルと呼ぶ ✓ 本記事では2種類の世代交代モデル（MGG, JGG）を紹介 初期集団の 乱数生成 親個体群の 複製選択 実数値交叉 による 子個体群の 生成 次の集団の 生存選択 集団 親 子 次の集団 満たさなければ戻る 停止条件を 満たせば終了
5. 5 MGG (Minimal Generation Gap) ✓ 世代交代モデルの一つ ✓ 親個体数が2個の場合を前提に設計（BLX-αなど） ✓ 多親を用いた交叉に対しては収束が遅れる恐れあり 複製選択 ① 集団から親個体をランダムに非復元抽出 （個体数は交叉に依存） 子個体の生成 ② 親個体群に交叉を繰り返し適用し，子個体を生成 生存選択 ③ 親個体群から2個体をランダムに選択し子個体に追加 家族と呼ぶ ④ 家族の中から評価値が最良の1個体とルーレット選択により 1個体を選択 ⑤ 家族に選ばれていない親個体群に選択した2個体を追加 ⑥ 親個体群を集団に戻し，次集団とする 小林重信，人工知能学会論文誌，Vol. 24, No. 1, pp. 147-162 (2009)
6. 6 JGG (Just Generation Gap) ✓ MGGを多親交叉向けに改良した世代交代モデル ✓ 生存選択の対象を子個体に限定し，親個体は全て淘汰 複製選択 ① 集団から親個体をランダムに 非復元抽出（個体数は交叉に依存） 子個体の生成 ② 親個体群に交叉を繰り返し適用し 子個体を生成 生存選択 ③ 子個体群か評価値が上位の個体を 親個体の数だけ選択 ④ 選択した個体を集団に追加 次集団とする 小林重信，人工知能学会論文誌，Vol. 24, No. 1, pp. 147-162 (2009)
7. 7 実数値交叉 ✓ 実数値ベクトルの親個体近傍に 子個体を生成する操作を実数値交叉と呼ぶ ✓ 本記事では5種類の実数値交叉を紹介 （BLX-α, UNDX, UNDX-m, SPX, REXstar） 初期集団の 乱数生成 親個体群の 複製選択 実数値交叉 による 子個体群の 生成 次の集団の 生存選択 集団 親 子 次の集団 満たさなければ戻る 停止条件を 満たせば終了
8. 8 BLX-α (BLend Crossover alpha) ✓ 親個体数は2個 ✓ 2つの親個体からなる区間の両端をα倍した領域内に ランダムに子個体を生成 ✓ 悪スケール性の影響は受けにくいが 変数間依存性の強い関数には対処できない 2次元での例 子個体数1000の場合 親1 親2 I x αI x αI x I y αI y αI y 棟朝雅晴，遺伝的アルゴリズムーその理論と先端的手法ー（2015）
9. 9 UNDX (Unimodal Normal Distribution Crossover) ✓ 親個体数は3個 ✓ 変数間依存性を考慮した交叉手法 ✓ 悪スケール性の強い関数に対処できない 2次元での例 子個体数1000の場合 親1 親2 親3 喜多等，計測自動制御学会論文集，Vol. 36, No. 10, pp. 875-883 (2000) 親1~親2の方向が主軸 正規分布に従って生成 主軸に親3が近いと 子個体は主軸近くに生成 主軸から親3が遠いと 子個体のばらつきは大きく
10. 10 UNDX-m ✓ 親個体数は(入力変数の次元+1)個 ✓ UNDXのスケール依存性の改善を意図した多親交叉 ✓ UNDXより変数間依存性や悪スケール性に強い 小林重信，人工知能学会論文誌，Vol. 24, No. 1, pp. 147-162 (2009) 2次元での例 子個体数1000の場合 親1 親2 親3 重心 重心を中心に分布 主親(この例だと親1親2)に したがって分布を決定 3親が一直線に並ぶと 子個体は一方向に生成 親1親2から親3が遠くても 親3の近くにも子個体が生成
11. 11 SPX (SimPlex Crossover) ✓ 親個体数は(入力変数の次元+1)個 ✓ 重心-親個体ベクトルをε倍した点により張られる 単体 (simplex)の内部に子個体をランダム生成 ✓ 変数間依存性や悪スケール性に強い 樋口等，人工知能学会論文誌，Vol. 16, No. 1, pp. 147-155 (2001) 親1 親2 親3 重心 2次元での例 子個体数1000の場合 ε 1
12. 12 親1 親2 親3 重心 親3’ 親1’ 親2’ この例では 親1,親2’,親3の評価値が高く 全体の重心から親1,親2’,親3 の重心に向かう方向に 子個体を生成 親1,親2’, 親3の重心 REXstar (Real-coded Ensemble Crossover star) ✓ 親個体数は(入力変数の次元+1)個 ✓ SPXの重心に対する非対称性を排除するため 親個体の重心に対する鏡像点を設定 ✓ 親個体と鏡像点の内，評価値の高い点を中心に子個体を生成 ✓ 変数間依存性や悪スケール性に強い 2次元での例 子個体数1000の場合 小林重信，人工知能学会論文誌，Vol. 24, No. 1, pp. 147-162 (2009)