PowerPoint プレゼンテーション

分散確率モデル遺伝的アルゴリズム
佐野正樹（同志社大学大学院）
廣安知之（同志社大学工学部）
三木光範（同志社大学工学部）
下坂久司（同志社大学大学院）
筒井茂義（阪南大学経営情報学部）
Intelligent Systems Design Laboratory
発表の概要

新しい確率モデルGAの提案と有効性の検討
1. 従来の遺伝的アルゴリズム（GA）の問題点と
確率モデルGAの説明
2. 新しい確率モデルGAであるDPMBGA の提案と説明
3. 数値実験による DPMBGA の検討
4. まとめ
Intelligent Systems Design Laboratory
遺伝的アルゴリズムにおける交叉の役割
親個体の遺伝子を組み替え
新しい個体を生成
個体間の情報交換
評価
選択
交叉
突然変異
積み木仮説（Holland 1975）
複数の個体がビルディングブロック
（部分解）を探索．
交叉によってこれが組み合
わされる
GAによる解探索の主役と
考えられてきた
Intelligent Systems Design Laboratory
GAにおける交叉の問題点
交叉の働きは，発見されたビルディングブロックを母集
団に広めることで，結果として多様性を失わせる．
親個体のもつビルディングブロックを破壊することが多
い.（Wu 1997）
適合度に小さな変化または大きな改悪を生む事が多い．
（Nordin 1995）
新しいアプローチ
確率モデルGA
Probabilistic Model-Building GA : PMBGA
Intelligent Systems Design Laboratory
確率モデルGA
（１）良好な個体を母集団
から選択
分布の推定
（２）分布を推定し
確率モデルを構築
母集団
（３）新しい個体を生成し
母集団内の個体と置き換え
確率モデル
母集団内の良好な個体群の分布にもとづいて
確率的に新しい個体を生成
GAの交叉 → 確率モデルにもとづく個体の生成
Intelligent Systems Design Laboratory
確率モデルGAの分類（Pelikan1999）
設計変数のコード化手法による分類
f (x1, x2)
ビットストリング型 0 1 0 1 0 1
実数値ベクトル型
x1
x2
設計変数間の依存関係の考慮による分類
依存関係を考慮しない
2変数間の依存関係を考慮する
3変数以上の依存関係を考慮する
Intelligent Systems Design Laboratory
確率モデルGAの分類と提案手法
ビットストリング
依存関係を PBIL（Baluya1994）
考慮しない
UMDA（Muhelembein1996）
ｃGA（Lobo1998）
実数値ベクトル
SHCLVND （Rudolf1996）
Real-coded PBIL （Sevet1997）
PIPE（Salustowicz1997）
histogram PMBGA （筒井
分散確率モデル遺伝的アルゴリズム
2000）
Distributed
PMBGA : DPMBGA
2変数を
MIMIC（DeBonet1997）
GOA （吉田 2002）
考慮設計変数間の依存関係を考慮した
BMDA（Pelikan1999）
実数値確率モデルGA
3変数以上を ECGA（Harik1999）
考慮
FDA （Muhelembein1999）
BOA （Pelikan1999）
EBNA （Etxeberria1999）
EGNA （Etxeberria1999）
DPMBGA
Intelligent Systems Design Laboratory
提案する確率モデルGA

分散確率モデル遺伝的アルゴリズム
（Distributed PMBGA : DPMBGA）

複数のサブ母集団に分割

移住

多様性の維持

実数値確率モデルGA

主成分分析（PCA）により，
設計変数間の依存関係を考慮
Intelligent Systems Design Laboratory
各サブ母集団内の処理の概要
サブ母集団
(1) 良好な個体の抽出
x2
v1
v2
x1
(4) 相関を復元して置き換え
x2
(2) PCA による
設計変数の
無相関化
v1
v2
x2
x1
x1
(3) 正規分布による
子個体の生成
Intelligent Systems Design Laboratory
良好な個体の抽出
サブ母集団
良好な個体の抽出
x2
x1
サンプル個体群

サンプル個体群の抽出

適合度の上位から一定割合の個体を抽出

同じ設計変数を持つ個体を重複して選択しない
Intelligent Systems Design Laboratory
主成分分析による設計変数の無相関化

目的


