並列GAモデル[8]

多様性を維持することによって過剰収束問題を回避し, また並列計算機上での計算効率 を向上させるために, いくつかのモデルが提案され, 数値計算により実証されてきた. これらの並列GAモデルは次の二つのアプローチに大別される.

・coarse-grained GA (Island GA) :

 
いくつかの独立したサブ集団で並列に進化計算を行ない, 定期的に各々のサブ集団の中 の最も良い個体を近隣のサブ集団に移住させる.

・fine-grained GA (Cellular GA):

 
一つの集団として進化するが, 各々の個体は2次元(1次元)格子状に配列したセル内に置 かれ, 近傍の個体との間でのみ選択と交配が行なわれる.

これら二つのモデルは, それぞれ MIMD と SIMD という異なる並列アーキテクチャに適 しているは自ずから明らかである. CM-5 や nCUBE 等の MIMD マシンのそれぞれのプロ セッサは island GA のサブ集団に対応する. 一方, CM-2 やアレイプロセッサ等の SIMD マシンはプロセッサの配列がセルの配列に対応する.

並列計算機上での実装面からみると, 単純GAの選択や交配等の全体制御を一つの中央プ ロセッサで実行し, 最も計算時間のかかる適応度計算や(コーディング方法によるが)交 配を複数のプロセッサに振り分ける master-slave GA(micro-grained GA とも呼ぶ) も一種の並列GAと考えることができる(図5.1).

図5.1 適応度計算を並列化した master-slave GA

• a Island GA
• b Cellular GA