被服率 - 同志社大学 生命医科学部

多目的最適化の進化的計算手法
によるアプローチ
同志社大学 工学部
廣安 知之
三木 光範
渡邉 真也
進化的計算手法による多目的最適
化の拡がり
Evolutionary Multi-Criterion Optimization
(EMO)
•GECCO
•2001 San Francisco
•2002 New York
2セッション
•IEEE CEC
•2001 Soul
•2002 Honolulu
2セッション
•EMO’01,03
目的
•本セッション発表以外の代表的な手
法の説明
•得られた解の比較
■多目的最適化とは
• 複数の評価基準(目的関数)
• 各評価基準との間にトレードオフの関係
→ 完全な最適解が存在しない
パレート最適解
→ 他の任意の解と比較して
総合的に劣らない解
パレート最適解集合の探索
可能領域
弱パレート最適解
パレート最適解
■パレートランキング
• Goldberg, Fonsecaらが提案
• 解の優劣関係に基づいてランクを決定
• 個体xがn個の個体に優越されているときの個体xのランクrx
rx 1  nx
1
1
3
6
1
1
3
6
3
1
1
3
1
1
1
1
■シェアリング
• 探索個体の多様性維持し,パレート解集合を広く分布させる
• 個体の近傍の混み具合を示すニッチ数(niche count)を用いる.
• パラメータ:シェアリングレンジにより,シェアリング半径を決定
N
mx   s(d ( xi , x j ))
ニッチ数:
j 1
d
s(d )  max{0,1 
}
シェアリング関数:
i
 share
σshare = シェアリング半径
■ SPEA-II (2001)
→ Eckart Zitzler Strength Pareto Evolutionary Algorithm-II
• SPEA-IIはランキング法に密集評価技術
• シェアリングの方法としてクラスタリング手法
• エリートアーカイブによるエリート保存戦略
Ranking
sharing
■ NSGA-II(2000)
→
Non-dominated Sorting Genetic Algorithm-II
Kalyanmoy Deb(非優越ソートGA-II)
SrinivasらのNSGAをDebが改良
• エリート保存戦略を導入
• Goldbergのランキングソートの効率化
• シェアリングに代わる混雑度の評価指標の導入
Ranking
sharing
■ エリートアーカイブ
■ MSLC
• 局所的培養型マスタースレーブモデル
~Master-Slave model with Local Cultivation~
多目的の特徴を備えたマスタースレーブ型並列アルゴリズム
特徴
•
•
•
•
近傍交叉
パレート保存個体群の利用
局所的選択
解へ収束するための適切な淘汰圧
f2(x)
■ MSLC
• 近傍交叉
– 多目的では,対象とする目的関数空間が広く
各個体ごとに探索している解領域が異なって
いる.
近傍でない個体と交叉を行っても,
効果的な探索は期待できない.
f1(x)
■ MSLC
• 近傍交叉
f2(x)
• 近傍同士のペアによる交叉
– 個体のソートを行う.
ただし,毎世代ペアが異なる
ように何らかの仕組みを取り
入れてやる必要がある.
f1(x)
f2(x)
■ MSLC
• パレート保存個体群の利用
– 多目的では,最終的に求める解候補 (パレー
ト解)が複数存在するため,探索途中での優
良な個体の欠落を防ぐ必要がある.
探索個体群に優
優良個体保存群
探索個体群
良個体群を反映
させることにより
探索の高速化,
効率化を期待す
ることができる.
f1(x)
■ MSLC
• 局所的選択
• 解へ収束するための適切な淘汰圧
– 2個体によるトーナメント選択を用いる(バ
イトーナメント).
・2個体ずつのペアを作成し,ペア間の優れている
個体を次世代に残す.
・個体のランク付け(適合度)は,全ての個体を用い
て行う (比較集合を用いる一般的なトーナメント選
択ではない).
■ MSLC
■ MSLC
■誤差(精度)
得られた解集合と真のパレート解の差
→ パレート解集合と得られた解集合とのユークリッド距離の平均
評価対象: 精度
問題点:
• 真のパレート解が既知でなければ使用不可
• 精度がよい解が少数求まっている場合,その解集合を本当に良
い解集合といえるかどうか.
■被服率
各区間に得られた解が存在する割合
区間の分割:
パレート解の各目的関数おける最大値と
最小値の間を一定の数で分割する.
評価対象: 多様性,解の幅広さ
→ 1 に近づくほど,良い解集合
例)
f1 → 6/8 = 0.75
f2 → 5/8 = 0.63
被覆率 = 0.69
■パレート比較割合
2手法で得られた解集合の精度を比較
各種法で得られた解集合をすべて
合わせて再度ランキングし,再度
パレート解と評価された解の割合
手法1
手法2
評価対象: 精度
再評価後
例)
手法1 → 8/10
手法2 → 2/10
手法1 : 手法2 = 80 : 20
■解集合のカバーする面積
• 得られた解集合がカバーしていない面積の割合: S
→ 最小化
パレート解集合のカバーする面積: Spareto
得られた解集合がカバーする面積: S
S