x2
v2
設計変数間の依存関係を
考慮した子個体の生成
v1
x1
PCA による
設計変数の
無相関化
処理の流れ
1. 最良個体アーカイブの更新
x2
2. アーカイブに対する主成分分析
3. 設計変数の無相関化
x1
Intelligent Systems Design Laboratory
最良個体アーカイブの更新
x2
サブ母集団
現世代までの
最良個体のアーカイブ
x1
アーカイブの分布

最良個体アーカイブ

現世代までに出現した最良個体を蓄積

アーカイブサイズは一定

各サブ母集団が保持
Intelligent Systems Design Laboratory
アーカイブに対する主成分分析

最良個体アーカイブの分布に対し，
主成分分析（PCA）を行う

x2
v2
最良個体アーカイブの
v1
x1
設計変数の分散共分散行列 S を
アーカイブの分布
求める

S の固有ベクトル V = (V1, V2, …, VD, )
を求める（D：設計変数の数）

固有値が大きいほど，固有ベクトル方向の分散
が大きい
Intelligent Systems Design Laboratory
設計変数の無相関化

サンプル個体群の無相関化

x2
v2
v1
サンプル個体群の設計変数から，
最良個体アーカイブの平均を
x1
引き，行列 X に格納

PCA による
設計変数の
無相関化
固有ベクトルV を用いて，
行列Xを回転
Y= XV

x2
固有ベクトル向きが，
座標軸の向きに一致
x1
Intelligent Systems Design Laboratory
正規分布による子個体の生成
サブ母集団

子個体の生成


相関を復元して戻す
x2
v1
v2

各設計変数について，
独立に正規乱数を発生
設計変数の分散値を増幅
サブ母集団の入れ替え

子個体の相関を復元し，
サブ母集団全体を置き換え
x2
x1
正規分布による
子個体の生成
x1
無相関化後の分布
Intelligent Systems Design Laboratory
提案手法の特徴

主成分分析（PCA）を用いた確率モデル GA

母集団分割による多様性の維持

実数値ベクトルの染色体

主成分分析（PCA）により，
設計変数間の依存関係を考慮して子個体を生成

PCAにおいて，複数世代にわたって蓄積した
最良個体アーカイブを使用

正規分布による分布推定
Intelligent Systems Design Laboratory
数値実験1 ：主成分分析の効果の検討

設計変数間の依存関係に対する主成分分析（PCA）
の効果について，3つのモデルの比較によって検討

with PCA

without PCA ：全てのサブ母集団でPCAを行わない

: 全てのサブ母集団でPCAを実行
DES
: 半数のサブ母集団でのみPCAを実行
環境分散スキーム（Miki, 1998）
（Distributed Environment Scheme）
DES
with PCA
without PCA
Intelligent Systems Design Laboratory
対象問題（１）

設計変数間に依存関係の無い関数
n

Rastrigin: 10n   xi2  10cos(2xi )
i 1

(5.12  xi  5.12)
n=20
n

Schwe fel:    xi sin
i 1
 x 
i
(512  xi  512)
n=10
Intelligent Systems Design Laboratory
対象問題（２）

設計変数間に依存関係のある関数
n 1

Rosenbrock:  100( xi 1  xi2 ) 2  (1  xi ) 2

i 1
(2.048  xi  2.048)
n=20
 i 
Ridge :    x j 
i 1  j 1

n
※
2
(64  xi  64)
n=20
n
xi2
 xi 
Grie wank: 1  
  cos 
 i
i 1 4000
i 1
n
(512  xi  512)
n=20
Intelligent Systems Design Laboratory
パラメータ
DPMBGA
個体数
サブ母集団数
染色体長(L)
エリート/島
選択法
良好な個体の抽出率
正規乱数の分散の増幅率
最良個体アーカイブ
突然変異率
移住間隔
移住個体数（移住率）
移住個体
試行
512
32集団 × 16個体
設計変数の数
1
最良個体を選択
0.25
2.0
100個体
1/ (10×L)
5
1個体（0.0625）
ランダムに送出，最悪個体を置き換え
20
Intelligent Systems Design Laboratory
最適値到達の割合

関数評価値が最適値に到達した割合（20試行中）
最適値： 1.0E-10 ，終了条件：関数評価回数 3.0E+06
with PCA
Rastrigin
Schwefel
Rosenbrock
Ridge
Griewank
0
20
20
20
19
without PCA
20
20
0
20
17
DES
20
20
20
20
20

