【正文】 、 E(j)分別表示在狀態(tài) i、 j下的能量， T是溫度， K＞ 0是波爾茲曼常數(shù)。此時系統(tǒng)處于某個狀態(tài) i的概率由波爾茲曼（ Boltzmann） 分布給出： ? （ 6） ? 其中 為歸一化因子， S是所有可能狀態(tài)的集合。 ?????????????????????????????????????KTiEjEKTiETKTiEKTjEKTiETTKTjETKTiEjieeZeeeZZeZeTPTP)()()()()()()()(1111)()(由于 E(i)＜ E(j)， 所以該項小于 1 ? 當(dāng)溫度趨于無窮時： 其中 |S|表示系統(tǒng)所有可能的狀態(tài)數(shù)。 ? ?SeeTPSjKTjEKTiETiT1lim)(lim)()(????????????????????????????? 當(dāng)溫度趨于 0時 ： ? 設(shè) Sm表示系統(tǒng)最小能量狀態(tài)的集合， Em是系統(tǒng)的最小能量。以概率 1達到能量最小的狀態(tài)。 ???????????TTiEiEEiETTP)(0)(0)(如果如果? 在高溫下，系統(tǒng)基本處于無序的狀態(tài)，基本以等概率落入各個狀態(tài)。隨著溫度的緩慢下降，系統(tǒng)落入低能量狀態(tài)的概率逐步增加，而落入高能量狀態(tài)的概率逐步減少，使得系統(tǒng)各狀態(tài)能量的期望值隨溫度的下降單調(diào)下降，而只有那些能量小于期望值的狀態(tài)，其概率才隨溫度下降增加，其他狀態(tài)均隨溫度下降而下降。因此最終系統(tǒng)將以概率 1處于具有最小能量的一個狀態(tài)。 組合優(yōu)化問題與退火過程的類比 固體退火過程 組合優(yōu)化問題 物理系統(tǒng)中的一個狀態(tài) 組合優(yōu)化問題的解 狀態(tài)的能量 解的指標(biāo)函數(shù) 能量最低狀態(tài) 最優(yōu)解 溫度 控制參數(shù) 1， 隨機選擇一個解 i， k=0， t0=Tmax（ 初始溫度 ） ， 計算指標(biāo)函數(shù) f(i)。 3， Begin 4， 如果在該溫度內(nèi)達到了平衡條件 ， 則轉(zhuǎn) （ 13） 。 7， 計算指標(biāo)函數(shù) f(j)。 9， 計算 10， 如果 Pt(i=j)Random(0, 1)， 則 i=j， f(i)=f(j)。 14， End 15， 輸出結(jié)果 。 tifjft ejiP)()()(????算法中的問題 ? 初始溫度的選取 ? 內(nèi)循環(huán)的結(jié)束條件，即每個溫度狀態(tài)交換何時結(jié)束 ? 外循環(huán)的結(jié)束條件，即溫度下降到什么時候結(jié)束 ? 溫度的下降方法 ? 在模擬退火過程中，給定溫度下狀態(tài)（解）的轉(zhuǎn)移可以看作是一個馬爾可夫鏈。 At(i,j) 是接受概率，表示在狀態(tài) i產(chǎn)生狀態(tài) j后，接受狀態(tài) j的概率。 定理 ： 在定理 1的條件下，如果對于任意兩個狀態(tài) 有： 則有： Sji ?,0),(lim)()( 0 ??? ? jiAjfif tt????????其他如果01)(lim0mmttSiSiP定理 （放寬了定理 1的條件） Gt(i,j)、 At(i,j)滿足定理 1中除條件（ 2）以外的所有其他條件，并且： 1，對于任意兩個狀態(tài) i、 j， 它們相互為鄰居或者相互都不為鄰居； 2，對于任意 i， Gt(i,j)滿足： 3，狀態(tài)空間 S對于鄰域是連通的； 則與模擬退火算法相伴的時齊馬爾可夫鏈存在平穩(wěn)分布，其分布概率為： ????? ??其他如果0)()(1),( iNjiNjiGtSijiAjNiiAiNiPSjmtmtt ??? ??,),()(),()()(算法的實現(xiàn) ? （ 1） 初始溫度 t0； ? （ 2） 溫度 t的衰減函數(shù) ， 即溫度的下降 方法； ? （ 3） 算法的終止準(zhǔn)則 ， 用終止溫度 tf或 者終止條件給出； ? （ 4） 每個溫度 t下的馬爾可夫鏈長度 Lk。在 Metropolis準(zhǔn)則下，即要求： 10),(???tjife? 如果我們給定一個比較大的接受概率 P0，則： ? ?100 ln),(???Pjift? 其中， 可以有以下估計方式： ),( jif?))((m i n))((m a x),( ififjif SiSi ?? ???2,)()(),(SjfifjifSji?????39。())(39。0SiSfiSfjifSi???????起始溫度的選?。?2） ? 假設(shè)在 t0下隨機的生成一個狀態(tài)序列 ， 分別用 m1和 m2表示指標(biāo)函數(shù)下降的狀態(tài)數(shù)和指標(biāo)函數(shù)上升的狀態(tài)數(shù) ， 表示狀態(tài)增加的平均值 。 產(chǎn)生的狀態(tài)總數(shù)接受的狀態(tài)數(shù)溫度的下降方法（ 1） ? 等比例下降 kk tt ??? 110 ?? ?溫度的下降方法（ 2） ? 等值下降 ttt kk ???? 1溫度的下降方法（ 3） ? 由定理 1我們知道，在一定的條件下，與模擬退火算法相伴的時齊馬爾可夫鏈存在平穩(wěn)分布。 Lk的選取與具體的問題相關(guān)，一般與鄰域的大小直接關(guān)聯(lián)，通常選擇為問題規(guī)模 n的一個多項式函數(shù)。 – 規(guī)定一個狀態(tài)接受率 R， R等于該溫度下接受的狀態(tài)數(shù)除以總生成的總狀態(tài)數(shù)。 – 在迭代的過程中，若干相鄰的狀態(tài)稱為“一代”，如果相鄰兩代的解的指標(biāo)函數(shù)差值小于規(guī)定的值的話，則停止該溫度下的迭代。 算法的終止原則 （ 2） ? 循環(huán)總控制法 給定一個指定的溫度下降次數(shù) K， 當(dāng)溫度的迭代次數(shù)達到 K次時，則算法停止。 算法的終止原則 （ 4） ? 接受概率控制法 給定一個小的概率值 p， 如果在當(dāng)前溫度下除了局部最優(yōu)狀態(tài)外，其他狀態(tài)的接受概率小于 p值，則算法結(jié)束。 設(shè) f0、 f1為該領(lǐng)域中的局部最優(yōu)值和局部次最優(yōu)值。此時的終止溫度 tf為： Ne tff101???Nfft fln21 ??算法的終止原則 （ 6） ? 相對誤差估計法 設(shè)溫度 t時指標(biāo)函數(shù)的期望值為： 則當(dāng)終止溫度 1時，由泰勒展開近似有： ???Sit iPiftf )()()(fttfmfdttfdtftf???)()(? 由于： ? 所以可用下式估計當(dāng)前解與最優(yōu)解之間的誤差 ： ? ? mtftf ??)(lim0fttfmfdttfdtftf???)()(? 或者使用相對于 的相對誤差： ???? fttfdttfdft )()()(?f???????)()()(2ftdttfdftftttf ff? 實際計算時： ? 其中： ???)()()(022tfttftffff???niiXfntf1)(1)(???niiXfntf122 )(1)(應(yīng)用舉例 —— 旅行商問題 ? 解的表示： – n個城市的任何一種排列均是問題的一個可能解，表示為 : ? 指標(biāo)函數(shù) (能量函數(shù) ) 其中 ),...,( 1 n??????nin iidf11 1),...,( ????11 ?? ??n? 新解的產(chǎn)生 – 采用第一節(jié)介紹的兩個城市間的逆序交換方式得到問題的一個新解。 則逆序排列 u和 v之間的城市，得到問題的新解為： 則兩個路徑的距離差為： ),...,( 1 n??),...,...,...,( 1111 nvvuvu ??????? ???)()( 1111 vvuuvuvu ddddf ???????? ???? ?????? 新解的接受準(zhǔn)則 ????? ??? ??其他如果tftefA01? 初始參數(shù)的確定 ? 康立山等人的方法： – 初始溫度 t0=280； – 在每個溫度下采用固定的迭代次數(shù) ，Lk=100n， n為城市數(shù)； – 溫度的衰減系數(shù)＝ ， 即 tk+1= tk； – 算法的停止準(zhǔn)則為：當(dāng)相鄰兩個溫度得到的解無任何變化時算法停止 。 生物進化與遺傳算法 群體 種群 子群 選擇 婚配 變異 遭淘汰 的群體 生物進化中的概念 遺傳算法中的作用 環(huán)境 適應(yīng)函數(shù) 適應(yīng)性 適應(yīng)值函數(shù) 適者生存 適應(yīng)函數(shù)值最大的解被保留的概率最大 個體 問題的一個解 染色體 解的編碼 基因 編碼的元素 群體 被選定的一組解 種群 根據(jù)適應(yīng)函數(shù)選擇的一組解 交配 以一定的方式由雙親產(chǎn)生后代的過程 變異 編碼的某些分量發(fā)生變化的過程 生物進化與遺傳算法之間的對應(yīng)關(guān)系 遺傳算法的三個主要操作 ? 選擇 ? 交配 ? 變異 ? “輪盤賭”法 ： 設(shè)群體的規(guī)模為 N， F(xi)(i=1, ..., N)是其中 N個染色體的適應(yīng)值。 ? “確定性”法 對于規(guī)模為 N的群體，一個選擇概率為p(xi)的染色體 xi被選擇次數(shù)的期望值 e(xi)： 對于群體中的每一個 xi， 首先選擇 次。然后按照 從大到小對染色體排序，依次取出 個染色體，這樣就得到了 N個染色體。當(dāng)染色體采用二進制形式編碼時，交配過程是以這樣一種形式進行的： a1 a2 ... ai ai+1 ... an b1 b2 ...