1、 w算法的提出算法的提出 模擬退火算法最早的思想由模擬退火算法最早的思想由Metropolis等（等（1953）提出，提出，1983年年Kirkpatrick等將其應用于組合優化。等將其應用于組合優化。w算法的目的算法的目的 解決解決NP復雜性復雜性問題；問題； 克服優化過程陷入局部極小；克服優化過程陷入局部極小； 克服初值依賴性。克服初值依賴性。 w物理退火過程物理退火過程 什么是退火：什么是退火： 退火是指將固體加熱到足夠高的溫度，使分子呈隨退火是指將固體加熱到足夠高的溫度，使分子呈隨機排列狀態，然后逐步降溫使之冷卻，最后分子以機排列狀態，然后逐步降溫使之冷卻，最后分子以低能狀態排列，固體

2、達到某種穩定狀態。低能狀態排列，固體達到某種穩定狀態。 w物理退火過程物理退火過程 加溫過程加溫過程增強粒子的熱運動，消除系統原先可增強粒子的熱運動，消除系統原先可能存在的非均勻態；能存在的非均勻態； 等溫過程等溫過程對于與環境換熱而溫度不變的封閉系對于與環境換熱而溫度不變的封閉系統，系統狀態的自發變化總是朝自由能減少的方向統，系統狀態的自發變化總是朝自由能減少的方向進行，當自由能達到最小時，系統達到平衡態；進行，當自由能達到最小時，系統達到平衡態； 冷卻過程冷卻過程使粒子熱運動減弱并漸趨有序，系統使粒子熱運動減弱并漸趨有序，系統能量逐漸下降，從而得到低能的晶體結構。能量逐漸下降，從而得到低能

3、的晶體結構。w熱力學中的退火現象指物體逐漸降溫時發生的物理熱力學中的退火現象指物體逐漸降溫時發生的物理現象：現象： 溫度越低，物體的能量狀態越低，到達足夠的低點溫度越低，物體的能量狀態越低，到達足夠的低點時，液體開始冷凝與結晶，在結晶狀態時，系統的時，液體開始冷凝與結晶，在結晶狀態時，系統的能量狀態最低。緩慢降溫（退火，能量狀態最低。緩慢降溫（退火，annealing）時，）時，可達到最低能量狀態；但如果快速降溫（淬火，可達到最低能量狀態；但如果快速降溫（淬火，quenching），會導致不是最低能態的非晶形。），會導致不是最低能態的非晶形。w大自然知道大自然知道慢工出細活慢工出細活： 緩緩降

4、溫，使得物體分子在每一溫度時，能夠有足緩緩降溫，使得物體分子在每一溫度時，能夠有足夠時間找到安頓位置，則逐漸地，到最后可得到最夠時間找到安頓位置，則逐漸地，到最后可得到最低能態，系統最穩定。低能態，系統最穩定。 w模仿自然界退火現象而得，利用了物理中固體物質模仿自然界退火現象而得，利用了物理中固體物質的的退火過程退火過程與一般與一般優化優化問題的相似性問題的相似性 從某一初始從某一初始溫度溫度開始，伴隨溫度的不斷下降，結合開始，伴隨溫度的不斷下降，結合概率突跳概率突跳特性在解空間中特性在解空間中隨機隨機尋找尋找全局最優解全局最優解 w數學表述數學表述 在溫度在溫度T，分子停留在狀態，分子停留在

