Cellular GA

局所的なルールだけで動作が記述される分布系モデルは, 超並列アーキテクチャの最も 得意とする問題である. 複雑系の動特性を多数の要素の局所的な相互作用によって記述 し解析する共同現象(synergetics)の研究からセルラーオートマトンが生まれ, 並列計 算の汎用的な枠組みを提供した. そこからセルラーオートマトンをGAに適用する試みが なされ, 効率的な計算が可能であることが数値実験により示された.

Cellular GA は空間性 (spatiality) という概念で特長づけられる. 集団中の各 個体はそれぞれ空間上のある位置に配置される. 通常, 空間は2次元グリッドで, 境界 効果を避けるためにトーラス状の配列とする. 個体の空間的配置を与えることにより, 個体間に近接構造が定義される. 2次元グリッドでいえば, 最も近接している個体は必 ず8個体ある. 遺伝オペレータは確率的局所的な更新ルールとみなされ, 大域的な制御 構造はもはや必要なくなる.

各セルは1個体しか入れないので, 選択はセルごとに, そのセルの個体と近傍セルの個 体の間で実行される. 交配は近傍の個体間で行なわれ, 突然変異は単純GAと同じである. Cellular GA も多くのバリエーションが存在するが, 基本的アルゴリズムは以下のよう に整理できる.

Step 1:

対象問題の適当なコーディングを定義し, 初期個体をランダムに発生 させ, グリッド上の各セルに配置し, 各々の適応度を計算する.

Step 2:

各々のセル c について Step 3 〜 Step 5 を繰り返す.

Step 3:

適応度を計算する.

Step 4:

セル c の近傍のセルから適応度に応じて個体を一つ選び, セル c の個体と交配し, 子個体をセル c に割り当てる.

Step 5:

セル c の個体に突然変異を適用する.

初期の研究の一つは Manderick と Spiessens [23] から発表された. fine-grained GA と単純GAの性能を比較し, fine-grained なアプローチの方がより広 い空間を探索していることを示した. これは選択が局所的なため選択圧力が緩和される ことによる. 逆に比較的単純な問題では余分な探索が発生するために効率が落ちること もある. この研究での興味深い成果として, 単純GAでは存在する最適集団サイズが並 列GAでは存在しないこと, すなわちプロセッサ数に比例して集団サイズを大きくすれば 性能/効率が向上することがある. また, 近傍のサイズとの関係について, サイズが大 きくすると単純GAに近付くが, 狭い範囲の近傍(9, 25セル)で十分にロバストな性能が 得られると結論づけている.

同時期に Mühlenbein [26] も fine-grained GA のシステム ASPARAGOS を発表し, 組合せ最適化問題の一種である二次割当問題 (QAP: Quadratic Assignment Problem) に適用した. このシステムでは, 各個体はそれぞれ局所山登りを 行ない, 選択は順位付けに基づき, 交配は投票手続きに変更されている. 局所山登りは 新しい遺伝オペレータとみなされており, 選択, 交配, 突然変異は局所最適値に到達し た後に適用し, 新たな局所最適値の発見のための greedy huristics として使わ れた. ASPARAGOS は Gorges-Scheleuter と von Laszewski [24] [13] [39] により他の組合せ最適化問題(巡回セール スマン問題, グラフ分割問題)に適用された. 困難な問題においては単純GAよりも良い 探索結果が得られており, パラメータ設定にもよりロバストであることが示された.

図5.3 二次元グリッド型の近接構造を持つ cellular GA