EMO分野における最近の動向 立命館大学 情報理工学部 知能情報学科 渡邉 真也

Presentation on theme: "EMO分野における最近の動向 立命館大学 情報理工学部 知能情報学科 渡邉 真也"— Presentation transcript:

1 EMO分野における最近の動向 立命館大学 情報理工学部 知能情報学科 渡邉 真也
Computational intelligence Lab. 立命館大学 情報理工学部 知能情報学科 渡邉 真也

2 発表の流れ 進化的多目的最適化 (Evolutionary Multi-criterion Optimization: EMO）の概略
進化的手法を利用した手法 アルゴリズム以外の話題について テスト問題，評価手法，応用事例など 最近のトレンド データマイニング関連への応用 パレート支配の概念に関する応用 ε-dominance, local-dominance，α-domination等 単一目的の多目的化 GA，ES，ACO以外の手法を用いたEMO手法

3 多目的最適化問題 多目的最適化 複数の評価基準に基づいて最適化を行う 例） 大阪から東京へ向かう 場合の最適な交通手段
(Multi-objective Optimization Problem: MOP) 複数の評価基準に基づいて最適化を行う 例） 大阪から東京へ向かう 場合の最適な交通手段 時間 運賃 パレート最適 フロント パレート最適解 劣解

4 多目的最適化問題 多目的における最適性とは 多目的最適化 優越（domination） 1：優越されていない → パレート最適解
1：優越されていない → パレート最適解 （自動車は，どの解にも優越されていない） 2：優越されている → 劣解 （電車は，自動車に優越されている） 時間 運賃 パレート最適 フロント パレート最適解 劣解 多目的最適化 パレート最適解集合，もしくはパレート最適解の少なくとも1つを探索すること

5 進化的多目的最適化手法 （EMO） 進化的手法を多目的へ応用 Evolutionary Multi-objective Optimization（EMO） (Multi-Objective Evolutionary Algorithms: MOEAs) 遺伝的アルゴリズム（Genetic Algorithm: GA） 進化戦略（Evolutionary Strategy: ES） アントコロニー（Ant Colony Optimization： ACO） シミュレーテッドアニーリング（Simulated Annealing: SA） 従来の数理的手法（単一目的化する手法）と比較したメリット 問題に対する予備知識が不要． 離散的な問題に対しても適用可能． 一度の探索で複数のパレート最適解を探索可能．

6 多目的最適化問題の解について 多目的最適化問題の解に求められる性質 パレート最適解への近さ（精度）
パレート最適フロントに対する幅広さ，均一度合い より広く，かつ均一に得られているのが理想 非劣解 : 探索により得られた劣っていない解 パレート最適解 : 真の解 f1(x) f2(x) パレート最適フロント f1(x) f2(x) パレート最適フロント f2(x) パレート最適フロント f1(x)

7 EMOにおける代表的な手法（1980～1997） VEGA：Schaffer (1985) MOGA：Fonseca (1993)
最も初期のMOEAｓ． MOGA：Fonseca (1993) NSGA：N. Srinivas, K.Deb (1994) NPGA：J.Hornら他 (1994) 各目的の中間に位置する バランスのとれた解が得られない 世代 t 世代 t+1 部分個体群１ （目的１を基準に選択） 選択 遺伝的操作 母集団 Pｔ 母集団 Pｔ+1 部分個体群n （目的nを基準に選択） パレートランクに基づく選択 パレートフロント全体を得ることができる．

8 EMOにおける代表的な手法（1998～現在） エリート保存（パレートアーカイブ）を利用した手法 SPEA ： E.Zitzler（1998）
SPEA2 ： E. Zitzler, M. Laumanns (2001) PAES : J.D.Knowles and D.W.Corne(2000) NSGA-II： Deb, Goel (2001) 解の損失機会が大幅に減少し， EMOアルゴリズムの性能が大きく向上 アルゴリズムの流れ Step1: 初期個体生成 Step2:探索個体群の選択 （メイティング選択） Step3:探索個体群 の遺伝的操作を行う Step4:アーカイブ個体群の更新 （環境選択） アーカイブ個体群 探索個体群 ＋

9 EMOにおけるテスト問題について（１） アルゴリズムの性能を評価するために様々なテスト問題が考案されている． 連続関数
アルゴリズムの性能を評価するために様々なテスト問題が考案されている． 連続関数 ZDTシリーズ（K. Deb 1999） 変数の数を自由に設定できる． KUR（Kursawe 1991） CTPシリーズ（Debら 2001） ， 制約を付きの問題． DTLZシリーズ（Deb. Kら 2001） ， 目的関数の数も自由に設定できる ZDT3

10 EMOにおけるテスト問題について（２） 離散的な問題 多目的0/1ナップザック問題（Zitlerら 1998） 目的関数 制約条件
pi,j = ナップザック i に付随するアイテムjの利益 wi,j =ナップザック i に付随するアイテムjの重量 ci,= ナップザック i の容量 その他，ジョブショップスケジューリング問題，輸送問題など

11 解の評価方法 得られた非劣解する評価方法 ２つの観点から評価を行う 多様性（幅広く，かつまんべんなく解が得られているか）
精度（どれだけ真のパレート解に近いか） 得られた解集合そのものだけを用いて評価（unary） 2つ解集合を相対的に評価（binary） Sampling of the Pareto frontier Lines of Intersection (ILI) (Knowles and Corne 2000) = 5/12=0.42 = 7/12=0.58 得られた非劣解集合から到達フロント(点線ライン)を形成する． 等間隔に引かれたサンプリング線と到達フロントの交点を求め，比較する． 全ての交点における比較を行い，優越の割合を決定する．

12 最近のトレンドについて データマイニング関連への応用 パレート支配の概念に関する応用 単一目的問題に対する多目的化
多目的クラスタリング（MOCK）の紹介 パレート支配の概念に関する応用 ε-dominance，α-domination, local-dominance 単一目的問題に対する多目的化 1つの目的を分解する方法，目的を追加する方法など GA，ES，ACO以外の手法を用いたEMO手法 Particle Swarm Optimization（PSO）を用いたMOEAs

13 多目的クラスタリング（MOCK） クラスタ間においてデータの密度が大きく異なっている場合でもクラスタリングできる． 多目的クラスタリング(Multiobjective clustering with automatic k-determination: MOCK） （Handl and Knowles，2005） クラスタのコンパクト性に関する評価関数 クラスタの中心と各点との偏差を利用 データ点の連結性性に関する評価関数 近傍データ同士がどの程度同じクラスタグループに属しているかを測定 2つの異なる評価関数を使用 事前にクラスタ数を指定することなく 良質なクラスタリング結果を得ることができる．

14 パレート支配に関する概念の応用（１） 3目的以上の目的関数の多い場合の問題点 MOEAsの探索が進まない
パレート解の次元数が大きくなり，探索個体に劣解が生まれにくくなる． MOEAsの探索が進まない パレート支配の領域を広げる ε-dominance （Laumannsら，2002） α-domination （Ikedaら， 2001） local-dominance（Satoら， 2004） ある目的のみ僅かに優越しているためパレートとなっているような個体（弱パレートに近い個体）を削除

15 ε-dominance 支配領域をε分 だけ増加させる．

16 α-domination パラメータα（0≦α＜1）によって解の優越領域が変化 定義 解xが解yをα-dominateする 優越領域
2目的最小化

17 local-dominance Step1: 目的関数空間でのベクトルからサブ母集団を生成 Step2:
サブ母集団の中心軸がπ/4 になるように回転させ，その状態でパレート支配の関係をチェックする．

18 単一目的問題に対する多目的化 元の問題を複数の部分問題に分解する方法 元の目的に新たな目的を追加する方法
問題を複数の部分問題に分割し，それらの部分問題を解くことにより元の問題の解を得る方法（Knowles et al. 2001） 元の目的に新たな目的を追加する方法 問題の制約条件を目的関数化する方法 （Coello et al. 2000) 元の目的における制約を緩和したものをもう一つの目的として評価する方法 （渡邉 ら，2005） 元の目的にノイズを加えた目的を2つめの目的として用いる方法（渡邉 ら，2005） EMOではトレードオフ領域に探索が集中するため，制約境界付近を効率よく探索することができる．

19 Particle Swarm Optimization（PSO）を用いたMOEAs
Particle Swarm Optimization(PSO,J.Kennedy, 1995） 連続関数を対象とした多点探索手法 「位置」と「速度」を用いて探索を行う．最良解の位置を利用して探索方向を決定する．収束性が強く，局所解探索に有効． 多目的へのPSOの利用 MOPSO（multi objective particle swarm optimization） （Coelloら，2004） 高い収束性を活かして，効率よくパレート平面を探索 その他，興味深いのEAsのEMOへの適用としては， Differential Evolution(DEoptim: Differential Evolution Optimization （連続関数のための最適化手法）など

20 MOPSO ハイパーキューブ Step1 ：母集団を初期化する. Step2 ：各個体の速度を0に初期化する.
Step6 ：各個体のp-bestを初期化する. Step7 ：以下の操作を最大探索回数まで繰り返す. 速度の更新 位置の更新 PSOでは個体群の最良解 の代わりに アーカイブ個体の情報を利用する．

21 出版数（論文，プロシーリングなど） Carlos A. Coello Coello，Evolutionay Multi-Objective Optimization: A Historical View of the Field, IEEE Computational Intelligence Magazine Feb Vol.1 Num.1 pp.28-36より

22 おわりに EMO分野は，2003年をピークにやや停滞している感がある． 今後の興味深いTopicとしては
近似関数（応答局面，NN）を用いた高負荷の問題に対する適用． パレート領域における局所性を利用した探索効率の向上 データ識別やデータマイニング分野での応用 MOEAsの実装に関する問題. MOEAｓを実装するためのツールの開発など 得られたパレート解集合からの解選考に関する研究