進化的計算手法の並列計算機への実装 三木 光範 日本機械学会２０００年度年次大会先端技術フォーラム 進化的計算手法とその応用の新展開 進化的計算手法の並列計算機への実装 Implementation of Evolutionary Computation to Parallel Computers 同志社大学 工学部 三木 光範

進化的計算手法 生物の進化のプロセスを工学的なシステムの 最適化に利用 特徴 ・解の確率的摂動 ・適合度による選択

代表的な進化的計算手法 進化戦略 遺伝的アルゴリズム 遺伝的プログラミング シミュレーテッドアニーリング 複雑な実問題にも適用可能 Evolutional Strategy Genetic Algorithms Genetic Programming Simulated Annealing 複雑な実問題にも適用可能 良好な解が得られる

進化的計算手法の問題点 並列化 並列処理の利点 計算時間の短縮 計算モデルの変化に伴う解精度の向上 一般に，進化的計算手法では膨大な反復計算が必要 計算負荷が大きい 並列化 並列処理の利点 計算時間の短縮 計算モデルの変化に伴う解精度の向上

計算機の高速化 MHz CPUの開発競争 クロック周波数は 1GHz以上に 汎用PCの性能の 飛躍的向上

PC Cluster 複数の汎用PCをネットワークで接続（クラスタ化） 並列ライブラリを用いた並列処理 ネットワーク 並列ライブラリ Ethernet (100BASE-T, Myrinetなど) 並列ライブラリ MPI・PVM コストパフォーマンスの高い並列計算環境

PC Clusterのコストパフォーマンス PC Cluster 　　400 MFLOPS(8node) ¥ 1,000,000 ~ ¥ 1,600,000 Fujitsu VPP5000　　4137.30 MFLOPS ¥ 4,400,000 (月額レンタル料)

並列計算機のネットワーク 専用並列計算機 PC Cluster 計算機の通信性能やネットワークトポロジ に適した計算モデルの設計が重要 高速なネットワーク・独自のトポロジ 計算モデルを最適化させればさらに高速に PC Cluster 低速なネットワーク・通信のオーバヘッド大 通信量の少ない計算モデルが適する 計算機の通信性能やネットワークトポロジ に適した計算モデルの設計が重要

GAの並列化 生物の進化の過程を工学的に応用した最適化手法 並列モデル 個体の評価の計算負荷が高い アルゴリズム自体に並列性が高い 粒度によって分類が可能 細粒度：マスタ－・スレーブモデル，セルラーモデル 粗粒度：島モデル

分散GA（島モデル） 母集団を複数のサブ母集団に分割 一定世代ごとに移住 各サブ母集団が独自の 領域を探索 サブ母集団を各プロセッサ に割り当て 一定世代ごとに移住 通信の頻度は低い 特徴 良好な解を速く求めることができる

マスタースレーブモデル（細粒度） 評価計算のみを並列化 評価 ：スレーブで処理 PE master slave 評価以外 ：マスターで処理 評価　　　　：スレーブで処理 PE master Shared memory 評価 slave 評価以外　：マスターで処理 特徴 計算量は逐次モデルと等しい 1CPUがマスターとして必要 通信の頻度が高い

セルラーモデル（細粒度） 遺伝的操作を局所的に実行 各個体は空間上のある位置 に配置 近傍の個体との間のみで 交叉・選択を行う 特徴 局所的なルールだけで動作 を記述可能 同種のトポロジを持つ 超並列アーキテクチャに向く

GAの並列化のメリット 台数効果による高速化 アルゴリズム的高速化 並列計算機の計算パワーを利用 早熟収束問題の回避 並列分散モデルによる多様性の維持 島モデル・セルラーモデル

台数効果による高速化 分散GA（島モデル）における計算速度

アルゴリズム的高速化（分散の効果） 対象問題 単一母集団ＧＡ 分散ＧＡ 移住なし Rastrigin関数（４変数） 文献４）三木・廣安・金子 SP_0 Convergence ratio Generations SP_1 対象問題 SP_2 Rastrigin関数（４変数） SP_3 Convergence ratio Generations

アルゴリズム的高速化（移住の効果） 分散ＧＡ 移住なし 分散ＧＡ 移住あり 文献４）三木・廣安・金子 SP_0 SP_0 SP_1 SP_1 Convergence ratio Convergence ratio Generations Generations

アルゴリズム的高速化（適合度の推移） SGA - 400個体 早熟収束によって最適解は PDGA - 50個体 8サブ母集団 　早熟収束によって最適解は 　得られない PDGA - 50個体　8サブ母集団 ・各サブ母集団では局所探索 ・移住によって多様性を保つ　　 対象問題 ：10変数Rastrigin関数 パラメータ： 交叉率 0.6，突然変異率 0.01， 移住率 0.3，移住間隔 5

シミュレーテッドアニーリング（SA） 金属の焼きなましを模擬した最適化法 温度パラメータによって解の摂動を制御 エネルギーと呼ばれる目的関数が増加する方向へ の解の推移を，確率的に許す．（改悪の受理） 高温時 低温時 Opt

SAの並列化 並列モデル SAはマルコフ連鎖をたどる 逐次性が強く並列化は困難 ・逐次SAを並列実行，解を交換 独立型並列SA 同期 SA 独立型並列SA 定期同期型並列SA 受理時同期型並列SA 温度並列SA ・温度の異なるSAを並列実行，解を交換

温度並列SA（TPSA） アルゴリズム 確率的に良質な解が低温PEに移動 特徴 ・通信量は少ない ・温度スケジュールの自動化 高温 低温 最低温 確率的に良質な解が低温PEに移動 解交換 最高温 特徴 ・通信量は少ない ・温度スケジュールの自動化

温度並列SAの利点 逐次SA 温度並列SA 温度スケジュールは 単調な減少 最適なスケジュール の決定は困難 Time T1 T2 T3 T4 T5 Initial Solution 温度スケジュールは 単調な減少 最適なスケジュール の決定は困難 温度並列SA Initial Solution Time T1 T2 T3 T4 T5 T6 PE1 PE2 PE3 PE4 PE5 PE6 解自身が自動的に温度スケジュールを決定

温度並列SAの性能 6.94E-04 6.08E-04 トラス構造物の最適化における 温度とトラスの総体積の履歴

まとめ 進化的計算手法は様々な実問題に有効 進化的計算手法は計算負荷が高く並列化は重要 安価な並列計算環境 ＰＣ Cluster 実装する並列計算機に応じた計算モデルの設計 台数効果による高速化とアルゴリズム的高速化