多目的最適化の進化的計算手法によるアプローチ

Presentation on theme: "多目的最適化の進化的計算手法によるアプローチ"— Presentation transcript:

1 多目的最適化の進化的計算手法によるアプローチ
同志社大学　工学部 廣安　知之 三木　光範 渡邉　真也

2 進化的計算手法による多目的最適化の拡がり
Evolutionary Multi-Criterion Optimization (EMO) GECCO 2001 San Francisco 2セッション 2002 New York IEEE　CEC 2001 Soul ２セッション 2002 Honolulu EMO’０１，０３

3 本セッション発表以外の代表的な手法の説明 得られた解の比較
目的 本セッション発表以外の代表的な手法の説明 得られた解の比較

4 ■多目的最適化とは → 完全な最適解が存在しない パレート最適解 → 他の任意の解と比較して 総合的に劣らない解 パレート最適解集合の探索
複数の評価基準（目的関数） 各評価基準との間にトレードオフの関係 →　完全な最適解が存在しない パレート最適解 →　他の任意の解と比較して 　 総合的に劣らない解 パレート最適解集合の探索 可能領域 弱パレート最適解 パレート最適解

5 ■パレートランキング 6 Goldberg, Fonsecaらが提案 解の優劣関係に基づいてランクを決定
個体xがn個の個体に優越されているときの個体xのランクrx　 1 3 6 3 6 1

6 ■シェアリング 探索個体の多様性維持し，パレート解集合を広く分布させる
個体の近傍の混み具合を示すニッチ数(niche count)を用いる． パラメータ：シェアリングレンジにより，シェアリング半径を決定 ニッチ数： シェアリング関数： σshare　=　シェアリング半径

7

8

9 ■ SPEA-II (2001) →　Eckart Zitzler Strength Pareto Evolutionary Algorithm-II SPEA-IIはランキング法に密集評価技術 シェアリングの方法としてクラスタリング手法 エリートアーカイブによるエリート保存戦略 sharing Ranking

10 ■ NSGA-II(2000) → Non-dominated Sorting Genetic Algorithm-II
　Kalyanmoy Deb(非優越ソートGA-II) 　　SrinivasらのNSGAをDebが改良 エリート保存戦略を導入 Goldbergのランキングソートの効率化 シェアリングに代わる混雑度の評価指標の導入 Ranking sharing

11 ■ エリートアーカイブ

12 ■ MSLC 特徴 局所的培養型マスタースレーブモデル 近傍交叉 パレート保存個体群の利用 局所的選択 解へ収束するための適切な淘汰圧
～Master-Slave model with Local Cultivation～ 多目的の特徴を備えたマスタースレーブ型並列アルゴリズム 特徴 近傍交叉 パレート保存個体群の利用 局所的選択 解へ収束するための適切な淘汰圧 On the other hand , As MSLC is one of the Master-Slave model , there are a few master processes and several slave processes. This model adopt the concept of Minimal Generation Gap model. This figure shows the concept of the MSLC. You can see, Master node and slave node repeatedly exchange two populations as sub populations each other. At first, in master process two individuals are chosen and are sent to a slave process. Secondly, slave process receives two individuals from master process and performs GA operators (cross over, mutation , evaluation and selection). After the selection, the selected two individuals are sent back to master process. After receiving two individuals from the slave process, master process substitute these individuals to old individuals. These operation is performed until all the individuals are sent and received . Therefore, One Loop is finished when all populations are exchanged to new ones. And the master process has pareto archive apart from search individuals. The reason is to prevent the lack of solutions that are looked on search.

13 ■ MSLC 近傍交叉 多目的では，対象とする目的関数空間が広く各個体ごとに探索している解領域が異なっている． f2(x)
近傍でない個体と交叉を行っても， 効果的な探索は期待できない．

14 ■ MSLC 近傍交叉 近傍同士のペアによる交叉 個体のソートを行う． f2(x)
ただし，毎世代ペアが異なるように何らかの仕組みを取り入れてやる必要がある． f1(x)

15 ■ MSLC パレート保存個体群の利用 多目的では，最終的に求める解候補 （パレート解）が複数存在するため，探索途中での優良な個体の欠落を防ぐ必要がある． 探索個体群に優良個体群を反映させることにより探索の高速化，効率化を期待することができる． 優良個体保存群 探索個体群 f2(x) f1(x)

16 ■ MSLC 2個体によるトーナメント選択を用いる（バイトーナメント）． 局所的選択 解へ収束するための適切な淘汰圧
・2個体ずつのペアを作成し，ペア間の優れている 個体を次世代に残す． ・個体のランク付け（適合度）は，全ての個体を用い て行う （比較集合を用いる一般的なトーナメント選 択ではない）．

17 ■ MSLC

18 ■ MSLC

19 ■誤差（精度） 得られた解集合と真のパレート解の差 評価対象： 精度 問題点： → パレート解集合と得られた解集合とのユークリッド距離の平均
→　パレート解集合と得られた解集合とのユークリッド距離の平均 評価対象：　精度 問題点： 真のパレート解が既知でなければ使用不可 精度がよい解が少数求まっている場合，その解集合を本当に良い解集合といえるかどうか．

20 ■被服率 各区間に得られた解が存在する割合 区間の分割： 評価対象： 多様性，解の幅広さ
パレート解の各目的関数おける最大値と 最小値の間を一定の数で分割する． 評価対象：　多様性，解の幅広さ →　1 に近づくほど，良い解集合 例）　 f1　→　6/8　=　0.75 f2　→　5/8　=　0.63 被覆率　=　0.69

