渡邉 真也, 廣安 知之， 三木 光範 同志社大学 工学部 Faculty of Engineering，Doshisha Univ

Presentation on theme: "渡邉 真也, 廣安 知之， 三木 光範 同志社大学 工学部 Faculty of Engineering，Doshisha Univ"— Presentation transcript:

1 渡邉 真也, 廣安 知之， 三木 光範 同志社大学 工学部 Faculty of Engineering，Doshisha Univ
多目的最適化問題における 進化的アルゴリズムの並列化 渡邉 真也, 廣安 知之， 三木 光範 同志社大学 工学部 Faculty of Engineering，Doshisha Univ 知的システムデザイン研究室の渡邉です． ただいまより多目的最適化問題における進化的アルゴリズムの並列化と題しまして 発表させて頂きます．

2 本研究の目的 多目的GAにおける新たな並列アルゴリズムの提案とその有効性の検証
領域分割型GA （Divided Range Multi-Objective Genetic Algorithm: DRMOGA） -分割母集団型モデル 局所的培養型マスタースレーブモデル（Master-Slave model with Local Cultivation: MSLC） -マスタースレーブ型モデル 本研究の目的は，多目的GAにおける新たな並列アルゴリズムの提案とその有効性の検証です． 具体的には，2つの新たな並列アルゴリズムを提案します， 1つは領域分散型GA（英語・・DRMOGA）というアルゴリズムでして，これは分割母集団モデルの1つです． もう1つは，局所的マスタースレーブモデル（英語・・・MSLC）でして，これはマスタースレーブ型モデルの1つです． これら2つのモデルを数値実験に適用し，従来までの単一母集団GA，島モデルGAといった手法との比較を行っていきたいと思います．

3 本発表の流れ 多目的最適化 多目的GA 提案する並列アルゴリズム 多目的0/1ナップザック問題 数値実験 結論
・ 提案する2つの並列アルゴリズムの説明 多目的0/1ナップザック問題 数値実験 ・ 多目的0/1ナップザック問題を対象とした結果 ・ 携帯電話のネットワーク設計問題を対象とした結果 結論

4 多目的最適化 f ･多目的最適化 可能領域 ・パレート最適解 トレードオフの関係にある，複数の評価基準を同時に最適化 複数，無限存在
1 (x) 2 パレート最適解 Ex) ポートフォリオ問題，複合最適化設計 ・パレート最適解 複数，無限存在 GAの多点探索が有効 まず始めに多目的最適化の説明を行います． 多目的最適化では，トレードオフの関係にある複数の評価基準を同時に最適化します． 一般に多目的最適化において全ての評価基準を満たすような解は存在しません．そのため，パレート最適解という概念を用いて解探索を行います． パレート解とは図に示されるような，可能領域内におけるの曲線，直線として表されます．そのため，パレート解は複数もしくは,無限に存在します． そこで近年，GAの多点探索という特徴を活かしてパレート解集団を1度の探索で求めようとする多目的GAに関する研究が注目を集めてきました．

5 GAによる多目的最適化への応用 f f ・多目的GA 交叉・突然変異を用いて パレート最適解集合の探索を行う (x) パレート最適解 (x)
B世代 X世代 Y世代 (x) f 2 パレート最適解 Z世代 f 1 (x) 多目的GAでは，SGAと同様交叉・突然変異を用いてパレート最適解集合を直接探索を行います． 概念的には，図のように世代が進むに連れ徐々にパレート最適解に近づいていき，最終的に最も真のパレート解に近い解集合を得ることができるものと思われます．

6 多目的GAの並列分散化 並列・分散化 多目的GAでは・・ ・膨大に個体数が必要 ・個体の多様性が重要 ・評価関数計算の負荷が高い
・使用メモリの増大 ・分散化による多様性の確保 ・計算時間の短縮 しかし，多目的GAでは ・膨大に個体数が必要， ・個体の多様性が重要． ・評価関数の計算負荷が高い といった問題点が指摘されています． これらの問題点に対する有効な手段の1つとして，並列分散化があります， 並列・分散化を行うことにより ・メモリ増加による，使用個体の増加． ・分散化による多様性の確保． ．計算負荷分散による，計算時間の短縮． を実現することができます． しかしながら現在までの所，多目的GAにおける並列分散化の研究は十分に行われていません．

