環境分散遺伝的アルゴリズムの 多目的最適化問題への適用

Presentation on theme: "環境分散遺伝的アルゴリズムの 多目的最適化問題への適用"— Presentation transcript:

1 環境分散遺伝的アルゴリズムの 多目的最適化問題への適用
Multi-Objective Genetic Algorithms with Distributed Environment Scheme 三木光範 同志社大学工学部 廣安知之 同志社大学大学院 上浦二郎 ○ それでは，環境分散遺伝的アルゴリズムの多目的最適化問題への適用と題して，同志社大学の上浦から発表させて頂きます． よろしくおねがいします．

2 研究背景（GAを用いた多目的最適化） パレート的アプローチ Ranking. Goldberg(1989)
Multi-Objective GA (MOGA). Fonseca (1993) Niched Pareto GA (NPGA). Horn, Nafploitis,Goldberg (1994) Non-dominated sorting GA (NSGA). Srinivas and Deb (1994) Strength Pareto Evolutionary Algorithms (SPEA). Zitzelr (1998) Distributed Range MOGA (DRMOGA). Hiroyasu (2000) 非パレート的アプローチ Vector Evaluated GA (VEGA). Schaffer (1985) VEGA+Pareto optimum individuals. Tamaki(1995) 単一目的化アプローチ Multi-Objective Genetic Local Search (MOGLS). Murata, Ishibuchi, Tanaka (2001) GAを用いた多目的最適化の研究は数多く行われています．これらの研究は，多目的最適化における最適解の集合であるパレート解の候補となる個体を探索中に明示的に扱うかどうかによってパレート的アプローチと非パレート的アプローチに分類されます． また，多目的最適化を単一目的の最適化として扱う研究もされています．本発表ではこれを特に単一目的化アプローチと呼びます． （クリック） 本発表では，この単一目的化アプローチを用いた多目的最適化を行っています．

3 単一目的化アプローチによる多目的最適化 重みパラメータによって多目的最適化を単一目的化 各目的関数に重みパラメータωを設定
重みと目的関数の加重和 →　単一の目的関数 重みの変化 →　複数のパレート解 多目的最適化を単一目的化する方法として重みパラメータを用いるものがあります． これは，各目的関数に重みパラメータを設定し，その重みと各目的関数の加重和を単一の目的関数とする方法で， 重みを変化させて複数回の試行を行うことにより，複数のパレート解を得ることを期待するものです．

4 単一目的化アプローチの並列化 評価を分散することによる並列化
セルラーモデルによる並列化（Murata,Ishibuchi,and Matsuo 2001） 島モデルによる並列化 一方で，多目的最適化は最適解が複数存在するために，単一目的の最適化と比較して計算にかかるコストが大きくなると考えられます．このため，多目的最適化を並列化することは有効であるといえますが，単一目的化アプローチの多目的最適化を並列化する方法にはこれらの方法が考えられます． まず，単純に解の評価を複数のプロセッサに分散することによる並列化，次にセルラーモデルによる並列化，そして島モデルによる並列化です． （クリック） 本発表では，この島モデルによる並列化に適した多目的GAを提案します．

5 分散遺伝的アルゴリズム 母集団を複数の島に分割 移住 各島で独立して遺伝的操作
分散遺伝的アルゴリズム（分散GA） （Tanese 1989） GAの並列化モデル 母集団を複数のサブ母集団（島）に分割 → 島モデル 各島内で独立して遺伝的操作 移住（移住率，移住間隔） 母集団を複数の島に分割 母集団 移住 次に分散遺伝的アルゴリズムについて説明します． 分散遺伝的アルゴリズム，分散GAはGAの並列化モデルの１つであり，母集団を複数の島と呼ばれるサブ母集団に分割することから島モデルとも呼ばれます． 分散GAは各島の中で独立して遺伝的操作を行いますが，各島間で探索情報を交換するために移住という操作を行います． ここで，移住操作を行う世代間隔を移住間隔，個体数に占める移住する個体の割合を移住率というパラメータで定めます． 各島で独立して遺伝的操作

