Bayesian Networkを用いた
確率モデル遺伝的アルゴリズムの
解探索特性の検討
同志社大学 大学院 工学研究科
知識工学専攻 博士前期課程
2002年度724番
中村 康昭
2004年1月29,30日 修士論文諮問会
研究背景
最適化:目的関数の最大(最小)化
LSIの配置
トラス構造
たんぱく質の
構造解析
スケジューリング
様々なヒューリスティック手法(SA,GA等)が提案されている
2004年1月29,30日 修士論文諮問会
遺伝的アルゴリズム
Genetic Algorithm(GA)
生物の進化過程を模倣した最適化手法
環境により適合した個体が生存する
選択
(自然淘汰)
交叉
親個体の形質を受け継いだ子個体が生まれる
(有性生殖)
子個体の遺伝子が一部変異する
(突然変異)
部分解を組み合わせることにより良好な探索を行う
突然変異
[問題点]
従来の交叉では変数間に依存関係のある問題に対しては
部分解を破壊する可能性 [’97 Annie]
2004年1月29,30日 修士論文諮問会
変数間に依存関係のある問題
例)関数 f (x,y,z | 0≦x , y , z ≦ 10 ) の最小化問題
f (x,y,z) = x + y + z
f (x,y,z) = 2x - xy +y + z
各変数をそれぞれ
小さくすることにより最小化される
(依存関係はない)
x=0の時:y=0とすると最小
x≠0の時:yは大きくすると最小
xとyに依存関係がある
2004年1月29,30日 修士論文諮問会
変数間に依存関係のある問題
例)関数 f (x,y,z | 0≦x , y , z ≦ 10 ) の最小化問題
f (x,y,z) = x + y + z
f (x,y,z) = 2x - xy +y + z
各変数をそれぞれ
小さくすることにより最小化される
(依存関係はない)
x=0の時:y=0とすると最小
x≠0の時:yは大きくすると最小
xとyに依存関係がある
GAにおける交叉
解候補1
x
y
z
解候補2
x
y
z
セットにして交叉すべき
2004年1月29,30日 修士論文諮問会
変数間に依存関係のある問題
例)関数 f (x,y,z | 0≦x , y , z ≦ 10 ) の最小化問題
f (x,y,z) = x + y + z
f (x,y,z) = 2x - xy +y + z
各変数をそれぞれ
小さくすることにより最小化される
(依存関係はない)
x=0の時:y=0とすると最小
x≠0の時:yは大きくすると最小
xとyに依存関係がある
GAにおける交叉
解候補1
x
y
z
x
y
z
解候補2
x
y
z
x
y
z
2004年1月29,30日 修士論文諮問会
変数間に依存関係のある問題
例)関数 f (x,y,z | 0≦x , y , z ≦ 10 ) の最小化問題
f (x,y,z) = x + y + z
f (x,y,z) = 2x - xy +y + z
各変数をそれぞれ
小さくすることにより最小化される
(依存関係はない)
x=0の時:y=0とすると最小
x≠0の時:yは大きくすると最小
xとyに依存関係がある
解候補1
x
y
z
セットにして交叉すべき
解候補2
x
y
z
依存関係を認識する必要
2004年1月29,30日 修士論文諮問会
ベイジアンネットワーク
変数間に存在する依存関係を有向グラフにより表現するデータ構造
x と y の間に依存関係があるとき
構築可能なネットワーク
構築可能なネットワークから,問題の特性を示すものを選ぶことが必要
2004年1月29,30日 修士論文諮問会
ベイジアンネットワークの評価方法
2004年1月29,30日 修士論文諮問会
ベイジアンネットワークの活用
最適化手法としてのベイジアンネットワークの適用
ネットワークと良好な解から新たな解を生成する
ネットワーク
x : 50%の確率で0と10が発現
y : xの値に応じて発現確率が変化
x=10のとき: 75% の確率で10
z : 50%の確率で0が発現
残りの確率で1と2が発現する
良好な解の分布から新たな解の候補を生成することができる
2004年1月29,30日 修士論文諮問会
確率モデル遺伝的アルゴリズム
Probabilistic Model Building Genetic Algorithm
(PMBGA,確率モデルGA)
(1)良好な個体を母集団から選択
分布の推定
個体
(探索点)
(2)確率モデルの構築
母集団
ベイジアンネットワーク
(4)母集団内の個体と置き換え
(3)新しい個体を生成
部分解の破壊を防止し,良好な探索をすることが可能となる
2004年1月29,30日 修士論文諮問会
研究目的
ベイジアンネットワークを用いた確率モデルGA [‘99 Pelikan]
各変数としてバイナリ値{0,1}を用いて検討
• 依存関係のある問題に対する探索の有効性
• 母集団の高い収束性
実問題をバイナリ値のみで表現するのは困難
【目的】
・バイナリ値以外の問題にベイジアンネットワークを適用
・解探索特性を検討し,遺伝的操作を適用する
2004年1月29,30日 修士論文諮問会
対象問題
部分だまし問題
2
0
1
1
0
1
・・・
2
1
1
全設計変数を3変数ずつの部分問題に分割
各変数が取ることができる値は{0,1,2}の3種類
l 1
f ( X )  m ax f k ( ui ) i 0
ui :3変数中にiが含まれる個数
含まれるビットが全て“0,1”のとき
 0.9
 0.8

