Island GA

Island モデルは生物学的な棲み分けと分化の現象を土台に考案された. Island (島) は地理的な孤立環境の典型例である. 個体の集団は独立したいくつかのサブ集団に分け られ, 同一の最適化関数(＝適応度)をそれぞれ独自に最大化するように進化する. サブ 集団間には近接構造が定義され, 定期的(数〜数十世代間隔が一般的, この期間を epoch と呼ぶこともある)に最良の個体を交換する. この個体の交換を移住 ( migration) と呼ぶ.

Island GA にもいくつかの実現方法がある. それらの主な違いは, 近接構造の定義, 移 住の頻度, サブ集団内部での GA の方式である. しかし, これらはすべて以下の基本ア ルゴリズムのバリエーションとみなすことができる.

Step 1:

対象問題の適当なコーディングを定義し, 初期個体をランダムに発生 させ, 個のサブ集団に分割する.

Step 2:

サブ集団間の近接構造を定義する.

Step 3:

各々のサブ集団 SP ( )において Step 4 〜 Step 5 を繰り返す.

Step 4:

遺伝オペレータ(選択, 交配, 突然変異, 局所山登り, ・・・)を 世代にわたって適用する.

Step 5:

最良の個体を近傍の n 個のサブ集団に送る. それぞれのサブ集団か らそれらの最良の個体を受けとり, (最も適応度の低い方から, 最も似ている, ランダ ムに選んだ, ・・・) n 個の個体と置き換える.

最初の Island GA の研究の一つは Pettey, Leuze, Gregenstette [28] に よる. この研究での主要な課題は, 問題が複雑かつ個体の表現が長いために適応度の計 算に非常に時間がかかるという問題であった. この問題を解決するために, いくつかの サブ集団で並列に進化させるという方法を提案した.

同じ時期に Cohoon, Hegde, Martin, Richards [3] は古生物学の punctuated equilibria 理論に刺激され, 類似した並列GAモデルを発表した. この理 論は, 異域特化(共通の先祖を持っていても地理的に隔絶されると, 環境の違いから急 速に独自の進化を歩む)と, 平衡安定(一旦安定な環境に落ち着くとそれを持続させるよ うな力が働く)の二つの原理に基づいており, これらの原理を並列GAに採り入れた. 各 々のサブ集団は平衡安定に達するまで世代を繰り返し, 安定したら環境を変化させるた めにサブ集団の一部を近傍のサブ集団にコピーする.

やはり同時期に, 他のサブ集団に移住させる個体を, そのサブ集団の中で平均以上の適 応度を持つ個体の中からルーレット選択により確率的に選ぶという Island モデルが Tanese [38] によって発表された.

これらの Island モデルは, 以降多くの研究者から様々な修正案が報告されているが, 基本的には最初の Island モデルの枠組みでとらえることができる. 例えば, Kröger, Schwenderling, Vornberger [21] は各々のサブ集団が近傍の サブ集団の最良個体群と交配するモデルを提案した. サブ集団内での局所最適値を発見 すると, 近傍のサブ集団に局所最適個体をばらまき, 外部から個体群を採り入れる. 個 体の交換は非定期的に発生する. Mühlenbein, Schomisch, Born [27] は, Island モデルに局所山登り (local hill-climbing) という新しい遺伝オペレータを導入した. 局所山登りは適応度が実数関数の場合に、個体が持つ値を初期値として最急降下法に より個体近傍における局所最適解に移動するオペレータであり, 探索過程の最終段階で有効に働 くので, 適応度の分散を評価してサブ集団が安定状態に近付いたかを判定している.

図5.2 リング型の近接構造を持つ island GA