3、，接近平均值1??D?，?D?為狀態(tài)空間D中狀態(tài)的個(gè)數(shù)．此時(shí)，具有最低能量狀態(tài)的波茲曼概率接近并超出平均值1??D?．當(dāng)rmin是D中具有最低能量的狀態(tài)時(shí)，得由所以，關(guān)于溫度T是單調(diào)下降的．又有其中，D0是具有最低能量的狀態(tài)集合，因此得到，當(dāng)T趨向于0時(shí)，當(dāng)溫度趨向于0時(shí)，(2.1)決定的概率漸近由此可以得到，在溫度趨向于0時(shí)，分子停留在最低能量狀態(tài)的概率趨向1．綜合上面的討論，分子在最低能量狀態(tài)的概率變化趨勢(shì)由圖(a)表示．對(duì)于非能量最小的狀態(tài)，由(2.2)和分子在能量最小狀態(tài)的概率是單調(diào)減小的事實(shí)，在溫度
4、較高時(shí)，分子在這些狀態(tài)的概率在附近，依賴于狀態(tài)的不同，使(2.1)決定的概率在(0,t)是單調(diào)升的；再由(2.4)可知，當(dāng)溫度趨于0時(shí)，(2.1)定義的概率趨于0．概率變化曲線見(jiàn)圖(b)．可能超過(guò)由(2.3)和(2.4)可知存在一個(gè)溫度t，從上面的討論得到，在溫度很低時(shí)，能量越低的狀態(tài)的概率值越高，在極限狀況，只有能量最低的點(diǎn)概率不為０．即有1.系統(tǒng)在T平衡時(shí)，系統(tǒng)狀態(tài)的概率分布趨于(2.1)式，0.0020.0160.1170.865t=0.50.1810.2210.2690.325t=50.2320.24
5、30.2560.269t=20例2.1簡(jiǎn)化概率分布(2.1)為其中q(t)為標(biāo)準(zhǔn)化因子．設(shè)共有四個(gè)能量點(diǎn)x=1,2,3,4,在此觀察t=20,5,0.5,三個(gè)溫度點(diǎn)概率分布變化．二．Metropolis準(zhǔn)則固體在恒定溫度下達(dá)到熱平衡的過(guò)程可以進(jìn)行模擬．1953年，Metropolis等提出重要性采樣法．他們用下述方法產(chǎn)生固體的狀態(tài)序列：先給定以粒子相對(duì)位置表征的初始狀態(tài)i，作為固體的當(dāng)前狀態(tài)，該狀態(tài)的能量是Ei．然后用攝動(dòng)裝置使隨機(jī)選取的某個(gè)粒子的位移隨機(jī)地產(chǎn)生一微小變化，得到一個(gè)新?tīng)顟B(tài)j，新?tīng)顟B(tài)的能量是Ej
6、．如EjEi，則考慮熱運(yùn)動(dòng)的影響，該新?tīng)顟B(tài)是否重要狀態(tài)，要依據(jù)固體處于該狀態(tài)的幾率來(lái)判斷．由(2.1)知，固體處于i和j的概率的比值等于相應(yīng)Boltzmann因子的比值，即r是一個(gè)小于1的數(shù)．用隨機(jī)數(shù)發(fā)生器產(chǎn)生一個(gè)[0,1)區(qū)間的隨機(jī)數(shù)?，若r>?，則新?tīng)顟B(tài)j作為重要狀態(tài)，否則舍去．若新?tīng)顟B(tài)j是重要狀態(tài)，就以j取代i成為當(dāng)前狀態(tài)，否則仍以i為當(dāng)前狀態(tài)，再重復(fù)以上新?tīng)顟B(tài)產(chǎn)生過(guò)程．在大量固體狀態(tài)的變換后，系統(tǒng)趨于能量較低的平衡狀態(tài)，固體狀態(tài)的概率分布趨于(2.1)式的Bo
7、ltzmann概率分布．由(?)式可知，高溫下可接受與當(dāng)前狀態(tài)能差較大的新?tīng)顟B(tài)為重要狀態(tài)．而在低溫下只能接受與當(dāng)前狀態(tài)能差較小的新?tīng)顟B(tài)為重要狀態(tài).這與不同溫度下熱運(yùn)動(dòng)的影響完全一致．在溫度趨與零時(shí)，就不能接受任一Ej>Ei的新?tīng)顟B(tài)j了．上述接受新?tīng)顟B(tài)的準(zhǔn)則稱為Metropolis準(zhǔn)則，相應(yīng)的算法稱為Metropolis算法．這種算法的計(jì)算量顯著減少．三．模擬退火算法對(duì)固體退火過(guò)程的研究給人們以新的啟示．1982年，Kirkpatrick等首先意識(shí)到固體退火過(guò)程與組合優(yōu)化問(wèn)題之間存在的類(lèi)似性，Metropoli
8、s等對(duì)固體在恒定溫度下達(dá)到熱平衡的模擬也給他們以啟迪：應(yīng)該把Metropolis準(zhǔn)則引入到過(guò)程中來(lái)．最終他們得到一種對(duì)Metropolis算法進(jìn)行迭代的組合優(yōu)化算法，這種算法模擬固體退火過(guò)程，稱之為模擬退火算法．我們可以將組合優(yōu)化問(wèn)題同金屬物體退火進(jìn)行類(lèi)比：組合優(yōu)化問(wèn)題金屬物體假設(shè)算法用以解決如下組合優(yōu)化問(wèn)題：解費(fèi)用(目標(biāo))函數(shù)最優(yōu)解狀態(tài)能量能量最低的狀態(tài)模擬退火算法Step1任選一個(gè)初始解x0；x
