GA - Tanaka-Waizumi Research Group

遺伝的アルゴリズムへの
統計力学的アプローチ
大阪大学大学院理学研究科
鈴木譲
CISJ2005 於早稲田大学理工学部
2005年11月8日
GA
f :
L
ビット
個体( L ビットの列) → 正実数（適合度）
L
ビット
L
ビット
個体 1
個体 1
個体 1
個体 2
個体 2
個体 2
集団
集団
集団
個体
M
世代１
M
個体
世代 2
世代交代によって、集団に適合度
M
世代 t
個体
f ( i ) の高い個体 i が含まれるようにする
L は、十分に大きい ( L が小さければ全探索)
遺伝的操作
• 選択：
c( i ) ：
(
)
(
)
c
i
f
i
P
j c( i ) f ( i )
個体
に比例する確率で個体
を選択
i の頻度
• 交叉：
1
i
2
3
4
1
2
3
d
a
b
c
4
1点交叉
a
b
c
d
(他に複数点交叉、一様交叉など)
• 突然変異
a
b
c
d
a
B
c
( 選択2回 → 交叉1回 → 1個体をランダムに選択 → 突然変異 ) x
d
M
回
エルゴードな有限マルコフ連鎖
集団内の個体の順序は気にしない
L = 2; M = 3; û = ( c(00) ; c(01) ; c(10) ; c(11))
(0,0,0,3), (0,0,1,2), (0,0,2,1), (0,0,3,0), (0,1,0,2), (0,1,1,1),
(0,1,2,0), (0,2,0,1), (0,2,1,0), (0,3,0,0), (1,0,0,2), (1,0,1,1),
(1,0,2,0), (1,1,0,1), (1,1,1,0), (1,2,0,0), (2,0,0,1), (2,0,1,0),
(2,1,0,0), (3,0,0,0)
Q = Q( û 0j û) ：
推移確率行列
有限マルコフ連鎖がエルゴード的：
突然変異確率>0
Qk
=)
の各成分 > 0 となる有限の
9k
エルゴード
よい解が早く見つかるのなら、交叉、突然変異にこだわることはない
ボルツマン分布ありきとしてのGA
É ì ( > 0) ;
f (i )
M à! 1
g( i ) :=
最大
1
Éì
( )
log f ( i )
g( i )
最大
交叉なし、突然変異なしであれば、
pt + 1( i ) / pt ( i ) expf É ì g( i )g
ì 0 > 0; ì t := ì 0 + t É ì
(温度の逆数が増えていく)
pt ( i ) = expf ì t g( i )g=Z
lim t !
Z=
1
pt ( i ) > 0=) f ( i )
P
j 2 f 0;1gL
最大
expf ì t g( j )g
（
L の指数時間）
なぜGA
M < 1 ;
交叉なし、突然変異なし
=)
エルゴードではない
• GAは進化の過程を模倣しているので、適合性の高い個体だけが生き残る
(John Holland)
• 飛行機が飛ぶことを誰も証明していないが、皆安心して乗っている
(David Goldberg)
GAは、エルゴード性を維持しながら、
ボルツマン分布を推定しながら、
温度を下げている
(Heinz Mulenbein)
Estimation of Distribution Algorithms
1.
初期集団をランダムに発生、
2.
t 世代目の集団に基づいて、
t := 1
2a.
M 個中、適合度の高い N 個体を選択
2b.
N 個の個体に基づいて、 pt ( i ) を推定
2c.
êt ( i ) に基づいて、 t + 1世代の M 個の個体をランダムに生成
p
3.
停止条件が満足されない場合、t
:= t + 1
として、2へ
エルゴードな有限マルコフ連鎖
(公理論的なGAの範囲内)
BN
確率変数間の条件付独立性を有向グラフで図示
P(C,A,R,E,B) = P(B) P(C|B) P(R|E,B) P(A|R,E,B) P(C|A,R,E,B)
Burglary
Earthquake
Radio
Announcement
Alarm
Call
BN
確率変数間の条件付独立性を有向グラフで図示
P(C,A,R,E,B) = P(B) P(E|B) P(R|E,B) P(A|R,E,B) P(C|A,R,E,B)
Burglary
Earthquake
Radio
Announcement
Alarm
Call
BN
確率変数間の条件付独立性を有向グラフで図示
P(C,A,R,E,B) = P(B) P(E|B) P(R|E,B) P(A|R,E,B) P(C|A,R,E,B)
P(C,A,R,E,B) = P(B) P(E) P(R|E) P(A|E,B) P(C|A)
Burglary
Earthquake
Radio
Announcement
Alarm
Call
BNの推定との関係
P(X (1) = x (1) ; X (2) = x (2) ; ááá; X ( L ) = x ( L ) )
QN
= i = 1 P(X ( i ) = x ( i ) j(X ( k) = x ( k) ) k2 ù(i ))
ù( i ) ò f 1; 2; ááá; i à 1g; ù(1) = f g
M
個の例から
X
X
ù = (ù(1) ; ù(2) ; ááá; ù( L ) ) を推定
(1)
=
ááá
(1)
=
(1)
x 1 ; ááá; X ( L )
(1)
x M ; ááá; X ( L )
構造推定も、パラメータ推定も
L
=
(L )
x1
個体数
(L )
xM
の集団と
みなせる
ááá
=
の指数時間かかる
M
個体長 L
GAにおける平均場近似
各変数を独立
P(X (1) = x (1) )P(X (2) = x (2) )áááP(X ( L ) = x ( L ) )
とみなして、
qt (x ( j ) ) = P(X ( j ) = x ( j ) ); j = 1; ááá; L
のパラメータ推定のみを行う(相対頻度)
ê
qt ( i ) =
O( L )
QL
(j )
ê
(
)
q
x
j=1 t
i = (x (1) ; ááá; x ( L ) )
の計算量だが、K-L情報量
D (ê
pt jj ê
qt )
大
GAにおけるベータ近似
分布
êt
p
のグラフを D ( p
êt jj ê
qt ) 最小の木で近似
( k;l ) ( k )
ê
qt ( x ; x ( l ) )
P
=
I ( k; l ) :=
H ( k) :=
P
P
êt (ááá; x ( k) ; ááá; x ( l ) ; ááá)
p
( k;l )
ê
qt
( k;l )
log
( k)
ê
qt
( ) ()
k l
ê
qt qt
( k)
qt log ê
qt
x ( k) à ê
P
P
êt jjê
D (p
qt ) =
f k;l g2 E I ( k; l )
k 2 V H ( k) à
Chow-Liuアルゴリズム
V = f 1; 2; ááá; L g; E = f g
として、
E [ f f k; l gg がループを持たない
1．
２．
I ( k; l )(õ 0)
となる f
１
３
k; l g を E
２
４
が最大
に加えていく ( D ( p
êt jj ê
qt ) が最小)
l
k
1
2
3
4
1
I ( k; l )
2
6
3
5
4
4
Ｋ
K
3
2
1
Chow-Liuアルゴリズム
V = f 1; 2; ááá; L g; E = f g
として、
E [ f f k; l gg がループを持たない
1．
２．
I ( k; l )(õ 0)
となる f
１
３
k; l g を E
２
４
が最大
に加えていく ( D ( p
êt jj ê
qt ) が最小)
l
k
1
2
3
4
1
I ( k; l )
2
6
3
5
4
4
Ｋ
K
3
2
1
Chow-Liuアルゴリズム
V = f 1; 2; ááá; L g; E = f g
として、
E [ f f k; l gg がループを持たない
1．
２．
I ( k; l )(õ 0)
となる f
１
３
k; l g を E
２
４
が最大
に加えていく ( D ( p
êt jj ê
qt ) が最小)
l
k
1
2
3
4
1
I ( k; l )
2
6
3
5
4
4
Ｋ
K
3
2
1
Chow-Liuアルゴリズム
V = f 1; 2; ááá; L g; E = f g
として、
E [ f f k; l gg がループを持たない
1．
２．
I ( k; l )(õ 0)
となる f
１
３
k; l g を E
２
４
が最大
に加えていく ( D ( p
êt jj ê
qt ) が最小)
l
k
1
2
3
4
1
I ( k; l )
2
6
3
5
4
4
Ｋ
K
3
2
1
Chow-Liuアルゴリズム
V = f 1; 2; ááá; L g; E = f g
として、
E [ f f k; l gg がループを持たない
1．
２．
I ( k; l )(õ 0)
となる f
１
３
k; l g を E
２
４
が最大
に加えていく ( D ( p
êt jj ê
qt ) が最小)
l
k
1
2
3
4
1
I ( k; l )
2
6
3
5
4
4
Ｋ
K
3
2
1
Chow-Liuアルゴリズム
V = f 1; 2; ááá; L g; E = f g
として、
E [ f f k; l gg がループを持たない
1．
２．
I ( k; l )(õ 0)
となる f
１
３
k; l g を E
２
４
が最大
に加えていく ( D ( p
êt jj ê
qt ) が最小)
l
k
1
2
3
4
1
I ( k; l )
2
6
3
5
4
4
Ｋ
K
3
2
1
Chow-Liuアルゴリズム
V = f 1; 2; ááá; L g; E = f g
として、
E [ f f k; l gg がループを持たない
1．
２．
I ( k; l )(õ 0)
となる f
１
３
k; l g を E
２
４
が最大
に加えていく ( D ( p
êt jj ê
qt ) が最小)
l
k
1
2
3
4
1
I ( k; l )
2
6
3
5
4
4
Ｋ
K
3
2
1
Chow-Liuアルゴリズム
V = f 1; 2; ááá; L g; E = f g
として、
E [ f f k; l gg がループを持たない
1．
２．
I ( k; l )(õ 0)
となる f
１
３
k; l g を E
２
４
が最大
に加えていく ( D ( p
êt jj ê
qt ) が最小)
l
k
1
2
3
4
1
I ( k; l )
2
6
3
5
4
4
Ｋ
K
3
2
1
Chow-Liuアルゴリズム
V = f 1; 2; ááá; L g; E = f g
として、
E [ f f k; l gg がループを持たない
1．
２．
I ( k; l )(õ 0)
となる f
１
３
k; l g を E
２
４
が最大
に加えていく ( D ( p
êt jj ê
qt ) が最小)
l
k
1
2
3
4
1
I ( k; l )
2
6
3
5
4
4
Ｋ
K
3
2
1
Chow-Liuアルゴリズム
V = f 1; 2; ááá; L g; E = f g
として、
E [ f f k; l gg がループを持たない
1．
２．
I ( k; l )(õ 0)
となる f
１
３
k; l g を E
２
４
が最大
に加えていく ( D ( p
êt jj ê
qt ) が最小)
l
k
1
2
3
4
1
I ( k; l )
2
6
3
5
4
4
Ｋ
K
3
2
1
Chow-Liuアルゴリズム
V = f 1; 2; ááá; L g; E = f g
として、
E [ f f k; l gg がループを持たない
1．
２．
I ( k; l )(õ 0)
となる f
１
３
k; l g を E
２
４
が最大
に加えていく ( D ( p
êt jj ê
qt ) が最小)
l
k
1
2
3
4
1
I ( k; l )
2
6
3
5
4
4
Ｋ
K
3
2
1
Chow-Liuアルゴリズム
V = f 1; 2; ááá; L g; E = f g
として、
E [ f f k; l gg がループを持たない
1．
２．
I ( k; l )(õ 0)
となる f
１
３
k; l g を E
２
４
が最大
に加えていく ( D ( p
êt jj ê
qt ) が最小)
l
k
1
2
3
4
1
I ( k; l )
2
6
3
5
4
4
Ｋ
K
3
2
1
Chow-Liuアルゴリズム
V = f 1; 2; ááá; L g; E = f g
として、
E [ f f k; l gg がループを持たない
1．
２．
I ( k; l )(õ 0)
となる f
１
３
k; l g を E
２
４
が最大
に加えていく ( D ( p
êt jj ê
qt ) が最小)
l
k
1
2
3
4
1
I ( k; l )
2
6
3
5
4
4
Ｋ
K
3
2
1
Chow-Liuアルゴリズム
V = f 1; 2; ááá; L g; E = f g
として、
E [ f f k; l gg がループを持たない
1．
２．
I ( k; l )(õ 0)
となる f
１
３
k; l g を E
２
４
が最大
に加えていく ( D ( p
êt jj ê
qt ) が最小)
l
k
1
2
3
4
1
I ( k; l )
2
6
3
5
4
4
Ｋ
K
3
2
1
Chow-Liuアルゴリズム
V = f 1; 2; ááá; L g; E = f g
として、
E [ f f k; l gg がループを持たない
1．
２．
I ( k; l )(õ 0)
となる f
k; l g を E
１
２
３
４
が最大
に加えていく ( D ( p
êt jj ê
qt ) が最小)
E = f f 1; 2g; f 1; 3g; f 1; 4gg
Ｋ
K
ボルツマン分布の因数分解
自明な因数分解
(1)
pt (x ; ááá; x
というよりは、
L
(L )
)=
QL
( j ) (1)
( j à 1)
(
j
ááá
)
p
x
x
;
;
x
j=1 t
によらない定数個数の変数の因子の積に
f (001) ; f (011) が大 =)
スキーマ
0# 1
の適合度大
スキーマ仮説: GAは、適合度の高いスキーマを学習する情報処理
ìt
が大きくなっても、ボルツマン分布の因数分解は同じ（事前に行えるはず）
場合1:
g( x ) が加法的に分解可能
g : f 0; 1gL !
R + ; g( x ) = log f ( x )
s1; s2; ááá; sm ò V := f 1; 2; ááá; L g; x = (x (1) ; ááá; x ( L ) )
Pm
g( x ) =
k= 1 gk( x sk)
g(x (1) ; x (2) ; x (3) ) = J 23x (2) x (3) + J 31x (3) x (1) + J 12x (1) x (2)
=) V = f 1; 2; 3g; s1 = f 2; 3g; s2 = f 3; 1g; s3 = f 1; 2g
g(x (1) ; x (2) ; x (3) ) = J 23x (2) x (3) + J 31x (3) x (1) + J 4x (4)
=) V = f 1; 2; 3; 4g; s1 = f 2; 3g; s2 = f 3; 1g; s3 = f 4g
Running Intersection Property
s1 = f 2; 3g; s2 = f 3; 1g; s3 = f 1; 2g
d0 = f g; d1 = f 2; 3g; d2 = f 1; 2; 3g; d3 = f 1; 2; 3g
b1 = f 2; 3g; b2 = f 1g; b3 = f g
ò s1; s2
c1 = f g; c2 = f 3g ò s1; c3 = f 1; 2g 6
d0 = f g; dk := [
k
j = 1 sj ;
k = 1; 2; ááá; m について、bk 6
= fg
dm = V
k = 2; 3; ááá; m について、 ck ó sj なる 9j ( < k )
1. 各
2.
3.
bk := skndkà 1; ck := sk \ dkà 1
f skgm
k= 1
RIPを満たさない
Running Intersection Property
s1 = f 2; 3g; s2 = f 3; 1g; s3 = f 4g
d0 = f g; d1 = f 2; 3g; d2 = f 1; 2; 3g; d2 = f 1; 2; 3; 4g
b1 = f 2; 3g; b2 = f 1g; b3 = f 4g
c1 = f g; c2 = f 3g ò s1; c3 = f g ò s1
f skgm
k= 1
RIPを満たす
pt (x (1) ; x (2) ; x (3) ) = pt (x (2) ; x (3) )pt (x (1) j x (3) )pt (x (4) )
=
pt ( x (2) ;x (3) ) pt ( x (3) ;x (1) ) pt ( x (4) )
pt ( x (3) )
RIPまとめ
f skgm
k = 1 の非巡回性
(
( ) f skgm を頂点とするJunction Tree が存在）
k= 1
RIPが満足されないとき
１．
f skgm
k= 1
の順序を変える
２．
f skgm
k= 1
の一部をマージする
場合2：スキーマが無向グラフで表現
確率変数間の条件付独立性
JT = (V; E)
１．各
C2 V
が無向グラフ
に対して、
有向グラフ：ベイジアンネットワーク(BN)
無向：マルコフネットワーク(MN)
G = ( V; E )
のJunction Tree
Cò V
２．
G の各クリーク c に対して C ó c となる C 2 V
３．
C1; C2 2 V
を結ぶ各 C
2V
に対して、 C
が存在
ó C1 \ C2
Junction Tree アルゴリズム
に辺を加えて長さ4以上のサイクルを無くす (三角化)
1.
G
2.
C1; ááá; Cm
G のクリークとし、
V := f C1; ááá; Cmg:E := f g
以下の2条件を満たす f Ck ; Cl g を E に加える。
3.
を
がループを持たない
3a．
E[ f f Ck; Cl gg
3b．
# ( Ck \ Cl )(õ 0)
Eã： E
の各要素 f
が最大
Ck; Cl g を Ck \ Cl
pt ( V) =
Q
pt ( v)
2V
v
Q
e2Eã pt ( e)
で置き換えた集合
x (1)
x (2)
(3)
x (4)
x
x (1)
x (2)
(3)
x (4)
x
x (1)
x (2)
(3)
x (4)
x
C1 = f x (1) ; x (2) ; x (3) g; C2 = f x (1) ; x (3) ; x (4) g
x (1)
x (2)
(3)
x (4)
x
C1 = f x (1) ; x (2) ; x (3) g; C2 = f x (1) ; x (3) ; x (4) g
x
(1)
x (3)
x
(2)
x (1) x (3)
x (1) x (4)
x (3)
C1 = f x (1) ; x (2) ; x (3) g; C2 = f x (1) ; x (3) ; x (4) g
V = f C1; C2g; E = f f C1; C2gg; Eã = f C1 \ C2g
(1) (2) (3)
(1) (3) (4)
(
)
(
p
x
;x
;x
p
x
;x ;x )
t
pt (x ; x ; x ; x ) = t
pt ( x (1) ;x (3) )
(1)
(2)
(3)
(4)
Junction Tree
x
(1)
x (3)
x
(2)
x (1) x (3)
JT = (V; E)
x (1) x (4)
x (3)
最適なJTを求める
• Junction Treeは、各無向グラフに対して、複数個存在
• 分子の各因数の変数の個数の和を最小にすることは、NP困難
まとめ
• GAは、統計力学的にみると、もっとよくわかる
• GAは、エルゴードな有限マルコフ連鎖の中で、よいものを選べばよい。
• よいGAならば、温度を下げながら、エルゴード性を保ちながら、ボルツマ
ン分布を推定している。
• 個体長 L が十分に大きいので、 L の多項式時間で実行せよ。
• 構造推定 vs 因数分解。因数分解もそれなりに難しい。
今後に向けて: GA vs 変分方程式
P
m
g( x ) =
k= 1 gk( x sk)
P
Pm
=
x q( x ) g( x ) =
k= 1 askqk( x sk)
U( q)
D ( qjj p) = U( q) à H ( q) +
平均場近似であれば
定数
Qm
q( x ) = k= 1 qk( x )
Pm P
H (q) = à k= 1 x (k) q(x ( k) ) log q(x ( k) )
@D ( qjj p)
@qk
=
qk =
qk
log 1à qk
+
1
1+ exp[@U=@qk]
@U
@qk
= 0
ベーテ近似、菊池近似でも最適化問題は解ける
D ( qjj p) !
mi n
確率の和=1の制約条件の下で、 q
に関するラグランジュ未定係数法を解く
問題： GAによる解法と変分方程式の解法で、相互乗り入れはあるのか

Download Report