f ( u1 )  
 0.7
1.0
if u1  0
if u1  1
if u1  2
if u1  3
3変数に“2”が含まれるとき
 0 . 5 i f u2  1

f ( u 2 )   0 i f u2  2
1.1 i f u  3
2

2004年1月29,30日 修士論文諮問会
関数評価値の具体的な例
【問題の特徴】
高
評価値
低
2
2
2
1
1
1
0
0
0
1
0
0
1
0
2
2
0
2
だまし問題が入れ子状態となっている
“2” に注目
3変数がすべて“2”の時が評価値は最大
それ以外は“2”の数が多いほど評価値は小
“2” が0個の時
3変数がすべて“1”の時評価値は大
それ以外は“1”の数が多いほど評価値は小
最適解:すべての部分問題で3変数が“2”となるとき
2004年1月29,30日 修士論文諮問会
パラメータ
個体数
遺伝子長
300×i (i=1~10)
30(10個の部分問題)
個体抽出率
50%
個体置換率
50%
終了条件
各ノードへのリンク上限
突然変異率
試行回数
1000世代もしくは
母集団の95%以上がエリートに収束
2
0
30
2004年1月29,30日 修士論文諮問会
実験結果
• 最適解に到達していない
• 個体数が増えると収束までの評価計算が増加する
2004年1月29,30日 修士論文諮問会
考察
母集団に含まれる個体が増加するにつれて
得られる解はよくなるが,最適解に到達していない
個体数をさらに増やす
評価計算回数の増加につながる
最適解に到達していない状態で母集団が収束
母集団の多様性を保つ遺伝的操作の適用
【対応策】
GAにおける突然変異の要素を取り入れ,
母集団に含まれる個体の多様性を維持する
適用する突然変異について検討を行う
2004年1月29,30日 修士論文諮問会
突然変異の適用
誤った依存関係を認識して母集団が安定している
Z
Z
Xa
Xa
Xb
Xc
Xb
Xc
有効なネットワーク
・・・
Z
・・・
Xa Xb
Xc ・・・
依存関係を誤認識しているときには,一部のネットワークを
除外して値を決定する方法が有効
2004年1月29,30日 修士論文諮問会
従来のGAにおける突然変異
誤った依存関係を認識して母集団が安定している
Z
Z
Xa
Xa
Xb
Xb
Xc
Xc
有効なネットワーク
・・・
2
・・・
12
1
1
・・・
各変数が突然変異をするかどうか値の決定後に決まる
依存関係を表わすネットワークを無視して1つの変数が変わる
2004年1月29,30日 修士論文諮問会
本研究で検討する突然変異
変数を決定する時に
各変数について,突然変異を行うかどうか決定する
Z
Z
Xa
Xa
Xb
Xb
Xc
Xc
有効なネットワーク
・・・
2
・・・
12
2
2
・・・
子孫ノードの値は突然変異後の値によって決定する
依存関係を表わすネットワークが有効に活用される
2004年1月29,30日 修士論文諮問会
パラメータ設定
個体数
遺伝子長
300×i (i=1~10)
30
個体抽出率
50%
個体置換率
50%
終了条件
各ノードへのリンク上限
突然変異率
試行回数
1000世代
2
1/30(1/遺伝子長)
30
2004年1月29,30日 修士論文諮問会
実験結果
従来の突然変異
検討する突然変異
検討する突然変異において,良好な結果が得られた
2004年1月29,30日 修士論文諮問会
まとめ
ベイジアンネットワークを用いた確率モデルGA
依存関係を持つバイナリ値以外の問題に対する検討実験
【結果】従来の手法では最適解に到達しない
解探索特性に沿った突然変異の適用
確率モデルを考慮した形での突然変異を行うことにより
従来の突然変異を適用したときよりも良好な結果を得た
今後の課題
より多くの変数値を用いる実問題への適用
2004年1月29,30日 修士論文諮問会
[講演発表]
第46回 システム制御情報学会 研究発表講演会
「Actor-Criticを用いた知的ネットワークシステムの提案」
質疑応答
2004年1月29,30日 修士論文諮問会
補足資料
2004年1月29,30日 修士論文諮問会
実験結果
・最適解に到達していない
・母集団サイズが増えると収束までの評価計算が増加する
個体数
300
600
900
1200
1500
1800
2100
2400
2700
3000
収束回数
30
30
30
30
30
29
26
26
26
25
2004年1月29,30日 修士論文諮問会
コード化
遺伝的アルゴリズムでは,形質を示す値を遺伝子情報に変換する
0~2の値をバイナリコーディング
コード化
0 → 00
1 → 01
2 → 10
ルール
最初のビットが0のとき:次のビットは0,1
最初のビットが1のとき:次のビットは1
変数間の依存関係ではない
変数間の依存関係
「00」など,一つの設計変数を表現するビット群の間に生じている
依存関係であり,個々のビット間に生じる依存関係は無意味
コード化せずに変数間の依存関係を認識する必要性
2004年1月29,30日 修士論文諮問会
ベイジアンネットワークの構築
3変数があったときに考えられる
ネットワークの構築パターンについて考える
構築可能なネットワーク
各ネットワークを解の傾向から評価
依存関係を示す
ネットワークを特定することが可能
良好な解の分布からネットワークのモデルを構築する
2004年1月29,30日 修士論文諮問会
最適解に収束しなかった試行(掲載する例)
収束しているが,最適解を得ていない試行
計算回数 個体の持つ遺伝子情報
適合度
12150 000,111,111,111,111,111,111,111,111,111 9.9
9000
111,111,111,111,111,111,111,111,000,111 9.9
9900
111,111,111,111,111,111,111,111,111,000 9.9
9450
111,111,000,111,111,111,111,111,111,111 9.9
収束していない試行
計算回数 個体の持つ遺伝子情報
適合度 含有率
180000 000,111,111,111,111,000,111,111,111,111
9.8
18%
180450 111,111,111,111,000,000,111,111,111,111
9.8
79%
2004年1月29,30日 修士論文諮問会
ベイジアンネットワークの信頼度
親ノード
K2 metric
n
qi
( N 'ij )
i 1
j 1
( N 'ij  Nij )
p( D)  
ri

x1
x2
子ノード
(1  Nijk )
k 1
(1)
( N )  ( N  1)!, n :ノード数 ,
qi : 親ノードのパターン数 , ri : 子ノードのパターン数
K2 metricの大きくなるネットワークとは
親ノードの値は分散している
親ノードの値が決定したときの子ノードの値は偏っている
2004年1月29,30日 修士論文諮問会
3変数中に2が含まれる確率
各変数の値は条件付き確率表(CPT)により決定
CPTは優良個体群の分布に基づき作成
X1から順に値が決定する
X1
X1の値の発現確率
P(X1)=0 P(X1)=1 P(X1)=2
X2
X3
2004年1月29,30日 修士論文諮問会
3変数中に2が含まれる確率
各変数の値は条件付き確率表(CPT)により決定
CPTは優良個体群の分布に基づき作成
X1から順に値が決定する
X1
X2
X3
X2の値の発現確率
X1 P(X2)=0
P(X2)=1
P(X2)=2
0
1
2
2004年1月29,30日 修士論文諮問会
3変数中に2が含まれる確率
各変数の値は条件付き確率表(CPT)により決定
CPTは優良個体群の分布に基づき作成
X1から順に値が決定する
X1
X2
X3
X3の値の発現確率
X1
X2
0
0
0
1
0
2
P(X2)=0 P(X2)=1
P(X2)=2
…
2
2
低
低
高
2004年1月29,30日 修士論文諮問会
3変数中に2が含まれる確率
各変数の値は条件付き確率表(CPT)により決定
CPTは優良個体群の分布に基づき作成
X1から順に値が決定する
X1
X1の値の発現確率
P(X1)=0 P(X1)=1 P(X1)=2
小
X2の値の発現確率
X1 P(X2)=0
0
P(X2)=1
P(X2)=2
X3
X3の値の発現確率
X1
X2
0
0
0
1
0
2
P(X2)=0 P(X2)=1
P(X2)=2
…
1
2
X2
2
2
高
X1=2となる確率が低くなると全体の2の発現確率は下がる
2004年1月29,30日 修士論文諮問会
最終的に収束する解
個体数を300としたときの1試行の例
収束する解 [111,111,111,111,222,111,111,111,111,000]
4500(150×30)の変数中,“2”が含まれるのが3個まで淘汰される
2004年1月29,30日 修士論文諮問会
実験結果(提案手法:突然変異率1%)
従来の突然変異
提案する突然変異
検討を行った突然変異において,良好な結果が得られた
[デモンストレーション]
2004年1月29,30日 修士論文諮問会
最適解が得られていない原因の検討
ベイジアンネットワーク
3変数のうち
最初の変数に残りの変数が依存
X1
2
0
X2
2
1
X3
2
最初の変数が“2”ならば残りの2変数
“2”となると評価値が高くなる
0
最初の変数が“0”や“1”ならば
残りの2変数も{0,1}で構成するほうがよい
依存関係のある最初の変数の値の発現確率に
残りの変数が影響される
2004年1月29,30日 修士論文諮問会
優良個体に含まれる変数値の推移
個体数を300としたときの1試行の例
各部分問題で3変数がともに“2”でなければ評価値が低いため
“2”が淘汰されている
2004年1月29,30日 修士論文諮問会
従来のGAにおける突然変異
すべての変数が決定している状態で
各変数について,突然変異を行うかどうか決定する
2
2
X1
2
1
X2
X4
1
1
・・・
X3
X5
X6
2004年1月29,30日 修士論文諮問会
従来のGAにおける突然変異
すべての変数が決定している状態で
各変数について,突然変異を行うかどうか決定する
2
2
X1
2
2
X2
X4
1
1
X3
X5
・・・
X1
X6
X2
X4
X3
X5
X6
ネットワークの依存関係を考慮せずに突然変異する
2004年1月29,30日 修士論文諮問会
従来のGAにおける突然変異
すべての変数が決定している状態で
各変数について,突然変異を行うかどうか決定する
2
2
X1
2
1
X2
X4
1
1
・・・
X3
X5
X6
2004年1月29,30日 修士論文諮問会
従来のGAにおける突然変異
すべての変数が決定している状態で
各変数について,突然変異を行うかどうか決定する
2
2
X1
2
2
X2
X4
1
1
X3
X5
・・・
X1
X6
X2
X4
X3
X5
X6
ネットワークの依存関係を考慮せずに突然変異する
2004年1月29,30日 修士論文諮問会
本研究で提案する突然変異
変数を決定する時に
各変数について,突然変異を行うかどうか決定する
X1
X2
X4
X3
X5
X1
X6
X2
X4
X3
X5
X6
子孫ノードの値は突然変異後の値によって決定する
依存関係を表わすネットワークが有効に活用される
2004年1月29,30日 修士論文諮問会
従来のGAにおける突然変異
すべての変数が決定している状態で
各変数について,突然変異を行う
Za
Za
Xb
Xb
Xc
・・・
2
12
1
Xc
Xd
1
Xd
・・・
各変数が突然変異をするかどうか値の決定後に決まる
依存関係を表わすネットワークを無視して1つの変数が変わる
2004年1月29,30日 修士論文諮問会
研究目的
ベイジアン最適化アルゴリズム(BOA)[‘99 Pelikan]
各変数としてバイナリ値を用いて検討
・母集団の高い収束性
・依存関係のある問題に対する探索の有効性
実問題を取り扱うには,バイナリ値にコード化する必要がある
実際の変数間の依存関係
コード化前の変数間に生じている依存関係は
各ビット間の依存関係は関係がない
問題に応じてバイナリ値に依存関係の生じるコード化が必要
【目的】 コード化せずに表現型の値を変数として用いる
2004年1月29,30日 修士論文諮問会
2004年1月29,30日 修士論文諮問会
ダウンロード

X - 知的システムデザイン研究室