7 単一目的GAにおける並列モデル 分割母集団モデル Island model (Free topology) マスタースレーブモデル
セルラーモデル マスタースレーブモデル PE master Shared memory 評価 slave 分割母集団モデル Island model (Free topology) マスタースレーブモデル Global Parallelization (Only evaluate in parallel) セルラーモデル Neighborhood model (Mainly Grid topology) 島モデル

8 多目的と単一目的ではGAに求められる性能が異なる
・分割母集団モデル（島モデル） （D. Q. Vicini など） ・Master-Slave GA （ B. R. Jonesら） 多目的と単一目的ではGAに求められる性能が異なる ・局所探索が必要 ・探索の全ての段階において多様性の保持が必要 しかしながら現在までの所，多目的GAにおける並列分散化の研究は十分に行われていません． 現在までに，行われてきた多目的GAにおける並列モデルについてみていきます． 単一目的GAからの単純な適用例としては，島モデル分散GAがVieiniやその他多くの研究者によって行われています．また，Master – Slave型GAについてはJonesらによって適用されてきました． しかし，多目的問題と単一目的問題ではGAに求められる性能が大きく異なります． 具体的には， ・局所探索が必要であること ・単一目的GAでは，探索の初期及び中期段階において解の多様性が保持されていれば良いのに対して，多目的では探索の全ての段階において多様性の保持が必要であること などが挙げられます． そこで，本研究ではより多目的の特性を取り入れた新たな並列アルゴリズムとして 領域分散型GA，局所的培養型マスタースレーブモデルの2つのアルゴリズムを提案します．

9 提案する並列アルゴリズム 分割母集団モデル
領域分割型GA （Divided Range Multi-Objective Genetic Algorithm: DRMOGA） マスタースレーブモデル 局所的培養型マスタースレーブモデル（Master-Slave model with Local Cultivation: MSLC）

10 島モデル分散型（DGA） ・多目的GAに対する島モデルの問題点 島1 島2 ・島毎に探索の重複が起こり，探索の無駄が生じる．
(x) f 2 f 1 (x) 2 f (x) 1 (x) 島2 f 2 f (x) 1 ・多目的GAに対する島モデルの問題点 ・島毎に探索の重複が起こり，探索の無駄が生じる． ・一島あたりの個体数が多数必要． GAでは，従来より島モデルとよばれる分散モデルが提唱されており，単目的GAではその有効性が幾つかの論文により検証されています． 島モデルでは，このように個体を島数と均等になるように適当に分配します． しかし，求める解候補が複数存在する多目的問題では， ・島毎に探索の重複が起こり，探索の無駄が生じる． ・一島あたりの個体数が多数必要となり，結果としてより多くの個体数が必要となる． などの問題点が挙げられます． 本発表では，より多目的問題の特徴にあった分割手法が必要と考え，新たに領域分散型GAモデルを提案します．

11 2.分割島ごとの個体数が等しくなるように分配
領域分割型GA f 1 (x) 2 分割島1 (x) f 2 分割島1 分割島2 f 1 (x) 2 分割島2 真のパレート最適解 Min Max f (x) 1 1.任意の目的関数値を基準に個体ソート 2.分割島ごとの個体数が等しくなるように分配 3.任意の世代間隔で基準を変化させて再分配 まず，領域分散型GAについて説明します． 領域分散型では，個体を任意の目的関数値を基準にソートし，各分割島の個体数が等しくなるように分配します． その結果，図に示しますうように各分割島ごと，異なる，探索領域を担当することになります． また，探索が進むにつれ乱れてくる各分割島の探索領域を整え直すため，任意の世代間隔ごとに基準を変化させ再分配を行います．

12 領域分割型と島モデル分散型の比較 ・島モデル分散型の場合 = + ・領域分割型の場合 = + f2(x) f1(x) f2(x) f1(x)
ここで，領域分散型モデルの特徴を明確にするために島モデル分散型との比較を示します． 島モデルの場合には，各島毎では，ある程度散らばって探索をしているような場合でも，全島の個体を合計した最終的な解候補は，部分的に偏っていたり，幅広く解を得ることができないといったことが考えられます． 対して，領域分散型では，この図のように分割島毎の探索領域が独立されているため，全体として見た場合にも，部分的に偏らず，パレート曲線に均一に幅広く解が得られるものと考えらます．

