並列GAの分類学

• 単純GAの改良
• 並列GAの分類
• Injection-Island GA (iiGA)
• 数値実験結果と考察

Lin, Punch III, Goodman [35] は各種の並列GAの特徴を整理・分類し, グラ フ分割問題について数値実験的評価を行なった. その結果, (1)並列GAの単純GAに対す る優位性, (2)island GA では多数のサブ集団間で非同期の移住が効率的, (3)移住先は 近接構造によらず個体の類似性によって選ぶ方がよいことが分かり, (4)新しい並列GA モデル Injection Island GA を提案した.

単純GAの改良

単純GAの過剰収束問題の回避や演算量削減のために, 従来から遺伝オペレータにはさま ざまな改良法が提案されてきた. 確率的なルーレット選択に対しては, 適応度順位 i の一次式 ai+b で選択確率を決定する線形ランク選択, モンテカルロ法に近い一様ランク選択, Simulated Annealing を応用した ボルツマントーナメント選択などがある.

交配に対しては, 子個体に似ている個体と置換する crowding scheme, 一つの遺 伝子型は最大1個体のみ存在する uniqueness 操作, 似ている個体群の平均値に 比例した選択確率を持つ sharing 関数, 似ている個体同士しか交配できない表 現型比較関数などがある.

並列GAの分類

並列GAは個体と集団のトポロジーから mgGA, fgGA, cgGA に分類できる. ノードごとに 個体(個体群)を割り当て, 適応度計算のみを並列化した Micro-Grain GA(mgGA) は, 適 応度計算が支配的な問題では有効であるが, 過剰収束の問題は扱っていない. ノードご とに個体を割り当て, 各個体はオーバーラップした複数の部分集団に属する Fine-Grain GA(fgGA) は部分集団の適当な近接構造のの設定が難しい. 独立したサブ集 団を持つ Coarse-Grain GA(cgGA) はサブ集団間の通信は比較的小さい.

Coarse-Grain GA はさらに移住方法, 接続方法, 同質性の3つの側面から分類できる.

・移住方法:

 

・接続方法:

 

・同質性:

 

Injection-Island GA (iiGA)

筆者の提案する非同期, 固定or動的接続, 異質ノードの新しい island GA である. ビットをいろいろなブロック単位に縮約し, 解像度の異なる部分集団から構成される. 個体の移住は低解像度の部分集団から高解像度の部分集団へのみ行なわれる. 移住方法 には, Simple(最高解像度のノードへのみ移住), Complete(上位解像度の全ノードへ 移住), Strict(自分の子ノードへのみ移住), Loose(子ノードと最高解像度ノードへのみ 移住)がある. iiGAのメリットは, 以下のようにまとめられる.

• 低解像度のビルディングブロックは, 低解像度で直接発見できる.
• 低解像度の探索空間は小さいので, 早期に良い解を発見できる.
• 親子関係にあるノードは同じ探索空間を持つので, 高解像度で精緻化できる.
• 部分問題への分割と部分最適化を実現している.
• ブロック分割不適当の危険をさまざまなブロックサイズの並列化で回避している.

数値実験結果と考察

48,96頂点の3-CCC(Cube-Connected-Cycles)構造を持つ, マルチレベルグラフの分割問 題を対象にした. 集団サイズは5000個体で, 1/5/10/25個のサブ集団に分割した. サブ 集団の近接構造は同期/非同期島(一次元リング接続), 孤立島, 動的接続(集団の類似性 に依存)である. 単純GAでは1000世代で最適解に達したものはないが, 25-部分集団では すべて最適解に到達した. 探索性能は部分集団の数に関係する. 非同期移住により, ほ ぼノード数に比例した高速化が達成された. 移住なしの孤立島モデルもかなり良い結果 が出たことは興味深い. iiGA は, 最も高性能の cgGA よりもさらに良く, 将来性が期 待できる.