2模擬退火算法收斂性

1、2.2　模擬退火算法收斂性,一　馬爾可夫鏈,定義2.1：設(shè)?X(k)?k ?0,1,2,?為隨機(jī)變量序列， X(k) ? i 稱在時(shí)刻 k 處于狀態(tài) i，i??，? 稱為狀態(tài)空間．當(dāng) ? 中的狀態(tài)數(shù)有限時(shí)，稱為有限狀態(tài)空間．若對任意的正整數(shù)n，?X(k)?k ?0,1,2,? 滿足,則稱?X(k)?k ?0,1,2,? 為馬爾可夫鏈，簡稱馬氏鏈．,馬氏鏈具有一種記憶遺忘功能，它只記憶前一時(shí)刻的狀態(tài)．(2.8)可以簡單地記成,稱為一步轉(zhuǎn)

2、移概率．當(dāng)狀態(tài)空間有限時(shí)，稱為有限馬氏鏈．,定義2.2：馬氏鏈?X(k)?k ?0,1,2,?稱為齊次的，,如果對任意 m 和 n 及任意狀態(tài) i 和 j ，只要,即要求轉(zhuǎn)移概率與 n 無關(guān)，也即無論質(zhì)點(diǎn)在何時(shí)處于狀態(tài) i ，只要由 i 出發(fā)經(jīng)一單位時(shí)間轉(zhuǎn)移到 j ，其概率都相同．反之，若一個馬氏鏈的相伴轉(zhuǎn)移概率依賴于n，就稱該馬爾可夫鏈為非齊次的．,P(X(n) ? i) > 0， P(X(m) ? i) > 0 就有,用

3、,表示馬氏鏈的n步轉(zhuǎn)移概率，它表示自i出發(fā)，經(jīng)n步到達(dá) j 的概率．,例　當(dāng)溫度 t 給定時(shí)，由(2.5)，(2.6)，(2.7)確定的馬氏鏈?zhǔn)驱R次的．,由馬氏鏈的性質(zhì)，模擬退火算法收斂性證明沿用下面過程．,齊次算法：,(1)在每一個給定的溫度t，給出(2.5)的一步轉(zhuǎn)移概率 pij (t) 的一些限定條件．得到平穩(wěn)分布概率,其中，X(n,t)表示在溫度 t 時(shí)，馬氏鏈第 n 步運(yùn)動的隨機(jī)變量．,(2)給出平穩(wěn)分布應(yīng)該滿足的條件，使