Rastrigin（依存関係無し）で with PCAが最適値に到達せず

Rosenbrock（依存関係あり）で without PCAが最適値に到達せず

環境分散モデル（DES）は，全ての関数において最適値に到達
Intelligent Systems Design Laboratory
最適値到達までの関数評価回数の平均
2.5E+06
with PCA
without PCA
DES
2.0E+06
1.5E+06
1.0E+06
5.0E+05
0.0E+00
Rastrigin
Schwefel
Rosenbrock
Ridge

依存関係の無い問題では without PCA が有効

依存関係のある問題では with PCA が有効

Griewank
環境分散モデル（DES）は，
依存関係の有無にかかわらず，良好な性能
Intelligent Systems Design Laboratory
数値実験2 ： UNDX+MGGとの性能比較

単峰性正規分布交叉（UNDX）（小野ら, 1999）


実数値GAの代表的な交叉法
設計変数間に依存関係の
ある問題に有効
C1
P2
C2
P1

Minimal Generation Gap （MGG）（佐藤ら, 1997）

世代交代モデル

多様性の維持
parents
children
比較実験により，DPMBGA の有効性を検証
Intelligent Systems Design Laboratory
パラメータ
UNDX+MGG
DPMBGA（DES）
個体数
サブ母集団数
染色体長(L)
エリート/島
選択法
確率モデル，
交叉
最良個体アーカイブ
突然変異率
移住間隔
移住個体数（移住率）
移住個体
試行
多峰性関数： 300
単峰性関数： 50
1
32集団 × 16個体
設計変数の数
設計変数の数
1
1
最良個体を選択
α=0.5, β=0.35
分散の増幅率
： 2.0
良好な個体の抽出率： 0.25
交叉回数： 100
512
100個体
1/ (10×L)
5
-
1個体（0.0625）
-
ランダムに送出，
最悪個体と入れ替え
0
-
20
Intelligent Systems Design Laboratory
実験結果（Rastrigin, Schwefel）

設計変数間に依存関係の無い問題（多峰性）
1.0E+04
DPMBGA
1.0E+02
UNDX+MGG
1.0E+00
1.0E-02
1.0E-04
1.0E-06
1.0E-08
1.0E-10
0.E+00
1.E+06
2.E+06
3.E+06
4.E+06
Evaluation Value l
Evaluation Value l
1.0E+04
1.0E+02
1.0E+00
1.0E-02
1.0E-04
UNDX+MGG
1.0E-08
1.0E-10
0.E+00
Number of Evaluations
1.E+06
2.E+06
3.E+06
4.E+06
Number of Evaluations
Rastrigin

DPMBGA
1.0E-06
Schwefel
DPMBGA が良好な性能を示す
Intelligent Systems Design Laboratory
実験結果（Rosenbrock, Ridge）
設計変数間に依存関係のある問題（単峰性）
1.0E+04
1.0E+06
1.0E+02
1.0E+04
DPMBGA
1.0E+02
UNDX+MGG
DPMBGA
1.0E+00
UNDX+MGG
1.0E-02
1.0E-04
1.0E-06
1.0E-08
Evaluation Value l
Evaluation Value l

1.0E+00
1.0E-02
1.0E-04
1.0E-06
1.0E-08
1.0E-10
0.E+00
1.E+06
2.E+06
3.E+06
4.E+06
1.0E-10
0.E+00
2.E+06
3.E+06
4.E+06
Number of Evaluations
Number of Evaluations
Ridge
Rosenbrock

1.E+06
DPMBGA が良好な性能を示す
Intelligent Systems Design Laboratory
実験結果（Griewank）

設計変数間に依存関係のある問題（多峰性）
Evaluation Value l
1.0E+04
DPMBGA
1.0E+02
UNDX+MGG
どの問題に対しても，
環境分散スキームを
用いたDPMBGAが
良好な性能を示している
1.0E+00
1.0E-02
1.0E-04
1.0E-06
1.0E-08
1.0E-10
0.E+00
1.E+06
2.E+06
3.E+06
4.E+06
Number of Evaluations
Griewank

