高畠一哉
アニーリングスケジュールの定数倍加速
Abstract:シミュレーテッドアニーリング法で用い
られるアニーリングスケジュールT(t)=c/1n(t+b) (b,
cはある定数）によるマルコフ連鎖は強エルゴード性
を持つことが知られているがこのアニーリングスケジ
ュールは収束が遅いと言われている．
本論文ではこの時刻を任意の定数倍したアニーリン
グスケジュールT(t)=c/1n(at+b)によるマルコフ連鎖
も強エルゴード性を持つことを示し収束の速さの理論
的評価を示す．さらに一般の時間的非一様な弱（強）
エルゴード性を持つマルコフ連鎖の場合でも比較的緩
やかな条件下で任意の定数a∈{1,2,…｝に対して次の
条件(1),(2)を同時に満たす推移行列の部分列がとれ
ることを示す．
(1)その部分列を推移行列とするマルコフ連鎖も弱
（強）エルゴード性を持つ．
(2)部分列の第t項を元の推移行列の時系列の第h(t)
項とするとt→∞のときh(t)/t→aである．
このことはアニーリングスケジュールをある意味でい
くらでも加速できることを示している．
キーワード シミュレーテッドアニーリング，アニーリングスケジュール，時間的非一様なマルコフ連鎖，弱エルゴード性，強エルゴード性