【正文】 起始溫度的選?。?3） ? 模擬固體的升溫過程： （ 1） 給定一個希望的初始接受概率 P0， 給定一個較低的初始溫度 t0， 比如 t0＝ 1； （ 2） 隨機的產(chǎn)生一個狀態(tài)序列 ， 并計算該序列的接收率： 如果接收率大于給定的初始接受概率 P0， 則轉(zhuǎn) （ 4） ； （ 3） 提高溫度 ， 更新 t0， 轉(zhuǎn) （ 2） ； （ 4） 結束 。(),(139。))1(39。 起始溫度的選?。?1） ? 一個合適的初始溫度，應保證平穩(wěn)分布中每一個狀態(tài)的概率基本相等，也就是接受概率 P0近似等于 1。 ????????? ???jiliAliGjijiAjiGjiPiliNlttttt 如果如果),(),(),(1),(),(),(定理 滿足條件的 Gt(i,j)、 At(i,j) 舉例： ????? ??其他如果0)(1),(iNjNjiG t????? ?? ??其他如果tifjfteifjfjiA )()()()(1),( 說明：條件 2的后半部分除外，該條件與具體的問題有關。對于任意兩個狀態(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的概率。 16， 結束 。 11， 轉(zhuǎn) （ 4） 12， End 13， tk+1=Drop(tk)， k=k+1。 8， 如果 f(j)f(i)， 則 i=j， f(i)=f(j)， 轉(zhuǎn) （ 4） 。 5， Begin 6， 從 i的鄰域 N(i)中隨機選擇一個解 j。 2， 如果滿足結束條件 ， 則轉(zhuǎn) （ 15） 。 達到最小能量狀態(tài)的三個條件 ? （ 1） 初始溫度必須足夠高； ? （ 2） 在每個溫度下 ， 狀態(tài)的交換必須足夠充分； ? （ 3） 溫度 T的下降必須足夠緩慢 。因此，隨著能量期望值的逐步下降，能量低于期望值的狀態(tài)逐步減少，當溫度趨于 0時，只剩下那些具有最小能量的狀態(tài)，系統(tǒng)處于其他狀態(tài)的概率趨近于 0。在給定的溫度下，系統(tǒng)落入低能量狀態(tài)的概率大于系統(tǒng)落入高能量狀態(tài)的概率，這樣在同一溫度下，如果系統(tǒng)交換的足夠充分，則系統(tǒng)會趨向于落入較低能量的狀態(tài)。 ? 當溫度上升或下降時： ? ?TiSjjiSjTKTjEiSjKTjETiiTTiiTKTiETTKTiETKTiEiEiEKTTPTPjEiEKTTPZejEiEKTTPejEKTZTPTPKTiETZZTPTPKTiETZeZZeKTiEZeTTTP????????????????????????????????????????????????????????????????)()()()()()()()()()(1)()()()()()(1)()(22)(2)(222)(2)(2)(? 系統(tǒng)落入低能量狀態(tài)的概率隨著溫度的下降單調(diào)上升，而系統(tǒng)落入高能量狀態(tài)的概率隨著溫度的下降單調(diào)下降。上式分子、分母同乘以 ? ??????????????????????????SjKTjEKTiETiTeeTP)()(00lim)(limKTmEe? ???????????????????????????????????????????????????????????????????????????????????????????????mmmSjKTEjEKTEiETSjKTEjESjKTEjEKTEiETSjKTEjEKTEiETiTSiSiSeeeeeeeTPmmmmmmmmmm如果如果01limlimlim)(lim)()(0)()()(0)()(00? 當溫度趨近于 0時，系統(tǒng)以等概率趨近于幾個能量最小的狀態(tài)之一，而系統(tǒng)處于其他狀態(tài)的概率為 0。 ? 當溫度很高時，系統(tǒng)處于各個狀態(tài)的概率基本相等，接近于平均值，與所處狀態(tài)的能量幾乎無關。 ? ?TKTiEi ZeTP)(??????SjKTjET eZ)(? 考察一下式（ 6）隨溫度 T的變化情況： – 同一溫度下，兩個能量不同的狀態(tài) – 高溫下的情況 – 低溫下的情況 – 當溫度下降時的情況 ? 在給定的溫度 T下，設有 i、 j兩個狀態(tài)，E(i)＜ E(j) ： ? 即在任何溫度 T下，系統(tǒng)處于能量低的狀態(tài)的概率大于處于能量高的狀態(tài)的概率。 KTjEiEe)()( ?? 在給定的溫度 T下，當進行足夠多次的狀態(tài)轉(zhuǎn)換后，系統(tǒng)將達到熱平衡。一方面，物理系統(tǒng)傾向于能量較低的狀態(tài)，另一方面，熱運動又妨礙了系統(tǒng)準確落入低能狀態(tài)。如果退火過程是緩慢進行的，也就是說，溫度的下降如果非常緩慢的話，使得在每個溫度下，粒子的排列都達到一種平衡態(tài)，則當溫度趨于 0（絕對溫度）時，系統(tǒng)的能量將趨于最小值。 ? 退火過程： 隨著溫度的下降，粒子的熱運動逐漸減弱，粒子逐漸停留在不同的狀態(tài)，其排列也從無序向有序方向發(fā)展，直至到溫度很低時，粒子重新以一定的結構排列。 不同規(guī)模下皇后問題的 平均求解時間 皇 后 數(shù) 100 500 1000 2021 5000 10000 30000 平均時間（秒） 5 5 12 28 170 900 10000 模擬退火算法 ? 是局部搜索算法的一種擴展 ? 最早由 Metropolis在 1953年提出，Kirkpatrick等人在 1983年成功地將模擬退火算法用于求解組合優(yōu)化問題。 5， 如果陷入了局部極小 ， 既交換了所有的皇后 后 ， 沖突數(shù)仍然不能下降 ， 則轉(zhuǎn) 1。 2， 計算皇后間的沖突數(shù) conflicts。 8， End 9， k = k+1 10， 如果 k達到了指定的次數(shù) ， 則從 k個結果中選 擇一個最好的結果輸出 ， 否則轉(zhuǎn) （ 2） 11， 輸出結果 12，結束 多種方法的集成 ? 以上幾種解決方法可以結合在一起使用，比如第一、第二種方法的結合，就產(chǎn)生了我們將在后面介紹的模擬退火方法。中的最優(yōu)解 6， 如果 f(xn) f(xb)， 則 xb ＝ xn， P = N(xb)， 轉(zhuǎn) 3 7， 否則 P = P – P39。 局部搜索算法 3（ Local Search 3） 1， k = 0 2， 隨機的選擇一個初始的可能解 x0∈ D， xb=x0， P=N(xb) 3， 如果不滿足結束條件 ， 則 4， Begin 5， 選擇 P的一個子集 P39。 8， End 9， 輸出計算結果 10， 結束 存在問題 ? 起始點問題 A B 全局最大值 局部最大值 解決方法 ? 隨機的生成一些初始點，從每個初始點出發(fā)進行搜索，找到各自的最優(yōu)解。中的最優(yōu)解 5， 如果 f(xn) f(xb)， 則 xb ＝ xn 6， 按照某種策略改變步長 ， 計算 P = N(xb)， 轉(zhuǎn) 2 7， 否則 P = P – P39。 選擇概率的計算 ? 設求最大值： ???)(m ax)()()(xNxjiijxfxfxP選擇概率的計算 ? 當求最小值時： ? ?)(11)(1))(1()(1)(m ax)(m axm axm i nixNxjiixPxNxPxPxPj????????局部搜索算法 1（ Local Search 1） 1， 隨機的選擇一個初始的可能解 x0∈ D， xb=x0，P=N(xb) 2， 如果不滿足結束條件 ， 則 3， Begin 4， 對于所有的 x∈ P計算指標函數(shù) f(x)， 并按照式 （ 3） 或者式 （ 4） 計算每一個點 x的概率 5， 依計算的概率值 ， 從 P中隨機選擇一個點 xn， xb ＝ xn， P = N(xb)， 轉(zhuǎn) 2 6， End 7， 輸出計算結果 8， 結束 存在的問題 ? 步長問題 初始值 搜索到的最優(yōu)解 解決方法 ? 變步長 初始值 搜索到的最優(yōu)解 局部搜索算法 2（ Local Search 2） 1， 隨機的選擇一個初始的可能解 x0∈ D， xb=x0， 確定一個初始步長計算 P=N(xb) 2， 如果不滿足結束條件 ， 則 3， Begin 4， 選擇 P的一個子集 P39。 第一次循環(huán) 從 P中選擇一個元素， 假設 xn = (a, c, b, d, e), f(xn) = 42, f(xn) f(xb), P = P – {xn} = {(a, d, c, b, e), (a, e, c, d, b), (a, b, d, c, e), (a, b, e, d, c), (a, b, c, e, d)} 第二次循環(huán) 從 P中選擇一個元素， 假設 xn = (a, d, c, b, e), f(xn) = 45, f(xn) f(