適応的重みを有する 多目的最適化のための分散遺伝的アルゴリズム 廣安 知之，○上浦 二郎，三木 光範，渡邉 真也 同志社大学 多目的最適化問題 互いに競合する複数の目的が存在する最適化問題 ・求めるべき解が複数存在する →ある目的を改善するために， 他の目的を改悪せざるを 得ない解 ・非劣解（集合） 探索の過程で得られたどの解にも 優越されない解（の集合） ・パレート最適解（集合） 定義された解空間のどの解にも 優越されない解（の集合） 2 同志社大学 遺伝的アルゴリズムを用いた多目的最適化 ・遺伝的アルゴリズム → 多点探索による最適化手法 → 求める解が複数存在する多目的最適化に適する → 多目的遺伝的アルゴリズム •MOGA : Fonseca (1993) •NPGA2 : Erickson, Mayer, Horn (2001) •SPEA2 : Zitzler (2001) •NSGA-II : Deb, Goel (2001) など多数 3 同志社大学 従来手法（SPEA2, NSGA-II）の探索のアプローチ ・パレート的アプローチ 解の優越関係をもとにした適合度の割り当て → すべての目的を同等に評価 → ある目的を重視した解を得にくい 4 同志社大学 よい多目的最適化手法とは 1．パレート解に近い非劣解を得る 2．多様な非劣解を得る 従来手法 (NSGA-II, SPEA2)は．．． ・高精度の非劣解を得るための複数のメカニズム → パレート解に近い非劣解を得ることができる ・パレート的アプローチ → ある目的を重視した非劣解を得にくい 多様かつ高精度の非劣解を得られる手法を提案 5 同志社大学 提案手法 : 重み適応型遺伝的アルゴリズム Adaptive Weighted Genetic Algorithm : AWGA 特徴 • 分割母集団モデル：複数のサブ母集団(島)からなる母集団 • 重み分散：各島に異なる重みベクトル • 近傍移住：重みベクトルの近い島間で個体交換 • 重み変化：重みベクトルの変化 6 同志社大学 提案手法(AWGA)の概要 分割母集団モデル 重み分散 近傍移住 重み変化 7 同志社大学 母集団分割モデル：分散遺伝的アルゴリズム ・複数のサブ母集団(島)によって母集団を構成 → 移住：島間の個体交換 → 各島に異なるパラメータ設定を行うことで， 各島に異なる特徴を与えることが可能（三木 ‘00） → 単目的最適化では性能が向上 多目的最適化では性能が悪化（廣安 ‘00） 8 同志社大学 重み分散 ・各島は異なる重みベクトル → 各島で単目的最適化，全体で多目的最適化 → 各島の探索範囲が限定→少ない個体数で探索可能 ・初期値として0.0から1.0までを 均等に割り当てる → 探索中に適応的に変化 例）2 目的, 5 島 9 同志社大学 重み変化 ・重みベクトルを探索中に変化させる → 探索が疎の部分を重点的に探索 → 各島の初期収束を抑制可能 重みベクトルと目的関数値を考慮して重みを変化 → 偏りなく分布する非劣解を得ることが可能 10 同志社大学 近傍移住 ・近い重みベクトルを持つ島間で個体を交換 → 非劣解が非劣解フロントの一部に偏ることを防ぐ 11 同志社大学 アーカイブの使用による非凸型フロントへの対応 ・重みでは非凸型のフロント上の非劣解を得ることはできない 凸型 非凸型 ・エリート保存戦略として，適合度の高い個体だけでなく 非劣解をもアーカイブに保持（非劣解アーカイブ） → 探索途中に得られた解は淘汰されない → 選択圧を下げる（トーナメントサイズを小さくする） とにより，非劣解が選ばれる可能性が高くする 12 こ 同志社大学 提案手法(AWGA)のまとめ 13 同志社大学 数値実験 ・様々なパレート最適フロントを持つ問題への適用 → 非凸を含む様々なパレート最適フロントにおいて 提案手法は非劣解を得ることができる ・他手法との性能比較 → 既存手法（NSGA-II）に対する提案手法の優位性 14 同志社大学 様々なパレート最適フロントを持つ問題への適用 • 対象問題 ZDT1-6 15 問題名 特徴 ZDT1 連続，凸型 ZDT2 連続，非凸型 ZDT3 非連続，凸型 ZDT4 連続，凸型，多峰性 ZDT5 非連続，凸型，だまし問題 ZDT6 連続，非凸，解空間に偏り 同志社大学 様々なパレート最適フロントを持つ問題への適用 ・個体数 50，島数 10，世代数 1000 ・30試行で得られたすべての非劣解集合 16 同志社大学 既存手法との比較 • 比較対象 NSGA-II • 対象問題 KUR, 750荷物3目的ナップサック問題 (KP750-3) • 比較方法 Ratio of Non-dominated Individuals of Two Sets RNI-2の例 手法１ 手法2 → 手法2 3/7 17 手法１ 4/7 同志社大学 既存手法との比較 (KUR) ・個体数 100，島数 10，世代数 1000，30試行 AWGA NSGA-II AWGA 70% NSGA-II 30% RNI-2 提案手法が非劣解の幅広さ，精度ともに優れている 18 同志社大学 既存手法との比較実験 (KP750-3) ・個体数 300，島数 30，評価数 1,000,000，30試行 AWGA NSGA-II NSGA-II 40% AWGA 60% RNI-2 提案手法が幅広さ，精度ともに勝る 19 同志社大学 発表のまとめ １：提案手法 • 重み適応型遺伝的アルゴリズム （Adaptive Weighted Genetic Algorithm） – 分割母集団モデル → 並列化可能 – 重み分散 – 重み変化 – 近傍移住 – アーカイブの利用 20 同志社大学 発表のまとめ ２：実験結果 • 様々なパレート最適フロントへの適用実験 – 非凸型パレート最適フロントにおいても探索可能 • 既存手法（NSGA-II）との比較実験 – 幅広さ，精度ともに，既存手法よりもよい解を得た 多様，高精度の非劣解を得る 重み適応型遺伝的アルゴリズムは有効 21 同志社大学 Fin. 22 同志社大学 適応変化（トーナメントサイズ） ・トーナメントサイズが移住の際に適応的に変化 → 非凸型の非劣解フロントを探索可能とするため ・例）島Bのトーナメントサイズの適応変化 Case 1 Case 2 重みが高いほど良い目的値 重みが機能している 重みが高くとも同じ目的値 重みが機能していない（非凸） トーナメントサイズを＋1 トーナメントサイズを－1 （最大トーナメントサイズは初期値） （最小トーナメントサイズは 1 ） 23 同志社大学 長い探索による非劣解集合の改善 • KP750-3 は提案手法が劣る – RNI-2は 精度の悪い幅の広い非劣解集合よりも 精度の良い幅の狭い非劣解集合を評価 4 / 14 10 / 14 長い探索による 非劣解集合の改善を検証する 解評価数 ↓ 解評価数 24 600,000 1,000,000 同志社大学 長い探索による非劣解集合の改善 (KP750-3) ・個体数 300，島数 30，評価数 1,000,000，30試行 長い探索を行うことにより精度の良い，幅広い非劣解集合を 得ることができる 25 同志社大学 提案手法(AWGA)の流れ １．個体群，重みベクトルの初期化 ２．複製選択 ・個体群，エリートアーカイブ，非劣解アーカイブから トーナメント選択により親個体を 2個体抽出 ３．近傍移住，適応変化 ・複製選択で抽出した個体を移住 ４．子個体生成 ・交叉，突然変異 ５．複製選択 ・親＋子個体群からランダムに2個体を選択し， 個体群の適合度の低い個体を置換 6．終了判定 ・終了しない場合は世代を+1して 2へ戻る 26 同志社大学 近傍移住 ・近い重みベクトルを持つ島間で個体を交換 ・重みベクトル、トーナメントサイズの適応変化 → 非劣解が非劣解フロントの一部に偏ることを防ぐ 手順１．重みベクトルの各要素を基準に近傍島を定義 wi i：目的 目的i ：島3の近傍島は島2と4 手順2．2つの近傍島から個体を受け取る 近傍島が1島の場合 その島から個体を受け取る 手順３．重みベクトル，トーナメントサイズの適応変化 27 同志社大学 アーカイブの利用 ・適合度の高い個体をアーカイブに保持（エリートアーカイブ） ・非劣解をアーカイブに保持（非劣解アーカイブ） → 探索の効率上昇 → 非凸型フロントへの対応 ※ アーカイブに格納可能な エリート，非劣解の数は パラメータ 28 同志社大学 重み変化 ・重みベクトルが移住の際に適応的に変化 → 非劣解が非劣解フロントの一部に偏ることを防ぐ → 各島の初期収束を抑制可能 → 探索効率の低下 i ・例）島Bの目的 の重み変化 島Ｂと島Aの重み差 > 島Bと島Cの重み差 → 島Bの重みを島Aに近づける 正規乱数により島Bの重みを更新 島A, Cは島Bの近傍島 29 平均：(島Bの重み)＋α(島A,Bの重み差) 標準偏差：β(島A,Bの重み差) 同志社大学
© Copyright 2024 ExpyDoc