13 局所的培養型マスタースレーブモデル 局所的培養型マスタースレーブモデル
～Master-Slave model with Local Cultivation～ MGG（Minimal Generation Gap）モデル（M. Satohら） を参考 全個体を入れ替えた時点で1世代終了 概念図で表すとこのようになります． マスターでは，2個体づつを各スレーブに送ります．スレーブの方ではその個体を基に各種GAオペレータを適用し，その後，新たな2個体をマスターへ返すといった仕組みです． ただし，本モデルは全個体が入れ替えられた時点で1世代終了となるためMGGモデルとは世代モデルが異なっています．

14 局所的培養型マスタースレーブモデル 特徴 スレーブ数の自由度が高い 多様性の保持機能 マスターノードの負荷軽減
スレーブ数が結果に左右されない． 多様性の保持機能 選択が局所的に行われるため全体の多様性が保持される． マスターノードの負荷軽減 （従来のマスタースレーブGAと異なり）GAオペレータの負荷がスレーブノードにかかるため，マスターの負荷が少ない． 提案モデルの特徴です． まず，高いスレーブ数の自由度．これは，結果にスレーブ数が左右されないということを意味しています．次に，多様性の維持機能．これは，MGGモデルにおける特徴の一つで，選択が局所的に行われるため全体の多様性が保持されるということです．それから，マスターノードの負荷軽減．これは，従来のマスタースレーブGAと異なりGAオペレータの負荷がスレーブノードにかかるため，マスターの負荷が少ないためです．

15 多目的0/1ナップザック問題 多目的化 0/1ナップザック問題 前提条件 重量と利益を持つ荷物のセット． ナップザックの任意の重量制限．
限られた容量のなかで最大の利益を持つ 荷物の組み合わせを求める． ナップザック数およびナップザック に付随する荷物のセットを複数化． 多目的化 次に今回用いた適用問題である多目的ナップザック問題について説明します． 一般に，0/1ナップザック問題は，重量と利益を持つ荷物のセットから成り立っており，ナップザックには任意の重量制限がかけられています．その目的は，「限られた容量のなｋで最大の利益を持つ荷物の組み合わせを求める」ことです． この0/1ナップザック問題は，ナップザック数およびナップザックに付随する荷物のセットを複数化することにより容易に多目的化することができます．

16 Knapsack Problem 多目的0/1ナップザック問題 目的関数 ・100荷物2目的 ・250荷物2目的 ・750荷物2目的
制約条件 多目的ナップザック問題はこのような式で定式されます． 目的関数におけるpは利益を表しており，xは0もしくは1をとるベクトル，設計変数値です．xが1であるならばその荷物は選択され，0であれば選択されていないことを意味します． 制約条件は，各荷物の総量が各ナップザックの許容重量以下であることを意味しています．

17 SGA ：単一母集団GA DGA ：分割母集団モデル DRMOGA：領域分割型GA MSLC ：局所的培養型MSモデル
適用手法とパラメータ 適用手法 SGA ：単一母集団GA DGA ：分割母集団モデル DRMOGA：領域分割型GA MSLC ：局所的培養型MSモデル GAオペレータ 交叉方法 1点交叉 選択方法 パレート保存戦略 突然変異 ビット反転 パラメータ 個体数 400，4000 交叉率 1.0 突然変異率 0.01 移住率 0.1 移住間隔 10世代 島数（プロセス数） 16 本発表で用いた手法は，SGA，DGA，NMSの3手法です．用いたパラメータ及び用いた各種GAオペレータを示します．

18 数値実験 実験項目 100，250，750荷物の3つの例題に対する各手法の有効性の検証
プロット図より各手法を比較 分割母集団モデル（DGA，DRMOAG）におけるプロセス数の解へ与える影響について検証 16プロセスの場合と128プロセスの場合の結果比較 各並列手法（DGA，DRMOGA，MSLC）の計算時間・並列化効率についての検証 同一条件下における各手法のプロセス数と計算時間の関係

19 数値実験～100荷物，400個体～ SGA DGA DRMOGA MSLC f2(x) f1(x)

20 数値実験～100荷物，4000個体～ SGA DGA DRMOGA MSLC f2(x) f1(x)

21 数値実験～250荷物，400個体～ SGA DGA DRMOGA MSLC f2(x) f1(x)

22 数値実験～250荷物，4000個体～ SGA DGA DRMOGA MSLC f2(x) f1(x)

23 数値実験～750荷物，400個体～ SGA DGA DRMOGA MSLC f2(x) f1(x)

24 数値実験～750荷物，4000個体～ SGA DGA DRMOGA MSLC f2(x) f1(x)

