PowerPoint プレゼンテーション

適応的重みを有する
多目的最適化のための分散遺伝的アルゴリズム
廣安 知之,○上浦 二郎,三木 光範,渡邉 真也
同志社大学
多目的最適化問題
互いに競合する複数の目的が存在する最適化問題
・求めるべき解が複数存在する
→ある目的を改善するために,
他の目的を改悪せざるを
得ない解
・非劣解(集合)
探索の過程で得られたどの解にも
優越されない解(の集合)
・パレート最適解(集合)
定義された解空間のどの解にも
優越されない解(の集合)
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の例
手法1
手法2
→
手法2
3/7
17
手法1
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
同志社大学
発表のまとめ 1:提案手法
• 重み適応型遺伝的アルゴリズム
(Adaptive Weighted Genetic Algorithm)
– 分割母集団モデル → 並列化可能
– 重み分散
– 重み変化
– 近傍移住
– アーカイブの利用
20
同志社大学
発表のまとめ 2:実験結果
• 様々なパレート最適フロントへの適用実験
– 非凸型パレート最適フロントにおいても探索可能
• 既存手法(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)の流れ
1.個体群,重みベクトルの初期化
2.複製選択
・個体群,エリートアーカイブ,非劣解アーカイブから
トーナメント選択により親個体を 2個体抽出
3.近傍移住,適応変化
・複製選択で抽出した個体を移住
4.子個体生成
・交叉,突然変異
5.複製選択
・親+子個体群からランダムに2個体を選択し,
個体群の適合度の低い個体を置換
6.終了判定
・終了しない場合は世代を+1して 2へ戻る
26
同志社大学
近傍移住
・近い重みベクトルを持つ島間で個体を交換
・重みベクトル、トーナメントサイズの適応変化
→ 非劣解が非劣解フロントの一部に偏ることを防ぐ
手順1.重みベクトルの各要素を基準に近傍島を定義
wi
i:目的
目的i :島3の近傍島は島2と4
手順2.2つの近傍島から個体を受け取る
近傍島が1島の場合
その島から個体を受け取る
手順3.重みベクトル,トーナメントサイズの適応変化
27
同志社大学
アーカイブの利用
・適合度の高い個体をアーカイブに保持(エリートアーカイブ)
・非劣解をアーカイブに保持(非劣解アーカイブ)
→ 探索の効率上昇
→ 非凸型フロントへの対応
※
アーカイブに格納可能な
エリート,非劣解の数は
パラメータ
28
同志社大学
重み変化
・重みベクトルが移住の際に適応的に変化
→ 非劣解が非劣解フロントの一部に偏ることを防ぐ
→ 各島の初期収束を抑制可能
→ 探索効率の低下
i
・例)島Bの目的 の重み変化
島Bと島Aの重み差 > 島Bと島Cの重み差
→ 島Bの重みを島Aに近づける
正規乱数により島Bの重みを更新
島A, Cは島Bの近傍島
29
平均:(島Bの重み)+α(島A,Bの重み差)
標準偏差:β(島A,Bの重み差)
同志社大学