slide

分散確率モデル遺伝的アルゴリズム
佐野正樹（同志社大学大学院）
廣安知之（同志社大学工学部）
三木光範（同志社大学工学部）
下坂久司（同志社大学大学院）
筒井茂義（阪南大学経営情報学部）
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の分類（Pelikan, 1999）
設計変数のコード化手法による分類
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）
分散確率モデル遺伝的アルゴリズム
2変数を
MIMIC（DeBonet1997）
GOA （吉田 2002）
Distributed
PMBGA : DPMBGA
考慮 BMDA（Pelikan1999）
設計変数間の依存関係を考慮した
実数値確率モデルGA
3変数以上を ECGA（Harik1999）
考慮
FDA （Muhelembein1999）
BOA （Pelikan1999）
EBNA （Etxeberria1999）
EGNA （Etxeberria1999）
DPMBGA
Intelligent Systems Design Laboratory
連続関数最適化と設計変数間の依存関係

連続関数最適化手法に求められること


母集団の多様性の維持
設計変数間の依存関係の考慮
設計変数間の依存関係
x2
x2

f (x1, x2)
x2
x1
良好な個体の
生成には
依存関係の考慮
が必要
依存関係無し
x1
依存関係あり
x1
設計変数間の依存関係を考慮した実数値確率モデルGAを提案
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において最良個体アーカイブを使用
– アーカイブにPCAを適用
– 固有ベクトルを用いてサンプル個体群を変換
– PCAに，任意の数の個体を使用可能

正規分布による分布推定
Intelligent Systems Design Laboratory
数値計算例

テスト関数を用いた数値実験

設計変数の依存関係と主成分分析との関係について検討

既存の実数値GA （UNDX+MGG）との性能比較

最適解が探索空間の端にある対象問題についての検討
Intelligent Systems Design Laboratory
対象問題（１）

設計変数間に依存関係の無い関数
Rastrigin : 10n   xi2  10 cos( 2xi ) 
n
i 1
(5.12  xi  5.12)
n=20
n

Schwefel :    xi sin
i 1
 x 
i
(512  xi  512)
n=10
Intelligent Systems Design Laboratory
対象問題（２）

設計変数間に依存関係のある関数
Rosenbrock :  100( xi 1  xi2 ) 2  (1  xi ) 2  (2.048  xi  2.048)
n 1
i 1
n=20
 i 
Ridge :    x j 
i 1  j 1

n
※
2
(64  xi  64)
n=20
n
xi2
 xi 
Griewank : 1  
  cos 
 i
i 1 4000
i 1
n
(512  xi  512)
n=20
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
パラメータ
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
without PCA
DES
0
20
20
20
20
20
19
20
0
20
17
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）
512
多峰性関数： 300
単峰性関数： 50
32集団 × 16個体
1
個体数
サブ母集団数
染色体長(L)
設計変数の数
設計変数の数
エリート/島
選択法
確率モデル，
交叉
1
最良個体を選択
分散の増幅率
： 2.0
良好な個体の抽出率： 0.25
最良個体アーカイブ
突然変異率
移住間隔
移住個体数（移住率）
移住個体
試行
1
α=0.5, β=0.35
交叉回数： 100
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
Number of Evaluations
4.E+06
Evaluation Value l
Evaluation Value l
1.0E+04
1.0E+02
1.0E+00
1.0E-02
1.0E-04
DPMBGA
1.0E-06
UNDX+MGG
1.0E-08
1.0E-10
0.E+00
1.E+06
3.E+06
4.E+06
Number of Evaluations
Rastrigin

2.E+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
Number of Evaluations
4.E+06
1.0E-10
0.E+00
1.E+06
3.E+06
4.E+06
Number of Evaluations
Ridge
Rosenbrock

2.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
実験3 ：最適解が端にある問題について

実数値GAの問題点


最適解が探索領域の境界付近にある問題で性能悪化
Boundary Extension by Mirroring (BEM)
（Tsutsui,1998）