25 プロセス数の与える解への影響 分割母集団モデルにおけるプロセス数の 解へ与える影響
分割母集団モデルでは，1島内（1プロセス）における個体数が解へ大きく影響する． DGA，DRMOGAに対して，4000個体を用いた場合における16プロセスと128プロセスでの解を比較，考察

26 数値実験～100荷物，4000個体～ 128p 128p 16p 16p DGA DRMOGA

27 数値実験～250荷物，4000個体～ 128p 128p 16p 16p DGA DRMOGA f2(x) f2(x) f1(x)

28 数値実験～750荷物，4000個体～ 128p 128p 16p 16p DGA DRMOGA f2(x) f2(x) f1(x)

29 各アルゴリズムの並列化効率 16657.2 4042.4 1/4 実験条件 ・4000個体 ・750荷物2目的 ・1000世代 method
Number of method Times (sec) Processors SGA 1 4042.4 1/4 MSLC 1 2 5160.8 実験条件 4 2371.0 ・4000個体 ・750荷物2目的 ・1000世代 8 1675.9 16 1685.1 DGA 1 2 4011.3 4 1318.3 8 477.3 16 213.4 DRMOGA 1 2 4271.1 4 1500.3 8 583.2 16 264.3

30 Speed Up Speed Up DRMOGA DGA MSLC Ideal Number of Process

31 数値実験に対する考察 DRMOGAはDGAと比較して一意的に優位である．
MSLCは，DRMOGA程ではないものの他の手法と比較して同程度以上の解品質を得られる． 領域分割型モデルの方がマスタースレーブ型と比べて並列化効率が圧倒的に良い．

32 ネットワーク設計問題 ネットワーク設計問題 アンテナの種類（3種類のアンテナ） 設置するサイト 候補サイトの中から
領域内の候補サイトの中から 設置するサイトとアンテナの種類を決定 　アンテナの種類（3種類のアンテナ） 　設置するサイト 　候補サイトの中から 　アンテナを設置する 　サイトの決定 　（　候補サイト）

33 ネットワーク設計問題の定式化 -制約- -目的- トレードオフの関係 実験条件 ・80， 160個体 ・対象領域 100m×100m
　電波のカバー領域の最大化 　設計コストの最小化 -制約- 　電波の重なり 　電波のカバー領域 　アンテナのコスト トレードオフの関係 実験条件 ・80， 160個体 ・対象領域 100m×100m ・200世代

34 数値実験～80個体～ DRMOGA SGA DGA MSLC f2(x) f1(x)

35 数値実験～160個体～ DRMOGA SGA DGA MSLC f2(x) f1(x)

36 各アルゴリズムの並列化効率 19447.8 実験条件 ・80個体 ・20世代 method Times (sec) 23634.1
Number of method Times (sec) Processors SGA 1 MSLC 1 2 4 7787.4 実験条件 8 3382.8 16 1875.5 ・80個体 ・20世代 DGA 1 2 8506.7 4 4085.0 8 2097.9 16 1073.1 DRMOGA 1 2 9044.7 4 4244.0 8 2089.7 16 1058.6

37 Speed Up DRMOGA DGA MSLC Ideal Speed Up Number of Process

38 ネットワーク設計問題における結果の考察 分割母集団型モデル（DGA，DRMOGA）に比べSGA, MSLCが良好な結果
総個体数が少ないために分割母集団モデルでは効果的な探索が行えない． 全ての並列手法において線形に近い並列化効率 評価関数の計算負荷が重いため，評価部分の並列化がそのまま結果に反映されるため

39 結論 DGAと比較してDRMOGAは，多目的最適化問題に適している．
1島内における個体数の数によって解が影響を受ける． 1島内において十分な個体数がなければ効果的な探索はできない． マスタースレーブ型は用いるプロセス数に影響を受けることはない．

40 結論 (2) 評価計算負荷の高い問題においてはMSLCは，最も良好な手法である． 評価計算負荷によって各手法の並列化効率は異なる．
評価計算負荷の高い問題では，1島内における個体数が非常に限られてしまう．そのため，分割母集団モデルは充分な探索を行うことができない． 評価計算負荷によって各手法の並列化効率は異なる． 評価計算負荷の低い場合には，DGA，DRMOGAが非常に優れていた．MSLCは，あまり良好な並列化効率は得られなかった． 評価計算負荷の高い場合には，どの手法でも線形に近い良好な並列化効率が得られた．

