遺伝的アルゴリズム概説(3) -- 分散遺伝的アルゴリズム


: back :

概要

分散遺伝的アルゴリズム(Distributed Genetic Algorithm : DGA)はGAの母集団を複数の分割母集団(島)に分割し, 各島内で遺伝的操作を行うというGAの並列化モデルの1つである. DGAでは各島間で解探索の情報を交換するために,移住という操作を行う. Fig.1に移住の概念図を示す.
Fig1.移住の概念図
Fig1. 移住の概念図

流れ

DGAの流れをFig.1に示す.SPGAの流れと異なるのは移住(Migration)という操作が加わった点である.
Fig2.DGAの流れ図
Fig2. DGAの流れ図

移住とは

移住は,数世代に一度,各島内で選ばれた1つまたは複数個の個体(移住個体 : Migrant)を別の島と交換することで実現される. このとき,各島内における移住個体の割合を移住率(Migration Rate), 何世代おきに移住するかを移住間隔(Migration Interval)と呼ぶ.

移住の意味

集団遺伝学において,地理的種形成というものがある. これは,元々同じ種であったものが地殻変動などによって地理的に隔離される状態が続くと, それぞれの集団の中で独自の遺伝子変化が進むためにいずれは生殖的な隔離に至る,というものである. 同一の島の中でのみ交叉が行われるという点で,DGAはこれと類似している. それぞれの島で独立に探索が進むため,各島で個体は大きく異なり,母集団全体としての多様性が維持される. ここで,DGAは同じ母集団サイズを持つSPGAと比較して1島あたりの個体数が少ないため,島内では早熟収束が起こりやすくなる. しかし,移住によって他の島で成長した遺伝子情報を持つ個体を取り入れることにより島内での多様性も維持できる.

解探索の特徴

Fig.3はDGAにおける解探索の様子である.個体の配置はSPGAの解探索の様子を示した図と同一であるが, 島1では局所解B,島2では局所解B,島3では局所解Cというように, 島ごとに異なった局所最適解に向かって探索が行われるため,最適解に到達する可能性が高くなる. しかし,移住回数が過多な場合には局所解に向かう個体によって最適解に近い個体の遺伝子情報が破壊されてしまうことが考えられる.
Fig3.DGAにおける解探索の様子
Fig3. DGAにおける解探索の様子

問題点

DGAは,前述したGAのもつ問題点のうち,並列化によって「高い計算負荷」を, 母集団を分割することによって「早熟収束による局所解への収束」を解消することができる. しかし,「パラメータ設定の複雑さ」については以下に示す新たな問題点も現出してきた.

設定すべきパラメータの増加

移住を行うために移住率と移住間隔という新たなパラメータが必要となる. これらのパラメータは他のパラメータと同様に解探索能力に大きな影響を与える. しかも,最適な移住率,移住間隔の設定は対象問題によって異なると考えられるため, 最適なパラメータを設定するために多くの予備実験が必要となる.

既存のパラメータの再検討

SPGAとDGAでは解の探索メカニズムが異なるために, SPGAに存在したパラメータでもDGAでは最適な設定が異なる.
: back :

: PDGA Research Group : Top Page :
(1) 2001.09.14