5、狀態r滿足滿足Boltzmann概率分概率分布布DsBBBTksETZTZkrrEETkrETZrEEP)(exp)()(Boltzmann0)()(exp)(1)(子：為概率分布的標準化因常數。為的能量，表示狀態機變量，表示分子能量的一個隨 w數學表述數學表述 在在同一個溫度同一個溫度T，選定兩個能量，選定兩個能量E1E2，有，有TkEETkETZEEPEEPBB12121exp1exp)(10模擬退火算法基本思想模擬退火算法基本思想：在一定溫度下，搜索從一個狀態：在一定溫度下，搜索從一個狀態隨機地變化到另一個狀態；隨著溫度的不斷下降直到最低溫度，隨機地變化到另一個狀態；隨著溫度的不斷下降直

6、到最低溫度，搜索過程以概率搜索過程以概率1停留在最優解停留在最優解 wBoltzmanBoltzman概率分布概率分布告訴我們：告訴我們： （1）在同一個溫度，分子停留在能量小狀態的概率）在同一個溫度，分子停留在能量小狀態的概率大于停留在能量大狀態的概率大于停留在能量大狀態的概率 （2）溫度越高，不同能量狀態對應的概率相差越小；）溫度越高，不同能量狀態對應的概率相差越小；溫度足夠高時，各狀態對應概率基本相同。溫度足夠高時，各狀態對應概率基本相同。 （3）隨著溫度的下降，能量最低狀態對應概率越來）隨著溫度的下降，能量最低狀態對應概率越來越大；溫度趨于越大；溫度趨于0時，其狀態趨于時，其狀態趨于1

7、 w數學表述數學表述 若若|D|為狀態空間為狀態空間D中狀態的個數，中狀態的個數，D0是具有最低能是具有最低能量的狀態集合：量的狀態集合： 當溫度很高時，每個狀態概率基本相同，接近平均當溫度很高時，每個狀態概率基本相同，接近平均值值1/|D|； 狀態空間存在超過兩個不同能量時，具有最低能量狀態空間存在超過兩個不同能量時，具有最低能量狀態的概率超出平均值狀態的概率超出平均值1/|D| ； 當溫度趨于當溫度趨于0時，分子停留在最低能量狀態的概率時，分子停留在最低能量狀態的概率趨于趨于1。能量最低狀態能量最低狀態 非能量最低狀態非能量最低狀態 wMetropolis準則（準則（1953）以概率接受新

8、狀態以概率接受新狀態 固體在恒定溫度下達到熱平衡的過程可以用固體在恒定溫度下達到熱平衡的過程可以用Monte Carlo方法方法（計算機隨機模擬方法）加以模擬，雖（計算機隨機模擬方法）加以模擬，雖然該方法簡單，但必須大量采樣才能得到比較精確然該方法簡單，但必須大量采樣才能得到比較精確的結果，計算量很大。的結果，計算量很大。 wMetropolis準則（準則（1953）以概率接受新狀態以概率接受新狀態 若在溫度若在溫度T，當前狀態，當前狀態i 新狀態新狀態j 若若Ej=randrom0,1 s=sj; Until 抽樣穩定準則滿足；抽樣穩定準則滿足； 退溫退溫tk+1=update(tk)并令并

9、令k=k+1； Until 算法終止準則滿足；算法終止準則滿足； 輸出算法搜索結果。輸出算法搜索結果。 w影響優化結果的主要因素影響優化結果的主要因素 給定初溫給定初溫t=t0，隨機產生初始狀態，隨機產生初始狀態s=s0，令，令k=0； Repeat Repeat 產生新狀態產生新狀態sj=Genete(s)； if min1,exp-(C(sj)-C(s)/tk=randrom0,1 s=sj; Until 抽樣穩定準則滿足；抽樣穩定準則滿足； 退溫退溫tk+1=update(tk)并令并令k=k+1； Until 算法終止準則滿足；算法終止準則滿足； 輸出算法搜索結果。輸出算法搜索結果。三

10、函數兩準則三函數兩準則初始溫度初始溫度 Step1 設定初始溫度設定初始溫度t = tmax, 任選初始解任選初始解r = r0Step2 內循環內循環 Step2.1 從從r的鄰域中隨機選一個解的鄰域中隨機選一個解rt, 計算計算r和和rt對應目標對應目標函函 數值數值, 如如rt對應目標函數值較小，則令對應目標函數值較小，則令r = rt; 否則若否則若 exp(-(E(rt)-E(r)/t)random(0,1), 則令則令r=rt. Step2.2 不滿足內循環停止條件時，重復不滿足內循環停止條件時，重復Step2.1Step3 外循環外循環 Step3.1 降溫降溫t = decre

11、ase(t) Step3.2 如不滿足外循環停止條件，則轉如不滿足外循環停止條件，則轉Step2；否則算；否則算法結束法結束1. 達到終止溫度達到終止溫度2. 達到迭代次數達到迭代次數3. 最優值連續若干步最優值連續若干步保持不變保持不變1. 目標函數均值穩定目標函數均值穩定2. 連續若干步的目標連續若干步的目標值變化較小值變化較小3. 固定的抽樣步數固定的抽樣步數w模擬退火算法的步驟模擬退火算法的步驟 w定義定義 ) 1()(Pr) 1(,) 1 (,)0()(Pr )( )(,1021inXjnXinXiXiXjnXZnkXkkXss，滿足稱為馬爾可夫鏈，若隨機序列時刻狀態變量的取值。為間

12、，為所有狀態構成的解空令 w定義定義 一步轉移概率：一步轉移概率： n步轉移概率：步轉移概率： 若解空間有限，稱馬爾可夫鏈為若解空間有限，稱馬爾可夫鏈為有限狀態有限狀態； 若若 ，稱馬爾可夫鏈為，稱馬爾可夫鏈為時齊的時齊的。) 1()(Pr) 1(,inXjnXnpji) 1()(,npnpZnjiji)0()(Pr)(,iXjnXpnji w模擬退火算法對應了一個馬爾可夫鏈模擬退火算法對應了一個馬爾可夫鏈 模擬退火算法：新狀態接受概率僅依賴于新狀態和模擬退火算法：新狀態接受概率僅依賴于新狀態和當前狀態，并由溫度加以控制。當前狀態，并由溫度加以控制。 若固定每一溫度，算法均計算馬氏鏈的變化直至

13、平若固定每一溫度，算法均計算馬氏鏈的變化直至平穩分布，然后下降溫度，則稱為穩分布，然后下降溫度，則稱為時齊算法時齊算法； 若無需各溫度下算法均達到平穩分布，但溫度需按若無需各溫度下算法均達到平穩分布，但溫度需按一定速率下降，則稱為一定速率下降，則稱為非時齊算法非時齊算法。w分析收斂性分析收斂性w原則原則 產生的候選解應遍布全部解空間產生的候選解應遍布全部解空間w方法方法 在當前狀態的鄰域結構內以一定概率方式（均勻分在當前狀態的鄰域結構內以一定概率方式（均勻分布、正態分布、指數分布等）產生布、正態分布、指數分布等）產生w原則原則 (1)在固定溫度下，接受使目標函數下降的候選解的在固定溫度下，接受

14、使目標函數下降的候選解的概率要大于使目標函數上升的候選解概率；概率要大于使目標函數上升的候選解概率； (2)隨溫度的下降，接受使目標函數上升的解的概率隨溫度的下降，接受使目標函數上升的解的概率要逐漸減小；要逐漸減小； (3)當溫度趨于零時，只能接受目標函數下降的解。當溫度趨于零時，只能接受目標函數下降的解。w方法方法 具體形式對算法影響不大具體形式對算法影響不大 一般采用一般采用min1,exp(-C/t)w收斂性分析收斂性分析 通過理論分析可以得到初溫的解析式，但解決實際通過理論分析可以得到初溫的解析式，但解決實際問題時難以得到精確的參數；問題時難以得到精確的參數； 初溫應充分大；初溫應充分

15、大；w實驗表明實驗表明 初溫越大，獲得高質量解的機率越大，但花費較多初溫越大，獲得高質量解的機率越大，但花費較多的計算時間；的計算時間；w方法方法 （1）均勻抽樣一組狀態，以各狀態目標值得方差）均勻抽樣一組狀態，以各狀態目標值得方差為初溫；為初溫； （2）隨機產生一組狀態，確定兩兩狀態間的最大）隨機產生一組狀態，確定兩兩狀態間的最大目標值差，根據差值，利用一定的函數確定初溫；目標值差，根據差值，利用一定的函數確定初溫； （3）利用經驗公式。）利用經驗公式。w時齊算法的溫度下降函數時齊算法的溫度下降函數 （1） ，越接近越接近1 1溫度下降越溫度下降越慢，且其大小可以不斷變化；慢，且其大小可以不

16、斷變化； （2） ，其中，其中t0為起始溫度，為起始溫度，K為算法溫度為算法溫度下降的總次數。下降的總次數。10 , 0 ,1kttkk0tKkKtkw非時齊模擬退火算法非時齊模擬退火算法 每個溫度下只產生一個或少量候選解每個溫度下只產生一個或少量候選解w時齊算法時齊算法常用的常用的Metropolis抽樣穩定準則抽樣穩定準則 （1）檢驗目標函數的均值是否穩定；）檢驗目標函數的均值是否穩定； （2）連續若干步的目標值變化較小；）連續若干步的目標值變化較小； （3）按一定的步數抽樣。）按一定的步數抽樣。w常用方法常用方法 （1）設置終止溫度的閾值；）設置終止溫度的閾值； （2）設置外循環迭代次數

17、；）設置外循環迭代次數； （3）算法搜索到的最優值連續若干步保持不變；）算法搜索到的最優值連續若干步保持不變； （4）概率分析方法。）概率分析方法。w模擬退火算法的優點模擬退火算法的優點 質量高；質量高； 初值魯棒性強；初值魯棒性強； 簡單、通用、易實現。簡單、通用、易實現。w模擬退火算法的缺點模擬退火算法的缺點 由于要求較高的初始溫度、較慢的降溫速率、較低由于要求較高的初始溫度、較慢的降溫速率、較低的終止溫度，以及各溫度下足夠多次的抽樣，因此的終止溫度，以及各溫度下足夠多次的抽樣，因此優化過程較長。優化過程較長。w改進的可行方案改進的可行方案 （1）設計合適的狀態產生函數；）設計合適的狀態產

18、生函數； （2）設計高效的退火歷程；）設計高效的退火歷程； （3）避免狀態的迂回搜索；）避免狀態的迂回搜索； （4）采用并行搜索結構；）采用并行搜索結構； （5）避免陷入局部極小，改進對溫度的控制方式；）避免陷入局部極小，改進對溫度的控制方式； （6）選擇合適的初始狀態；）選擇合適的初始狀態； （7）設計合適的算法終止準則。）設計合適的算法終止準則。 w改進的方式改進的方式 （1）增加升溫或重升溫過程，避免陷入局部極小；）增加升溫或重升溫過程，避免陷入局部極小； （2）增加記憶功能（記憶）增加記憶功能（記憶“Best so far”狀態）；狀態）； （3）增加補充搜索過程（以最優結果為初始解）

19、；）增加補充搜索過程（以最優結果為初始解）； （4）對每一當前狀態，采用多次搜索策略，以概率）對每一當前狀態，采用多次搜索策略，以概率接受區域內的最優狀態；接受區域內的最優狀態； （5）結合其它搜索機制的算法；）結合其它搜索機制的算法； （6）上述各方法的綜合。）上述各方法的綜合。 w改進的思路改進的思路 （1）記錄）記錄“Best so far”狀態，并即時更新；狀態，并即時更新； （2）設置雙閾值，使得在盡量保持最優性的前提下）設置雙閾值，使得在盡量保持最優性的前提下減少計算量，即在各溫度下當前狀態連續減少計算量，即在各溫度下當前狀態連續 m1 步保持步保持不變則認為不變則認為Metrop

20、olis抽樣穩定，若連續抽樣穩定，若連續 m2 次退溫次退溫過程中所得最優解不變則認為算法收斂。過程中所得最優解不變則認為算法收斂。w改進的退火過程改進的退火過程 （1）給定初溫）給定初溫t0，隨機產生初始狀態，隨機產生初始狀態s，令初始最優解，令初始最優解s*=s，當前狀態為當前狀態為s(0)=s，i=p=0； （2）令）令t=ti，以，以t，s*和和s(i)調用改進的抽樣過程，返回其所得調用改進的抽樣過程，返回其所得最優解最優解s*和當前狀態和當前狀態s(k)，令當前狀態，令當前狀態s(i)=s(k)； （3）判斷）判斷C(s*)m2? 若是，則轉第若是，則轉第(6)步；否則，返回第步；否

21、則，返回第(2)步；步； （6）以最優解）以最優解s*作為最終解輸出，停止算法。作為最終解輸出，停止算法。w改進的抽樣過程改進的抽樣過程 （1）令）令k=0時的初始當前狀態為時的初始當前狀態為s(0)=s(i)，q=0； （2）由狀態）由狀態s通過狀態產生函數產生新狀態通過狀態產生函數產生新狀態s，計算增量，計算增量C=C(s)-C(s)； （3）若）若CC(s)? 若是，則令若是，則令s*=s，q=0；否則，令；否則，令q=q+1。若。若C0，則以，則以概率概率exp(-C/t)接受接受s作為下一當前狀態；作為下一當前狀態； （4）令）令k=k+1，判斷，判斷qm1? 若是，則轉第若是，則轉

22、第(5)步；否則，返回步；否則，返回第第(2)步；步； （5）將當前最優解）將當前最優解s*和當前狀態和當前狀態s(k)返回改進退火過程。返回改進退火過程。 wTSP Benchmark 問題問題 41 94;37 84;54 67;25 62; 7 64;2 99;68 58;71 44;54 62;83 69;64 60;18 54;22 60;83 46;91 38;25 38;24 42;58 69;71 71;74 78;87 76;18 40;13 40;82 7;62 32; 58 35;45 21;41 26;44 35;4 50w算法流程算法流程 w初始溫度的計算初始溫度的計

23、算 for i=1:100 route=randperm(CityNum); fval0(i)=CalDist(dislist,route); end t0=-(max(fval0)-min(fval0)/log(0.9); w狀態產生函數的設計狀態產生函數的設計 （1）互換操作，隨機交換兩個城市的順序；）互換操作，隨機交換兩個城市的順序； （2）逆序操作，兩個隨機位置間的城市逆序；）逆序操作，兩個隨機位置間的城市逆序； （3）插入操作，隨機選擇某點插入某隨機位置。）插入操作，隨機選擇某點插入某隨機位置。 28359146728359146728359146728159346728341956

24、7235981467w參數設定參數設定 截止溫度截止溫度 tf=0.01; 退溫系數退溫系數 alpha=0.90; 內循環次數內循環次數 L=200*CityNum; w運行過程運行過程 w運行過程運行過程 w運行過程運行過程 w運行過程運行過程 w運行過程運行過程 w運行結果運行結果 w換熱器模型換熱器模型 兩級管殼式換熱器組成的換熱器系統，數學模型高兩級管殼式換熱器組成的換熱器系統，數學模型高度非線性，其目標函數通常是多峰度非線性，其目標函數通常是多峰(谷谷)的，具有很的，具有很多局部最優解。多局部最優解。w優化目標優化目標 以換熱器系統的總費用年值最小作為優化設計的目以換熱器系統的總費用年值最小作為