S  1
i
S pareto
Si  f 2 ( xi )  ( f1 ( xi 1 )  f1 ( xi ))
ナップサック問題:
パレート解集合が未知であるため,各ナップサックの
価値の総和を最大値として用いる
■対象問題
ZDT4(Zitzler, Deb,and Thiele 2000)
多峰性問題
■対象問題2
ZDT6 (Zitzler,Deb,and Thiele 2000)
偏重パレート問題
■対象問題3
KUR (Kursawe 1991)
多峰性問題
ナップザック問題
■対象問題3
(Zitzler, and Thiele 1999)
• 0/1ナップザック問題
前提条件
重量と利益を持つ荷物のセット.
ナップザックの任意の重量制限.
目的
限られた容量のなかで最大の利益を持つ
荷物の組み合わせを求める.
多目的化
ナップザック数およびナップザック
に付随する荷物のセットを複数化.
■対象問題3
• 多目的0/1ナップザック問題
目的関数
m
f i ( x )   pi , j  x j
制約条件
j 1
m
 1,2,, n :  wi , j  x j  ci
j 1
x  ( x1, x2 ,, xm )  0,1m
pi , j  ナップザック iの荷物jにおける利益
wi , j  ナップザック iの荷物jにおける重量
ci  ナップザック iの許容重量
■ ZDT4(多峰性のある連続テスト関数)
(Zitzler, Deb, and Thiele 1999)
■ZDT4(被服率)
■ ZDT6(偏重パレート問題)
(Zitzler, Deb, and Thiele 1999)
■ZDT6 (被服率)
■ KUR
■KUR (被服率)
■ KP750-2(多目的ナップザック問題)
(Zitzler, and Thiele 1999)
■ KP750-2(被服率)
■ KP750-3(被服率)
■ KP750-4(被服率)
■誤差(精度)
得られた解集合と真のパレート解の差
→ パレート解集合と得られた解集合とのユークリッド距離の平均
評価対象: 精度
問題点:
• 真のパレート解が既知でなければ使用不可
• 精度がよい解が少数求まっている場合,その解集合を本当に良
い解集合といえるかどうか.
■被服率
各区間に得られた解が存在する割合
区間の分割:
パレート解の各目的関数おける最大値と
最小値の間を一定の数で分割する.
評価対象: 多様性,解の幅広さ
→ 1 に近づくほど,良い解集合
例)
f1 → 6/8 = 0.75
f2 → 5/8 = 0.63
被覆率 = 0.69
■パレート比較割合
2手法で得られた解集合の精度を比較
各種法で得られた解集合をすべて
合わせて再度ランキングし,再度
パレート解と評価された解の割合
手法1
手法2
評価対象: 精度
再評価後
例)
手法1 → 8/10
手法2 → 2/10
手法1 : 手法2 = 80 : 20
■解集合のカバーする面積
• 得られた解集合がカバーしていない面積の割合: S
→ 最小化
パレート解集合のカバーする面積: Spareto
得られた解集合がカバーする面積: S
S

S  1
i
S pareto
Si  f 2 ( xi )  ( f1 ( xi 1 )  f1 ( xi ))
ナップサック問題:
パレート解集合が未知であるため,各ナップサックの
価値の総和を最大値として用いる
終わりに
•手法に対する新たなアイディア
•表示方法
•対象問題
■ MOGADES
→




Multi-Objective Genetic Algorithms with
Distributed Environment Scheme ( MOGADES )
環境分散スキームを用いた多目的遺伝的アルゴリズム
各島に異なった重みパラメータ(重み分散)
類似した重み付けを持つ島間で移住(近傍移住)
目的関数間のスケールの違いにより重みを変化(重み変
化)
エリート個体とパレート解候補個体群を保存
(エリート+パレート保存)
■ MOGADES