21 ■パレート比較割合 ２手法で得られた解集合の精度を比較 評価対象： 精度
各種法で得られた解集合をすべて 合わせて再度ランキングし，再度 パレート解と評価された解の割合 評価対象：　精度 例）　 手法1　→　8/10 手法2　→　2/10 手法1　：　手法2　=　80　：　20 手法1 手法2 再評価後

22 ■解集合のカバーする面積 得られた解集合がカバーしていない面積の割合： S → 最小化 ナップサック問題：
パレート解集合のカバーする面積：　Spareto 得られた解集合がカバーする面積：　S ナップサック問題： パレート解集合が未知であるため，各ナップサックの 価値の総和を最大値として用いる

23 ZDT4(Zitzler, Deb,and Thiele 2000)
■対象問題 ZDT4(Zitzler, Deb,and Thiele 2000) 多峰性問題

24 ZDT6 (Zitzler,Deb,and Thiele 2000)
■対象問題2 ZDT6 (Zitzler,Deb,and Thiele 2000) 偏重パレート問題

25 ■対象問題3 KUR (Kursawe 1991) 多峰性問題

26 ナップザック問題 ■対象問題3 多目的化 0/1ナップザック問題 前提条件 重量と利益を持つ荷物のセット． ナップザックの任意の重量制限．
（Zitzler, and Thiele 1999） 0/1ナップザック問題 前提条件 重量と利益を持つ荷物のセット． ナップザックの任意の重量制限． 目的 限られた容量のなかで最大の利益を持つ 荷物の組み合わせを求める． 次に今回用いた適用問題である多目的ナップザック問題について説明します． 一般に，0/1ナップザック問題は，重量と利益を持つ荷物のセットから成り立っており，ナップザックには任意の重量制限がかけられています．その目的は，「限られた容量のなｋで最大の利益を持つ荷物の組み合わせを求める」ことです． この0/1ナップザック問題は，ナップザック数およびナップザックに付随する荷物のセットを複数化することにより容易に多目的化することができます． ナップザック数およびナップザック に付随する荷物のセットを複数化． 多目的化

27 ■対象問題3 多目的0/1ナップザック問題 目的関数 制約条件 多目的ナップザック問題はこのような式で定式されます．
目的関数におけるpは利益を表しており，xは0もしくは1をとるベクトル，設計変数値です．xが1であるならばその荷物は選択され，0であれば選択されていないことを意味します． 制約条件は，各荷物の総量が各ナップザックの許容重量以下であることを意味しています．

28 ■ ZDT4（多峰性のある連続テスト関数） （Zitzler, Deb, and Thiele 1999）

29 ■ZDT4（被服率）

30 ■ ZDT6（偏重パレート問題） （Zitzler, Deb, and Thiele 1999）

31 ■ZDT6 （被服率）

32 ■ KUR

33 ■KUR （被服率）

34 ■ KP750-2（多目的ナップザック問題） （Zitzler, and Thiele 1999）

35 ■ KP750-2（被服率）

36 ■ KP750-3（被服率）

37 ■ KP750-4（被服率）

38 ■誤差（精度） 得られた解集合と真のパレート解の差 評価対象： 精度 問題点： → パレート解集合と得られた解集合とのユークリッド距離の平均
→　パレート解集合と得られた解集合とのユークリッド距離の平均 評価対象：　精度 問題点： 真のパレート解が既知でなければ使用不可 精度がよい解が少数求まっている場合，その解集合を本当に良い解集合といえるかどうか．

39 ■被服率 各区間に得られた解が存在する割合 区間の分割： 評価対象： 多様性，解の幅広さ
パレート解の各目的関数おける最大値と 最小値の間を一定の数で分割する． 評価対象：　多様性，解の幅広さ →　1 に近づくほど，良い解集合 例）　 f1　→　6/8　=　0.75 f2　→　5/8　=　0.63 被覆率　=　0.69

40 ■パレート比較割合 ２手法で得られた解集合の精度を比較 評価対象： 精度
各種法で得られた解集合をすべて 合わせて再度ランキングし，再度 パレート解と評価された解の割合 評価対象：　精度 例）　 手法1　→　8/10 手法2　→　2/10 手法1　：　手法2　=　80　：　20 手法1 手法2 再評価後

41 ■解集合のカバーする面積 得られた解集合がカバーしていない面積の割合： S → 最小化 ナップサック問題：
パレート解集合のカバーする面積：　Spareto 得られた解集合がカバーする面積：　S ナップサック問題： パレート解集合が未知であるため，各ナップサックの 価値の総和を最大値として用いる

42 手法に対する新たなアイディア 表示方法 対象問題
終わりに 手法に対する新たなアイディア 表示方法 対象問題

43 ■ MOGADES →　Multi-Objective Genetic Algorithms with 　　　　　Distributed Environment Scheme ( MOGADES ) 　　環境分散スキームを用いた多目的遺伝的アルゴリズム 各島に異なった重みパラメータ（重み分散） 類似した重み付けを持つ島間で移住（近傍移住） 目的関数間のスケールの違いにより重みを変化（重み変化） エリート個体とパレート解候補個体群を保存 (エリート＋パレート保存）

44 ■ MOGADES