41 探索の終了判定 １．Aのほとんどが優越されていない 探索が進んでいない 2．Aのほとんどが優越されている 探索が進んでいる
ある世代の個体群Aと任意世代後の個体群Bの優越関係を調べ，Aの内どの程度が個体Bに優越されているかを調べる． １．Aのほとんどが優越されていない 探索が進んでいない 2．Aのほとんどが優越されている 探索が進んでいる フロンティアの進行具合により終了を判断

42 プロセス数の与える解への影響

43 局所的培養型マスタースレーブモデル 局所的培養型マスタースレーブモデル
～Master-Slave model with Local Cultivation～ MGG（Minimal Generation Gap）モデル（M. Satohら） を参 アルゴリズムの特徴 各種GAオペレータは，全てスレーブノードが行う． 全てのGAオペレータは基本的に2個体のみで行われる． 次に局所的マスタースレーブモデル（MSLC）について説明します． 本アルゴリズムは，佐藤らの提案するMGGモデルの概念を並列に応用したものとなっており， アルゴリズムの特徴としては，従来のマスタースレーブ型モデルと異なり,各種GAオペレータは全てスレーブノードで行うといこと， 全てのGAオペレータは基本的に2個体のみで行われる

44 解の評価項目 パレート解を4つの評価項目により評価 ・被覆率 ・各目的関数ごとの最小値・最大値 ・計算時間もしくは計算回数 ・プロット図
真のパレート解をどれだけカバーしているか． ・各目的関数ごとの最小値・最大値 各目的関数軸における探索領域の分布 ・計算時間もしくは計算回数 探索にかかった計算時間，計算回数 ・プロット図 平均被覆率の場合における目的関数空間 のプロット図 次に解の評価について説明します． 本発表では，得られた解を次の4つの評価項目により評価しています． ・誤差は，真の解との平均的な離れ具合を数値化したものです． ・被覆率は，真のパレート解をどれだけ広くカバーしているかにかんするものです． ．計算回数は，評価関数（目的関数）の計算回数です． ・計算時間は，探索が終了するまでにかかった時間です．

45 数値実験 被覆率 （400個体）

46 数値実験 被覆率 （4000個体

47 プロセス数の与える解への影響

48 目的(1) 電波カバー領域の最大化

49 目的(2) 設計コストの最小化

50 制約条件 電波の重なり

51 分割母集団モデル（島モデル） 母集団を複数のサブ母集団に分割 一定世代ごとに移住 各サブ母集団が独自の 領域を探索 サブ母集団を各プロセッサ
に割り当て 一定世代ごとに移住 通信の頻度は低い 特徴 良好な解を速く求めることができる パラメータの増加

52 マスタースレーブモデル（細粒度） 評価計算のみを並列化 評価 ：スレーブで処理 PE master slave 評価以外 ：マスターで処理
評価　　　　：スレーブで処理 PE master Shared memory 評価 slave 評価以外　：マスターで処理 特徴 計算量は逐次モデルと等しい 1CPUがマスターとして必要 通信の頻度が高い

53 セルラーモデル（細粒度） 遺伝的操作を局所的に実行 各個体は空間上のある位置 に配置 近傍の個体との間のみで 交叉・選択を行う 特徴
局所的なルールだけで動作 を記述可能 同種のトポロジを持つ 超並列アーキテクチャに向く

54 プロセス数に関する考察 DGA，DRMOGA共に16プロセスの場合に比べ128プロセスの場合には解が大きく劣化した．
分割母集団モデルでは，1島辺りの個体数が解へ大きく影響する． 適切な個体数とプロセス数の関係を見つけるのは困難 マスタースレーブモデルでは，プロセス数による解への影響は無い MSLCは，この点において分割母集団モデルであるDGA，DRMOGAよりも優れている．

55 計算時間・並列化効率に関する考察 DGA,DRMOGAでは線形以上の並列化効率 MSLCでは，あまり良好な並列化効率が得られない
1島辺りの個体数の減少が，選択にかかる時間を大幅に減少させるため． MSLCでは，あまり良好な並列化効率が得られない 評価関数の計算負荷が軽いため，並列化の効果が得られにくい 総計算時間に対するマスターの手続き処理にかかる時間の割合が大きい

56 各手法の比較 DRMOGAは，従来のSGA,DGAと比較して良好な結果を得られた．
MSLCは，DRMOGA程では無いが，SGA，DGAと比較して同程度以上の結果を得られた． DGAは個体数が少ない場合において，個体が局所的に固まる傾向が見られた． 個体数が増加すると全ての手法において解の質が向上した．