模擬退火算法 第一節(jié)（經(jīng)典實用）

1、模擬退火算法 第一節(jié) 模擬退火模擬退火(simulated annealing)算法算法Metropolis 接受準(zhǔn)則接受準(zhǔn)則；并用一組稱為；并用一組稱為冷卻進(jìn)度表冷卻進(jìn)度表的參數(shù)控的參數(shù)控 制算法進(jìn)程，使算法在多項式時間里給出一個制算法進(jìn)程，使算法在多項式時間里給出一個 近似最優(yōu)解近似最優(yōu)解 模擬退火算法最早的思想由模擬退火算法最早的思想由Metropolis在在1953 年提出，年提出，Kirkpatrick在在1983年成功地應(yīng)用在組年成功地應(yīng)用在組 合最優(yōu)化問題中合最優(yōu)化問題中 第第2章模擬退火算法章模擬退火算法 模擬退火算法 第一節(jié) )1 . 2() )( exp( )( 1 )(

2、Tk rE TZ rEEP B 一固體退火過程一固體退火過程 退火是一種物理過程，固體退火是先將固體加退火是一種物理過程，固體退火是先將固體加 熱至熔化，再熱至熔化，再徐徐徐徐冷卻使之凝固成規(guī)整晶體的熱冷卻使之凝固成規(guī)整晶體的熱 力學(xué)過程力學(xué)過程 退火過程中，系統(tǒng)在每一溫度下達(dá)到平衡態(tài)，退火過程中，系統(tǒng)在每一溫度下達(dá)到平衡態(tài)， 系統(tǒng)狀態(tài)的分布滿足一定的概率分布，即在溫度系統(tǒng)狀態(tài)的分布滿足一定的概率分布，即在溫度 T，系統(tǒng)達(dá)到平衡態(tài)后，分子停留在狀態(tài)，系統(tǒng)達(dá)到平衡態(tài)后，分子停留在狀態(tài) r 滿足滿足 波茲曼波茲曼(Boltzmann)概率分布概率分布 2.1模擬退火算法及模型模擬退火算法及模型 模

3、擬退火算法 第一節(jié) Ds BT k sE TZ) )( exp()( 其中，其中，E(r)為為狀態(tài)狀態(tài) r 的能量的能量，kB 0為為波茲曼常數(shù)波茲曼常數(shù)， ) )( exp( Tk rE B E為分子能量的一個為分子能量的一個隨機(jī)變量隨機(jī)變量， 稱為稱為波茲曼因子波茲曼因子Z(T)為概率分布的為概率分布的標(biāo)準(zhǔn)化因子標(biāo)準(zhǔn)化因子， 先研究由先研究由(2.1)確定的函數(shù)隨確定的函數(shù)隨 T 變化的趨勢選變化的趨勢選 定兩個能量定兩個能量 E1 E2，在同一個溫度，在同一個溫度 T ，有，有 D 為為狀態(tài)空間狀態(tài)空間 模擬退火算法 第一節(jié) )exp(1)exp( )( 1 )()( 121 21 Tk

4、 EE Tk E TZ EEPEEP BB 0,1)exp( 12 T Tk EE B 因因為為 ）（所所以以2 . 200)()( 21 TEEPEEP 在同一個溫度，在同一個溫度，(2.2)表示表示分子停留在能量小狀分子停留在能量小狀 態(tài)的概率比停留在能量大狀態(tài)的概率要大態(tài)的概率比停留在能量大狀態(tài)的概率要大當(dāng)溫當(dāng)溫 度相當(dāng)高時，度相當(dāng)高時，(2.1)的概率分布使得每個狀態(tài)的概的概率分布使得每個狀態(tài)的概 率率基本相同，接近平均值基本相同，接近平均值1 D，D為狀態(tài)空間為狀態(tài)空間 D 中狀態(tài)的個數(shù)此時，具有最低能量狀態(tài)的波茲中狀態(tài)的個數(shù)此時，具有最低能量狀態(tài)的波茲 曼概率曼概率接近并超出平均值

5、接近并超出平均值1 D 模擬退火算法 第一節(jié) 0 )( min T rEEP ) 3 . 2( )( )( exp)( )( )( )( exp )( 2 TZ Tk sE sE rE TkTZ Tk rE T rEEP Ds B B B 當(dāng)當(dāng) rmin 是是 D中具有最低能量的狀態(tài)時，得中具有最低能量的狀態(tài)時，得 由由 模擬退火算法 第一節(jié) RDTk rE TZ rEEP B 0 min min 1 ) )( exp( )( 1 )( ) 4 . 2(0,0) )()( exp( )()(: min min T Tk rEsE R rEsEDs B )( min rEEP 所以，所以， 關(guān)于

6、溫度關(guān)于溫度 T是單調(diào)下降的是單調(diào)下降的又有又有 其中，其中，D0是具有最低能量的狀態(tài)集合，是具有最低能量的狀態(tài)集合， 模擬退火算法 第一節(jié) 0, 1 )( 0 min T D rEEP Pr T O D1 0 1 D 在在能能量量最最低低狀狀態(tài)態(tài))(a 因此得到，當(dāng)因此得到，當(dāng) T 趨向于趨向于 0 時，時， 0 1 D 當(dāng)溫度趨向于當(dāng)溫度趨向于 0時，時，(2.1)決定的概率漸近決定的概率漸近 由此可以得到，由此可以得到，在溫度趨向于在溫度趨向于 0時，分子停留在最時，分子停留在最 低能量狀態(tài)的概率趨向低能量狀態(tài)的概率趨向1綜合上面的討論，分子綜合上面的討論，分子 在最低能量狀態(tài)的概率變化

7、趨勢由圖在最低能量狀態(tài)的概率變化趨勢由圖(a)表示表示 模擬退火算法 第一節(jié) T Pr O D1 在在非非能能量量最最低低狀狀態(tài)態(tài))(b 對于非能量最小的狀態(tài)，由對于非能量最小的狀態(tài)，由(2.2)和分子在能量最小狀和分子在能量最小狀 態(tài)的概率是單調(diào)減小的事實，在溫度較高時，分子在態(tài)的概率是單調(diào)減小的事實，在溫度較高時，分子在 D 1 這些狀態(tài)的概率在這些狀態(tài)的概率在附近，依賴于狀態(tài)的不同，附近，依賴于狀態(tài)的不同， 使使(2.1)決定的概率在決定的概率在(0 ,t)是單調(diào)升的；再由是單調(diào)升的；再由(2.4)可知，可知， 當(dāng)溫度趨于當(dāng)溫度趨于 0時，時，(2.1)定義的概率趨于定義的概率趨于 0概

8、率變化概率變化 曲線見圖曲線見圖(b) ; 1 D 可能超過可能超過由由(2.3)和和(2.4)可知存在一個溫度可知存在一個溫度t， 模擬退火算法 第一節(jié) ) )( exp( )( 1 )( Tk rE TZ rEEP B 從上面的討論得到，從上面的討論得到，在溫度很低時，能量越低的在溫度很低時，能量越低的 狀態(tài)的概率值越高，在極限狀況，只有能量最低的狀態(tài)的概率值越高，在極限狀況，只有能量最低的 點(diǎn)概率不為點(diǎn)概率不為即有即有 0 0 0 0 0 1 )(.2 Dr Dr D rEEP T 0| )(lim 1| )(lim. 3 0 0 0 0 DrrEEP DrrEEP T T 1. 系統(tǒng)在

9、系統(tǒng)在 T 平衡時，系統(tǒng)狀態(tài)的概率分布趨于平衡時，系統(tǒng)狀態(tài)的概率分布趨于(2.1) 式，式， 模擬退火算法 第一節(jié) 0.0020.0160.1170.865t=0.5 0.1810.2210.2690.325t=5 0.2320.2430.2560.269t=20 1x2x3x4x , )exp( )( 1 )( t x tq xp 例例2.1簡化概率分布簡化概率分布(2.1)為為 其中其中q(t)為標(biāo)準(zhǔn)化因子設(shè)共有四個能量點(diǎn)為標(biāo)準(zhǔn)化因子設(shè)共有四個能量點(diǎn)x=1, 2, 3, 4, 4 1 )exp()( x t x tq在此在此觀察觀察 t = 20, 5, 0.5, 三個溫度點(diǎn)概三個溫度點(diǎn)概

10、 率分布變化率分布變化 模擬退火算法 第一節(jié) 二二 Metropolis準(zhǔn)則準(zhǔn)則 固體在恒定溫度下達(dá)到熱平衡的過程可以進(jìn)固體在恒定溫度下達(dá)到熱平衡的過程可以進(jìn) 行行模擬模擬 1953年，年，Metropolis等提出重要性采樣法他等提出重要性采樣法他 們用下述方法產(chǎn)生固體的狀態(tài)序列：們用下述方法產(chǎn)生固體的狀態(tài)序列： 先給定以粒子相對位置表征的初始狀態(tài)先給定以粒子相對位置表征的初始狀態(tài) i，作，作 為固體的當(dāng)前狀態(tài)，該狀態(tài)的能量是為固體的當(dāng)前狀態(tài)，該狀態(tài)的能量是 Ei 然后然后 用攝動裝置使隨機(jī)選取的某個粒子的位移隨機(jī)地用攝動裝置使隨機(jī)選取的某個粒子的位移隨機(jī)地 產(chǎn)生一微小變化，得到一個新狀態(tài)產(chǎn)

11、生一微小變化，得到一個新狀態(tài) j，新狀態(tài)的，新狀態(tài)的 能量是能量是Ej 如如Ej Ei ，則考慮熱運(yùn)動的影響，該新狀態(tài)，則考慮熱運(yùn)動的影響，該新狀態(tài) 是否重要狀態(tài)，要依據(jù)固體處于該狀態(tài)的幾率來是否重要狀態(tài)，要依據(jù)固體處于該狀態(tài)的幾率來 模擬退火算法 第一節(jié) )()exp( Tk EE r B ji 判斷由判斷由(2.1)知，固體處于知，固體處于 i 和和 j 的概率的比值等的概率的比值等 于相應(yīng)于相應(yīng)Boltzmann因子的比值，即因子的比值，即 r是一個小于是一個小于1的數(shù)用隨機(jī)數(shù)發(fā)生器產(chǎn)生一個的數(shù)用隨機(jī)數(shù)發(fā)生器產(chǎn)生一個0 ,1) 區(qū)間的隨機(jī)數(shù)區(qū)間的隨機(jī)數(shù) ，若，若r ，則新狀態(tài)，則新狀態(tài)

12、j 作為重要狀態(tài)，作為重要狀態(tài)， 否則舍去若新狀態(tài)否則舍去若新狀態(tài) j是重要狀態(tài)，就以是重要狀態(tài)，就以 j 取代取代 i 成成 為當(dāng)前狀態(tài)，否則仍以為當(dāng)前狀態(tài)，否則仍以 i 為當(dāng)前狀態(tài)，再重復(fù)以上為當(dāng)前狀態(tài)，再重復(fù)以上 新狀態(tài)產(chǎn)生過程新狀態(tài)產(chǎn)生過程在大量固體狀態(tài)的變換后，系統(tǒng)在大量固體狀態(tài)的變換后，系統(tǒng) 趨于能量較低的平衡狀態(tài)，固體狀態(tài)的概率分布趨趨于能量較低的平衡狀態(tài)，固體狀態(tài)的概率分布趨 于于(2.1)式的式的Boltzmann概率分布概率分布 模擬退火算法 第一節(jié) 由由( )式可知，高溫下可接受與當(dāng)前狀態(tài)能差式可知，高溫下可接受與當(dāng)前狀態(tài)能差 較大的新狀態(tài)為重要狀態(tài)而在低溫下只能接較大的

13、新狀態(tài)為重要狀態(tài)而在低溫下只能接 受與當(dāng)前狀態(tài)能差較小的新狀態(tài)為重要狀態(tài)受與當(dāng)前狀態(tài)能差較小的新狀態(tài)為重要狀態(tài).這這 與不同溫度下熱運(yùn)動的影響完全一致在溫度與不同溫度下熱運(yùn)動的影響完全一致在溫度 趨與零時，就不能接受任一趨與零時，就不能接受任一 Ej Ei 的新狀態(tài)的新狀態(tài) j 了了 上述接受新狀態(tài)的準(zhǔn)則稱為上述接受新狀態(tài)的準(zhǔn)則稱為Metropolis準(zhǔn)則，準(zhǔn)則， 相應(yīng)的算法稱為相應(yīng)的算法稱為Metropolis算法這種算法的算法這種算法的 計算量顯著減少計算量顯著減少 模擬退火算法 第一節(jié) 三模擬退火算法三模擬退火算法 對固體退火過程的研究給人們以新的啟對固體退火過程的研究給人們以新的啟 示

14、示1982年，年，Kirkpatrick等首先意識到固體等首先意識到固體 退火過程與組合優(yōu)化問題之間存在的類似性，退火過程與組合優(yōu)化問題之間存在的類似性， Metropolis等對固體在恒定溫度下達(dá)到熱平衡等對固體在恒定溫度下達(dá)到熱平衡 的模擬也給他們以啟迪：應(yīng)該把的模擬也給他們以啟迪：應(yīng)該把Metropolis準(zhǔn)準(zhǔn) 則引入到過程中來最終他們得到一種對則引入到過程中來最終他們得到一種對 Metropolis算法進(jìn)行迭代的組合優(yōu)化算法，這算法進(jìn)行迭代的組合優(yōu)化算法，這 種算法種算法模擬固體退火過程，稱之為模擬退火算模擬固體退火過程，稱之為模擬退火算 法法 模擬退火算法 第一節(jié) Dx xgts x

15、f 0)(. )(min 我們可以將我們可以將組合優(yōu)化問題同金屬物體退火組合優(yōu)化問題同金屬物體退火 進(jìn)行類比進(jìn)行類比： 組合優(yōu)化問題組合優(yōu)化問題金屬物體金屬物體 假設(shè)算法用以解決如下組合優(yōu)化問題：假設(shè)算法用以解決如下組合優(yōu)化問題： 解解 費(fèi)用費(fèi)用(目標(biāo)目標(biāo))函數(shù)函數(shù) 最優(yōu)解最優(yōu)解 狀態(tài)狀態(tài) 能量能量 能量最低的狀態(tài)能量最低的狀態(tài) 模擬退火算法 第一節(jié) 模擬退火算法模擬退火算法 Step1任選一個初始解任選一個初始解 x0；xi := x0 ；k:=0； Step2若在該溫度達(dá)到內(nèi)循環(huán)條件，則到若在該溫度達(dá)到內(nèi)循環(huán)條件，則到step3; Step3 tk+1:=d(tk)；k :=k+1；若滿足

16、停止條件，終；若滿足停止條件，終 t0:= tmax；(初始溫度初始溫度)； 否則，從鄰域否則，從鄰域 N(xi)中中隨機(jī)隨機(jī)選一選一xj ，計算，計算 fij=f(xj) f(xi) ；若；若fij 0，則，則 xi := xj ；否；否 則若則若exp( fij /tk )random(0,1)時，則時，則 xi := xj ；重復(fù)；重復(fù)step2； 止計算；否則，回到止計算；否則，回到step2 產(chǎn)生一個產(chǎn)生一個0與與1之間的一個之間的一個 隨機(jī)數(shù)隨機(jī)數(shù) 模擬退火算法 第一節(jié) (1)隨算法進(jìn)程遞減其值的隨算法進(jìn)程遞減其值的控制參數(shù)控制參數(shù) t 擔(dān)當(dāng)固體退擔(dān)當(dāng)固體退 火過程中的溫度火過程中

17、的溫度 T 的角色的角色 (2)對對 t 的每一取值，算法持續(xù)進(jìn)行的每一取值，算法持續(xù)進(jìn)行“產(chǎn)生新解產(chǎn)生新解 判斷接受舍棄判斷接受舍棄”的迭代過程就對應(yīng)著固體在的迭代過程就對應(yīng)著固體在 某一恒定溫度下某一恒定溫度下趨于熱平衡的過程趨于熱平衡的過程也就是執(zhí)行也就是執(zhí)行 了一次了一次Metropolis算法模擬退火算法從某個初始算法模擬退火算法從某個初始 解出發(fā)，經(jīng)過大量解的變換后，可以求得給定控解出發(fā)，經(jīng)過大量解的變換后，可以求得給定控 制參數(shù)值時組合優(yōu)化問題的制參數(shù)值時組合優(yōu)化問題的相對最優(yōu)解相對最優(yōu)解然后然后減減 小小t 的值，的值，重復(fù)執(zhí)行重復(fù)執(zhí)行Metropolis算法，就可以算法，就可

18、以在在 t 趨于零時，最終求得整體最優(yōu)解趨于零時，最終求得整體最優(yōu)解 (3)由于退火必須由于退火必須“徐徐徐徐”降溫，降溫，t 也必須也必須緩慢衰減緩慢衰減， 才能確保模擬退火算法最終趨于組合優(yōu)化問題的整才能確保模擬退火算法最終趨于組合優(yōu)化問題的整 體最優(yōu)解集體最優(yōu)解集 模擬退火算法 第一節(jié) (4)模擬退火算法依據(jù)模擬退火算法依據(jù)Metropolis準(zhǔn)則接受新解，準(zhǔn)則接受新解， 因此因此除接受優(yōu)化解外，還在一個限定范圍內(nèi)接除接受優(yōu)化解外，還在一個限定范圍內(nèi)接 受惡化解受惡化解，這正是，這正是模擬退火算法與局部搜索算模擬退火算法與局部搜索算 法的本質(zhì)區(qū)別所在法的本質(zhì)區(qū)別所在開始時開始時 t 值大

19、，可能接受值大，可能接受 較差的惡化解；隨著較差的惡化解；隨著 t 的減小，只能接受較好的減小，只能接受較好 的惡化解；最后在的惡化解；最后在 t 值趨于零時，就不再接受值趨于零時，就不再接受 任何惡化解了這就使算法任何惡化解了這就使算法既可以從局部最優(yōu)既可以從局部最優(yōu) 的陷阱中跳出，更有可能求得組合優(yōu)化問題的的陷阱中跳出，更有可能求得組合優(yōu)化問題的 整體最優(yōu)解整體最優(yōu)解；又不失簡單性和通用性因此對；又不失簡單性和通用性因此對 大多數(shù)組合優(yōu)化問題而言，模擬退火算法要大多數(shù)組合優(yōu)化問題而言，模擬退火算法要優(yōu)優(yōu) 于于局部搜索算法局部搜索算法 模擬退火算法 第一節(jié) )5 . 2( )()(1 )()