6 環境分散遺伝的アルゴリズム 島ごとに異なるパラメータを設定 環境分散遺伝的アルゴリズム（環境分散GA）（Miki 2000）
母集団を複数の島に分割 各島内で独立して遺伝的操作 島ごとに異なったパラメータを設定 パラメータ設定の煩雑性の緩和 母集団 移住 母集団の分割 分散GAの１つのモデルに環境分散GAがあります． これは，分散GAの各島ごとに異なったパラメータを設定するものです． 同時に複数のパラメータを設定することが可能であるために，パラメータ設定の煩雑性が緩和されると報告されています． 島 島ごとに異なるパラメータを設定

7 提案手法 環境分散スキームを用いた多目的遺伝的アルゴリズム
Multi-Objective Genetic Algorithms with Distributed Environment Scheme ( MOGADES ) 特徴 各島に異なった重みパラメータ（重み分散） 類似した重み付けを持つ島間で移住（近傍移住） 目的関数間のスケールの違いにより重みを変化（重み変化） エリート個体とパレート解候補個体群を保存 （エリート＋パレート保存） 次に提案手法について説明します． 本発表で提案するのは環境分散スキームを用いた多目的遺伝的アルゴリズム，Multi-Objective Genetic Algorithms with Distributed Environment Scheme (MOGADES)です． この手法の特徴に，各島に異なった重みパラメータを割り当てること，類似した重み付けを持つ島間で移住を行うこと，目的関数間のスケールの違いにより重みを変化させること，エリート個体とパレート解候補個体群を保存すること，があります． 本発表ではこれ以降これらのそれぞれの特徴を，重み分散，近傍移住，重み変化，エリート＋パレート保存と呼ぶことがあります．

8 MOGADESの流れ 分散 移住 MOGADESの流れ ・初期個体の発生 ・各島に異なった重みを与えて 母集団を分割（重み分散）
　母集団を分割（重み分散） 移住 ・類似した重み付けを持つ 　島間で移住（近傍移住） 提案手法の流れについて説明します． 提案手法ではまず最初に（クリック）， 初期個体を発生させた後（クリック）， 各島に異なった重みを与えて母集団を分割します． 複数のプロセッサに対して島を割り当てることにより，提案手法を並列化することができます（クリック） ． 移住は，類似した重み付けを持つ島との間で起こり，同時に目的関数間のスケールの違いにより各島の重み付けが変化します． 各島は移住間隔毎に移住を繰り返しながら独立して遺伝的操作を行います ． これが全体としての提案手法の流れです． ・目的関数間のスケールの違い 　により重みを変化（重み変化）

9 MOGADESの流れ（続き：各島内） MOGADESの流れ 各島は単一目的の最適化 適合度値の高い個体（エリート）を保存
全体は多目的の最適化 パレート解候補個体群を保存 保存したエリート個体，パレート解候補個体群と交叉・突然変異によって生成された個体群の 合計の個体群から次世代の個体群を選択 （エリート＋パレート保存） 提案手法において各島は単一目的の最適化を行っています． このため，各島ごとに適合度の高い個体を個体群とは別に保存しています． 一方で，提案手法は全体としては多目的の最適化を行っています． このため，各島ごとに探索途中に発見されたパレート解候補個体群を個体群とは別に保存しています． こちらの図は各島での探索の流れを示したものです． これが交叉，突然変異の対象となる個体群，これが保存されたエリート個体群，そしてこれが保存されたパレート解候補個体群です． このようにエリート個体とパレート解候補個体群を個体群とは別に保存しておきます． そしてこれらの個体群，エリート個体群，パレート解候補個体群から次世代の個体群を選択します． パレート解候補個体群 エリート個体（群）

