【正文】 計算指標函數(shù) f(x)， 并按照式 （ 3） 或者式 （ 4） 計算每一個點 x的概率 5， 依計算的概率值 ， 從 P中隨機選擇一個點 xn， xb ＝ xn， P = N(xb)， 轉(zhuǎn) 2 6， End 7， 輸出計算結(jié)果 8， 結(jié)束 存在的問題 ? 步長問題 初始值 搜索到的最優(yōu)解 解決方法 ? 變步長 初始值 搜索到的最優(yōu)解 局部搜索算法 2（ Local Search 2） 1， 隨機的選擇一個初始的可能解 x0∈ D， xb=x0， 確定一個初始步長計算 P=N(xb) 2， 如果不滿足結(jié)束條件 ， 則 3， Begin 4， 選擇 P的一個子集 P39。， xn為 P39。中的最優(yōu)解 5， 如果 f(xn) f(xb)， 則 xb ＝ xn 6， 按照某種策略改變步長 ， 計算 P = N(xb)， 轉(zhuǎn) 2 7， 否則 P = P – P39。， 轉(zhuǎn) 2。 8， End 9， 輸出計算結(jié)果 10， 結(jié)束 存在問題 ? 起始點問題 A B 全局最大值 局部最大值 解決方法 ? 隨機的生成一些初始點，從每個初始點出發(fā)進行搜索，找到各自的最優(yōu)解。再從這些最優(yōu)解中選擇一個最好的結(jié)果作為最終的結(jié)果。 局部搜索算法 3（ Local Search 3） 1， k = 0 2， 隨機的選擇一個初始的可能解 x0∈ D， xb=x0， P=N(xb) 3， 如果不滿足結(jié)束條件 ， 則 4， Begin 5， 選擇 P的一個子集 P39。， xn為 P39。中的最優(yōu)解 6， 如果 f(xn) f(xb)， 則 xb ＝ xn， P = N(xb)， 轉(zhuǎn) 3 7， 否則 P = P – P39。， 轉(zhuǎn) 3。 8， End 9， k = k+1 10， 如果 k達到了指定的次數(shù) ， 則從 k個結(jié)果中選 擇一個最好的結(jié)果輸出 ， 否則轉(zhuǎn) （ 2） 11， 輸出結(jié)果 12，結(jié)束 多種方法的集成 ? 以上幾種解決方法可以結(jié)合在一起使用，比如第一、第二種方法的結(jié)合，就產(chǎn)生了我們將在后面介紹的模擬退火方法。 皇后搜索算法 （ Queen Search） 1， 隨機地將 n個皇后分布在棋盤上 ， 使得棋盤 的每行 、 每列只有一個皇后 。 2， 計算皇后間的沖突數(shù) conflicts。 3， 如果沖突數(shù) conflicts等于 0， 則轉(zhuǎn) （ 6） 4， 對于棋盤上的任意兩個皇后 ， 交換他們的行 或者列 ， 如果交換后的沖突數(shù) conflicts減少 ， 則接受這種交換 ， 更新沖突數(shù) conflicts， 轉(zhuǎn) 3。 5， 如果陷入了局部極小 ， 既交換了所有的皇后 后 ， 沖突數(shù)仍然不能下降 ， 則轉(zhuǎn) 1。 6， 輸出結(jié)果 7，結(jié)束。 不同規(guī)模下皇后問題的 平均求解時間 皇 后 數(shù) 100 500 1000 2021 5000 10000 30000 平均時間（秒） 5 5 12 28 170 900 10000 模擬退火算法 ? 是局部搜索算法的一種擴展 ? 最早由 Metropolis在 1953年提出，Kirkpatrick等人在 1983年成功地將模擬退火算法用于求解組合優(yōu)化問題。 ? 基本思想是借用金屬的退化過程改進局部搜索算法 固體退火過程 ? 溶解過程： 隨著溫度的不斷上升，粒子逐漸脫離開其平衡位置，變得越來越自由，直到達到固體的溶解溫度，粒子排列從原來的有序狀態(tài)變?yōu)橥耆臒o序狀態(tài)。 ? 退火過程： 隨著溫度的下降，粒子的熱運動逐漸減弱，粒子逐漸停留在不同的狀態(tài)，其排列也從無序向有序方向發(fā)展，直至到溫度很低時，粒子重新以一定的結(jié)構(gòu)排列。 ? 粒子不同的排列結(jié)構(gòu)，對應(yīng)著不同的能量水平。如果退火過程是緩慢進行的，也就是說，溫度的下降如果非常緩慢的話，使得在每個溫度下，粒子的排列都達到一種平衡態(tài)，則當(dāng)溫度趨于 0（絕對溫度）時，系統(tǒng)的能量將趨于最小值。 ? 如果以粒子的排列或者相應(yīng)的能量來表達固體所處的狀態(tài)，在溫度 T下，固體所處的狀態(tài)具有一定的隨機性。一方面，物理系統(tǒng)傾向于能量較低的狀態(tài)，另一方面，熱運動又妨礙了系統(tǒng)準確落入低能狀態(tài)。 Metropolis準則 ? 從狀態(tài) i轉(zhuǎn)換為狀態(tài) j的準則： ? 如果 E(j)≤E(i)， 則狀態(tài)轉(zhuǎn)換被接受； ? 如果 E(j)＞ E(i)， 則狀態(tài)轉(zhuǎn)移被接受的概率為： ? 其中 E(i)、 E(j)分別表示在狀態(tài) i、 j下的能量， T是溫度， K＞ 0是波爾茲曼常數(shù)。 KTjEiEe)()( ?? 在給定的溫度 T下，當(dāng)進行足夠多次的狀態(tài)轉(zhuǎn)換后，系統(tǒng)將達到熱平衡。此時系統(tǒng)處于某個狀態(tài) i的概率由波爾茲曼（ Boltzmann） 分布給出： ? （ 6） ? 其中 為歸一化因子， S是所有可能狀態(tài)的集合。 ? ?TKTiEi ZeTP)(??????SjKTjET eZ)(? 考察一下式（ 6）隨溫度 T的變化情況： – 同一溫度下，兩個能量不同的狀態(tài) – 高溫下的情況 – 低溫下的情況 – 當(dāng)溫度下降時的情況 ? 在給定的溫度 T下，設(shè)有 i、 j兩個狀態(tài)，E(i)＜ E(j) ： ? 即在任何溫度 T下，系統(tǒng)處于能量低的狀態(tài)的概率大于處于能量高的狀態(tài)的概率。 ?????????????????????????????????????KTiEjEKTiETKTiEKTjEKTiETTKTjETKTiEjieeZeeeZZeZeTPTP)()()()()()()()(1111)()(由于 E(i)＜ E(j)， 所以該項小于 1 ? 當(dāng)溫度趨于無窮時： 其中 |S|表示系統(tǒng)所有可能的狀態(tài)數(shù)。 ? 當(dāng)溫度很高時，系統(tǒng)處于各個狀態(tài)的概率基本相等，接近于平均值，與所處狀態(tài)的能量幾乎無關(guān)。 ? ?SeeTPSjKTjEKTiETiT1lim)(lim)()(????????????????????????????? 當(dāng)溫度趨于 0時 ： ? 設(shè) Sm表示系統(tǒng)最小能量狀態(tài)的集合， Em是系統(tǒng)的最小能量。上式分子、分母同乘以 ? ??????????????????????????SjKTjEKTiETiTeeTP)()(00lim)(limKTmEe? ???????????????????????????????????????????????????????????????????????????????????????????????mmmSjKTEjEKTEiETSjKTEjESjKTEjEKTEiETSjKTEjEKTEiETiTSiSiSeeeeeeeTPmmmmmmmmmm如果如果01limlimlim)(lim)()(0)()()(0)()(00? 當(dāng)溫度趨近于 0時，系統(tǒng)以等概率趨近于幾個能量最小的狀態(tài)之一，而系統(tǒng)處于其他狀態(tài)的概率為 0。以概率 1達到能量最小的狀態(tài)。 ? 當(dāng)溫度上升或下降時： ? ?TiSjjiSjTKTjEiSjKTjETiiTTiiTKTiETTKTiETKTiEiEiEKTTPTPjEiEKTTPZejEiEKTTPejEKTZTPTPKTiETZZTPTPKTiETZeZZeKTiEZeTTTP????????????????????????????????????????????????????????????????)()()()()()()()()()(1)()()()()()(1)()(22)(2)(222)(2)(2)(? 系統(tǒng)落入低能量狀態(tài)的概率隨著溫度的下降單調(diào)上升，而系統(tǒng)落入高能量狀態(tài)的概率隨著溫度的下降單調(diào)下降。 ???????????TTiEiEEiETTP)(0)(0)(如果如果? 在高溫下，系統(tǒng)基本處于無序的狀態(tài)，基本以等概率落入各個狀態(tài)。在給定的溫度下，系統(tǒng)落入低能量狀態(tài)的概率大于系統(tǒng)落入高能量狀態(tài)的概率，這樣在同一溫度下，如果系統(tǒng)交換的足夠充分，則系統(tǒng)會趨向于落入較低能量的狀態(tài)。隨著溫度的緩慢下降，系統(tǒng)落入低能量狀態(tài)的概率逐步增加，而落入高能量狀態(tài)的概率逐步減少，使得系統(tǒng)各狀態(tài)能量的期望值隨溫度的下降單調(diào)下降，而只有那些能量小于期望值的狀態(tài)，其概率才隨溫度下降增加，其他狀態(tài)均隨溫度下降而下降。因此，隨著能量期望值的逐步下降，能量低于期望值的狀態(tài)逐步減少，當(dāng)溫度趨于 0時，只剩下那些具有最小能量的狀態(tài)，系統(tǒng)處于其他狀態(tài)的概率趨近于 0。因