多目的遺伝的アルゴリズムの紹介と適用事例 Computational intelligence Lab. 立命館大学情報理工学部知能情報学科渡邉真也本発表の流れ 1. 多目的遺伝的アルゴリズム - 多目的最適化問題多目的遺伝的アルゴリズム 2. 多目的遺伝的アルゴリズムの実問題への適用 - ディーゼルエンジン噴射スケジュール問題矩形ブロック配置問題 3. 解選考支援システムの検討 4. 結論多目的最適化問題多目的最適化複数の評価基準に基づいて最適化を行う例）大阪から東京へ向かう場合の最適な交通手段運賃パレート最適解劣解パレート最適フロント時間多目的最適化問題多目的における最適性とは優越（domination） 1：優越されていない → パレート最適解（自動車は，どの解にも優越されていない） 2：優越されている → 劣解（電車は，自動車に優越されている）運賃パレート最適解劣解多目的最適化パレート最適フロント時間パレート最適解集合，もしくはパレート最適解の少なくとも1つを探索すること進化的多目的最適化手法（EMO） • EMO Evolutionary Multi-objective Optimization EMOにおける代表的手法 •VEGA Schaffer (1985) •MOGA Fonseca (1993) •NSGA N. Srinivas, K.Deb (1994) •MOGLS H.Ishibuchi, T.Murata (1998) •SPEA2 E. Zitzler, M. Laumanns (2001) •NPGA2 Erickson, Mayer, Horn (2001) •NSGA-II Deb, Goel (2001) 遺伝的アルゴリズム遺伝的アルゴリズム（Genetic Algorithms: GAs）自然界における生物の進化を模倣した確率的最適化手法交叉母集団突然変異選択個体個体同士の組み合わせ個体間の情報交換個体情報の変更母集団内の多様性の維持環境に適合した個体をより多く残す遺伝的アルゴリズム • GAの特徴利点 • • • • ほぼ全ての最適化問題に適用可能（汎用性）コーディングが比較的容易一般的に良質な解が得られる多点探索である - 大域的探索を行うことができる - 複数の解候補を探索することができる短所 • 計算コストが高い • 最適解の保証が無い（ヒューリスティック） • 設定パラメータが多い多目的遺伝的アルゴリズム・多目的GA 交叉・突然変異を用いてパレート最適解集合の探索を行う世代 1 一度の探索により複数のパレート最適解を探索可能世代 10 世代 3 多目的最適化問題の解について多目的最適化問題の解に求められる性質 1. パレート最適解への近さ（精度） 2. パレート最適フロントに対する幅広さ，均一度合い - より広く，かつ均一に得られているのが理想 f2(x) f22(x) 非劣解 : 探索により得られた劣っていない解パレート最適解 : 真の解パレート最適フロント f1(x) パレート最適フロント f1(x) 多目的最適化問題への適用について • EMOを多目的問題に適用する際のポイントは？ – EMOアルゴリズムはどれにするか？ • 近年提案されている手法，NSGA-II，SPEA2などに大差はない． – GAのコーディングはどのようにするのか？ –GAのコーディングはどのようにするのか？ • ビットコーディング，実数値コーディングなど •ビットコーディング，実数値コーディングなど – 交叉，突然変異はどのように実装するのか？ • 1点交叉，多点交叉，実数値交叉（UNDX,SBX） ––交叉，突然変異はどのように実装するのか？個体数，評価計算回数，交叉率，突然変異率などのパラメータ設定 •1点交叉，多点交叉，実数値交叉（UNDX,SBX） • ある程度は経験的に分かっている推奨値を利用できる． – 得られた解候補からどのように最終的な解を選考するのか？ • 10目的（10次元）の結果からどのように全体像をつかむのか？ • 10000個の候補からどのように1つの最終解を選択するのか？今回紹介する2つの事例 • ディーゼルエンジン噴射スケジュールの最適化 • 燃料噴射スケジュールを最適化することにより，ディーゼル燃焼の改善を試みる • 燃費，NOx排出量，すす排出量の3目的最小化問題 • 矩形ブロックの配置面積の最小化 • 配置面積の縦・横の長さを目的とする2目的最適化問題 • 様々なアスペクト比を持つ最小面積配置を呈示することが可能ディーゼルエンジン噴射スケジュール最適化対象問題ディーゼルエンジンの燃料噴射スケジュール最適化利点：燃費がよい耐久性が高い CO2の排出量が少ない欠点：環境への悪影響（NOx，すすの排出量が多い）燃料の噴射スケジュールを変更することで削減可能燃料消費率，NOx排出量，すす排出量の同時最適化を試みるディーゼルエンジン噴射スケジュール最適化多い NOx，すすが生成しやすい燃焼条件燃焼状態完全燃焼不完全燃焼燃焼温度高温低温 NOxは少ないがすすが多いすすは少ないが NOxが多い少ないすすすす排出量 NOx 少ない・正反対の性質があり，同時低減が困難多目的最適化問題 NOx排出量多いディーゼルエンジン噴射スケジュール最適化 • 噴射スケジュール – クランク角 -5 °から13°の18°区間における燃料噴射スケジュール（ただし，噴射期間は6区間） – 総噴射燃料，噴射期間は一定クランク角ピストンが一番上にくる状態（上死点：TDC）を 0 度とする -5° 13 18°区間を36分割（0.5°刻み）で扱う ° コーディングの詳細 • 噴射スケジュール – クランク角 -5 °から13°の18°区間における燃料噴射スケジュール（ただし，噴射期間は6区間） – 総噴射燃料，噴射期間は一定 • 6区分区分の高さおよび幅が設計変数（計12変数：各変数値は 10Bitのグレイコーディング）． • まず幅（噴射期間）の合計が一定となるようスケーリング（噴射期間の一定化）． • その上で総面積が一定となるように各矩形の高さをスケーリング（噴射量の一定化）ディーゼルエンジン噴射スケジュール最適化噴射スケジュール NCGA HIDECS 燃費,NOx,Soot 最適化部評価部噴射率：燃料噴射量の時間的変化 HIDECS：ディーゼル燃焼のシミュレータ (廣安 ‘83) 適用手法とパラメータ評価関数燃料消費率 (SFC)の最小化窒素酸化物 (NOx)排出量の最小化すす(Soot)排出量の最小化 GA オペレータ • 交叉 – 1点交叉 • 突然変異 – ビット反転設計変数クランク角 –5°から 13°における燃料噴射のスケジュールパラメータ •適用手法 100 個体数 NCGA (提案手法) 1.0 交叉率 NSGA-II (Debらの) 突然変異率 1/L 200 終了世代 3目的から形成される 5 試行回数パレート最適解を探索し， L：遺伝子長 72ビット各目的間の関係を把握するディーゼルエンジン噴射スケジュール最適化に関する数値結果ディーゼルエンジン噴射スケジュール最適化に関する数値結果（噴射スケジュール） •各目的最小解における噴射スケジュール NCGAによる 1試行の結果 NOx Best SFC:299.6 NOx:0.4309 Soot:0.1539 SFC Best SFC:183.7 NOx:1.743 Soot:0.2605 Soot Best SFC:267.8 NOx:1.05 Soot:0.09924 ディーゼルエンジン噴射スケジュール最適化に関する数値結果（噴射スケジュール） •SFC – NOx 間におけるトレードオフ 1 [SFC:183.7, NOx:1.74] NCGAによる 1試行の結果 2 [SFC:184.43, NOx:1.51] 3 [SFC:196.13, NOx:0.78] ディーゼルエンジン噴射スケジュール最適化に関する数値結果（噴射スケジュール） •SFC – NOx 間におけるトレードオフ 4 5 [SFC:231.47, NOx:0.66] [SFC:275.365, NOx:0.49] NCGAによる 1試行の結果 6 [SFC:299.556, NOx:0.43] 矩形パッキング問題･矩形ブロックを最小面積で配置する • ブロック配置後の全領域における横幅の最小化 • ブロック配置後の全領域における高さの最小化３６様々なアスペクト比を持つ最小配置を求める４ f2 １７５２ f1 実際に各ブロックを配置する図形のアスペクト比を解選好者が選択できるデータ構造表現 (配置手法) • シーケンスペア (Sequence-pair) • 非スライシング構造も表現可能なデータ構造 (村田 ’96) • 系列  の順列に基づいて任意の2つの矩形の相対的な位置関係を指定する ( ,  ) ①(XY，XY) → XはYの左 ②(XY，YX) → XはYの下 ③ ④ ① ③(YX，XY) → XはYの上 ④(YX，YX) → XはYの右 ② データ構造表現 (配置手法) ex) a ～ f の6つの矩形ブロックの場合順列 (- ,  ) データ構造表現 (配置手法) ex) a ～ f の7つの矩形ブロックの場合 f と b は，最下段で並んでいる f の上には c がおり，c の上には e がいるまた， e a d は同列に並んでいる c の右には b がいる適用手法とパラメータ対象問題 GA オペレータ • ブロック数 33，100，500 適用手法 • 交叉 – PPEX（部分一致交叉） • 突然変異 – ブロック縦・横反転 • NCGA (提案手法) • non-NCGA (近傍交叉を行わないNCGA) パラメータ • SPEA2 (Zitzlerら) 個体数 • NSGA-II (Debら) 交叉率突然変異率終了世代試行回数 L: ブロック数 100 1.0 1/L 200 30 PPEX(部分一致交叉) • それぞれの親からランダムにブロックを1個ずつ選択 • 選択したブロックを中心に窓領域を生成し，窓に含まれるブロック集合を交叉対象とする． • 交叉対象の各ブロックについて相手の親ブロックの順番に入れ替え，子にコピー． • 交叉対象以外の各ブロックはそのまま子にコピー．矩形パッキング問題に関する数値結果 (33 blocks ）提案手法矩形パッキング問題に関する数値結果 (100 blocks ）提案手法矩形パッキング問題に関する数値結果 (500blocks）提案手法矩形パッキング問題に関する数値結果（33 blocks,レイアウト図）提案手法矩形パッキング問題に関する数値結果（100 blocks,レイアウト図）提案手法解選考支援システム • 多目的環境下における解選考の難しさ – 高次元空間における解候補の視覚化 • 3次元以上では全体像を把握できない PCA，クラスタリング手法などによる高次元空間の低次元化 – 膨大に存在するパレート解候補からの最終解の選択 • 候補が膨大すぎて選びきれない何らかの基準に基づいた解の抽出（α-dominationに基づく抽出法） α‐domination戦略 α-domination戦略 • 2つの目的間のトレードオフ比に上下界を設定し，解の支配領域を緩める（広げる）． – ある目的において少し劣り，他の目的では大きく優れている場合にはdominateすることを認める． α-domination戦略を用いた優越関係 f2 通常の優越関係優越領域優越領域合理性の高い解を抽出合理的な解優越される解優越されない解 α-domination戦略で優越されない解 f1 合理性が高い α‐domination戦略を利用した解の抽出 α-domination戦略を用いて解の抽出を行うと・・・凸パレート非凸パレートある特定の部分のみが抽出され，パレートフロント全体から幅広い解が抽出されない． α‐domination戦略を利用した解の抽出（２） • 分割型α-dominationの利用 – 目的関数空間全体を幾つかの小領域に分割し，その分割された範囲内においてαdominationによる抽出を行う．幅広い範囲から合理性の高い解が抽出することができる． Demonstration • 作成したシステム（試作）のデモまとめ • 多目的GAを実問題へ応用する際，通常の端目的GAと同様，コーディングと遺伝的操作（交叉，突然変異）の設定がカギとなる． – コーディングでは，解空間の規模，最適性（コーディングが全ての解表現を含んでいる）などがポイントとなる． – 遺伝的操作では，コーディングの特徴を十分に把握し，そのコーディングにおいて有効な手法であるかを吟味する必要がある． • 得られた解候補から解を選び出すための，効果的な支援システム – 得られた解の全体を把握 → 何らかの形で低次元化 – 膨大な解候補を削減 → 何らかの方法で特徴的な解を選び出す．補足 • 発表者の電子メールアドレス – [email protected] • 発表に用いたソースプログラム – http://mikilab.doshisha.ac.jp/dia/downloa d/index.html • 発表者の論文リスト – http://www.ritsumei.ac.jp/~sin/Paper/Pa per.html • 多目的最適化全般の論文リスト – http://www.lania.mx/~ccoello/EMOO/EMO Obib.html