10 MOGADESの特徴 各島に異なった重みパラメータ（重み分散） 類似した重み付けを持つ島間で移住（近傍移住）
目的関数間のスケールの違いにより重みを変化（重み変化） エリート個体とパレート解候補個体群を保存（エリート＋パレート保存） ここでもう一度提案手法の特徴について述べます． 提案手法の特徴には，重み分散，近傍移住，重み変化，エリート＋パレート保存の４つがあります． 次にこれらの特徴について説明します．

11 重み分散 目的 一度の試行で広範囲に渡るパレート解を探索する 方法 2目的のとき → 任意の島数に関して均等に重み分散可能
2目的のとき →　任意の島数に関して均等に重み分散可能 ３目的以上 →　均等に重み分散可能な島数が限定される 例 ３目的のとき ４分割＝１０通り 5分割＝15通り 重み分散は，一度の試行で広範囲に渡るパレート解を探索することを目的としています． ２目的の場合には任意の島数について均等に重みを分散させることが可能です． しかし，３目的以上になると均等に重みを分散させることが可能である島数が限定されます． 例えば，３目的の場合，重みの分割数を４とすると重みは１０通りとなります． ここで重みの分割数を１増やして５にすると重みは１５通りになります． つまり島数が１１から１４の間であるときには重みを均等に分散させることができません．

12 近傍移住 目的 類似性の高い島と移住を行うことによる効率的な探索 方法 ある目的関数について島をソートし，隣接する２島に移住
両端に位置する島からは隣接する1島に移住 ３目的以上　→　移住ごとにソートの基準となる目的関数を変化 例 ３目的，１０島のとき 近傍移住は類似性の高い島と移住を行うことによる効率的な探索を目的としています． 各島をある目的関数についてソートし，隣接する２島に移住を行います．ただし，両端の島からは隣接する１島にのみ移住を行います． ３目的以上の場合には移住の度にソートの基準となる目的関数を変化させます． ３目的の場合を例にとって説明すると，一回目の移住の時には目的１についてソートし，２回目には目的２について，３回目には目的３についてソートを行い，４回目には再び目的１についてソートを行います． こうすることで，全体としては全ての近傍に移住を行います．

13 重み変化 ω ＝ γ・ω | F2(A) – F2(B) | ～ ＝ γ＝ 1/100 ＝ ω | F1(A) – F1(B) | 目的
スケールの大きい目的関数に探索が偏ることを防ぐ 方法 各目的関数に対する重みが１の島の最上位の個体がもつ 各関数値から目的関数のスケール比を求める スケール比を用いて各島の重みを変化 例 2目的，目的１(F1)が目的２(F2)の１００倍のスケールを持つ A :F１の重みが１の島のエリート 重み変化はスケールの大きい目的関数に探索が偏ることを防ぐことを目的としています． ２目的で目的１が目的２の１００倍のスケールを持つ場合を例にして説明します． A，Ｂはそれぞれ目的１，目的２に対する重みが１の島のエリート個体です． このA，Bがもつ目的関数値の比をとるとおよそ１００分の１となります． これを目的１に対する重みに掛け合わせることによって目的１と目的２を等価に評価できると考えられます． B :F2の重みが１の島のエリート ω F1new ＝ γ・ω F1base F2new ＝ ω F2base | F2(A) – F2(B) | | F1(A) – F1(B) | ＝ γ＝ 1/100 ～

14 エリート＋パレート保存 目的 局所探索と大域探索の効率化 方法
各島はそれぞれが独立したエリート個体とパレート解候補個体群を 探索個体群とは別に保存 保存したエリート個体，パレート解候補個体群，交叉・突然変異によって生成された個体群から次世代の個体群を選択 エリート＋パレート保存は局所探索性能と大域的な探索性能の両方を向上させることを目的としています． 方法は先ほど述べました通り， 各島が独立してエリート個体とパレート解候補個体群を個体群とは別に保存し， 保存したエリート個体，パレート解候補個体群，個体群から次世代の個体群を選択するというものです． ・・・ パレート解候補個体群 島1 島2 島3 エリート個体（群）

