一様でない遷移確率を用いた 焼き鈍し法
宗久・丹沢研究室 T04kf022
鈴木悠也
焼き鈍し法
• 焼きなまし法とは最大値探索問題の解法の１ つであり、温度を示すパラメーターを徐々に 下げることにより最適な解を求めるものであ る。
研究目的
今回の研究目的は温度が一定という条件の 下でも温度を徐々に下げていく場合と同様に 一様でない遷移確率を実現し最適な解を求 めることである。
焼き鈍し法のアプローチ
集合Ｓの要素を変数とする目的関数fの最大値 探索問題
fをエネルギーとみなし、その最大値を与える平 衡状態 を求める問題と考える
収束状態が最適分布となるようなマルコフ 連鎖をつくり、適当な初期状態から状態遷 移させる
↓
tb
マルコフ連鎖
次の状態が現在の状態だけに依存するような 過程のうち時間のパラメータｔが離散的で状態 空間Ｓが有限であるときのもの
過程が時間に依存しないとき
一様なマルコフ連鎖 であるという 過程が時間に依存するとき
一様でないマルコフ連鎖 であるという
状態遷移確率Ｐ
( )
と表される
状態遷移確率は
に遷移する から
のとき状態
i t
X j t
X P
j i
S j
i
=
= +
∈
) ( )
1 (
,
遷移確率行列Ｍ
( )
の遷移確率行列という 行列Ｍをマルコフ連鎖
列の成分とする 行
を を満たすとき
かつ
が 列の成分
行
j i
t j i M
t j i M t
j i M
i t
X j t
X P t
j i M j
i
S j
)
; , (
1 )
; , ( 0
)
; , (
) ( )
1 (
)
; , (
=
≥
=
= +
≡
∑∈
チャップマン・コルモゴルの方程式
• 一様でないマルコフ連鎖
• 一様なマルコフ連鎖
( )
る 行列は下の式で表され ｘ行ｙ列の要素とする
i を t
X j m
t X P m
t t j i
M ( , ; , + ) ≡ ( + ) = ( ) =
)) 1 (
( )
1 (
) ( )
,
(t t + m = M t ⋅ M t + M t + m −
M
M m
m t
t
M ( , + ) =
マルコフ連鎖のエルゴード定理
マルコフ連鎖の遷移確率行列Ｍが既約かつ非 周期的であるとき初期状態分布ｃによらず時間 経過とともに平衡分布ｂに収束する
b cM m t
t
m =
∞
lim→
• 一様でないマルコフ連鎖でも以下の式が 成り立つ
Ｍは以下の式を満たすものである
b m
M M
cM t
t
m ⋅ =
∞
→ (0) (1) ( )
lim
b k
bM t
t ( )=
:平衡分布
→b
t
Ｍを掛けることにより誤差が等しいか小さくなる ことの証明
∑ −
=
−
i
i i
t
tc b c b
b c
b
cM t t t
t − ≤ −
0
1
≥
∑ =
ji i
ji
M
M
実際の状態分布 :
tc
b bM t
t =
( ) ( )
( ) ( )
(c b) M (c b) c b
M b
c M
b c
M b
c M
b c
bM cM
t t
j
j i
ji j
j
i j
ji j
i j
ji j
i j
ji j
t t
t t
−
=
−
=
−
=
−
≤
−
−
=
−
=
−
=
∑
∑
∑
∑ ∑
∑ ∑
∑ ∑
右辺 左辺
b c
b
cM t t t
t − ≤ −
等号が成立するのはすべての成分に対して か
が成り立つときである
ただし 以外では
なのですべての成分に対して
が成り立つことはないので
( c − b) j M ji ≥ 0
b c =
( c − b) j M ji ≤ 0
(c − b) j ≥ 0
(c − b) j ≤ 0
0 ,
1 ,
0 ,
1 ≥ = ≥
= ∑
∑ i
i
i i
i
i c b b
c
等号が成立するには
が存在する必要がある しかし
ｎは数回程度で上の式は成り立つので状態が すでに平衡状態に達しているとき以外ではほぼ 等号は成立はしない
[M (1)M (2)M (n)]ij ≠ 0
= 0 M ji
マルコフ連鎖を作るための平衡分布として ボルツマン分布がある
( ) ( f T )
T T f
b i
S i
i
i exp /
/ exp
) 1
( ∑
∈
=
order-3だまし問題を使用する
関数ｆの値は表1の値を使用する 表１：関数ｆの値
マルコフ連鎖の設計
受理行列Aと遷移行列Ｑ（ｔ）を用いてi行j列
の成分Ｍ(i,j;t)が次式で表される行列Ｍを作る
=
−
≡ ∑ ≠
≠ x j
j i
for j
i A t
j i Q
j i
for j
i A t
j i Q t
j i
M
) , ( )
; , ( 1
) , ( )
; , ( )
; , (
マルコフ連鎖の設計（２）
行と列の要素数が集合Sの要素数に等しく、
i行j列の成分A(i,j)が次式で表されるよう な行列Aを考える
( )
) ,
0 ( )
/ 1 ( )
(
)
; ( /
)
; ( )
, (
∞
∈
∀
≡
≡
s for
s sW
s W
T i
g T
j g
W j
i A
<
= ≥
1 )
; ( /
)
; (
1 ) 1
( g j T g i T s
s s
W
マルコフ連鎖の設計（３）
受理行列Aと等しい要素数の行と列を持ち、
i行j列の成分Ｑ(i,j;t)が次式を満たすような既 約で対称な遷移行列Ｑを考える
0 )
; , ( :
, 1 )
; , (
) 0 )(
; , ( ) 0
; , (
≥
∃
=
≠
≥
= =
∑∈
t j i Q
n t
j i Q
j i
for t
i j Q
j i
t for j
i Q
n S
y
今回の実験では6個の状態が次の遷移候補と して選ばれるのでその確率は1/6となる
• 一様なマルコフ連鎖
• 一様でないマルコフ連鎖
一様なマルコフ連鎖
１ビットの突然変異でＭの確率により状態遷移 していく
一様でないマルコフ連鎖
乱数により6個の状態を選びＭの確率により 状態遷移していく
それぞれの状態が現れる回数を全回数で割っ たものがそれぞれの状態が現れる確率となる
ボルツマン分布への収束証明実験
初期設定
• 温度 T=10
• 状態遷移数 3000000回
• 初期状態 ００１０１０
連鎖 図２：一様なマルコフ
ボルツマン分布との誤差の比較実験
• 一様なマルコフ連鎖
• 一様でないマルコフ連鎖
b cM
m
e( ) = t m − t
b m
M M
cM m
e( ) = t (0) (1) ( )− t
初期設定
• 温度 T=10
• m = 200 回
• 初期状態 ００１０１０
係 図１：誤差とｍとの関
Bit数を変えたときの誤差の比較実験
６ビット，１２ビット，１８ビット，２４ビットで初期 状態のｆの値が最小、最大、平均でそれぞれ 実験を行う
bit 6
bit 12
bit 18
bit 24
値 回掛けたときの誤差の を
表２：M 50
考察
• 一様なマルコフ連鎖では次の状態遷移候補 のｆの値は初期状態のｆの値との差が30以内 におさまるのでbitが大きくなるにつれ初期状 態のｆの値が大きい場合には一様でないマル コフ連鎖に比べ適していると推測できる
まとめ
• 一様でないマルコフ連鎖の場合でもボルツマ ン分布に収束する
参考文献
• 長尾智晴：最適化アルゴリズム，P209，昭晃 堂（2000）
• 平早哲郎：数学的保証をもつ遺伝的アルゴリ ズムの改良，山梨大学修士論文（2006）
実際の状態分布 :
tc tb:平衡分布
67
最適分布
実際の状態分布 :
:
→
→
b c
t t
68
bit 24
:平衡分布
tb
実際の状態分布 :
tc
平衡分布
一様なマルコフ連鎖ＭのもとでｂＭ＝ｂが成り立 つような状態分布ｂが存在するなら
その状態分布は以後時間的に変化しない このような状態分布ｂは平衡分布と呼ばれる
↓
結果
bitが小さいときは一様でないマルコフ連鎖のほ うが初期状態によらず誤差が小さくなるがbitが 大きくなるにつれ初期状態のfの値が大きいと 平衡分布に収束に時間がかかる
誤差が0.01以下となるｍの最小値
の最小値 表２：m
今後の展開
• 一様でないマルコフ連鎖の理論をさらに研究 し、このプログラムを拡張していく
