環境分散遺伝的アルゴリズムの 多目的最適化問題への適用 Multi-Objective Genetic Algorithms with Distributed Environment Scheme 同志社大学工学部 廣安知之 同志社大学工学部 三木光範 同志社大学大学院 ○ 上浦二郎 研究背景（GAを用いた多目的最適化） パレート的アプローチ Ranking. Goldberg(1989) Multi-Objective GA (MOGA). Fonseca (1993) Niched Pareto GA (NPGA). Horn, Nafploitis,Goldberg (1994) Non-dominated sorting GA (NSGA). Srinivas and Deb (1994) Strength Pareto Evolutionary Algorithms (SPEA). Zitzelr (1998) Distributed Range MOGA (DRMOGA). Hiroyasu (2000) 非パレート的アプローチ Vector Evaluated GA (VEGA). Schaffer (1985) VEGA+Pareto optimum individuals. Tamaki(1995) 単一目的化アプローチ Multi-Objective Genetic Local Search (MOGLS). Murata, Ishibuchi, Tanaka (2001) 単一目的化アプローチによる多目的最適化 重みパラメータによって多目的最適化を単一目的化 各目的関数に重みパラメータωを設定 重みと目的関数の加重和 → 単一の目的関数 重みの変化 → 複数のパレート解 単一目的化アプローチの並列化 評価を分散することによる並列化 セルラーモデルによる並列化（Murata,Ishibuchi,and Matsuo 2001） 島モデルによる並列化 分散遺伝的アルゴリズム 分散遺伝的アルゴリズム（分散GA） （Tanese 1989） GAの並列化モデル 母集団を複数のサブ母集団（島）に分割 → 島モデル 各島内で独立して遺伝的操作 移住（移住率，移住間隔） 母集団 各島で独立して遺伝的操作 母集団を複数の島に分割 移住 環境分散遺伝的アルゴリズム 環境分散遺伝的アルゴリズム（環境分散GA）（Miki 2000） 母集団を複数の島に分割 各島内で独立して遺伝的操作 島ごとに異なったパラメータを設定 母集団 パラメータ設定の煩雑性の緩和 移住 母集団の分割 島 島ごとに異なるパラメータを設定 提案手法 環境分散スキームを用いた多目的遺伝的アルゴリズム Multi-Objective Genetic Algorithms with Distributed Environment Scheme ( MOGADES ) 特徴 各島に異なった重みパラメータ（重み分散） 類似した重み付けを持つ島間で移住（近傍移住） 目的関数間のスケールの違いにより重みを変化（重み変 化） エリート個体とパレート解候補個体群を保存 （エリート＋パレート保存） MOGADESの流れ MOGADESの流れ ・初期個体の発生 ・各島に異なった重みを与えて 母集団を分割（重み分散） ・類似した重み付けを持つ 島間で移住（近傍移住） ・目的関数間のスケールの違い により重みを変化（重み変化） 分散 移住 MOGADESの流れ（続き：各島内） MOGADESの流れ 各島は単一目的の最適化 – 適合度値の高い個体（エリート）を保存 全体は多目的の最適化 – パレート解候補個体群を保存 保存したエリート個体，パレート解候補個体 群と交叉・突然変異によって生成された個体 群の 合計の個体群から次世代の個体群を選択 （エリート＋パレート保存） パレート解候補個体群 エリート個体（群） MOGADESの特徴 各島に異なった重みパラメータ（重み分散） 類似した重み付けを持つ島間で移住（近傍移住） 目的関数間のスケールの違いにより重みを変化（重み変化） エリート個体とパレート解候補個体群を保存（エリート＋パレート 保存） 重み分散 目的 一度の試行で広範囲に渡るパレート解を探索する 方法 2目的のとき → 任意の島数に関して均等に重み分散可能 ３目的以上 → 均等に重み分散可能な島数が限定される 例 ３目的のとき ４分割＝１０通り 5分割＝15通り 近傍移住 目的 類似性の高い島と移住を行うことによる効率的な探索 方法 ある目的関数について島をソートし，隣接する２島に移住 両端に位置する島からは隣接する1島に移住 ３目的以上 → 移住ごとにソートの基準となる目的関数を変化 例 ３目的，１０島のとき 重み変化 目的 スケールの大きい目的関数に探索が偏ることを防ぐ 方法 各目的関数に対する重みが１の島の最上位の個体がもつ 各関数値から目的関数のスケール比を求める スケール比を用いて各島の重みを変化 例 2目的，目的１(F1)が目的２(F2)の１００倍のスケールを持 つ A :F１の重みが１の島のエリート B :F2の重みが１の島のエリート | F2(A) – F2(B) | | F1(A) – F1(B) | ～ 1/100 ＝ γ＝ ωF1new ＝ γ・ω F1base ωF2new ＝ ωF2base エリート＋パレート保存 目的 局所探索と大域探索の効率化 方法 各島はそれぞれが独立したエリート個体とパレート解候補個体 群を 探索個体群とは別に保存 保存したエリート個体，パレート解候補個体群，交叉・突然変 異によって生成された個体群から次世代の個体群を選択 ・・・ パレート解候補個体群 島1 島2 島3 エリート個体（群） 有効性の検証 概要 4種類の数値実験により提案手法の特徴が有効であることを示 す 対象問題 多目的0/1Knapsack問題 – アイテムセットは E.Zitzler (1999)を使用 – ７５０items ２目的 – ７５０items ３目的 – ７５０items ２目的，Ｆ１を１００倍に評価 パラメータ 個体数：110（２目的），660（3目的） 島数：11（２目的），66（３目的）→ 重みは11分割 終了条件：解の評価が一定回数を越えた場合 実験１ 概要 重み分散を行うことによる探索への影響を調べる 全島の重みを同一に設定して複数回試行を行った場合と 重み分散して１回試行を行った場合の性能を比較する 対象問題 750items 2目的 パラメータ 全島の重みを同一に設定 個体数 ：110 島数 ：11 評価回数：100000 × 11試行 ＝ 1100000 重み分散 個体数 ：110 島数 ：11（重みは11分割） 評価計算：1100000×1試行 ＝ 1100000 実験１ 結果 重み分散は有効である 実験２ 概要 近傍移住を行うことによる解探索への影響を調べる 移住先をランダムに選ぶ場合と 近傍移住を行った場合の性能を比較する 対象問題 750items 3目的 パラメータ 移住先をランダムに選ぶ 個体数 ：660 島数 ：66（重みは11分割） 評価回数：1000000 近傍移住 個体数 ：660 島数 ：66（重みは１1分割） 評価計算：1000000 実験２ 結果 近傍移住は有効である 近傍移住（MOGADES） ランダム 実験３ 概要 重み変化を行うことによる解探索への影響を調べる 重みが変化しない場合と 移住時に重み変化を行う場合の性能を比較する 対象問題 750items 2目的 （Knapsack１の価値を100倍に評価） パラメータ 重みが変化しない場合 個体数 ：110 島数 ：11（重みは11分割） 評価回数：1100000 重み変化 個体数 ：110 島数 ：11（重みは11分割） 評価計算：1100000 実験３ 結果 重み変化は有効である 実験４ 概要 パレート解候補個体を保存することによる解探索への影響 を 調べる パレート解候補個体を保存しない場合と パレート解候補個体を保存する場合の性能を比較する 対象問題 750items 3目的 パラメータ パレート解候補個体を保存しない場合 個体数 ：660 島数 ：66 （重みは11分割） 評価回数：2000000 パレート解候補個体を保存する場合 個体数 ：660 島数 ：66 （重みは11分割） 評価計算：2000000 実験４ 結果 パレート解候補個体を保存することは有効である 保存する（MOGADES） 保存しない 結論 各島に異なった重み付けを行いパレート解の探索を行う MOGADESを提案した MOGADESの特徴が有効である 各島に異なった重みパラメータを与える 重み付けの類似する島との間で移住を行う 目的関数間のスケールの違いにより重みを変化させる パレート解候補個体を保存する MOGADESは多目的最適化問題の 解法として有効である
© Copyright 2024 ExpyDoc