15 有効性の検証 概要 4種類の数値実験により提案手法の特徴が有効であることを示す 対象問題 多目的0/1Knapsack問題
アイテムセットは E.Zitzler (1999)を使用 ７５０items ２目的 ７５０items ３目的 ７５０items ２目的，Ｆ１を１００倍に評価 パラメータ 個体数：110（２目的），660（3目的） 島数：11（２目的），66（３目的）→ 重みは11分割 終了条件：解の評価が一定回数を越えた場合 次に，提案手法の有効性を示すために実験を行います． 対象問題は先ほどの発表にもありました多目的0/1ナップサック問題です． アイテムセットはZitzlerの定義したものを使用し， 750items２目的， 750items３目的，750items２目的でF1を100倍に評価する問題の３つの問題について実験を行いました． パラメータは，２目的では１１０個体１１島，３目的では６６０個体６６島としました．終了条件は解の評価が一定回数を超えた場合としています．

16 実験１ 概要 重み分散を行うことによる探索への影響を調べる
全島の重みを同一に設定して複数回試行を行った場合と 重み分散して１回試行を行った場合の性能を比較する 対象問題 750items 2目的 パラメータ 全島の重みを同一に設定 個体数　：110 島数　　：11 評価回数： × 11試行 ＝　 重み分散 個体数　：110 島数　　：11（重みは11分割） 評価計算： ×1試行 ＝　 １つ目の実験は，重み分散の効果を調べるものです． 重みを同一に設定して複数回の試行を行った場合と，重み分散を行って１回試行を行った場合の性能を比較します． 対象問題は７５０items２目的です． パラメータはこのように設定しました． 全島の重みを同一に設定した場合と重み分散をした場合で合計の評価計算回数が同じになるようにしています．

17 実験１ 結果 重み分散は有効である 結果について説明します．
実験１　結果 重み分散は有効である 結果について説明します． この軸がナップサック１の価値を示す軸，この軸がナップサック２の価値を示す軸です． この問題は最大化が目的なのでこの点に近づくほど良い解となります． こちらの青い点は提案手法で得られたパレート解， これらの点は重みを変化させて試行を行った場合の各試行で得られたパレート解をプロットしたものです． この図から，明らかに提案手法が優れたパレート解を早く発見できていることが分かり， 重み分散が有効であるといえます．

18 実験２ 概要 近傍移住を行うことによる解探索への影響を調べる 移住先をランダムに選ぶ場合と 近傍移住を行った場合の性能を比較する 対象問題
750items 3目的 パラメータ 移住先をランダムに選ぶ 個体数　：660 島数　　：66（重みは11分割） 評価回数： 近傍移住 個体数　：660 島数　　：66（重みは１1分割） 評価計算： ２つ目の実験は，近傍移住の効果を調べるものです． 移住先をランダムに選ぶ場合と，近傍移住を行った場合の性能を比較します． 対象問題は７５０items３目的です． パラメータはこのように設定しました．

19 実験２ 結果 近傍移住は有効である 近傍移住（MOGADES） ランダム 結果です．
実験２　結果 近傍移住は有効である 結果です． この軸がナップサック１の価値を示す軸，この軸がナップサック２の価値を示す軸，そしてこの軸がナップサック３の価値を示す軸です． この問題は最大化が目的なのでこの点に近づくほど良い解となります． 水色の点が探索によって得られたパレート解，それ以外の赤，青，緑の点はパレート解を投影したものです． 左側が提案手法によって得られたパレート解，右側は移住先をランダムに選んだ場合に得られたパレート解です． 提案手法はより広い領域についてしかも精度の高い解を発見されています． こちらのグラフは先ほどの発表でもありました手法の優越を示すグラフです． 提案手法によって得られたパレート解が移住先をランダムに選んだ場合に得られたパレート解の全てに優越していることが分かります． これらから，明らかに提案手法が優れたパレート解を早く発見できていることが分かり， 近傍移住が有効であるといえます． 近傍移住（MOGADES） ランダム

