MIMD アーキテクチャの Island GA

MIMD アーキテクチャはIsland GA の実装に最も適している. サブ集団内部の計算量に 対して, サブ集団間の通信量が圧倒的に少ないので, サブ集団をプロセッサに割り当て るだけで, かなりの高速化が望めるからである.

最初に Island GA を並列計算機上で実装したのは Tanese [38] である. Tanese は プロセッサが n-次元バイナリ立方体結合している hypercube 型 並列計算機 nCUBE 上を用いた(図5.4). 総個体数は約400と固定 し, 次元を 1〜6 (=64PE) に変化させたときの性能を, サブ集団が要した世代数の合計 で比較した. 総世代数は逐次型 GAとほぼ同じという結果を得た. これはプロセッサ数 にほぼ線形の速度向上である. サブ集団間の通信コストは総演算量の約3%と見積もっ た.

Pettey, Leutze [29]も8ノードの hypercube 型並列計算機上に実装し, ス キーマ定理が逐次型GAで保証する探索効率が並列GAにおいても成り立つことを数値的に 検証した.

前述した Mühlenbein, Schomisch, Born[27] の Island GA は, ``megaframe hypercluster'' と呼ばれる梯子型結合を持つ並列計算機上に実装された (図5.5). 1, 4, 8, 16プロセッサで速度向上を比較した. 興味深い 結果として, 比較的易しい問題では小さな速度向上しか得られなかったが, 困難な問題 では4から8プロセッサの場合に台数効果以上の超線形高速化が得られたことである.

図5.4 1〜4次元の hypercube 結合

図5.5 梯子型結合 (megaframe hypercluster)[27]