A Parallel Genetic Algorithm with Distributed

環境分散遺伝的アルゴリズムの
有効性の検討
知的システムデザイン研究室
36990711 金子美華
生物の進化
 親の形質が子に伝えられる
 異種間での交雑
 変異
新種
 環境への適応の度合に応じて増殖していく
Intelligent Systems Design Lab., Doshisha Univ., Japan
遺伝的アルゴリズム（Genetic Algorithms）
 生物の進化を模倣
 複数の個体を用いて探索を行う
 遺伝的操作を繰り返す
選択
t 世代目
交叉
突然変異
010111010
101110101
111110010
t+1 世代目
010110010
101110001
111111010
Intelligent Systems Design Lab., Doshisha Univ., Japan
GAの問題点
 計算負荷が高い
 複数の個体を用いて，複数の世代数繰り返し計算を行う
並列化
 パラメータ設定が複雑
 個体数，交叉率，突然変異率など
 設定する値によって解の品質は大きく異なる
 適切な値を知るためには予備実験が必要
環境分散GA
Intelligent Systems Design Lab., Doshisha Univ., Japan
分散GA
単一母集団GA
分散GA
（Single Population GA）
（Distributed GA）
サブ母集団毎にGAを行う
一定間隔おきに個体の交換（移住）を行う
母集団の多様性を保つことができる
並列処理に適している
Intelligent Systems Design Lab., Doshisha Univ., Japan
環境分散GA （Distributed Environment
GA）
分散GA
環境分散GA
全てのサブ母集団に
等しい値のパラメータを設定
サブ母集団ごとに
異なる値のパラメータを設定
パラメータの適切な値を知るために
多くの予備実験が必要
パラメータのチューニングが不要
Intelligent Systems Design Lab., Doshisha Univ., Japan
研究の背景と目的
 環境分散GA


複数のパラメータを設定することができる
予備実験が不要
 分散させる環境

交叉率と突然変異率
“A Parallel Genetic Algorithm with Distributed Environment Scheme”，
Proceedings of the International Conference on Parallel and Distributed Processing
Techniques and Applications, (2000)
ペナルティパラメータ
 個体数
 シェアリングパラメータ

Intelligent Systems Design Lab., Doshisha Univ., Japan
制約付き最適化問題
制約条件のもとで目的関数を最適化

GAは制約付きの問題を解くことができない

実問題は制約付き
x2
制約条件
ペナルティ関数法
0
x1
Intelligent Systems Design Lab., Doshisha Univ., Japan
ペナルティ関数法
満たされない制約条件を罰金化した項を
目的関数と組み合わせた関数を最適化
P( x,  )  f ( x)   cˆi
1
x2
制約条件
f (x) :目的関数
cˆi
: xにおいて満たされない制約

: ペナルティパラメータ
0
x1
ペナルティパラメータの適切な値は未知
Intelligent Systems Design Lab., Doshisha Univ., Japan
実験の概要（対象問題）
 Sphere関数

n
2
x
i 1 i
1
f(x)
f ( x1,..., xn ) 
1
5.11  xi  5.12
制約条件 : xi  1.0
x2
x1
Intelligent Systems Design Lab., Doshisha Univ., Japan
実験の概要（パラメータ設定）
単一母集団GAおよび分散GAにおいて
ペナルティパラメータの違いが解の品質に与える影響
ペナルティパラメータ＝ { 0.0 , 10-2, 10-1, 100, 101, 102, 103, 104 }
2次元
単一母集団GA
単一母集団GA
10個体
8次元
単一母集団GA
20個体
80個体
単一母集団GA
160個体
分散GA （分割数8） 80個体
分散GA （分割数8） 160個体
選択：ルーレット選択，エリート保存戦略
交叉：一点交叉，交叉率0.6
突然変異率： 1/染色体長
Intelligent Systems Design Lab., Doshisha Univ., Japan
実験結果（２次元）
最適解の発見率の比較
1.0
Success rate
0.8
0.6
SPGA_10
SPGA_80
DGA_80
0.4
0.2
0.0
|
0.0 10-2
10-1 100
|
101
|
102
|
103
|
104
Penalty parameter
Intelligent Systems Design Lab., Doshisha Univ., Japan
実験結果（８次元その１）
最適解の発見率の比較
1.0
Success rate
0.8
0.6
SPGA_20
SPGA_160
DGA_160
0.4
0.2
0.0
0.0
10-2
10-1
100
101
102
103
104
Penalty parameter
Intelligent Systems Design Lab., Doshisha Univ., Japan
実験結果（８次元その２）
1000世代目での最良個体の適合度
0.261
Fitness value
0.260
0.259
0.258
SPGA_20
SPGA_160
DGA_160
0.257
0.256
0.255
|
|
0.0
10-2
|
10-1
|
100
|
101
|
|
|
102
103
104
Penalty parameter
Intelligent Systems Design Lab., Doshisha Univ., Japan
ペナルティパラメータの適切な値
2次元
単一母集団GA_10個体
100
単一母集団GA_80個体
101, 102
分散GA_80個体
100 以上
8次元
単一母集団GA_20個体
10-1
単一母集団GA_20個体
10-1
分散GA_160個体
10-1
適切な値は母集団サイズ，対象問題によって異なる
Intelligent Systems Design Lab., Doshisha Univ., Japan
環境分散GA
適切な値は母集団サイズ，対象問題によって異なる
適切な値を知るためには予備実験が必要
環境分散GA
8種類のペナルティパラメータ
{ 0.0 , 10-2, 10-1, 100, 101, 102, 103, 104 }
を8つのサブ母集団に分散させて設定
10-2
0.0
10-1
104
100
103
10
2
101
Intelligent Systems Design Lab., Doshisha Univ., Japan
実験結果（２次元）
最適解の発見率の比較
1.0
Success rate
0.8
0.6
SPGA_10
SPGA_80
DGA_80
DEGA
0.4
0.2
0.0
0.0
10-2
10-1
|
|
|
100
101
102
|
103
|
104
|
DE
Penalty parameter
Intelligent Systems Design Lab., Doshisha Univ., Japan
実験結果（８次元）
最適解の発見率の比較
1.0
Success rate
0.8
0.6
SPGA_20
SPGA_160
DGA_160
DEGA
0.4
0.2
0.0
|
0.0
10-2 10-1
100
101
102
103
104
DE
Penalty parameter
Intelligent Systems Design Lab., Doshisha Univ., Japan
環境分散GAの効果
 異なる値が設定されたサブ母集団
 異なる探索範囲
 多様性の維持
 移住と交叉
 異なるサブ母集団間の解が組み合せられる
