PowerPoint プレゼンテーション

探索領域分割型GA
Divided Searching Area GA
知的システムデザイン研究室
赤塚浩太
Intelligent systems design laboratory
Kouta Akatsuka
概要
研究背景
探索領域分割型GA
数値実験
考察
まとめ
概要
研究背景
探索領域分割型GA
数値実験
概要
考察
依存関係の評価
依存のない問題
まとめ
依存のある問題
へのアプローチ
一部に依存のある問題
概要
研究背景
探索領域分割型GA
数値実験
考察
Rastrigin,Schwefel
[依存関係なし]
まとめ
Original Function
[一部に依存関係]
Rosenbrock,Griewank [依存関係あり]
概要
研究背景
探索領域分割型GA
数値実験
考察
まとめ
移住パラメータに関する考察
解空間の増大に関する考察
概要
研究背景
探索領域分割型GA
数値実験
考察
まとめ
研究背景
単一母集団GA
分割母集団GA
並列化
そこで!
が容易
移住と島数のパ
解の品質
の向上
ラメータを必要
未知の
としない新たな
問題・・・
島数・移住
GAを考案
パラメータ
の増加
探索領域分割型GA-概要
設計変数間の依存関係に注目
移住率・島数のパラメータに
依
大きく影響していると考えられる
存
分散
関 依存有り
そこで
係
依存関係を評価し、最適な
領域分割
評 依存無し
パラメータ、アルゴリズムを
価
自動決定する
探索領域分割型GA-概要
染色体
設計変数1
設計変数2
分散GA
島1
島2
島3
設計変数3
各島はすべて
の設計変数を
解く
通常は移住パ
ラメータに従い
移住を行う
探索領域分割型GA-概要
設計変数1
設計変数2
染色体
領域分割GA
島1
計算
終了後
島2
島3
設計変数3
各島は対象と
なる設計変数
のみを解く
移住は行わず
最後に解を集
める
探索領域分割型GA-依存関係の評価
依存関係評価
統計学を利用
独自の方法で代用
探索領域分割型GA-依存関係の無い問題
設計変数間に
依存関係が無い
各設計変数毎に
解を求め最後に
合わせれば良い
F(x,y) の最小値を求める
x,yには依存関係が無いため
F(x,y)=g(x)+h(y) と分解できる
探索領域分割型GA-依存関係の無い問題
設計変数間に
依存関係が無い
各設計変数毎に
解を求め最後に
合わせれば良い
F(x,y)=g(x)+h(y) と分解できる
g(x) と h(y) をそれぞれ最小化
g(x):F(x,a) h(y):F(a,y)
探索領域分割型GA-依存関係の無い問題
F(x,y,z)
x y z
島1
島2
島3
x
y
z
X
Y
解を集める
Z
島 設計変
=
数 数の数
F(X,Y,Z)
=解
XYZ
探索領域分割型GA-依存関係のある問題
依存関係のある問題
F(x,y,z)
x y z
島1
島2
島3
x1y1z1
x2y2z2
x3y3z3
最適なものを選択
分散GA
島数=
設計変数の数
移住無し
F(x2,y2,z2)
=解
x2y2z3
探索領域分割型GA-一部に依存関係がある問題
一部の設計変数間に
依存関係のある問題
依存関係のある
設計変数を塊に
依存関係のな
い設計変数間
領域
分割
依存関係のあ
る設計変数間
分散
GA
x1x2+x3x4
x1x2
x3x4
x1x2
x3x4
x1x2
x1x2
x3x4
x3x4
数値実験
Rastrigin
Schwefel
依存関係
無し
Original
一部に有り
Rosenbrock
Griewank
依存関係
有り
数値実験
実験に用いたGA
探索領域分割型GA(DSAGA)
移住率[0.0,0.3,0.6]の分散GA
(DGA-[0.0,0.3,0.6])
実験に用いたその他のパラメータ
個体数600
島数10
突然変異率1/L
エリート保存
交叉率0
移住間隔5
試行回数10
数値実験
依存関係無し(Rastrigin:Schwefe
l)
800
DSAGA
700
最
適
解
発
見
世
代
600
DGAMIG0.0
DGAMIG0.3
DGAMIG0.6
500
400
300
200
100
0
Rastrigin
Schwefel
数値実験
依存関係一部にあり(Original)
適
合
度
0.45
0.4
0.35
0.3
0.25
0.2
0.15
0.1
0.05
0
DSAGA
DGA-MIG0.0
DGA-MIG0.3
DGA-MIG0.6
Original
最
適
解
発
見
世
代
1000
900
800
700
600
500
400
300
200
100
0
Original
数値実験
依存関係有り(Rosenbrock:
1.2
Griewank)
DSAGA
1
DGAMIG0.0
DGAMIG0.3
DGAMIG0.6
0.8
適
合 0.6
度
0.4
0.2
0
Rosenbrock
Griewank
考察-移住パラメータ
未知の問題
移住率:0,0.3,0.6
DGA
移住間隔:2,5,10
の7種パラメータ
最適なパラメータ設定が困難
設定のDGA
DSAGA
DSAGA
有効性を検証
考察-移住パラメータ
DSAGAと移住パラメータを変えたDGA
解発見世代(Rast,Schw)・適合度を元にした性能
1.0
0.9
0.8
0.7
0.6
0.5
dsaga
移住無し
10-0.3
10-0.6
5-0.3
5-0.6
2-0.3
2-0.6
0.4
0.3
0.2
0.1
0.0
Rastrigin
Schwefel
Original
Rosenbrock
Griewank
考察-移住パラメータ
DSAGAはGriewank以外の関数
において,もっとも良い結果
Griewankでも,他の関数・パラメータ
に比べ,それなりに良好な結果
DGAにおける移住パラメータ増加
という欠点を補う事ができる
考察-設計変数,染色体長の増加
Rastrigin 15Bitx20設計変数
最
適
解
発
見
世
代
1000
900
800
700
600
500
400
300
200
100
0
DSAGA
DGA
100bit
300bit
2.7倍 3.5倍
まとめ
移住率,島数のパラメータ
今後の課題
を無くす新たなGAを考案
統計学の応用
依存無し 性能を大幅に向上
中程度の依存関係
DGAの最適パラメータ
最適な島数
依存有り
には劣る場合もあるが
良好な結果
依存関係を調査する独自の方法
F(x,y)=x+y
F(x,-1)
F(x,0)
F(x,1)
x
x
x
依存関係を調査する独自の方法
F(x,y)=xy
F(x,-1)
x
F(x,0)
x
F(x,1)
x
解発見世代・適合度を元にした性能
Rastrigin/Schwefel
1000世代ですべて解がでたため、
解が求まった世代を元に
1-Gen/1000
その他の関数
DSAGA以外では1000世代では解が
求まらなかったため、適合度を元に
1-Fitness