EMO分野における最近の動向 Computational intelligence Lab. 立命館大学情報理工学部知能情報学科渡邉真也発表の流れ • 進化的多目的最適化 (Evolutionary Multi-criterion Optimization: EMO）の概略 – 多目的最適化 – 進化的手法を利用した手法 – アルゴリズム以外の話題について • テスト問題，評価手法，応用事例など • 最近のトレンド – データマイニング関連への応用 – パレート支配の概念に関する応用 • ε-dominance, local-dominance，α-domination等 – 単一目的の多目的化 – GA，ES，ACO以外の手法を用いたEMO手法多目的最適化問題多目的最適化 (Multi-objective Optimization Problem: MOP) 複数の評価基準に基づいて最適化を行う例）大阪から東京へ向かう場合の最適な交通手段運賃パレート最適解劣解パレート最適フロント時間多目的最適化問題多目的における最適性とは優越（domination） 1：優越されていない → パレート最適解（自動車は，どの解にも優越されていない） 2：優越されている → 劣解（電車は，自動車に優越されている）運賃パレート最適解劣解多目的最適化パレート最適フロント時間パレート最適解集合，もしくはパレート最適解の少なくとも1つを探索すること進化的多目的最適化手法（EMO） • 進化的手法を多目的へ応用 Evolutionary Multi-objective Optimization （EMO） (Multi-Objective Evolutionary Algorithms: MOEAs) – 遺伝的アルゴリズム（Genetic Algorithm: GA） – 進化戦略（Evolutionary Strategy: ES） – アントコロニー（Ant Colony Optimization： ACO） – シミュレーテッドアニーリング（Simulated Annealing: SA）従来の数理的手法（単一目的化する手法）と比較したメリット問題に対する予備知識が不要．離散的な問題に対しても適用可能．一度の探索で複数のパレート最適解を探索可能．多目的最適化問題の解について多目的最適化問題の解に求められる性質 1. パレート最適解への近さ（精度） 2. パレート最適フロントに対する幅広さ，均一度合い - より広く，かつ均一に得られているのが理想 f2(x) f22(x) 非劣解 : 探索により得られた劣っていない解パレート最適解 : 真の解パレート最適フロント f1(x) パレート最適フロント f1(x) EMOにおける代表的な手法（1980～1997） • VEGA：Schaffer (1985) – 最も初期のMOEAｓ．世代 t 選択各目的の中間に位置するバランスのとれた解が得られない部分個体群１（目的１を基準に選択）遺伝的操作母集団 Pｔ世代 t+1 母集団 Pｔ+1 部分個体群n （目的nを基準に選択）パレートランクに基づく選択 • MOGA：Fonseca (1993) • NSGA：N. Srinivas, K.Deb (1994) • NPGA：J.Hornら他 (1994) パレートフロント全体を得ることができる． 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:アーカイブ個体群の更新（環境選択）探索個体群＋ EMOにおけるテスト問題について（１） • アルゴリズムの性能を評価するために様々なテスト問題が考案されている．連続関数 – ZDTシリーズ（K. Deb 1999）変数の数を自由に設定できる． ZDT3 min f1 ( x)  x1 min f 2 ( x)  g ( x)  h( f1 , g )  g ( x) 1  10 100 i 2 ( xi ) 99   f  0.25 f  h( f1 , g )  1   1   1 sin(10f1 )   g  g   s.t. xi  [0,1], i  1,,100 – KUR（Kursawe 1991） – CTPシリーズ（Debら 2001），制約を付きの問題． – DTLZシリーズ（Deb. Kら 2001），目的関数の数も自由に設定できる EMOにおけるテスト問題について（２）離散的な問題多目的0/1ナップザック問題（Zitlerら 1998）目的関数荷物の数 fi ( x)   pi , j  x j i 1,2 j 1 制約条件荷物の数 w j 1 x  ( x1, x2 ,, x750 ) i, j  x j  ci x j  0,1 pi,j = ナップザック i に付随するアイテムjの利益 wi,j =ナップザック i に付随するアイテムjの重量 ci,= ナップザック i の容量その他，ジョブショップスケジューリング問題，輸送問題など解の評価方法 • 得られた非劣解する評価方法２つの観点から評価を行う多様性（幅広く，かつまんべんなく解が得られているか）精度（どれだけ真のパレート解に近いか）得られた解集合そのものだけを用いて評価（unary） 2つ解集合を相対的に評価（binary） Sampling of the Pareto frontier Lines of Intersection (ILI) (Knowles and Corne 2000) = 5/12=0.42 = 7/12=0.58 • • • 得られた非劣解集合から到達フロント(点線ライン)を形成する．等間隔に引かれたサンプリング線と到達フロントの交点を求め，比較する．全ての交点における比較を行い，優越の割合を決定する．最近のトレンドについて • データマイニング関連への応用 – 多目的クラスタリング（MOCK）の紹介 • パレート支配の概念に関する応用 – ε-dominance，α-domination, local-dominance • 単一目的問題に対する多目的化 – 1つの目的を分解する方法，目的を追加する方法など • GA，ES，ACO以外の手法を用いたEMO手法 – Particle Swarm Optimization（PSO）を用いたMOEAs 多目的クラスタリング（MOCK） • 多目的クラスタリング(Multiobjective clustering with automatic k-determination: MOCK）（Handl and Knowles， 2つの異なる評価関数を使用 2005）クラスタのコンパクト性に関する評価関数 – クラスタの中心と各点との偏差を利用データ点の連結性性に関する評価関数 – 近傍データ同士がどの程度同じクラスタグループに属しているかを測定クラスタ間においてデータの密度が大きく異なっている場合でもクラスタリングできる．事前にクラスタ数を指定することなく良質なクラスタリング結果を得ることができる．パレート支配に関する概念の応用（１） • 3目的以上の目的関数の多い場合の問題点 – パレート解の次元数が大きくなり，探索個体に劣解が生まれにくくなる． MOEAsの探索が進まないパレート支配の領域を広げる • ε-dominance （Laumannsら，2002） • α-domination （Ikedaら， 2001） • local-dominance（Satoら， 2004）ある目的のみ僅かに優越しているためパレートとなっているような個体（弱パレートに近い個体）を削除 ε-dominance 支配領域をε分だけ増加させる． α-domination パラメータα（0≦α＜1）によって解の優越領域が変化定義優越領域優越領域解xが解yをα-dominateする y 2目的最小化 local-dominance Step1: 目的関数空間でのベクトルからサブ母集団を生成 Step2: サブ母集団の中心軸がπ/4 になるように回転させ，その状態でパレート支配の関係をチェックする．単一目的問題に対する多目的化 • 元の問題を複数の部分問題に分解する方法 – 問題を複数の部分問題に分割し，それらの部分問題を解くことにより元の問題の解を得る方法（Knowles et al. 2001） • 元の目的に新たな目的を追加する方法 – 問題の制約条件を目的関数化する方法 EMOではトレードオフ（Coello et al.領域に探索が集中する 2000) ため，制約境界付近を – 元の目的における制約を緩和したものをもう一つ効率よく探索することの目的として評価する方法（渡邉ら，2005）ができる． – 元の目的にノイズを加えた目的を2つめの目的として用いる方法（渡邉ら，2005） 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 （連続関数のための最適化手法）など MOPSO • • • • • ハイパーキューブ Step1 ：母集団を初期化する. Step2 ：各個体の速度を0に初期化する. Step3 ：各個体を評価する. Step4 ：非劣解をアーカイブに保存 Step5 ：ハイパーキューブの更新を行う. ハイパーキューブは均一なアーカイブを実現するためのメカニズムである． • Step6 ：各個体のp-bestを初期化する. • Step7 ：以下の操作を最大探索回数まで繰り返す.  w vt  R1  (Pi best  Pi now )  R2  ( Aref  Pi now ) i i 位置の更新 P t 1  P t  vt PSOでは個体群の最良解 Gbestの代わりに速度の更新 vt 1 アーカイブ個体の情報を利用する．出版数（論文，プロシーリングなど） Carlos A. Coello Coello，Evolutionay Multi-Objective Optimization: A Historical View of the Field, IEEE Computational Intelligence Magazine Feb. 2006 Vol.1 Num.1 pp.28-36よりおわりに • EMO分野は，2003年をピークにやや停滞している感がある．今後の興味深いTopicとしては • 近似関数（応答局面，NN）を用いた高負荷の問題に対する適用． • パレート領域における局所性を利用した探索効率の向上 • データ識別やデータマイニング分野での応用 • MOEAsの実装に関する問題. MOEAｓを実装するためのツールの開発など • 得られたパレート解集合からの解選考に関する研究