遺伝的アルゴリズムを用いた並列グラフ分割アルゴリズム

スポンサーリンク

概要

論文の詳細を見る
本論文では,遺伝的アルゴリズムを用いた新たな並列グラフ分割アルゴリズムを提案し,このアルゴリズムを用いることによって,従来のヒューリスティックアルゴリズムと比ベてより良い解をより高速に求めることができることを示す.この並列グラフ分割アルゴリズムは,従来のヒューリスティックアルゴリズムと遺伝的アルゴリズムを組み合わせたものであるが,より高速な処理を実現するために,(1)非同期型細粒度並列遺伝的アルゴリズムおよび(2)新たなグラフ分割問題向き交叉オぺレータを用いている.15プロセッサによる並列処理では14〜18倍の性能向上を確認した.また,本論文で提案する細粒度並列遺伝的アルゴリズムと,複数のコロニーを用いる粗粒度並列遺伝的アルゴリズムを組み合わせることによって,より高並列な処理が実現できることをシミュレーションにより示す.
一般社団法人情報処理学会の論文
1993-04-15

著者

関連論文

もっと見る

スポンサーリンク