20 実験３ 概要 重み変化を行うことによる解探索への影響を調べる 重みが変化しない場合と 移住時に重み変化を行う場合の性能を比較する 対象問題
750items 2目的 （Knapsack１の価値を100倍に評価） パラメータ 重みが変化しない場合 個体数　：110 島数　　：11（重みは11分割） 評価回数： 重み変化 個体数　：110 島数　　：11（重みは11分割） 評価計算： ３つ目の実験は，重み変化の効果を調べるものです． 重みを変化させない場合と，重み変化を行った場合の性能を比較します． 対象問題は７５０items２目的で，ナップサック１の価値を１００倍に評価する問題です． パラメータはこのように設定しました．

21 実験３ 結果 重み変化は有効である 結果です． この軸がナップサック１の価値を示す軸，この軸がナップサック２の価値を示す軸です．
実験３　結果 重み変化は有効である 結果です． この軸がナップサック１の価値を示す軸，この軸がナップサック２の価値を示す軸です． この問題は最大化が目的なのでこの点に近づくほど良い解となります． この青い点が提案手法によって得られたパレート解， こちらの赤い点は重み変化を行わない場合に得られたパレート解を示しています． 提案手法が広範囲に均一にパレート解を得ることができているのに対して 重み変化をしない場合には中央付近にパレート解が存在していません． この図は終了世代でのすべての個体群をプロットしたものです． 重み変化をしない場合にはスケールの大きいナップサック１に個体が偏っていることが分かります． 提案手法はより広い領域についてしかも精度の高い解を発見されています． また，優越度に関しても 提案手法によって得られたパレート解が重み変化をしない場合に得られたパレート解の全てに優越していることが分かります． これらから，明らかに提案手法が優れたパレート解を発見できていることが分かり， 重み変化が有効であるといえます．

22 実験４ 概要 パレート解候補個体を保存することによる解探索への影響を 調べる
パレート解候補個体を保存しない場合と パレート解候補個体を保存する場合の性能を比較する 対象問題 750items 3目的 パラメータ パレート解候補個体を保存しない場合 個体数　：660 島数　　：66 （重みは11分割） 評価回数： パレート解候補個体を保存する場合 個体数　：660 島数　　：66 （重みは11分割） 評価計算： ４つ目の実験は，パレート解候補個体群を保存することの効果を調べるものです． 保存しない場合と，保存する場合の性能を比較します． 対象問題は７５０items３目的です． パラメータはこのように設定しました．

23 実験４ 結果 パレート解候補個体を保存することは有効である 保存する（MOGADES） 保存しない 結果です．
実験４　結果 パレート解候補個体を保存することは有効である 結果です． この軸がナップサック１の価値を示す軸，この軸がナップサック２の価値を示す軸，そしてこの軸がナップサック３の価値を示す軸です． この問題は最大化が目的なのでこの点に近づくほど良い解となります． 水色の点が探索によって得られたパレート解，それ以外の赤，青，緑の点はパレート解を投影したものです． 左側が提案手法によって得られたパレート解，右側はパレート解候補個体群を保存しない場合に得られたパレート解です． 提案手法は多くの解が発見されています． 手法の優越度を比較すると， 提案手法はパレート解候補個体群を保存しない場合と比較して80％以上優越しています． これらから，提案手法がより多くのパレート解を発見できていることが分かり， パレート解候補個体を保存することが有効であるといえます． 保存する（MOGADES） 保存しない

24 結論 MOGADESは多目的最適化問題の 解法として有効である 各島に異なった重み付けを行いパレート解の探索を行う MOGADESを提案した
各島に異なった重みパラメータを与える 重み付けの類似する島との間で移住を行う 目的関数間のスケールの違いにより重みを変化させる パレート解候補個体を保存する 結論です． 本発表では，各島に異なった重み付けを行いパレート解の探索を行うMOGADESを提案しました． そして実験により，MOGADESの４つの特徴がいずれも有効であることを示しました． これらより，MOGADESは多目的最適化問題の解法として有効であるといえます． 以上です． ありがとうございました． MOGADESは多目的最適化問題の 解法として有効である