Grid環境における評価部にデータベースを
用いた遺伝的アルゴリズムの提案
同志社大学
廣安 知之 三木 光範
同志社大学大学院
○片浦 哲平 谷村 勇輔
はじめに
• Grid
• 最適化問題とは
• 提案する最適化システムについての説明
Optimization Engine, Function Agent,Database Server
Approximation Server, Analysis Server
• 遺伝的アルゴリズムの実装
• 数値実験
• まとめ
Grid
• 世界中の計算資源を結びつけて1つの巨大な
コンピュータとして有効活用する
Gridの可能性
• スーパーコンピュータを超える大規模計算能力
• 膨大なデータを格納できる大規模データベース
科学技術計算分野,大規模最適化問題への適用
最適化問題
• 目的関数の最大値・最小値を求める
• 最適化問題の例
構造物の設計
たんぱく質の構造予測
• 最適化問題は膨大な計算時間と計算量を要する
高速な計算資源
膨大な計算結果を格納するデータベース
最適化問題の解析
各最適化手法を実装
最適化計算を行う
解析計算を行う
膨大な時間を要する
目的関数の値を求める
GA,SAは,確率的探索のため重複計算が起こる
確率的探索による最適化
Grid環境における最適化システムを提案する
提案するGrid最適化システム
Optimization Engine
• 最適化問題に適用する最適化手法の
エンジン部分(最適化計算部分)を担当
• 決定論的手法・・・数理計画法
• 確率的手法・・・GA,SA
目的,理由
• 最適化手法だけに専念
Function Agent
• 各サーバ (Optimization Engine,Database Server,
Analysis Server,Approximation Server)
の結果に基づき適切なサーバを選択する
目的,理由
• 多数の通信の制御
• 通信状況の把握を容易に
Database Server
• 実際の実験データ,シミュレーションで得た目的
関数の評価値の格納
• 評価値の検索
目的,理由
• 重複した評価計算の省略
• 複数試行時のデータ有効利用
• 共同研究者とのデータ共有
Analysis Server
• 目的関数の評価を行う
• 全操作の中で最も処理時間を要する
• 性能のよい解析コードを持つ
目的,理由
• 評価計算だけに専念
• 多くの台数を割り当てられる
Approximation Server
• Database Serverの情報から近似評価値を作成
• 確率的手法にのみ有効
• 近似を利用するかどうかは利用者が選択できる
目的,理由
• 最適化計算の継続
近似操作
• 確率的手法において最適化計算の継続を
目的とする
(正しい適合度値を待ち進化が遅れるよりもよ
い)
• リソースを有効活用することで解探索を進める
• 近似手法はそれぞれの確率的手法,対象問題
による
具体的な動作
• データベースの検索に
成功する場合
• データベースの検索に
失敗する場合
終了条件を満たすまで繰り返される
検索に成功する場合
検索に成功する場合
検索に成功する場合
検索に成功する場合
検索に成功する場合
検索に成功する場合
検索に成功する場合
検索に失敗する場合
検索に失敗する場合
検索に失敗する場合
検索に失敗する場合
検索に失敗する場合
検索に失敗する場合
検索に失敗する場合
検索に失敗する場合
検索に失敗する場合
検索に失敗する場合
検索に失敗する場合
提案システムの目標
•
•
•
•
•
シミュレーションに物理実験の結果を使用できる
重複計算を省ける
複数試行において計算時間を短縮できる
複数人で行われている計算を集積できる
計算負荷の著しく高い問題には近似サーバを利
用することで計算時間の短縮を図ることができる
遺伝的アルゴリズム(GA)
• 生物の進化をモデル化した
最適化手法
• 評価と遺伝的操作
(選択・交叉・突然変異)
特徴
• 確率的探索→複数回試行
• 探索空間の広い大規模問題に適応
• 個体の評価に膨大な時間を要する
GAを実装した提案システム
GAにおける近似手法
データベースの2つの遺伝子情報を用いる
遺伝子の違い 適合度
2 bit
15
2 bit
20
数値実験
• 複数試行での計算時間の短縮
• 重複計算の防止
• 近似の有効性
対象問題
• One Max問題
遺伝子の1の数が適合度
全て1が最適解
実験パラメータ
※実験はPCクラスタ上で実行
実験1・・・データベースの効果を検証
実験2・・・近似の効果を検証
複数試行での計算時間の短縮
重複計算の防止
近似の有効性
まとめ
• Grid環境に対応した最適化システムを提案した
≫ データベースによって重複計算が防止できる
≫ 近似によって待機状態のリソースを有効利用した
評価計算ができる
• GAを実装したシステムによって検討を行った
今後の課題
• Grid環境での実行
非均質なネットワーク環境
非均質な計算環境
動的な環境
• 他の最適化手法での検討
補足資料
現在のシステム概要
• 実験はPCクラスタ上で実行
• Database Server が Function Agent と
Approximation Server を兼任
• Database Server に格納できるデータに
限界がある
優先評価
• 近似 → 最適化計算の継続
• 評価計算に対して最適化計算が大幅に進む
→ 評価待ちの情報が大量に発生
• 探索の進んだ最新の情報の計算が行われない
• 最新の未評価の情報を優先的に計算することで
解探索を有効に進める
優先評価
優先評価
優先評価
近似,優先評価の有効性
補足資料 終わり
Gridでの問題点
• 資源は無限に広がるが,利用するには費用がか
かる →リソースの有効利用
• 通信状態が動的に変化
• 計算資源の性能は非均質
Gridが注目される理由
• 遠隔地の研究者同士の共同作業
• インターネットの普及によるネットワーク化
• 高性能計算機導入のコスト
Gridの研究
Gridの可能性
• スーパーコンピュータを超える大規模計算能力
• 膨大なデータを格納できる大規模データベース
科学技術計算分野への応用
最適化問題への適用
ダウンロード

PPT - 同志社大学