ＰＣクラスタにおける２個体分散遺伝的アルゴリズムの高速化

Presentation on theme: "ＰＣクラスタにおける２個体分散遺伝的アルゴリズムの高速化"— Presentation transcript:

1 ＰＣクラスタにおける２個体分散遺伝的アルゴリズムの高速化
－ SWOPP 松山 2000 － ＰＣクラスタにおける２個体分散遺伝的アルゴリズムの高速化 August 2 – 5, 2000, Matsuyama Summer United Workshops on Parallel, Distributed and Cooperative Processing ○ 谷村 勇輔 廣安 知之 三木 光範 同志社大学大学院 知的システムデザイン研究室

2 背 景 遺伝的アルゴリズム（GA） PCクラスタ 強力な最適化手法の１つ 計算負荷が高い Dual GAの並列モデル 普及しつつある
背 景 遺伝的アルゴリズム（GA） 強力な最適化手法の１つ 計算負荷が高い Dual GAの並列モデル PCクラスタ 普及しつつある 応用事例はそれほど多くない

3 遺伝的アルゴリズム（GA） 母集団 Start (初期化) 個体 突然変異 交叉 交 叉 突然変異 選 択 評 価 反復計算 確率的多点探索
終了 (解の発見) 良い解

4 並列GA 単純GA（SGA）の並列モデル 分散GA（DGA）の並列モデル 近傍GAの並列モデル
個体評価の計算のみを並列化する 分散GA（DGA）の並列モデル 母集団を複数のサブ母集団（島）に分割する 近傍GAの並列モデル 個体をあるトポロジに配置する ２個体分散遺伝的アルゴリズム （Dual Individual Distributed GA） １島の個体数を２とした分散GA その並列モデル

5 Dual GA 島数 ＝ 総個体数 ／ ２ 交叉 ： 同じ（ペアは一意に決まる） 選択 ： エリートと優れた子個体
突然変異 ： 他方と１ビットずらす 交叉 選択 エリート 遺伝子 変異

6 Dual GAの移住の仕組み（逐次） 並列モデル プロセス数 ＜ 島数 １つのプロセスに複数の島を割り当てる プロセス内 個体移住
ランダムに形成されるリングトポロジ 個体交換の操作を行う 並列モデル プロセス数 ＜ 島数 １つのプロセスに複数の島を割り当てる

7 Dual GAの移住の仕組み（並列） プロセス内 プロセス間 個体移住 島移住 1プロセス

8 Dual GAの利点 多様性を維持できる アルゴリズムの簡易化 並列化の粒度を柔軟に変更できる
SGAやDGAに比べて，解の探索性能が良い アルゴリズムの簡易化 ソート，乱数の発生回数を減らせる 並列化の粒度を柔軟に変更できる Dual GAをPCクラスタ上で並列化し，その評価を行う

9 対象問題 ４つのテスト関数を用いて検証する 関数名 形状 依存関係 F1 Rastrigin 多峰性 なし
関数名 形状 依存関係 F1 Rastrigin 多峰性 なし F2 Rosenbrock 単峰性 あり F3 Ridge 単峰性 あり F4 Griewank 多峰性 多少あり

10 基本的なパラメータ設定 島数 192島 プロセス数 任意 コーディング 10bit グレイコード 交叉手法 一点交叉
島数 島 プロセス数 任意 コーディング 10bit グレイコード 交叉手法 一点交叉 突然変異率 ／ 遺伝子長 移住トポロジ リング状 プロセス内の移住間隔 ５ プロセス間の移住間隔 ５倍 プロセス間の移住率 （最低１個体）

11 計算環境（PCクラスタのスペック） プロセッサ PentiumⅡ(Deschutes) CPUクロック 400MHz
# プロセッサ数 × 16 メモリ容量 Mbytes × 16 ネットワーク Fast Ethernet (100Mbps) プロセッサ間通信 TCP/IP, MPICH 1.1.2 OS Linux コンパイラ gcc (egcs )

12 並列モデルの効果（F1） 30次元のRastrigin関数 （最適値 0）

13 並列モデルの効果（F2） 30次元のRosenbrock関数 （最適値 0）

14 並列実行（１） 移住間隔の影響 プロセス内の移住間隔とプロセス間の移住間隔による影響を調べる プロセス間通信はできるだけ，少なく済ませたい
「数値実験」 プロセス数は16，各プロセスあたりの島数は12 それぞれの組み合わせ（計４パターン）を調べる プロセス内の移住間隔 ： 5 ， 10 世代 プロセス間の移住間隔 ： 50 ， 100 世代

15 並列実行（１） 移住間隔の影響 30次元のRastrigin関数 （最適値 0）

16 並列実行（１） 移住間隔の影響 30次元のRosenbrock関数 （最適値 0）

17 プロセス数と島数 プロセス数 ＜ 島数 各プロセスに対して島をどう割り当てるか？ 最も高速に解を求めるには？
最も効率よくプロセッサを使うには？ 192島を均質に割り当てて実験を行う

18 並列実行（２） 島の割り当て 30次元のRastrigin関数 （最適値 0）

19 並列実行（２） 島の割り当て 30次元のRosenbrock関数 （最適値 0）

20 考 察 プロセスに対して，どう島を割り当てるか？ 解の探索性能を見る 対象問題に依存 通信負荷の割合を見る 対象問題，および計算機環境に依存
実行前に予測するのは困難

21 シミュレーション例 （方法） 通信負荷の割合を事前に調べる 計算負荷 Ｓ 逐次モデル 100世代 並列モデル 100世代 Ｐ
オーバーヘッド 並列モデル 100世代 通信（移住） Ｐ 実行時間の短縮率 ＝ Ｐ ／ Ｓ

22 シミュレーション例 （結果） 逐次モデル100世代を並列モデルで行った結果

23 結 論 Dual GAの並列モデル 逐次モデルより解の探索性能が良い PCクラスタにおいて十分に高速化可能
移住間隔は適切に設定する必要がある プロセスに島をどう割り当てるかは経験的に決まる

24 あ い