集団モデル

並列GAの代表的な集団モデルには, Island-GA, Cellular-GA の2種類があるが, 我々 は並列化が容易な Island-GA および単一集団の Simple-GA (単純GA)を実装した.

・Simple-GA (単純GA):

単一の集団内で進化計算を行ない, 並列性の存在しない従来 型のGAである. 実装上は Island-GA のサブ集団数が 1 の特別な場合と考える.

・Island-GA :

いくつかの独立したサブ集団で並列に進化計算を行ない, 同一 の最適化関数(＝適応度)をそれぞれ独立に最大化するように進化する. サブ集団間に は近接構造(topology)が定義され, 定期的(数〜数十世代間隔が一般的, この 期間をepoch と呼ぶ)に最良の個体を交換する. この個体の交換を移住 ( migration) と呼ぶ.

• 近接構造
• 移住方法

近接構造

サブ集団の近接構造として, 図図:Island-GAの近接構造の種類に示すようなリ ング型, 2次元格子型, 全結合型等がある. 高々数個体が数世代おきに移住すること により発生するプロセッサ間の通信量は,全体の計算量に比較すれば非常に小さ い. したがって, 近接構造の決定には通信コストの多少は考慮する必要がなく, 純粋 に並列GAの性能評価により決定すべき問題である. 我々は全結合型を採用した.

移住方法

単一のサブ集団内で世代交替を繰り返してゆくと, 次第に多様性が失われ探索が進ま なくなる傾向がある. そこで数世代おきに, 他のサブ集団から優秀な個体を導入する のが移住操作である. 各々のサブ集団について, ランダムに選んだサブ集団からラ ンダムに選んだ1つのパレート最適個体を移住してくるという方針を採用する.

図5.16 Island-GA の近接構造の種類