f(x)
探索領域外の個体が
生存
境界を基点として
目的関数の鏡像を拡張
探索領域の端に最適解が
ある問題に有効
拡張領域
探索領域
x
最適解が端にある場合のDPMBGAの探索能力について検討
DPMBGA と DPMBGA with BEM との比較
Intelligent Systems Design Laboratory
対象問題とDPMBGAの制約条件処理

対象問題

最適解が端に位置するように定義域を変更
例） Ridge 関数
x2
x2
最適解
x1

DPMBGAにおける
制約条件外の個体の処理

最も近い
実行可能領域（拡張領域）
の境界上に引き戻し
x1
x2
制約条件外
の個体
実行可能領域
x1
Intelligent Systems Design Laboratory
パラメータ
DPMBGA（DES）
個体数
512
サブ母集団数
染色体長(L)
32集団 × 16個体
設計変数の数
エリート/島
選択法
確率モデル，
交叉
1
最良個体を選択
分散の増幅率
： 2.0
良好な個体の抽出率： 0.25
最良個体アーカイブ
突然変異率
移住間隔
100個体
1/ (10×L)
5
移住個体数（移住率）
移住個体
BEM の拡張率
試行
1個体（0.0625）
ランダムに送出，最悪個体と入れ替え
0.0 (normal), 0.2 (with BEM)
20
Intelligent Systems Design Laboratory
解の履歴（Rastrigin, Schwefel）

設計変数間に依存関係の無い問題
1.0E+04
normal
with BEM
1.0E+02
1.0E+00
1.0E-02
1.0E-04
1.0E-06
1.0E-08
1.0E-10
0.0E+00

5.0E+05
1.0E+06
Evaluation Value
Evaluation Value
1.0E+04
normal
with BEM
1.0E+02
1.0E+00
1.0E-02
1.0E-04
1.0E-06
1.0E-08
1.0E-10
0.0E+00
2.5E+05
5.0E+05
Number of Evaluations
Number of Evaluations
Rastrigin (modified)
Schwefel (modified)
BEM を用いない通常のモデルが，良好な性能を示している
Intelligent Systems Design Laboratory
解の履歴（Rosenbrock, Ridge）

設計変数間に依存関係のある問題
1.0E+04
normal
with BEM
1.0E+02
1.0E+00
1.0E-02
1.0E-04
1.0E-06
1.0E-08
1.0E-10
0.0E+00
5.0E+05
1.0E+06
Number of Evaluations
Rosenbrock (modified)

Evaluation Value
Evaluation Value
1.0E+04
normal
with BEM
1.0E+02
1.0E+00
1.0E-02
1.0E-04
1.0E-06
1.0E-08
1.0E-10
0.0E+00
2.5E+05
5.0E+05
Number of Evaluations
Ridge (modified)
BEM を用いない通常のモデルが，良好な性能を示している
最適解が端にある場合も，通常のDPMBGAが良好な解を得る
Intelligent Systems Design Laboratory
まとめ

新しい実数値確率モデル GA ： DPMBGA の提案



主成分分析（PCA）の効果についての検討



設計変数間に依存関係のある問題に対してPCAが有効
依存関係の有無にかかわらず環境分散モデルが有効
UNDX+MGG との比較実験


母集団の分割により，多様性を維持
主成分分析（PCA）を用いて設計変数の依存関係を考慮
DPMBGA がより良好な性能を示す
最適解が探索領域の端に位置する問題について

BEM を適用しなくても良好な解を得る
DPMBGA は連続関数最適化において有効
Intelligent Systems Design Laboratory
補足資料
Intelligent Systems Design Laboratory
設計変数間の依存関係を考慮した手法

単峰性正規分布交叉（UNDX）（小野ら, 1999）
実数値GAの代表的な交叉法
 2つの親個体を結ぶ主軸付近に子個体生成
 正規分布


