多目的最適化問題における 進化的アルゴリズムの並列化 渡邉 真也, 廣安 知之， 三木 光範 同志社大学 工学部 Faculty of Engineering，Doshisha Univ Doshisha Univ., Japan 本研究の目的 • 多目的GAにおける新たな並列アルゴリズム の提案とその有効性の検証 • 領域分割型GA （Divided Range MultiObjective Genetic Algorithm: DRMOGA） -分割母集団型モデル • 局所的培養型マスタースレーブモデル （Master-Slave model with Local Cultivation: MSLC） -マスタースレーブ型モデル Doshisha Univ., Japan 本発表の流れ 1. 多目的最適化 2. 多目的GA 3. 提案する並列アルゴリズム ・ 一般的な並列分散型GAの説明 ・ 提案する2つの並列アルゴリズムの説明 4. 多目的0/1ナップザック問題 5. 数値実験 ・ 多目的0/1ナップザック問題を対象とした結果 ・ 携帯電話のネットワーク設計問題を対象とした結果 6. 結論 Doshisha Univ., Japan 多目的最適化 ･多目的最適化 トレードオフの関係にある，複数の評価基準を同 時に最適化 ・パレート最適解 複数，無限存在 GAの多点探索が有効 f2(x) Ex) ポートフォリオ問題，複合最適化設計 可能領域 パレート最適解 f1(x) Doshisha Univ., Japan GAによる多目的最適化への応用 ・多目的GA 交叉・突然変異を用いて パレート最適解集合の探索を行う A世代 B世代 f 2 (x) X世代 Y世代 パレート最適解 Z世代 f1(x) Doshisha Univ., Japan 多目的GAの並列分散化 多目的GAでは・・ ・膨大に個体数が必要 ・個体の多様性が重要 ・評価関数計算の負荷が高い 並列・分散化 ・使用メモリの増大 ・分散化による多様性の確保 ・計算時間の短縮 Doshisha Univ., Japan 単一目的GAにおける並列モデル セルラーモデル マスタースレーブモデル • 分割母集団モデル master Island model (Free topology) Shared memory 島モデル • マスタースレーブモデル Global Parallelization (Only evaluate in parallel) 評価 • セルラーモデル Neighborhood model PE (Mainly Grid topology) slave PE PE PE PE Doshisha Univ., Japan 多目的GAの並列分散化 ・現在までに多目的GAに適用されている並列モデル 単一目的GAからの単純な適用 ・分割母集団モデル（島モデル） （D. Q. Vicini など） ・Master-Slave GA （ B. R. Jonesら） 多目的と単一目的ではGAに求められる性能が異なる ・局所探索が必要 ・探索の全ての段階において多様性の保持が必要 Doshisha Univ., Japan 提案する並列アルゴリズム 分割母集団モデル • 領域分割型GA （Divided Range MultiObjective Genetic Algorithm: DRMOGA） マスタースレーブモデル • 局所的培養型マスタースレーブモデル（MasterSlave model with Local Cultivation: MSLC） Doshisha Univ., Japan 島1 f2(x) f2 (x) 島モデル分散型（DGA） f2 (x) f 1(x) 島2 f1(x) f 1(x) ・多目的GAに対する島モデルの問題点 ・島毎に探索の重複が起こり，探索の無駄が生じる． ・一島あたりの個体数が多数必要． Doshisha Univ., Japan f2(x) f2(x) 領域分割型GA 分割島1 分割島1 分割島2 f2(x) f1(x) 分割島2 Min 真のパレート最適解 Max f1(x) 1.任意の目的関数値を基準に個体ソート 2.分割島ごとの個体数が等しくなるように分配 3.任意の世代間隔で基準を変化させて再分配 f1(x) Doshisha Univ., Japan 領域分割型と島モデル分散型の比較 f2(x) f2(x) f2(x) ・島モデル分散型の場合 = + f1(x) f1(x) f1(x) f2(x) f2(x) f2(x) ・領域分割型の場合 = + f1(x) f1(x) f1(x) Doshisha Univ., Japan 局所的培養型マスタースレーブモデル • 局所的培養型マスタースレーブモデル ～Master-Slave model with Local Cultivation～ – MGG（Minimal Generation Gap）モデル（M. Satohら） を参考 全個体を入れ替えた時点で1世代終了 Doshisha Univ., Japan 局所的培養型マスタースレーブモデル 特徴 • スレーブ数の自由度が高い – スレーブ数が結果に左右されない． • 多様性の保持機能 – 選択が局所的に行われるため全体の多様性が保 持される． • マスターノードの負荷軽減 – （従来のマスタースレーブGAと異なり）GAオペ レータの負荷がスレーブノードにかかるため，マス ターの負荷が少ない． Doshisha Univ., Japan 多目的0/1ナップザック問題 • 0/1ナップザック問題 前提条件 重量と利益を持つ荷物のセット． ナップザックの任意の重量制限． 目的 限られた容量のなかで最大の利益を持つ 荷物の組み合わせを求める． 多目的化 ナップザック数およびナップザック に付随する荷物のセットを複数化． Doshisha Univ., Japan Knapsack Problem • 多目的0/1ナップザック問題 目的関数 m f i ( x ) pi , j x j 制約条件 j 1 ・100荷物2目的 ・250荷物2目的 ・750荷物2目的 m 1,2,, n : wi , j x j ci j 1 x ( x1, x2 ,, xm ) 0,1m pi , j ナップザック iの荷物jにおける利益 wi , j ナップザック iの荷物jにおける重量 ci ナップザック iの許容重量 Doshisha Univ., Japan 適用手法とパラメータ 適用手法 • • • • SGA ：単一母集団GA GAオペレータ DGA ：分割母集団モデル DRMOGA：領域分割型GA • 交叉方法 – 1点交叉 MSLC ：局所的培養型MSモデル • 選択方法 パラメータ 個体数 400，4000 交叉率 1.0 突然変異率 0.01 移住率 0.1 移住間隔 10世代 島数（プロセス数） 16 – パレート保存戦略 • 突然変異 – ビット反転 Doshisha Univ., Japan 数値実験 実験項目 • 100，250，750荷物の3つの例題に対する各手法 の有効性の検証 – プロット図より各手法を比較 • 分割母集団モデル（DGA，DRMOAG）における プロセス数の解へ与える影響について検証 – 16プロセスの場合と128プロセスの場合の結果比較 • 各並列手法（DGA，DRMOGA，MSLC）の計算 時間・並列化効率についての検証 – 同一条件下における各手法のプロセス数と計算時間 の関係 Doshisha Univ., Japan 数値実験～100荷物，400個体～ f2(x) SGA DGA DRMOGA MSLC f1(x) Doshisha Univ., Japan 数値実験～100荷物，4000個体～ f2(x) SGA DGA DRMOGA MSLC f1(x) Doshisha Univ., Japan 数値実験～250荷物，400個体～ f2(x) SGA DGA DRMOGA MSLC f1(x) Doshisha Univ., Japan 数値実験～250荷物，4000個体～ f2(x) SGA DGA DRMOGA MSLC f1(x) Doshisha Univ., Japan 数値実験～750荷物，400個体～ f2(x) SGA DGA DRMOGA MSLC f1(x) Doshisha Univ., Japan 数値実験～750荷物，4000個体～ f2(x) SGA DGA DRMOGA MSLC f1(x) Doshisha Univ., Japan プロセス数の与える解への影響 分割母集団モデルにおけるプロセス数の 解へ与える影響 • 分割母集団モデルでは，1島内（1プロセ ス）における個体数が解へ大きく影響する． – DGA，DRMOGAに対して，4000個体を用い た場合における16プロセスと128プロセスでの 解を比較，考察 Doshisha Univ., Japan 数値実験～100荷物，4000個体～ 128p 16p DGA 128p 16p DRMOGA Doshisha Univ., Japan 数値実験～250荷物，4000個体～ 128p 16p f2(x) f2(x) 128p 16p f1(x) DGA f1(x) DRMOGA Doshisha Univ., Japan 数値実験～750荷物，4000個体～ 128p 16p f2(x) f2(x) 128p 16p f1(x) DGA f1(x) DRMOGA Doshisha Univ., Japan 各アルゴリズムの並列化効率 of method Number Processors Times (sec) SGA MSLC 実験条件 ・4000個体 ・750荷物2目的 ・1000世代 DGA DRMOGA 1 1 2 4 8 16 1 2 4 8 16 1 2 4 8 16 16657.2 4042.4 5160.8 2371.0 1675.9 1685.1 16657.2 4011.3 1318.3 477.3 213.4 16657.2 4271.1 1500.3 583.2 264.3 1/4 Doshisha Univ., Japan Speed Up Speed Up DGA DRMOGA MSLC Ideal Number of Process Doshisha Univ., Japan 数値実験に対する考察 手法 解の精度 解の幅広さ SGA DGA DRMOGA MSLC △ ◎ ◎ △ △ × ◎ ○ プロセス数に 並列化効率 よる影響 × × ◎ ◎ ◎ × • DRMOGAはDGAと比較して一意的に優位である． • MSLCは，DRMOGA程ではないものの他の手法と比 較して同程度以上の解品質を得られる． • 領域分割型モデルの方がマスタースレーブ型と比べて 並列化効率が圧倒的に良い． Doshisha Univ., Japan ネットワーク設計問題 ネットワーク設計問題 領域内の候補サイトの中から 設置するサイトとアンテナの種類を決定 アンテナの種類 設置するサイト （3種類のアンテナ） 候補サイトの中から アンテナを設置する サイトの決定 （ 候補サイト） Doshisha Univ., Japan ネットワーク設計問題の定式化 -目的- -制約- • 電波のカバー領域の最大化 • 設計コストの最小化 • 電波の重なり • 電波のカバー領域 • アンテナのコスト トレードオフの関係 実験条件 ・80， 160個体 ・対象領域 100m×100m ・200世代 Doshisha Univ., Japan 数値実験～80個体～ f2(x) SGA DGA DRMOGA MSLC f1(x) Doshisha Univ., Japan 数値実験～160個体～ f2(x) SGA DGA DRMOGA MSLC f1(x) Doshisha Univ., Japan 各アルゴリズムの並列化効率 of method Number Processors Times (sec) SGA MSLC 実験条件 ・80個体 ・20世代 DGA DRMOGA 1 1 2 4 8 16 1 2 4 8 16 1 2 4 8 16 19447.8 23634.1 23415.9 7787.4 3382.8 1875.5 19447.8 8506.7 4085.0 2097.9 1073.1 19447.8 9044.7 4244.0 2089.7 1058.6 Doshisha Univ., Japan Speed Up Speed Up DGA DRMOGA MSLC Ideal Number of Process Doshisha Univ., Japan ネットワーク設計問題における結果の考察 • 分割母集団型モデル（DGA，DRMOGA）に比べ SGA, MSLCが良好な結果 – 総個体数が少ないために分割母集団モデルでは効果 的な探索が行えない． • 全ての並列手法において線形に近い並列化効率 – 評価関数の計算負荷が重いため，評価部分の並列 化がそのまま結果に反映されるため Doshisha Univ., Japan 結論 • DGAと比較してDRMOGAは，多目的最適化問題 に適している． – 問題の複雑度，用いる個体数に関わらず，DRMOGAの 方が良好な解を得ることができた． • 分割母集団モデル（DGA，DRMOGA）は，用いる プロセス数により大きく結果が異なる． – 1島内における個体数の数によって解が影響を受ける． – 1島内において十分な個体数がなければ効果的な探索 はできない． – マスタースレーブ型は用いるプロセス数に影響を受ける ことはない． Doshisha Univ., Japan 結論 (2) • 評価計算負荷の高い問題においてはMSLCは，最も 良好な手法である． – 評価計算負荷の高い問題では，1島内における個体数が非 常に限られてしまう．そのため，分割母集団モデルは充分 な探索を行うことができない． • 評価計算負荷によって各手法の並列化効率は異なる． – 評価計算負荷の低い場合には，DGA，DRMOGAが非常 に優れていた．MSLCは，あまり良好な並列化効率は得ら れなかった． – 評価計算負荷の高い場合には，どの手法でも線形に近い 良好な並列化効率が得られた． Doshisha Univ., Japan 探索の終了判定 ある世代の個体群Aと任意世代後の個体群Bの 優越関係を調べ，Aの内どの程度が個体Bに優 越されているかを調べる． １．Aのほとんどが優越されていない 探索が進んでいない 2．Aのほとんどが優越されている 探索が進んでいる フロンティアの進行具合により終了を判断 Doshisha Univ., Japan Cover rate プロセス数の与える解への影響 1 0.9 0.8 0.7 0.6 100 items 250 items 750 items 0.5 0.4 0.3 0.2 0.1 0 DGA(16P) DRMOGA(16P) DGA(128P) DRMOGA(128P) Doshisha Univ., Japan 局所的培養型マスタースレーブモデル • 局所的培養型マスタースレーブモデル ～Master-Slave model with Local Cultivation～ – MGG（Minimal Generation Gap）モデル（M. Satohら） を参 アルゴリズムの特徴 • 各種GAオペレータは，全てスレーブノード が行う． • 全てのGAオペレータは基本的に2個体のみ で行われる． Doshisha Univ., Japan 解の評価項目 パレート解を4つの評価項目により評価 ・被覆率 真のパレート解をどれだけカバーしているか． ・各目的関数ごとの最小値・最大値 各目的関数軸における探索領域の分布 ・計算時間もしくは計算回数 探索にかかった計算時間，計算回数 ・プロット図 平均被覆率の場合における目的関数空間 のプロット図 Doshisha Univ., Japan 数値実験 • 被覆率 （400個体） Doshisha Univ., Japan 数値実験 • 被覆率 （4000個体 Doshisha Univ., Japan Cover rate プロセス数の与える解への影響 1 0.9 0.8 0.7 0.6 100 items 250 items 750 items 0.5 0.4 0.3 0.2 0.1 0 DGA(16P) DRMOGA(16P) DGA(128P) DRMOGA(128P) Doshisha Univ., Japan 目的(1) 電波カバー領域の最大化 Doshisha Univ., Japan 目的(2) 設計コストの最小化 Doshisha Univ., Japan 制約条件 電波の重なり Doshisha Univ., Japan 分割母集団モデル（島モデル） 母集団を複数のサブ母集団に分割 各サブ母集団が独自の 領域を探索 サブ母集団を各プロセッサ に割り当て 一定世代ごとに移住 通信の頻度は低い 特徴 良好な解を速く求めることができる パラメータの増加 Doshisha Univ., Japan マスタースレーブモデル（細粒度） 評価計算のみを並列化 評価 ：スレーブで処理 評価以外 ：マスターで処理 master slave Shared memory PE 特徴 PE 計算量は逐次モデルと等しい PE 評価 1CPUがマスターとして必要 通信の頻度が高い PE PE Doshisha Univ., Japan セルラーモデル（細粒度） 遺伝的操作を局所的に実行 各個体は空間上のある位置 に配置 近傍の個体との間のみで 交叉・選択を行う 特徴 局所的なルールだけで動作 を記述可能 同種のトポロジを持つ 超並列アーキテクチャに向く Doshisha Univ., Japan プロセス数に関する考察 • DGA，DRMOGA共に16プロセスの場合に比べ 128プロセスの場合には解が大きく劣化した． – 分割母集団モデルでは，1島辺りの個体数が解へ 大きく影響する． – 適切な個体数とプロセス数の関係を見つけるのは 困難 • マスタースレーブモデルでは，プロセス数による 解への影響は無い – MSLCは，この点において分割母集団モデルである DGA，DRMOGAよりも優れている． Doshisha Univ., Japan 計算時間・並列化効率に関する考察 • DGA,DRMOGAでは線形以上の並列化効率 – 1島辺りの個体数の減少が，選択にかかる時間を大 幅に減少させるため． • MSLCでは，あまり良好な並列化効率が得られ ない – 評価関数の計算負荷が軽いため，並列化の効果が 得られにくい – 総計算時間に対するマスターの手続き処理にかか る時間の割合が大きい Doshisha Univ., Japan 各手法の比較 • DRMOGAは，従来のSGA,DGAと比較して良好 な結果を得られた． – DRMOGAは個体数，問題の荷物数に関わらず最も 幅広い解を得ることができる． – MSLCは，DRMOGA程では無いが，SGA，DGAと 比較して同程度以上の結果を得られた． • DGAは個体数が少ない場合において，個体が 局所的に固まる傾向が見られた． • 個体数が増加すると全ての手法において解の質 が向上した． Doshisha Univ., Japan
© Copyright 2024 ExpyDoc
