木構造のネットワーク上における並列進化計算

木構造のネットワーク上における並列進化計算
A Study on Parallel Evolutionary Computation on Tree Topology Networks
088510A 宮城 隼人
指導教員:
研究背景と目的
1
名嘉村 盛和
上記の best[i] は i 番目の遺伝子座，LR は確率ベクトル
遺伝アルゴリズム (Genetic Algorithms: GA) は並列化
の学習率を示している.
により計算速度の向上だけではなく探索の効率化も図れ
1
るため，著者等はツリートポロジー上の移住を有する並列
PV
モデルを提案し性能評価を行ってきた．一方，確率論に基
づいた分布推定アルゴリズム (Estimation of Distribution
2
3
4
0.5 0.5 0.5 0.5
1
2
4
0.4 0.6 0.6 0.6
Create
the population
Algorithms :EDA) が，数理的に扱いやすい進化計算手法
として注目を集めている．本研究では，EDA についても，
ツリートポロジー上の分散並列処理手法を開発している．
3
Learning from
Best Individual
0
1
1
1
Selected
Best Individual
一方，文献 [1] では、進化速度と集団の分散は比例すると
いう Fisher の定理を GA に適用した興味深い解析を行っ
ており，GA においても Fisher の定理が成立することを
理論的に導きだしている．本稿では，ツリートポロジー上
図 1: PBIL における確率ベクトルの更新
の GA と EDA の並列処理手法の性能を評価するために，
Fisher の定理に基づいて，評価値の分散と移住の効果との
関係を調べるものである．
2.1
ツリートポロジー
ツリートポロジーの代表的な例として，ライン，スター，
バランスツリー，サイドツリーが挙げられる. ラインは根
予備知識
2
2.3
から葉までの長さが大きく，スターは最も葉の数が多いと
遺伝的アルゴリズム
GA はランダムな値を持つ個体を生成し，母集団を生成
し，環境の適応度の高い個体が高確率で生き残れるように
選択される. 更に，個体間の交叉や突然変異によって，新
いう両極端のトポロジーである. 図 2 にこれらのトポロ
ジーを表しており，矢印は移住が行われる方向，丸印は島，
そして，黒丸印は根の島を示しており最も移住の効果を受
ける島である．
しい個体が形成される. このような操作が繰り返されるこ
とによってより良い個体を生成することが期待できる.
GA の並列モデルの代表例として，島モデルとよばれる
分散 GA が挙げられる. このモデルでは，島と呼ばれる，
複数のサブ母集団に分割し，それぞれ独立して遺伝操作を
(a) Star
(b) Line
実行し，移住間隔ごとに個体の移住を行う.
2.2
Population Based Incremental Learning
Population Based Incremental Learning(PBIL) とは，
EDA の一つであり，強化学習を元にした探索手法である.
(c) Balanced binary tree
特徴として，全個体を確率ベクトルとして扱うことが挙げ
られる. この確率ベクトルは母集団におけるビット 1 の割
(d) Sided binary tree
図 2: ツリートポロジーの種類
合を示しており，各遺伝子座に対応している.
PBIL の手順は，まず確率ベクトル PV の各要素を 0.5
で初期化を行う. 次に PV に基づいて集団を生成し，各個
体の順位付けを行う. 生成された個体群の中から最もよい
個体 best を用いて，式 (1) に基づき PV を更新する.
ツリートポロジーに基づく並列進化計算手法
3
3.1
遺伝的アルゴリズムの並列手法
ツリートポロジーに基づく移住付き島モデルの並列手法
として，まず各島に予め割当てられた GA プロセスを実
P V [i] = (P V [i] × (1.0 − LR)) + (LR × best[i])
(1)
行する．各島は予め設定されたツリートポロジーの各ノー
ドに対応づけられるので，GA プロセス間に親子関係が定
義される．各 GA プロセスは，一定間隔（移住間隔）毎
に，エリート解がアップデートされていれば親プロセスに
3.8
エリート解そのものを送信する．子プロセスから染色体を
3.6
送られた親プロセスは，最も悪い解と受信したエリート解
fitness
を入れ替える．これが本並列手法における移住となる．容
3.4
易に想像できるように，この並列 GA の性能は移住のベー
3.2
スになるツリートポロジーに大きく影響を受けることに
なる
3.2
GA-LINE
EDA-LINE
Single GA
Single EDA
3
分布推定アルゴリズムの並列手法
0
1000
2000
3000
4000
5000
generation
PBIL を島モデルに基づいて並列化し，ツリートポロジー
上で実行する. PBIL は GA と同じ多点型の繰り返し探索
図 4: GA および EDA における移住の評価曲線
であるため，ツリートポロジーの移住手順が適用できる.
並列化手法では，エリート解を選び，移住個体を確率ベ
35
クトルに更新させる. 通常，選ばれたエリート解はその島
GA-LINE
EDA-LINE
Single GA
Single EDA
30
の確率ベクトルの更新に用いられるが，ここでは移住する
25
variance
個体も更新に用いる. この更新手法を図 3 に示す.
Parent
20
15
10
PV
400
600
800
1000
1200
1400
5
0
500
Child
1500
2000
2500
3000
generation
3500
4000
4500
5000
図 5: GA および EDA における移住の分散曲線
Child
図 3: ツリートポロジー上における確率ベクトルの更新
1000
の島より評価値，分散値を取得した. 表 1 は各トポロジー
の平均評価値と収束世代を示している. GA のライント
例えば，子から親への移住が行われたとする. そのとき
ポロジーが最もよい結果をえることができ, スタートポロ
に，子から親へエリート解の送信が行われ，親がエリート
ジーは最も低かった. これは収束世代の長さに比例してい
解を受信する. 受信した親ノードは受信した解を自身の島
ると考えられる.
が持つ確率ベクトルにその情報を反映させる.
移住してくる個体の数を M とすると確率ベクトルの更
新式は以下の式 (2) で表される.
M
1 ∑
P V [i] = (P V [i]×(1.0−LR))+(LR×
best[i]) (2)
M j=1
4
表 1: 各トポロジーの平均評価値 (Fi) と収束世代 (Co)
GA-Fi EDA-Fi GA-Co EDA-Co
ライン
3.859
3.595
4512
3984
スター
3.593
3.293
1109
982
バランス
3.714
3.373
2111
2409
サイド
3.831
3.609
3532
4630
実験・検証
テスト問題として NK ランドスケープ問題を使用した.
パラメーターとして遺伝子長を 400, 移住間隔を 100 とし
て実験を行った. また，移住の効果と分散の関係を調べる
ため，突然変異のオペレーターは使用していない．
GA と EDA において移住の効果を確認するために，移
住のあるときのライントポロジーとないときの場合を比較
した. その結果，図 4 よりどちらのアルゴリズムも移住
5
まとめ
本研究では，移住による効果を検証するために，移住時
における評価値と分散を調べた. その結果，移住時におい
て分散を得ることによって収束を防ぎ，多様性を得られる
によって解が改善されることを確認した.
がある方がよい結果を示した. 図 5 より，移住が行われな
参考文献
かった場合，GA と EDA のどちらも 500 世代ほどで分散
[1] Hiroshi Hurutani，“Analysis of Genetic Algorithms by
Schema Theorem : Roles of Mutation and Crossover”，
Transactions of InformationProcessing Society of Japan，
Vol. 43 No. SIG 10(TOM7)， pp35-45，2002.
がなくなるが，移住によって分散が増加する.
次にトポロジーをライン，スター，バランスツリー，サ
イドツリーと変化させながら最も移住の効果をうける root