移住(Migration)は分散遺伝的アルゴリズム(Distributed Genetic Algorithms : DGA)に特有の操作であり,
島間で個体を交換するために行う.
この操作により,個々の島が独立しておこなっている局所探索の結果を個体集団全体で交換することができる.
ここでは,移住に関するパラメータである
移住率,
移住間隔,
移住機会,
移住トポロジ,
移住個体の抽出・挿入方法について説明する.
移住率
各島内の個体群に占める移住個体の割合のことを移住率(Migration Rate)という.
交叉率や突然変異率はどちらも確率であったが,移住率は割合である.
移住間隔
移住操作と移住操作の間隔のことを移住間隔(Migration Interval)という.
移住間隔が1の場合,毎世代移住を行うことになる.
移住機会
DGAにおいて移住操作は島間の個体情報の交換するためにある.
そのため移住操作は選択の直後に行うことが多い.
しかし,移住を他の遺伝的操作の直後に行うことも考えられる.
選択の後
選択の後に移住を行う.
交叉の後
交叉操作の後に移住を行うもの.
後述の移住個体の抽出方法としてBestやWorstを選択した場合には移住の前に評価を行う必要があるため,
選択の後に移住を行うモデルと比較して同じ評価計算回数でも世代数が異なる.
突然変異の後
突然変異の後に移住を行うもの.
移住トポロジ
移住操作を行う際にまず決めなければならないのは,どの島からどの島へ移住するか,ということである.
これを移住トポロジと呼ぶ.
移住トポロジとして以下のものについて説明する.
Random Ring
この手法は,移住元と移住先を結んだ線が1つのリングを形成するように移住先を定めるというものである[1].
また,各島からの移住先は移住操作の度に変化する.
Fig.1は島ごとにIDが与えられている状態でのRandom Ringの概念図である.
左の図は島をIDが順番に並ぶように配置したものであり,移住経路がランダムになっていることを示している.
右の図は経路に従って島を配置したものであり,移住経路が1つのリングを形成していることを示している.
bi-Directional Ring
この手法では,あらかじめ島にIDが与えられている.
その上で,各島はIDが隣り合っている2つの島と移住を行うというものである[2].
Fig.2はこの手法の概念図である.
この図において島1からは,1→2→3→4→5→6→7→8→1と1→8→7→6→5→4→3→2→1の2つのリングが形成されている.
このリングは一定であり,移住の度に変わることはない.
例えば島1には,移住の度に島2と島8から個体が移住してくることになる.
+1 +2 Topology
この手法では,あらかじめ島にIDが与えられている.
その上で,島iは島i+1と島i+2の2つの島から移住個体(Migrant)を受け入れるというものである[2].
Fig.3はこの手法の概念図である.
この図において島1からは,1→8→7→6→5→4→3→2→1と1→7→5→3→1の2つのリングが形成されている.
このリングは一定であり,移住の度に変わることはない.
例えば島1には,移住の度に島2と島3から個体が移住してくることになる.
+2 +3 Topology
この手法では,あらかじめ島にIDが与えられている.
その上で,島iは島i+2と島i+3の2つの島から移住個体を受け入れるというものである[2].
Fig.4はこの手法の概念図である.
この図において島1からは,1→7→5→3→1と1→6→3→8→5→2→7→4→1の2つのリングが形成されている.
このリングは一定であり,移住の度に変わることはない.
例えば島1には,移住の度に島3と島4から個体が移住してくることになる.
Ladder
この手法では島にはあらかじめIDが定められている.
また,島数は偶数でなくてはならない.
Fig.5はこの手法の概念図である[2].
この図において島1からは1→7→5→3→1という島IDが奇数の島を結ぶリングと,
1→2→1という偶数の島とのリングの2つのリングが形成されている.
このリングは移住の度に変わることはない.
例えば島1には,移住の度に島3と島2から個体が移住してくることになる.
移住個体の抽出方法
移住先に次いで,移住個体についても何種類かの選び方が考えられる.
ここでは,島a, b, cで移住がa→b→cのように起こるとき,
島bから島cに対して移住する個体をEmigrantと呼び,
島aから島bに移住してくる個体をImmigrantと呼ぶ.
本節ではEmigrantの抽出方法について述べる.
Random
島内の個体の適合度に関係なく,ランダムに選ぶもの.
Best
島内の最も適合度の高い個体から順に選ぶもの.
Worst
島内の最も適合度の低い個体から順に選ぶもの.
移住個体の抽出方法
本節ではImmigrantの挿入方法について述べる.
Hole
Emigrantが抜けた場所を穴埋めするもの.
この挿入方法を選択する場合,移住の前後で母集団全体を編成する個体は変化しない.
Random
島内の個体の適合度に関係なく,ランダムに選ぶもの.
この挿入方法を選択した場合,移住の前後で母集団全体を編成する個体が変化する.
Best
島内の最も適合度の高い個体から順に選ぶもの.
この挿入方法を選択した場合,移住の前後で母集団全体を編成する個体が変化する.
また,Emigrantの抽出方法としてBestを選択した場合,
Immigrantの挿入方法としてHoleを選択するのとBestを選択するのは同義である.
Worst
島内の最も適合度の低い個体から順に選ぶもの.
この挿入方法を選択した場合,移住の前後で母集団全体を編成する個体が変化する.
また,Emigrantの抽出方法としてWorstを選択した場合,
Immigrantの挿入方法としてHoleを選択するのとWorstを選択するのは同義である.
[1] J.Nang and K.Matsuo, "A Survey on the Parallel Genetic Algorithms",J.SICE,Vol.33,No.6,1994
[2] Erick Cant'u-Paz, "A survey of parallel genetic algorithms",Calculateurs Paralleles,1998