移民交叉を用いた多プロセス並列

PfGA についての検討

A Consideration of Parallel Distributed Parameter free Genetic Algorithm
by using Migrant Crossover
感性情報学講座

0312005003 赤平 俊之

指導教員： 小嶋和徳

1. はじめに遺伝的アルゴ リズム（ 以下 GA ）は多点探索と反復計算により計算コストが高い．この問題を解決するために計算を複数のプロセッサに分割し負荷を軽減する並列分散 GA が考案されている．また，計算機器の低価格化により PC が安価に購入可能となっている．そこで本研究では，安価な PC を効率的に利用するために PC クラスタを用いた並列化と，計伊藤慶明

石亀昌明（ 親 1，親 2 ＞子 1，子 2 ）適合度の高い親個体を残し個体数+1

Case3：片方の親個体が両子個体よりも優れている（ 親 1 ＞子 1，子 2 ）適合度の高い親個体と子個体を残す

Case4：片方の子個体が両親個体よりも優れている（ 子 1 ＞親 1，親 2 ）適合度の高い子個体を残し新個体作成算コストが低い PfGA を利用した並列分散 PfGA を

2.3. 移民処理として，移民個体を他プロセスに定住させず他プロ置き集団同士で移民を行う．移民方法は 1) を参考にセス内個体との交叉だけに使用する移民交叉の提案し，親個体より優れた子個体が発生した際にその優と検討を行う．

れた子個体を移民させる．移民先プロセスは，集団

2. 並列分散 PfGA 概要

内の個体と移民個体の中からもっとも適合度の低い導入し，並列分散 PfGA における効率的な移民手法

並列分散 PfGA では，1 プロセスにつき 1 集団を個体を削除することで集団サイズを維持する．

2.1. 並列分散 GA

2.4. 問題点の検討の処理時間や処理負荷を軽減する手法で，さらに集合，リング型トポロジ，メッシュ型トポロジの 3 種

並列分散 GA は処理を分散 並列化することで GA団同士で個体のやり取り (移民) を行うことで適合度予備実験として同プロセス数で移民を行わない場類の比較を行った．その結果，移民を行わなくともの上昇にもつながる．通常移民は他プロセスへの個高い性能を発揮し，メッシュ型トポロジではむしろ体のコピーという形をとる．その際の接続構造をト性能が落ちてし まうという結果となった．これは，ポロジといい，トポロジにより移民量や移民先が大移民が拡散することで多様性と PfGA の特徴であるきく変わり，結果にも大きな差が現れる．例えばプ

大域探索能力が低下するため，接続数が多いほど 局ロセスを輪状につなげたリング型トポロジは接続数所解に陥りやすくなり性能が低下したためである．

が少ないため大域探索能力に優れ，碁盤の目のよう

しかし，適合度の高い個体を移民させることで進化につなげたメッシュ型トポロジは接続数が多いため速度が向上することも確認できた．つまり優れた個局所探索能力に優れる．

体の遺伝子を他プロセスに伝え，かつ移民がそのま2.2. PfGA

初期集団数や交叉確率，突然変異確率といったパラメータ設定を必要としない GA であり，集団数も可変で世代ごとに集団から 2 個体を選択し遺伝的処理を行う．選択と淘汰は，親と子の 4 個体の適合度を比較してその大小によって４つの場合に分けてそれぞれ異なった処理を行う．

Case1：両子個体が両親個体よりも優れている（ 子 1，子 2 ＞親 1，親 2 ）両子個体と適合度の高い親個体を残し個体数+1

Case2：両親個体が両子個体よりも優れている

まの形で残らないようにすることでこの問題点の改善が図れると考えられる．

3. 移民交叉概要
3.1. 処理の流れ

移民を受け取ったプロセスは適合度の低い個体の削除を行わず，移民を集団とは別に保存しておく．
そして次に行う交叉では必ず移民を使用して交叉を行う．移民を使用した交叉（ 以下移民交叉）を行う
際，個体数の維持と移民個体が残らないようにする
ため，適合度による処理内容を変更する．移民を受1

け取らなかった場合の交叉は通常のものが行われる
ため，2 種類の交叉が存在することとなる．

0.95

3.2. 交叉時の処理

Case1:両子個体を残し ，個体数+1
Case2:処理を行わない（移民ではない親個体が残る）
Case3:移民以外で最も適合度の高い個体を残す
Case4:適合度の高い子個体を残す

3.3. 実験条件

diversity

0.9

変更後の交叉処理は以下のように変更した．

0.85

0.8

Ring EC
Ring Normal
Mesh EC
Mesh Normal

0.75

0.7
1

セス数は 100，試行回数は 10 回，問題関数は TSP100
都市問題，終了条件は 1 プロセスにつき 100 万世代とした．また多様性 D は各プロセスの最大適合度個体の遺伝子配列を比較し以下の式で算出した．
D=

PL PP PPk=1((j =1P i jC (gk  g ) =kg: 遺伝子 : 遺伝子座k3.4. 実験結果

(i ji=j +1 C (gk  gk )P ;(1)) 2)
=g

6100

1000
10000
generation

1000001e+06を示す．またそれぞれの多様性を図 3 に示す．

移民交叉の導入によって適合度，多様性ともに大きく上昇している．これらの上昇は，移民個体を残さないことによる多様性の維持と，移民個体の遺伝(1)

1 : ki = kj
0 : ki = kj
: 染色体長 : プロセス数
g

L

L10

図 3：リング メッシュ多様性比較

トポロジ形状はリングとメッシュを使用した．プロgg

P

子を残したことによる進化の促進が有効に働いたためと思われる．特にメッシュ型トポロジの上昇幅が大きいのは，直接移民を受け取らないぶん接続経路の多さが多様性低下につながらず，複数プロセスとの交叉が可能という利点が有効に働いたためと思われる．しかし，優れた移民個体をそのまま利用できないため進化速度は若干遅い結果となっており，こ図 1 ではリング型トポロジの，図 2 ではメッシュ型トポロジの移民交叉導入 非導入時の平均適合度1の点の改善が必要である．

4. まとめ本研究では，並列分散 PfGA に対し移民個体を交0.8

叉のみに使用する移民交叉を導入した．その結果，適合度と多様性を上昇させることができた．特に接fitness0.6

続経路の多いトポロジの大域探索能力低下という問題点の改善に成功した．

0.4

今後は移民交叉の更なる検証 改良とともに，ト0.2

ポロジ形状についても検討していきたい．

Mesh EC
Mesh Normal
01

10100

1000
10000
generation

1000001e+06

図 1：リング適合度比較

1参考文献1 ）木津左千夫，澤井秀文，足立進:可変な局所集団の適応的探索を用いたパラメータフリー遺伝的アルゴ リズムと その並列分散処理への拡張, 信

0.8

学論 (D-II),vol.j82-D-II,no.3,pp.512-521,March1999.

fitness

0.62 ）菊地雅彦:並列分散遺伝的アルゴ リズムにおける0.4多層型トポロジの探索性とパラメータの組み合わせに関する研究 岩手県立大学ソフトウェア情報学部 2008 年度博士前期過程論文 (2008)

0.2
Mesh EC
Mesh Normal
0110100

1000
10000
generation100000

図 2：メッシュ適合度比較

1e+063 ）今康徳:PDGA における階層コーン型トポロジの探索空間拡大に伴う探索性能の影響に関する考察, 第 9 回情報科学技術フォーラム (2010)