【文章內(nèi)容簡(jiǎn)介】 此最終系統(tǒng)將以概率 1處于具有最小能量的一個(gè)狀態(tài)。 達(dá)到最小能量狀態(tài)的三個(gè)條件 ? （ 1） 初始溫度必須足夠高； ? （ 2） 在每個(gè)溫度下 ， 狀態(tài)的交換必須足夠充分； ? （ 3） 溫度 T的下降必須足夠緩慢 。 組合優(yōu)化問(wèn)題與退火過(guò)程的類(lèi)比 固體退火過(guò)程 組合優(yōu)化問(wèn)題 物理系統(tǒng)中的一個(gè)狀態(tài) 組合優(yōu)化問(wèn)題的解 狀態(tài)的能量 解的指標(biāo)函數(shù) 能量最低狀態(tài) 最優(yōu)解 溫度 控制參數(shù) 1， 隨機(jī)選擇一個(gè)解 i， k=0， t0=Tmax（ 初始溫度 ） ， 計(jì)算指標(biāo)函數(shù) f(i)。 2， 如果滿足結(jié)束條件 ， 則轉(zhuǎn) （ 15） 。 3， Begin 4， 如果在該溫度內(nèi)達(dá)到了平衡條件 ， 則轉(zhuǎn) （ 13） 。 5， Begin 6， 從 i的鄰域 N(i)中隨機(jī)選擇一個(gè)解 j。 7， 計(jì)算指標(biāo)函數(shù) f(j)。 8， 如果 f(j)f(i)， 則 i=j， f(i)=f(j)， 轉(zhuǎn) （ 4） 。 9， 計(jì)算 10， 如果 Pt(i=j)Random(0, 1)， 則 i=j， f(i)=f(j)。 11， 轉(zhuǎn) （ 4） 12， End 13， tk+1=Drop(tk)， k=k+1。 14， End 15， 輸出結(jié)果 。 16， 結(jié)束 。 tifjft ejiP)()()(????算法中的問(wèn)題 ? 初始溫度的選取 ? 內(nèi)循環(huán)的結(jié)束條件，即每個(gè)溫度狀態(tài)交換何時(shí)結(jié)束 ? 外循環(huán)的結(jié)束條件，即溫度下降到什么時(shí)候結(jié)束 ? 溫度的下降方法 ? 在模擬退火過(guò)程中，給定溫度下?tīng)顟B(tài)（解）的轉(zhuǎn)移可以看作是一個(gè)馬爾可夫鏈。對(duì)于任意兩個(gè)狀態(tài) i和 j， 我們用 Pt(i, j)表示溫度 t下，從狀態(tài)i轉(zhuǎn)移到狀態(tài) j的一步轉(zhuǎn)移概率，則有： ? 其中： Gt(i,j) 是產(chǎn)生概率，表示從狀態(tài) i產(chǎn)生狀態(tài) j的概率。 At(i,j) 是接受概率，表示在狀態(tài) i產(chǎn)生狀態(tài) j后，接受狀態(tài) j的概率。 ????????? ???jiliAliGjijiAjiGjiPiliNlttttt 如果如果),(),(),(1),(),(),(定理 滿足條件的 Gt(i,j)、 At(i,j) 舉例： ????? ??其他如果0)(1),(iNjNjiG t????? ?? ??其他如果tifjfteifjfjiA )()()()(1),( 說(shuō)明：條件 2的后半部分除外，該條件與具體的問(wèn)題有關(guān)。 定理 ： 在定理 1的條件下，如果對(duì)于任意兩個(gè)狀態(tài) 有： 則有： Sji ?,0),(lim)()( 0 ??? ? jiAjfif tt????????其他如果01)(lim0mmttSiSiP定理 （放寬了定理 1的條件） Gt(i,j)、 At(i,j)滿足定理 1中除條件（ 2）以外的所有其他條件，并且： 1，對(duì)于任意兩個(gè)狀態(tài) i、 j， 它們相互為鄰居或者相互都不為鄰居； 2，對(duì)于任意 i， Gt(i,j)滿足： 3，狀態(tài)空間 S對(duì)于鄰域是連通的； 則與模擬退火算法相伴的時(shí)齊馬爾可夫鏈存在平穩(wěn)分布，其分布概率為： ????? ??其他如果0)()(1),( iNjiNjiGtSijiAjNiiAiNiPSjmtmtt ??? ??,),()(),()()(算法的實(shí)現(xiàn) ? （ 1） 初始溫度 t0； ? （ 2） 溫度 t的衰減函數(shù) ， 即溫度的下降 方法； ? （ 3） 算法的終止準(zhǔn)則 ， 用終止溫度 tf或 者終止條件給出； ? （ 4） 每個(gè)溫度 t下的馬爾可夫鏈長(zhǎng)度 Lk。 起始溫度的選?。?1） ? 一個(gè)合適的初始溫度，應(yīng)保證平穩(wěn)分布中每一個(gè)狀態(tài)的概率基本相等，也就是接受概率 P0近似等于 1。在 Metropolis準(zhǔn)則下，即要求： 10),(???tjife? 如果我們給定一個(gè)比較大的接受概率 P0，則： ? ?100 ln),(???Pjift? 其中， 可以有以下估計(jì)方式： ),( jif?))((m i n))((m a x),( ififjif SiSi ?? ???2,)()(),(SjfifjifSji?????39。))1(39。())(39。(),(139。0SiSfiSfjifSi???????起始溫度的選取（ 2） ? 假設(shè)在 t0下隨機(jī)的生成一個(gè)狀態(tài)序列 ， 分別用 m1和 m2表示指標(biāo)函數(shù)下降的狀態(tài)數(shù)和指標(biāo)函數(shù)上升的狀態(tài)數(shù) ， 表示狀態(tài)增加的平均值 。 則 m2個(gè)狀態(tài)中 ， 被接受的個(gè)數(shù)為： ),( jif?0),(2tjifem??? 所以平均接受率為： ? 求解有： 21),(2100mmemmPtjif?????? ? ????????????0102201ln),(PmPmmjift起始溫度的選?。?3） ? 模擬固體的升溫過(guò)程： （ 1） 給定一個(gè)希望的初始接受概率 P0， 給定一個(gè)較低的初始溫度 t0， 比如 t0＝ 1； （ 2） 隨機(jī)的產(chǎn)生一個(gè)狀態(tài)序列 ， 并計(jì)算該序列的接收率： 如果接收率大于給定的初始接受概率 P0， 則轉(zhuǎn) （ 4） ； （ 3） 提高溫度 ， 更新 t0， 轉(zhuǎn) （ 2） ； （ 4） 結(jié)束 。 產(chǎn)生的狀態(tài)總數(shù)接受的狀態(tài)數(shù)溫度的下降方法（ 1） ? 等比例下降 kk tt ??? 110 ?? ?溫度的下降方法（ 2） ? 等值下降 ttt kk ???? 1溫度的下降方法（ 3） ? 由定理 1我們知道，在一定的條件下，與模擬退火算法相伴的時(shí)齊馬爾可夫鏈存在平穩(wěn)分布。如果溫度每次下降的幅度比較小的話，則相鄰溫度下的平穩(wěn)分布應(yīng)該變化不大，也就是說(shuō)，對(duì)于任意一個(gè)狀態(tài) i， 相鄰溫度下的平穩(wěn)分布應(yīng)滿足： ???????1)()(111iPiPkktt? 一個(gè)充分條件是： ????????11)()(kmkmtfiftfifee1)()()1( ??????? kmkmtfiftfifee ?? 兩邊取對(duì)數(shù)，并整理得： ? 用 代替 可得溫度的衰減函數(shù)： mkkkfifttt?????)()1ln (11 ?kt?3 mfif ?)(ktkkk ttt??3)1ln (11 ????每一溫度下的停止準(zhǔn)則（ 1） ? 固定長(zhǎng)度方法 ? 在每一個(gè)溫度下，都使用相同的 Lk。 Lk的選取與具體的問(wèn)題相關(guān)，一般與鄰域的大小直接關(guān)聯(lián)，通常選擇為問(wèn)題規(guī)模 n的一個(gè)多項(xiàng)式函數(shù)。 每一溫度下的停止準(zhǔn)則（ 2） ? 基于接受率的停止準(zhǔn)則 ： – 規(guī)定一個(gè)接受次數(shù) R， 在某一溫度下，只有被接受的狀態(tài)數(shù)達(dá)到 R時(shí)，在該溫度下的迭代才停止，轉(zhuǎn)入下一個(gè)溫度。 – 規(guī)定一個(gè)狀態(tài)接受率 R， R等于該溫度下接受的狀態(tài)數(shù)除以總生成的總狀態(tài)數(shù)。如果接受率達(dá)到了 R， 則停止該溫度下的迭代，轉(zhuǎn)入下一個(gè)溫度。 – 在迭代的過(guò)程中，若干相鄰的狀態(tài)稱(chēng)為“一代”，如果相鄰兩代的解的指標(biāo)函數(shù)差值小于規(guī)定的值的話，則停止該溫度下的迭代。 算法的終止原則 （ 1） ? 零度法 設(shè)定一個(gè)正常數(shù) e， 當(dāng)時(shí) tke時(shí)，算法結(jié)束。 算法的終止原則 （ 2） ? 循環(huán)總控制法 給定一個(gè)指定的溫度下降次數(shù) K， 當(dāng)溫度的迭代次數(shù)達(dá)到 K次時(shí)，則算法停止。 算法的終止原則 （ 3） ? 無(wú)變化控制法 如果在相鄰的 n個(gè)溫度中，得到的解的指標(biāo)函數(shù)值無(wú)任何變化，則說(shuō)明算法已經(jīng)收斂。 算法的終止原則 （ 4） ? 接受概率控制法 給定一個(gè)小的概率值 p， 如果在當(dāng)前溫度下除了局部最優(yōu)狀態(tài)外，其他狀態(tài)的接受概率小于 p值，則算法結(jié)束。 算法的終止原則 （ 5） ? 領(lǐng)域平均概率控制法 設(shè)大小為 N的一個(gè)領(lǐng)域，在鄰域內(nèi)一個(gè)狀態(tài)被接受的平均概率為 1/N。 設(shè) f0、 f1為該領(lǐng)域中的局部最優(yōu)值和局部次最優(yōu)值。則次最優(yōu)解是除了局部最優(yōu)解以外接受概率最大的，其接受概率為： tffe01 ??? 如果該概率值小于平均值 1/N時(shí)，即： 可以認(rèn)為從局部最優(yōu)解跳出的可能性已經(jīng)很小了，因此可以終止算法。此時(shí)的終止溫度 tf為： Ne tff101???Nfft fln21 ??算法的終止原則 （ 6） ? 相對(duì)誤差估計(jì)法 設(shè)溫度 t時(shí)指標(biāo)函數(shù)的期望值為： 則當(dāng)終止溫度 1時(shí)，由泰勒展開(kāi)近似有： ???Sit iPiftf )()()(fttfmfdttfdtftf???)()(? 由于： ? 所以可用下式估計(jì)當(dāng)前解與最優(yōu)解之間的誤差 ： ? ? mtftf ??)(lim0fttfmfdttfdtftf???)()(? 或者使用相對(duì)于 的相對(duì)誤差： ???? fttfdttfdft )()()(?f???????)()()(2ftdttfdftftttf ff? 實(shí)際計(jì)算時(shí)： ? 其中： ???)()()(022tfttftffff???niiXfntf1)(1)(???niiXfntf122 )(1)(應(yīng)用舉例 —— 旅行商問(wèn)題 ? 解的表示： – n個(gè)城市的任何一種排列均是問(wèn)題的一個(gè)可能解，表示為 : ? 指標(biāo)函數(shù) (能量函數(shù) )