探索領域分割型ＧＡ Divided Searching Area GA 知的システムデザイン研究室 赤塚浩太 Intelligent systems design laboratory Kouta Akatsuka 概要 研究背景 探索領域分割型ＧＡ 数値実験 考察 まとめ 概要 研究背景 探索領域分割型ＧＡ 数値実験 概要 考察 依存関係の評価 依存のない問題 まとめ 依存のある問題 へのアプローチ 一部に依存のある問題 概要 研究背景 探索領域分割型ＧＡ 数値実験 考察 Rastrigin,Schwefel ［依存関係なし］ まとめ Original Function ［一部に依存関係］ Rosenbrock,Griewank ［依存関係あり］ 概要 研究背景 探索領域分割型ＧＡ 数値実験 考察 まとめ 移住パラメータに関する考察 解空間の増大に関する考察 概要 研究背景 探索領域分割型ＧＡ 数値実験 考察 まとめ 研究背景 単一母集団ＧＡ 分割母集団ＧＡ 並列化 そこで！ が容易 移住と島数のパ 解の品質 の向上 ラメータを必要 未知の としない新たな 問題・・・ 島数・移住 ＧＡを考案 パラメータ の増加 探索領域分割型ＧＡ-概要 設計変数間の依存関係に注目 移住率・島数のパラメータに 依 大きく影響していると考えられる 存 分散 関 依存有り そこで 係 依存関係を評価し、最適な 領域分割 評 依存無し パラメータ、アルゴリズムを 価 自動決定する 探索領域分割型ＧＡ-概要 染色体 設計変数１ 設計変数２ 分散ＧＡ 島１ 島２ 島３ 設計変数３ 各島はすべて の設計変数を 解く 通常は移住パ ラメータに従い 移住を行う 探索領域分割型ＧＡ-概要 設計変数１ 設計変数２ 染色体 領域分割ＧＡ 島１ 計算 終了後 島２ 島３ 設計変数３ 各島は対象と なる設計変数 のみを解く 移住は行わず 最後に解を集 める 探索領域分割型ＧＡ-依存関係の評価 依存関係評価 統計学を利用 独自の方法で代用 探索領域分割型ＧＡ-依存関係の無い問題 設計変数間に 依存関係が無い 各設計変数毎に 解を求め最後に 合わせれば良い Ｆ（ｘ，ｙ） の最小値を求める ｘ，ｙには依存関係が無いため Ｆ（ｘ，ｙ）＝ｇ（ｘ）+ｈ（ｙ） と分解できる 探索領域分割型ＧＡ-依存関係の無い問題 設計変数間に 依存関係が無い 各設計変数毎に 解を求め最後に 合わせれば良い Ｆ（ｘ，ｙ）＝ｇ（ｘ）+ｈ（ｙ） と分解できる ｇ（ｘ） と ｈ（ｙ） をそれぞれ最小化 ｇ（ｘ）：Ｆ（ｘ，ａ） ｈ（ｙ）：Ｆ（ａ，ｙ） 探索領域分割型ＧＡ-依存関係の無い問題 Ｆ（ｘ，ｙ，ｚ） ｘ ｙ ｚ 島１ 島２ 島３ ｘ ｙ ｚ Ｘ Ｙ 解を集める Ｚ 島 設計変 ＝ 数 数の数 Ｆ（Ｘ，Ｙ，Ｚ） ＝解 ＸＹＺ 探索領域分割型ＧＡ-依存関係のある問題 依存関係のある問題 Ｆ（ｘ，ｙ，ｚ） ｘ ｙ ｚ 島１ 島２ 島３ ｘ1ｙ1ｚ1 ｘ2ｙ2ｚ2 ｘ3ｙ3ｚ3 最適なものを選択 分散ＧＡ 島数＝ 設計変数の数 移住無し Ｆ（ｘ２，ｙ２，ｚ２） ＝解 ｘ２ｙ２ｚ３ 探索領域分割型ＧＡ-一部に依存関係がある問題 一部の設計変数間に 依存関係のある問題 依存関係のある 設計変数を塊に 依存関係のな い設計変数間 領域 分割 依存関係のあ る設計変数間 分散 ＧＡ ｘ1ｘ2+ｘ3ｘ4 ｘ1ｘ2 ｘ3ｘ4 ｘ1ｘ2 ｘ3ｘ4 ｘ1ｘ2 ｘ1ｘ2 ｘ3ｘ4 ｘ3ｘ4 数値実験 Rastrigin Schwefel 依存関係 無し Original 一部に有り Rosenbrock Griewank 依存関係 有り 数値実験 実験に用いたGA 探索領域分割型GA（DSAGA) 移住率［0.0,0.3,0.6］の分散GA （DGA-[0.0,0.3,0.6]) 実験に用いたその他のパラメータ 個体数600 島数10 突然変異率１/Ｌ エリート保存 交叉率0 移住間隔5 試行回数10 数値実験 依存関係無し（Ｒａｓｔｒｉｇｉｎ：Ｓｃｈｗｅｆｅ ｌ） 800 DSAGA 700 最 適 解 発 見 世 代 600 DGAMIG0.0 DGAMIG0.3 DGAMIG0.6 500 400 300 200 100 0 Rastrigin Schwefel 数値実験 依存関係一部にあり（Original） 適 合 度 0.45 0.4 0.35 0.3 0.25 0.2 0.15 0.1 0.05 0 DSAGA DGA-MIG0.0 DGA-MIG0.3 DGA-MIG0.6 Original 最 適 解 発 見 世 代 1000 900 800 700 600 500 400 300 200 100 0 Original 数値実験 依存関係有り（Rosenbrock： 1.2 Griewank） DSAGA 1 DGAMIG0.0 DGAMIG0.3 DGAMIG0.6 0.8 適 合 0.6 度 0.4 0.2 0 Rosenbrock Griewank 考察-移住パラメータ 未知の問題 移住率：0,0.3,0.6 ＤＧＡ 移住間隔：2,5,10 の７種パラメータ 最適なパラメータ設定が困難 設定のＤＧＡ ＤＳＡＧＡ ＤＳＡＧＡ 有効性を検証 考察-移住パラメータ DSAGAと移住パラメータを変えたＤＧＡ 解発見世代（Rast,Schw）・適合度を元にした性能 1.0 0.9 0.8 0.7 0.6 0.5 dsaga 移住無し 10-0.3 10-0.6 5-0.3 5-0.6 2-0.3 2-0.6 0.4 0.3 0.2 0.1 0.0 Rastrigin Schwefel Original Rosenbrock Griewank 考察-移住パラメータ DSAGAはGriewank以外の関数 において，もっとも良い結果 Griewankでも，他の関数・パラメータ に比べ，それなりに良好な結果 DGAにおける移住パラメータ増加 という欠点を補う事ができる 考察-設計変数，染色体長の増加 Rastrigin 15Bitｘ20設計変数 最 適 解 発 見 世 代 1000 900 800 700 600 500 400 300 200 100 0 DSAGA DGA 100bit 300bit 2.7倍 3.5倍 まとめ 移住率，島数のパラメータ 今後の課題 を無くす新たなＧＡを考案 統計学の応用 依存無し 性能を大幅に向上 中程度の依存関係 ＤＧＡの最適パラメータ 最適な島数 依存有り には劣る場合もあるが 良好な結果 依存関係を調査する独自の方法 Ｆ（ｘ，ｙ）＝ｘ+ｙ Ｆ（ｘ，-１） Ｆ（ｘ，0） Ｆ（ｘ，１） ｘ ｘ ｘ 依存関係を調査する独自の方法 Ｆ（ｘ，ｙ）＝ｘｙ Ｆ（ｘ，-１） ｘ Ｆ（ｘ，0） ｘ Ｆ（ｘ，１） ｘ 解発見世代・適合度を元にした性能 Rastrigin/Schwefel 1000世代ですべて解がでたため、 解が求まった世代を元に 1-Gen/1000 その他の関数 DSAGA以外では1000世代では解が 求まらなかったため、適合度を元に 1-Fitness
© Copyright 2024 ExpyDoc
