－ SWOPP 松山 2000 － ＰＣクラスタにおける２個体分散 遺伝的アルゴリズムの高速化 ○ 谷村 勇輔 廣安 知之 三木 光範 August 2 – 5, 2000, Matsuyama Summer United Workshops on Parallel, Distributed and Cooperative Processing 同志社大学大学院 知的システムデザイン研究室 背 景 遺伝的アルゴリズム（GA） – 強力な最適化手法の１つ – 計算負荷が高い – Dual GAの並列モデル PCクラスタ – 普及しつつある – 応用事例はそれほど多くない 遺伝的アルゴリズム （GA） Start (初期化) 評価 交叉 個体 突然変異 母集団 選択 反復計算 交叉 確率的多点探索 突然変異 終了 (解の発見) 良い解 並列GA 単純GA（SGA）の並列モデル – 個体評価の計算のみを並列化する 分散GA（DGA）の並列モデル – 母集団を複数のサブ母集団（島）に分割する 近傍GAの並列モデル – 個体をあるトポロジに配置する ２個体分散遺伝的アルゴリズム （Dual Individual Distributed GA） – １島の個体数を２とした分散GA – その並列モデル Dual GA • • • • 島数 ＝ 総個体数 ／ ２ 交叉 ： 同じ（ペアは一意に決まる） 選択 ： エリートと優れた子個体 突然変異 ： 他方と１ビットずらす エリート 交叉 選択 遺伝子 変異 Dual GAの移住の仕組み（逐次） プロセス内 個体移住 • ランダムに形成されるリングトポロジ • 個体交換の操作を行う 並列モデル – プロセス数 ＜ 島数 – １つのプロセスに複数の島を割り当てる Dual GAの移住の仕組み（並列） プロセス内 プロセス間 個体移住 島移住 1プロセス Dual GAの利点 多様性を維持できる – SGAやDGAに比べて，解の探索性能が良い アルゴリズムの簡易化 – ソート，乱数の発生回数を減らせる 並列化の粒度を柔軟に変更できる Dual GAをPCクラスタ上で並列化し，その 評価を行う 対象問題 ４つのテスト関数を 用いて検証する F1 F2 F3 F4 関数名 Rastrigin Rosenbrock Ridge Griewank 形状 多峰性 単峰性 単峰性 多峰性 依存関係 なし あり あり 多少あり 基本的なパラメータ設定 島数 プロセス数 コーディング 交叉手法 突然変異率 移住トポロジ プロセス内の移住間隔 プロセス間の移住間隔 プロセス間の移住率 192島 任意 10bit グレイコード 一点交叉 1 ／ 遺伝子長 リング状 ５ ５倍 0.1（最低１個体） 計算環境（PCクラスタのスペッ ク） プロセッサ CPUクロック # プロセッサ数 メモリ容量 ネットワーク プロセッサ間通信 OS コンパイラ PentiumⅡ(Deschutes) 400MHz 1 × 16 128Mbytes × 16 Fast Ethernet (100Mbps) TCP/IP, MPICH 1.1.2 Linux 2.2.12 gcc (egcs-2.91.61) 並列モデルの効果（F1） 30次元のRastrigin関数 （最適値 0） 適合度値 100 1プロセス 2プロセス 8プロセス 16プロセス 50 0 0 10000 20000 評価回数 30000 並列モデルの効果（F2） 30次元のRosenbrock関数 （最適値 0） 適合度値 150 1プロセス 2プロセス 8プロセス 16プロセス 100 50 0 0 10000 20000 30000 評価回数 40000 50000 並列実行（１） 移住間隔の影響 プロセス内の移住間隔とプロセス間の移 住間隔による影響を調べる プロセス間通信はできるだけ，少なく済ま せたい 「数値実験」 プロセス数は16，各プロセスあたりの島数は12 それぞれの組み合わせ（計４パターン）を調べる プロセス内の移住間隔 ： 5 ， 10 世代 プロセス間の移住間隔 ： 50 ， 100 世代 並列実行（１） 移住間隔の影響 30次元のRastrigin関数 （最適値 0） 適合度値 100 内5 - 外50 内5 - 外100 内10 - 外50 内10 - 外100 50 0 0 200 400 世代数 600 800 1000 並列実行（１） 移住間隔の影響 30次元のRosenbrock関数 （最適値 0） 適合度値 150 内5 - 外50 内5 - 外100 内10 - 外50 内10 - 外100 100 50 0 0 200 400 600 世代数 800 1000 プロセス数と島数 プロセス数 ＜ 島数 各プロセスに対して島をどう割り当てるか？ – 最も高速に解を求めるには？ – 最も効率よくプロセッサを使うには？ 192島を均質に割り当てて実験を行う 並列実行（２） 島の割り当て 30次元のRastrigin関数 （最適値 0） 適合度値 50 1プロセス 2プロセス 4プロセス 8プロセス 16プロセス 25 0 0 20 40 経過時間 [sec] 60 並列実行（２） 島の割り当て 30次元のRosenbrock関数 （最適値 0） 適合度値 80 1プロセス 2プロセス 4プロセス 8プロセス 16プロセス 40 0 0 30 60 経過時間 [sec] 90 考察 プロセスに対して，どう島を割り当てるか？ – 解の探索性能を見る • 対象問題に依存 – 通信負荷の割合を見る • 対象問題，および計算機環境に依存 実行前に予測するのは困難 シミュレーション例 （方法） 通信負荷の割合を事前に調べる Ｓ 計算 負荷 逐次モデル 100世代 オーバーヘッド 並列モデル 100世代 通信（移住） Ｐ 実行時間の短縮率 ＝ Ｐ ／ Ｓ シミュレーション例 （結果） 逐次モデル100世代を並列モデルで行った結果 1.2 逐次 0.01[sec] 逐次 0.05[sec] 逐次 0.1[sec] 計算時間の短縮率 1 0.8 0.6 0.4 0.2 0 0 4 8 プロセッサ数 12 16 結論 Dual GAの並列モデル – 逐次モデルより解の探索性能が良い – PCクラスタにおいて十分に高速化可能 – 移住間隔は適切に設定する必要がある – プロセスに島をどう割り当てるかは経験的に 決まる あ • い
© Copyright 2024 ExpyDoc