独立成分分析を用いた実数値交叉（高橋ら, 2001）
主成分分析（PCA）と独立成分分析（ICA）で個体分布変換
 ブレンド交叉（Blend Crossover : BLX-α）
 多様性維持


進化戦略（Evolution Strategy : ES）における
correlated mutation （Schwefel）
個体が分布の方向を示すパラメータを持つ
 多次元正規分布によって新しい個体を生成

Intelligent Systems Design Laboratory
correlated mutation との相違点

Correlated mutation を用いた進化戦略は，DPMBGA と同じく，
設計変数間の相関を考慮して新しい個体を生成する

相違点は下のとおり
correlated
DPMBGA
相関を考慮する
タイミング
相関の情報の収集
相関の情報の
存在位置
mutation
確率モデルからの
突然変異
子個体生成
突然変異や組み替え特定の個体群から
により探索
算出
各個体が保持
サブ母集団全体で
保持
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
主成分分析（3）
m
i /   j (i  1,2,..., n)
寄与率（n 個体 × m 変数）

j 1
全固有値の和に対する
当該固有値の比率
その主成分によって，変数の保有する変動がどれだけ
説明されたかを示す

累積寄与率
 寄与率の累積値
x2
寄与率低 v2
i
m
 / 
k 1
k
j 1
j
(i  1,2,..., n)
v1 寄与率高
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
主成分分析が有効に機能しない原因の検討

主成分分析（PCA）実行時の問題点


Rastrigin（多峰性，依存関係無し）において，
PCAによる性能の低下
f (x)
DPMBGAにおける主成分分析


最良個体アーカイブの相関を解析
アーカイブの個体分布が対象問題の
特性を正確に反映する必要性
局所解で停滞
最良個体アーカイブ
推測：アーカイブ内の個体が局所解に陥り，
その更新が停滞したことにより探索性能が悪化
Intelligent Systems Design Laboratory
アーカイブの更新（Rastrigin,
Rosenbrock）
アーカイブ内で更新された個体数の履歴
Number of Updates


model 1 （全ての島でPCAを行うモデル）
500
Number of Updates

400
300
200
100
0
0.0E+00
5.0E+05
1.0E+06
500
400
300
200
100
0
0.0E+00
5.0E+05
1.0E+06
Number of Evaluations
Number of Evaluations
Rastrigin
Rosenbrock
Rastrigin
：探索が進むとアーカイブの更新が少なくな
る

Rosenbrock ：アーカイブ内の多くの個体が更新される
Intelligent Systems Design Laboratory
解の履歴（Rastrigin, Rosenbrock）
10世代ごとにアーカイブを消去するモデル
200
20
（erase/10）
Evaluation Value
Evaluation Value

150
100
normal
erase/10
50
0
0.0E+00
2.5E+05
5.0E+05
normal
erase/10
15
10
5
0
0.0E+00
2.5E+05
5.0E+05
Number of Evaluations
Number of Evaluations
Rastrigin
Rosenbrock
： erase/10 の性能がよい

Rastrigin

Rosenbrock ： normal がよい解を得る
アーカイブ更新の停滞により，主成分分析（PCA）の効果が低下
Intelligent Systems Design Laboratory
実験1のまとめ（PCAについての検討）


設計変数間の依存関係と主成分分析（PCA）の関係

依存関係のある問題 → PCA を行う DPMBGA が有効

依存関係の無い問題 → PCA を行わない DPMGAが有効
PCAが有効に機能しない原因

最良個体アーカイブの更新の停滞
性能向上のアプローチ

環境分散モデル

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
Boundary Extension by Mirroring
 Boundary
1998）
Extension by Mirroring (BEM) （Tsutsui,
探索領域の境界から一定距離以内の個体が生存
― 拡張率（re）
 探索領域の境界を基点として目的関数を折り返して評価
 探索領域の端に最適解を有する問題に対して有効
f(x)

extended space
search space
x
Intelligent Systems Design Laboratory
Intelligent Systems Design Laboratory
Intelligent Systems Design Laboratory

Download Report