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

大规模分布式系统组合优化计算并行处理研究

基本信息

批准号：
15700034
负责人：
名嘉村盛和
金额：
$ 2.11万
依托单位：
University of the Ryukyus
依托单位国家：
日本
项目类别：
Grant-in-Aid for Young Scientists (B)
财政年份：
2003
资助国家：
日本
起止时间：
2003 至 2004
项目状态：
已结题

项目摘要

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

进化计算的并行处理是一个模型，其中每个计算节点保持染色体集，并且演变计算是独立促进的，即分布式模型是主流的。但是，由于每个计算节点都独立促进优化计算，因此从进化计算的角度进行了一些重复处理的相同分辨率。尽可能地减少本研究，因此我们提出了一种有效地探索用多个计算节点的解决方案的方法。节点是新的。节点是针对大规模分布式系统的，假设网格作为计算平台。进化计算中的沟通延迟。节点之间的功率，发现计算能力的差异对进化计算的质量有重大影响。