・2次元
・サブ母集団数4
・サブ母集団サイズ10
・ペナルティパラメータ
(1) 分散GA
{ 10-1, 10-1, 10-1, 10-1 }
(2) 分散GA
{ 101 , 101 , 101 , 101 }
(3) 環境分散GA { 0.0, 10-1, 101 , 103 }
Intelligent Systems Design Lab., Doshisha Univ., Japan
結論
 ペナルティパラメータの値によって
解の品質は異なる
 ペナルティパラメータの適切な値は
母集団サイズや対象問題によって異なる
 環境分散GAの性能
 単一母集団GAの性能を上回る
 分散GAの性能と同等以上
Intelligent Systems Design Lab., Doshisha Univ., Japan
論文リスト
1.分散遺伝的アルゴリズムにおける遺伝子群の特異な進化，JSME第１１回計算力学講演会講演論文集, (1998) , pp.29-30
2.環境分散型並列遺伝的アルゴリズム，電子情報通信学会電子情報通信学会技術研究報告 AI99011~21, (1999) , pp.87-94
3. 分散GAにおける解探索能力，第13回人工知能学会全国大会（1999）
4. 分散母集団GAにおける解探索能力，同志社大学理工学研究報告，Vol.40，No.2，pp.35-45（1999）
5. A Parallel Genetic Algorithm with Distributed Environment Scheme ，IEEE Proceedings of Systems, Man and Cybernetics
Conference SMC'99, (1999) , pp.695-700
6. 環境分散遺伝的アルゴリズムの解探索能力，情報処理学会第59回全国大会（1999）
7. 分散遺伝的アルゴリズムにおける最適な交叉率・突然変異率，情報処理学会第59回全国大会（1999）
8. 分散遺伝的アルゴルズムにおける交叉法とコーディング法の影響，情報処理学会第59回全国大会（1999）
9. 分散GAにおける解探索メカニズム，情報処理学会研究報告2000-MPS-29 p.21-24（2000）
10. A Parallel Genetic Algorithm with Distributed Environment Scheme，Proceedings of the International Conference on Parallel
and Distributed Processing Techniques and Applications, Volume 2, (2000) , pp.619-625
11. A Parallel Genetic Algorithm with Distributed Environment Scheme，Proceedings of Genetic and Evolutionary Computation
Conference , pp. 376, 2000.
Intelligent Systems Design Lab., Doshisha Univ., Japan
適合度の履歴（8次元）
Fitness value
単一母集団GA
20個体
単一母集団GA
160個体
分散GA
160個体
0.26
0.26
0.26
0.24
0.24
0.24
0.22
0.22
0.22
Penalty
Parameter
10-1
100
101
0.20
0.20
0.20
102
0.18
0.18
0.18
103
0.16
0.16
0
500
Generations
1000
104
0.16
0
500
Generations
1000
0
500
1000
Generations
Intelligent Systems Design Lab., Doshisha Univ., Japan
環境分散GA（交叉率と突然変異率）
Pop. Size 180
1.0E+03
1.0E+02
Pc - Pm
Function value
1.0E+01
1.0E+00
1.0E-01
1.0E-02
1.0E-03
1.0E-14
1.0E-04
～
～
～
～
0.3-0.1/L
0.6-0.1/L
1.0-0.1/L
0.3- 1/L
0.6- 1/L
1.0- 1/L
0.3-10/L
0.6-10/L
1.0-10/L
DE
1.0E-15
1.0E-05
SPGA CE
DE
PDGA
Rastrigin
SPGA CE
DE
PDGA
Schwefel
SPGA CE
DE
PDGA
Griewank
SPGA CE
DE
PDGA
Rosenbrock
Intelligent Systems Design Lab., Doshisha Univ., Japan
Intelligent Systems Design Lab., Doshisha Univ., Japan

Download Report