Next: Up: Previous:

SIMD アーキテクチャの Cellular GA

Cellular GA の SIMD アーキテクチャ上の実装はそれほど報告されていない. 最初に報 告されたのは Spiessens, Manderick [23] [37] である. 2次元グリッド状に接続された1024プロセッサ(32×32)の DAP (Distributed Array Processor) 計算機上に実装した. SIMD型の超並列計算機上での Cellular GA の単純GA に対する高速化率を, 総個体数 n, 近傍のサイズ s, 遺伝子型の長さ l の関数 としてオーダ計算により求めた(表5.1). 選択および合計欄に2種 類の値があるのは, 確率選択やランク選択, トーナメント選択など選択方法によっ てオーダが変わるからである.

table144

また, Collins [4] の文献では 16K プロセッサの CM-2 上で, 1個体を1プロセッサに割り当てて実装した. 単純GAに対し, 適応度の評価回数で比較しても数倍の高速化が得られており, 並列度の高い SIMD 型超 並列計算機上に実装しているので, 逐次計算機上の単純GAと比較すれば実質数千倍の高 速化が得られている計算になる.



Mitsubishi Research Institute,Inc.
Mon Feb 24 19:32:36 JST 1997