多目的最適化における個体密度を利用した戦略による GDE3 の改良 寺井 零（1167020) 知能工学専攻 知能システム研究室 指 導 : 高濱徹行教授 1 はじめに 多目的最適化問題とは、複数の目的関数に対し、与 えられた制約条件下でこれらを同時に最適化する問 題のことである。一般にどの解にも優越されない解 集合をパレート最適解集合と呼び、これに対応する 目的関数値の集合をパレートフロントと呼ぶ。本研 究では、交叉、突然変異により、多目的最適化問題を 解く手法として用いられる Generalized Differential Evolution3(以下 GDE3)[1] に着目した。GDE3 で は、得られた個体と元の個体が互いに実行可能で優 劣をつけることができない場合、二つとも一旦生存 させ、次の世代に移行する直前に非優越ソートと混 雑距離を用いて、劣解を削除する。しかし、多目的 問題の場合、優越関係を主として個体削除を行うと、 疎な個体が削除されてしまいパレート最適解集合に 値を用いて疎な個体を 5 つ選択する。その疎な個体 は次の世代に必ず残すようにする。また、交叉方法 として、疎な個体の周りに子を発生させるように、 ベースベクトルに疎な個体群からランダムに用い る。手法 B では、5 個の疎な個体群と通常の個体群 を用い、それぞれで異なる処理を採用する。疎な個 体群では、親子の優越関係に ID 値も考慮する。子 の ID 値が親の値より悪ければ優越関係が勝ってい ても置き換えない。すなわち、ID 値が親以下の値 で、かつ親より優越していれば子に置き換える。互 いに非優越であった場合、子供のみを非優越ソート にかけ、親は必ず次世代に残る。疎でない通常の個 体群では、通常の優越関係のみを用いて取捨選択を 決める。互いに非優越の場合は、疎な個体群から生 まれた子と一緒に非優越ソートにかけられる。 実験 偏りができる。本研究では、GDE3 を基とし、疎な 3 個体を重視することによりパレートフロントの分布 2 目的問題 UF1 から UF7、3 目的問題 UF8 から UF10 を解いた。2 目的問題、3 目的問題のオリジナ を改良する二つの手法を提案する。 2 疎な個体をベースベクトルとす ル GDE3 と二つの提案手法の結果の違いを Inverse る手法 Generational Distance(IGD 値) を用いて以下に示 した。IGD 値とは、真のパレートフロントにどれだ GDE3 の交叉方法は、ベースベクトル、差分ベク トルをランダムに用意し、互いに加算して子を生成 する。本研究では、ベースベクトルを疎な個体群か らランダムに選択する手法を提案する。疎な個体を 判別する指標として Individual Density(ID) があ る。ID 値の決定法を以下に示す。 1. 全ての個体に対して目的関数空間における最近 傍個体との距離（最小距離）を求める。 2. 全ての最小距離の平均 IDAvemin を計算する。 3. 全ての個体において IDAvemin よりも小さい 距離内に存在する個体の個数を ID の指標と する。 よって、ID は整数値をとり、0 が最も疎な状態と なる。 ID を用いて疎な個体を選択する手法として手法 A、 手法 B を提案する。手法 A は、１世代ごとに交叉 を終えて増えた個体も合わせた個体群の中から ID け近いか、被覆度があるかを示す指標であり、値が 小さいほど良い。 表 1: オリジナル GDE3、３０回試行平均 Mean Dev Best Worst UF1 0.005622 0.001382 0.004453 0.011265 UF2 0.013291 0.002298 0.009535 0.018130 UF3 0.086954 0.024812 0.054320 0.154112 UF4 0.021132 0.000738 0.019822 0.023339 UF5 0.081105 0.009971 0.057539 0.108340 UF6 0.135686 0.032515 0.094459 0.219587 UF7 0.023244 0.012663 0.010475 0.066299 UF8 0.256181 0.044390 0.181479 0.342376 UF9 0.084741 0.025566 0.044181 0.158083 UF10 0.434406 0.015673 0.374890 0.441211 表 2: 手法 A、３０回試行平均 Mean Dev Best Worst UF1 0.006044 0.000807 0.005025 0.007926 UF2 0.009465 0.001422 0.007346 0.013556 UF3 0.055132 0.006277 0.045435 0.070745 UF4 0.021416 0.000614 0.020144 0.022616 UF5 0.080357 0.007585 0.069280 0.102421 UF6 0.121310 0.015463 0.087993 0.155785 UF7 0.028811 0.010617 0.012204 0.060388 UF8 0.141283 0.064343 0.064985 0.420520 UF9 0.036807 0.004343 0.029489 0.046983 UF10 0.395771 0.061847 0.281392 0.441330 表 3: 手法 B、30 回試行平均 Mean UF1 0.005916 UF2 0.009207 UF3 0.055707 UF4 0.022005 UF5 0.078522 UF6 0.129838 UF7 0.025196 UF8 0.096960 UF9 0.074973 UF10 0.283360 Dev 0.001755 0.001187 0.008139 0.000566 0.007184 0.024454 0.013433 0.015668 0.013078 0.013099 Best 0.004613 0.007203 0.042401 0.021055 0.065377 0.094225 0.010260 0.073574 0.063995 0.264711 1 Worst 0.013750 0.012138 0.082736 0.023362 0.092834 0.182950 0.075887 0.124623 0.106130 0.311101 以下に UF8 から UF10 をオリジナル GDE3、手 法 A、手法 B で最適化した結果を示す。 0.8 0.6 0.4 0.2 01.2 1 0.8 0.6 0.4 0.2 0 0 0.2 0.4 0.6 0.8 1 1.2 図 6: UF10 手法 B IGD 値から、手法 A では UF8 と UF9 で大きな 向上が得られ、手法 B では UF8 と UF10 に大きな 1 向上が見られた。図 1 と図 5 より、UF8 と UF10 は 0.8 特にパレートフロントが偏りやすい問題であり、疎 な個体を重要視する提案手法が有効に働いたとみら 0.6 0.4 れる。また、図 3 より UF9 では UF8 や UF10 ほど 0.2 01.2 1 0.8 0.6 0.4 0.2 0 0 0.2 0.4 0.6 0.8 1 1.2 偏らないため、疎な個体を重視しすぎた手法 B より も手法 A のほうが結果が良かったと思われる。2 目 的問題においても提案手法はオリジナル GDE3 と 図 1: オリジナル GDE3 の UF8 同等の IGD 値が得られた。このように、3 目的問題 に有効性が認められた他、提案手法のパレートフロ 1 0.8 ントを見ても、オリジナル GDE3 より被覆度が向 0.6 上していることがわかる。 0.4 4 0.2 01.2 1 0.8 0.6 0.4 0.2 0 0 0.2 0.4 0.6 0.8 1 おわりに 1.2 多目的問題において、疎な個体を重視する手法に ついて実験し、その有効性を示した。手法 A では 図 2: UF8 手法 B UF9 の被覆度を改善し、手法 B では UF8 と UF10 の被覆度が向上し、どちらの手法も 2 目的問題の結 1 0.8 果を大きく改悪させることなく、3 目的問題におい 0.6 てオリジナル GDE3 より良い結果が得られた。 0.4 今後は、手法 B における通常個体群での疎な個 0.2 01.2 1 0.8 0.6 0.4 0.2 0 0 0.2 0.4 0.6 0.8 1 1.2 体の保存、交叉確率 CR パラメータやスケーリング ファクタ F を含めた適応的なチューニング、各目的 図 3: オリジナル GDE3 の UF9 関数の最良個体を重視した極端解の重視、前世代で 成功した解の進化方向を繰り返し用いる進化加速に 1 よる被覆度の改善や精度の向上を目指した研究に取 0.8 り組みたい。 0.6 0.4 参考文献 0.2 01.2 1 0.8 0.6 0.4 0.2 0 0 0.2 0.4 0.6 0.8 1 1.2 [1] S. Kukkonen and J. Lampinen: GDE3: The third evolution step of generalized differential evo- 図 4: UF9 手法 A lution, Proceedings of the 2005 IEEE Congress on Evolutionary Computation, pp. 443-450, 2005. 1 0.8 0.6 外部発表情報 0.4 寺井零, 原章, 高濱徹行, ”生存者選択にグラフを 0.2 01.2 1 0.8 0.6 0.4 0.2 0 0 0.2 0.4 0.6 0.8 1 1.2 利用した GDE3 による多目的最適化の提案”, 2011 IEEE SMC Hiroshima Chapter 若手研究会講演論 図 5: オリジナル GDE3 の UF10 文集, pp.35-38, 2011.
© Copyright 2024 ExpyDoc
