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