大規模分散システムにおける組合せ最適化計算の並列処理に関する研究

点击翻译按钮获取中文摘要

進化計算の並列処理は,各計算ノードが染色体集合を保持しそれに対して独立に進化計算を進めるモデル,すなわち,分散モデルが主流となっている.特に計算プラットフォームが分散システムの場合は,通信遅延がオーバーヘッドとなり易いため分散モデルが適していると言われている.しかしながら,各計算ノードが独立して最適化計算を進めることから,同じ解候補を複数のノードで計算する重複処理が発生する.ある程度の重複処理は進化計算の効率の観点からは必要なものであるが,極端に増加すると並列処理のメリットが低く抑えられてしまうという欠点がある.これは,システムが大規模化する程顕著に現れる.そこで本研究では,複数の計算ノードで効率良く解空間を探索する方法を提案した.提案手法はマスタースレーブ方式で,マスターノードがスレーブノード(計算ノード)の探索履歴を管理し,新たな探索空間の割当に利用している.計算機実験によって従来法と比較する事により提案手法の有効性が示された.また,計算ノード間で染色体のやり取りをするマイグレーションを導入した進化計算の並列処理手法を提案した.計算プラットフォームとしてGRIDを想定した大規模分散システムを対象とした.ここでは,分散システムのネットワークトポロジーを木構造と仮定し,トポロジーと通信遅延が進化計算にどのような影響を与えるかを計算機実験によって調べた.その結果,通信遅延は当然のことながら,直径,子孫ノードの数,独立ノード数等トポロジーのパラメータが最適化計算に影響を与えることが分かった.また,ライントポロジーに絞って,ノード間の計算パワーの差の影響について調査を行った.これにより,計算パワーの違いは進化計算の解の質に大きな影響を及ぼす事が分かった.