超多資源計算環境下における効率的な探索を実現するタブサーチメカニズム

本研究の目的は,並列処理と親和性の高い確率的最適化手法である遺伝的アルゴリズム(GA)を対象として,超大規模並列環境に適したメカニズムを考案することである.PCクラスタ,グリッドなどの多資源計算環境にGAを適用する際には,GAに膨大な計算リソースを有効に扱え,効率良く探索できるメカニズムが必要となる.本研究では,少ない計算量で有望な領域を集中して探索するといった特徴に加え,全数探索のような計算コストに対する探索領域のスケーラビリティを保証するメカニズムを有するGAを考案している.今年度は,次の研究実績を得た.1.GAに関する研究形質遺伝および獲得のための近傍探索に基づく交叉の汎用性を検証するため,NKモデルを用いて解探索の挙動の解析した.NKモデルは,ランドスケープの複雑さをパラメータ調節できる単純かつ柔軟な解析のためのモデルであり,多くの組合せ最適化問題がNKモデルに帰着される.NKモデルに適用することで,本手法がランドスケープの複雑さによらず,有効な解生成が可能であることを示した.また,データベースを利用することで,解探索の性能が向上することを示した.2.既探索領域データベースの応用に関する研究タブリストとして利用するデータベースについて,より大規模な問題および環境に対応させるため,データベースでの解表現を拡張した.これに伴い,GAにおける解のコーディングに変更を必要とするが,解探索に影響を与えないことを示した.実離散最適化問題として,規模が比較的大きい複雑ネットワーク解析,およびタンパク質立体構造予測に適用し,期待通りの挙動を示すことを確認した.なお,実験環境には,PCクラスタおよび,規模が拡大した同志社大学のキャンパスグリッド(United Devices社の商用ミドルウェアGrid MPを利用したシステム)を用いた.

本研究の目的は,並列処理と親和性の高い確率的最適化手法である遺伝的アルゴリズム(GA)を対象として,超大規模並列環境に適したメカニズムを考案することである.PCクラスタ,グリッドなどの多資源計算環境にGAを適用する際には,GAに膨大な計算リソースを有効に扱え,効率良く探索できるメカニズムが必要となる.本研究では,少ない計算量で有望な領域を集中して探索するといった特徴に加え,全数探索のような計算コストに対する探索領域のスケーラビリティを保証するメカニズムを有するGAを考案している.今年度は,次の研究実績を得た.1.GAに関する研究形質遺伝および獲得のための近傍探索に基づく交叉の汎用性を検証するため,NKモデルを用いて解探索の挙動の解析した.NKモデルは,ランドスケープの複雑さをパラメータ調節できる単純かつ柔軟な解析のためのモデルであり,多くの組合せ最適化問題がNKモデルに帰着される.NKモデルに適用することで,本手法がランドスケープの複雑さによらず,有効な解生成が可能であることを示した.また,データベースを利用することで,解探索の性能が向上することを示した.2.既探索領域データベースの応用に関する研究タブリストとして利用するデータベースについて,より大規模な問題および環境に対応させるため,データベースでの解表現を拡張した.これに伴い,GAにおける解のコーディングに変更を必要とするが,解探索に影響を与えないことを示した.実離散最適化問題として,規模が比較的大きい複雑ネットワーク解析,およびタンパク質立体構造予測に適用し,期待通りの挙動を示すことを確認した.なお,実験環境には,PCクラスタおよび,規模が拡大した同志社大学のキャンパスグリッド(United Devices社の商用ミドルウェアGrid MPを利用したシステム)を用いた.