20、( )( ,1 D ill ilil ijij ij ijtAtG ijtAtG tp 模擬退火算法的數(shù)學(xué)模型可以描述為：模擬退火算法的數(shù)學(xué)模型可以描述為：在給定在給定 鄰域結(jié)構(gòu)后，模擬退火過程是從一個狀態(tài)到另一鄰域結(jié)構(gòu)后，模擬退火過程是從一個狀態(tài)到另一 個狀態(tài)不斷地隨機(jī)游動個狀態(tài)不斷地隨機(jī)游動我們可用我們可用馬爾可夫鏈馬爾可夫鏈描描 述這一過程當(dāng)溫度述這一過程當(dāng)溫度 t 為一確定值時，兩個狀態(tài)為一確定值時，兩個狀態(tài) 的的轉(zhuǎn)移概率轉(zhuǎn)移概率定義為：定義為： Gij(t)稱為從稱為從 i 到到 j 的的產(chǎn)生概率產(chǎn)生概率， Gij(t)表示在狀態(tài)表示在狀態(tài) i時，時， j 狀態(tài)被選取的概率比較容易理解的是狀態(tài)被選取的概率比較容易理解的是 j 是是 i 的鄰居，如果在鄰域中等概率選取，則的鄰居，如果在鄰域中等概率選取，則 j 被被 模擬退火算法 第一節(jié) )6 . 2( )(0 )( )( 1 )( iNj iNj iN tGij )7 . 2( )()()exp( )()(1 )( jfif t f jfif tA ij ij 選中的概率為選中的概率為 Aij(t)稱為稱為接受概率接受概率， Aij(t)表示在狀態(tài)表示在狀態(tài) i 產(chǎn)生產(chǎn)生 j 后，后， 接受接受