DPMBGA が良好な性能を示す
Intelligent Systems Design Laboratory
まとめ
新しい実数値確率モデル GA である，DPMBGA の提案
母集団の分割により，多様性を維持
主成分分析（PCA）を用いて設計変数の依存関係を考慮
PCA の効果についての検討
設計変数間に依存関係のある問題に対して PCAが有効
UNDX+MGG との比較実験
DPMBGA がより良好な解を得る
DPMBGA は連続関数最適化に対して
有効な手法である
Intelligent Systems Design Laboratory
補足資料
Intelligent Systems Design Laboratory
突然変異と制約条件の処理


突然変異

突然変異率に従う

設計変数を，実行可能領域内にランダムに変更
制約条件の処理

実行可能領域内の
境界上に引き戻し
x2
制約条件外
の個体
実行可能領域
x1
Intelligent Systems Design Laboratory
良好な個体の抽出
サブ母集団
x2
良好な個体の抽出
x1

サンプル個体群の抽出


エリート
サンプル個体群
母集団から一定割合の最良個体を
重複しないように抽出
エリートの保存

一定数の最良個体（エリート）を保存

世代の最後にサブ母集団に復帰
Intelligent Systems Design Laboratory
最良個体アーカイブ
島（世代 1）
世代 1 までの
最良個体
島（世代 2）
世代 2 までの
最良個体
島（世代 3）
世代 3 までの
最良個体

現世代までに出現した最良個体を蓄積

一定のアーカイブサイズ
Intelligent Systems Design Laboratory
Intelligent Systems Design Laboratory
主成分分析（1）

主成分分析（Principal Component Analysis : PCA）
多変量データの持つ情報を，
少数個の総合特性値（主成分）に要約する手法
x2


分散が最大となる方向が，
第１主成分となる
v1 （第１主成分）
強い相関を有する分布は，
少数の主成分によって
表現可能
v2 （第２主成分）
x1
Intelligent Systems Design Laboratory
主成分分析（2）
平均偏差行列
： X （n 個体 × m 変数）
1 T
分散共分散行列
： S X X
n
S の固有値と固有ベクトル：  ,...,
v ,...,v
1
m
1
m
固有ベクトルが主成分に一致
 固有ベクトルが座標軸に一致するように回転すると，
変数間の相関が無くなる

x2
v2
x2
v1
座標軸の回転
x1
x1
Intelligent Systems Design Laboratory
Intelligent Systems Design Laboratory
分散遺伝的アルゴリズム

分散遺伝的アルゴリズム（DGA）
（Tanese1989）





島モデル（island model）
各島で遺伝的操作
移住
多様性の維持
高い解探索能力
(Tanese, Belding)
Intelligent Systems Design Laboratory
環境分散モデル

設計変数間の依存関係を考慮した環境分散モデル
（Distributed Environment Scheme : DES）（Miki, 1998）

依存関係を考慮する島
PCA を行う

依存関係を考慮しない島
PCA を行わない
with PCA
without PCA
Intelligent Systems Design Laboratory
Intelligent Systems Design Laboratory
PCAが有効に機能しない原因について

親個体の分布が狭いとき子個体の多様性が失われる
x2
x2
v1
v2
子個体の
分布が広い
子個体の
分布が狭い
x2
PCA あり

x1
x1
親個体
PCA 無し
最良個体アーカイブが更新されない

アーカイブ内の個体が局所解に陥る
Intelligent Systems Design Laboratory
Intelligent Systems Design Laboratory
単峰性正規分布交叉

単峰性正規分布交叉
（Unimodal Normal Distribution Crossover : UNDX）
（小野ら, 1999）
 実数値GAの代表的な交叉法
 設計変数間に依存関係のある問題に有効
 正規分布にしたがって2つの子個体生成
 親1，親2を結ぶ主軸成分（α）
 親3と主軸との距離で決まる成分（β）
P3
P2
C1
C2
P1
Intelligent Systems Design Laboratory
Minimal Generation Gap

Minimal Generation Gap （MGG）（佐藤ら, 1997）






世代交代モデル
多様性の維持
世代交代の連続化
世代交代の限定化
2個体の親を複製選択し，
複数回の交叉によって子個体を生成
親個体と子個体の中から生存選択で
parents
children
Intelligent Systems Design Laboratory
Intelligent Systems Design Laboratory
Intelligent Systems Design Laboratory
Intelligent Systems Design Laboratory
Intelligent Systems Design Laboratory

Download Report