メタヒューリスティックスの分散並列処理と自律分散最適化に関する研究

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

メタヒューリィスティックスの分散並列処理として,解空間の地形情報を考慮した並列遺伝アルゴリズムの実行手法を開発した.複数の遺伝アルゴリズムプロセスが独立して実行を進めて行くが,解の改善が見られなくなったら(局所解での飽和状態),他のプロセスに協調を求めるものである.また,大規模複雑な組み合せ最適化問題を解く手法として階層型分散並列遺伝アルゴリズムを開発した.これは上位層の遺伝アルゴリズムと下位層の遺伝アルゴリズムが協調しながら解を改善して行くものである.莫大な計算量が必要のため,並列化による高速化が有効であった.両アルゴリズムをPCクラスタ上にMPICHを用いて実装し計算機実験を行った結果,両方とも有効性が確かめられた.さらに階層型分散並列遺伝アルゴリズムをバイオインフォマティックスにおける遺伝子ネットワークの同定問題に適用し,その実用可能性も確認できた.複数倉庫配送経路問題における最適化においては,経路作成プロセスを倉庫毎に配置し,それぞれが割当て配送先について経路計画を立てる手法を開発した.経路作成プロセス同士は地理情報(距離情報)を考慮して,配送先の移動を減らすことを行っている(近傍構造の削減).また,各倉庫における経路計画では,従来法であるセービング法を改良した拡張セービング法を用いている.これにより時問制約を考慮した経路計画を効率良く行えるようになった.自律分散最適化の手法として,大域分散環境で動作する遺伝アルゴリズムを開発した(GRID-GA).提案手法は,地理的に離れた計算資源間で協調しながら最適化計算を進めるものである.このような状況では通信オーバーヘッドが負担になるので,マスターノードによる協調は現実的では無い.そこで本手法では,隣接プロセス同士のみで自律的に協調が行える仕組みを開発した.