改良 cellular GA

Maruyama, Hirose, Konagaya [25] は, 非同期で通信コストの小さい cellular GA モデルを発表した. このモデルではプロセッサごとに1個の活性 ( active) 個体とバッファ中の K 個の非活性 (suspended) 個体を持つ. 活性個 体はランダムに選んだ他のプロセッサに移住させ, 移住してきた個体は非活性個体とし て待機する. 非活性個体が定数 K を越えると適応度の低い個体が削除される. 活性個 体と非活性個体の一つを交配, 突然変異させ, 活性/ 非活性個体全体を中でルーレット 選択を行ない次世代の活性個体を選ぶ. このとき活性化個体が選ばれなければプロセッ サ内から削除する (図5.11).

このモデルは, 活性状態にある個体は一つのプロセッサで必ず一つであり, ルーレット 選択はバッファで待機している非活性個体と行なう点が新しい. バッファ中の非活性個 体をサブ集団とみなせば, island GA の変形とみることもできる.

関数最適化問題とグラフ分割問題に適用し, 過去にプロセッサ間通信が高速な並列計算 機用に開発した並列GAとほぼ同程度の性能を持ち, 通信コストが非常に低いのでLAN間 接続のワークステーション群でも線形に近い高速化が得られた.

図5.11 Maruyamaの改良型 fine-grained GA[25]