模擬退火運(yùn)算講解(1)課件

1、第三章 模擬退火算法 智能優(yōu)化計(jì)算華東理工大學(xué)自動(dòng)化系 2007年 3.1 模擬退火算法及模型 3.1.1 物理退火過程 3.1.2 組合優(yōu)化與物理退火的相似性 3.1.3 模擬退火算法的基本思想和步驟 3.2 模擬退火算法的馬氏鏈描述 3.2.1 馬爾可夫鏈 3.2.2 模擬退火算法與馬爾可夫鏈 3.3 模擬退火算法的關(guān)鍵參數(shù)和操作的設(shè)計(jì) 3.3.1 狀態(tài)產(chǎn)生函數(shù) 3.3.2 狀態(tài)接受函數(shù) 3.3.3 初溫 3.3.4 溫度更新函數(shù) 3.3.5 內(nèi)循環(huán)終止準(zhǔn)則 3.3.6 外循環(huán)終止準(zhǔn)則 智能優(yōu)化計(jì)算華東理工大學(xué)自動(dòng)化系 2007年 3.4 模擬退火算法的改進(jìn) 3.4.1 模擬退火算法的優(yōu)缺

2、點(diǎn) 3.4.2 改進(jìn)內(nèi)容 3.4.3 一種改進(jìn)的模擬退火算法3.5 模擬退火算法實(shí)現(xiàn)與應(yīng)用 3.5.1 30城市TSP問題（d*=423.741 by D B Fogel） 3.5.2 模擬退火算法在管殼式換熱器優(yōu)化設(shè)計(jì)中的應(yīng)用智能優(yōu)化計(jì)算華東理工大學(xué)自動(dòng)化系 2007年 3.1 模擬退火算法及模型 智能優(yōu)化計(jì)算華東理工大學(xué)自動(dòng)化系 2007年 算法的提出 模擬退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等將其應(yīng)用于組合優(yōu)化。算法的目的 解決NP復(fù)雜性問題； 克服優(yōu)化過程陷入局部極小； 克服初值依賴性。 3.1.1 物理退火過程3.1 模擬退火算

3、法及模型 智能優(yōu)化計(jì)算華東理工大學(xué)自動(dòng)化系 2007年 物理退火過程 什么是退火： 退火是指將固體加熱到足夠高的溫度，使分子呈隨機(jī)排列狀態(tài)，然后逐步降溫使之冷卻，最后分子以低能狀態(tài)排列，固體達(dá)到某種穩(wěn)定狀態(tài)。 3.1.1 物理退火過程3.1 模擬退火算法及模型 智能優(yōu)化計(jì)算華東理工大學(xué)自動(dòng)化系 2007年 物理退火過程 加溫過程增強(qiáng)粒子的熱運(yùn)動(dòng)，消除系統(tǒng)原先可能存在的非均勻態(tài)； 等溫過程對(duì)于與環(huán)境換熱而溫度不變的封閉系統(tǒng)，系統(tǒng)狀態(tài)的自發(fā)變化總是朝自由能減少的方向進(jìn)行，當(dāng)自由能達(dá)到最小時(shí)，系統(tǒng)達(dá)到平衡態(tài)； 冷卻過程使粒子熱運(yùn)動(dòng)減弱并漸趨有序，系統(tǒng)能量逐漸下降，從而得到低能的晶體結(jié)構(gòu)。 3.1.1

4、 物理退火過程3.1 模擬退火算法及模型 智能優(yōu)化計(jì)算華東理工大學(xué)自動(dòng)化系 2007年 數(shù)學(xué)表述 在溫度T，分子停留在狀態(tài)r滿足Boltzmann概率分布 3.1.1 物理退火過程3.1 模擬退火算法及模型 智能優(yōu)化計(jì)算華東理工大學(xué)自動(dòng)化系 2007年 Metropolis準(zhǔn)則（1953）以概率接受新狀態(tài) 固體在恒定溫度下達(dá)到熱平衡的過程可以用Monte Carlo方法（計(jì)算機(jī)隨機(jī)模擬方法）加以模擬，雖然該方法簡(jiǎn)單，但必須大量采樣才能得到比較精確的結(jié)果，計(jì)算量很大。 3.1.1 物理退火過程3.1 模擬退火算法及模型 智能優(yōu)化計(jì)算華東理工大學(xué)自動(dòng)化系 2007年 Metropolis準(zhǔn)則（19

5、53）以概率接受新狀態(tài) 若在溫度T，當(dāng)前狀態(tài)i 新狀態(tài)j 若EjEi，則接受 j 為當(dāng)前狀態(tài)； 否則，若概率 p=exp-(Ej-Ei)/kBT 大于0,1)區(qū)間的隨機(jī)數(shù)，則仍接受狀態(tài) j 為當(dāng)前狀態(tài)；若不成立則保留狀態(tài) i 為當(dāng)前狀態(tài)。 3.1.1 物理退火過程3.1 模擬退火算法及模型 智能優(yōu)化計(jì)算華東理工大學(xué)自動(dòng)化系 2007年 Metropolis準(zhǔn)則（1953）以概率接受新狀態(tài) p=exp-(Ej-Ei)/kBT 在高溫下，可接受與當(dāng)前狀態(tài)能量差較大的新狀態(tài)； 在低溫下，只接受與當(dāng)前狀態(tài)能量差較小的新狀態(tài)。 3.1.1 物理退火過程3.2 模擬退火算法的馬氏鏈描述 智能優(yōu)化計(jì)算華東理

6、工大學(xué)自動(dòng)化系 2007年 定義 3.2.1 馬爾科夫鏈3.2 模擬退火算法的馬氏鏈描述 智能優(yōu)化計(jì)算華東理工大學(xué)自動(dòng)化系 2007年 定義 一步轉(zhuǎn)移概率： n步轉(zhuǎn)移概率： 若解空間有限，稱馬爾可夫鏈為有限狀態(tài)； 若 ，稱馬爾可夫鏈為時(shí)齊的。 3.2.1 馬爾科夫鏈3.2 模擬退火算法的馬氏鏈描述 智能優(yōu)化計(jì)算華東理工大學(xué)自動(dòng)化系 2007年 模擬退火算法對(duì)應(yīng)了一個(gè)馬爾可夫鏈 模擬退火算法：新狀態(tài)接受概率僅依賴于新狀態(tài)和當(dāng)前狀態(tài)，并由溫度加以控制。 若固定每一溫度，算法均計(jì)算馬氏鏈的變化直至平穩(wěn)分布，然后下降溫度，則稱為時(shí)齊算法； 若無需各溫度下算法均達(dá)到平穩(wěn)分布，但溫度需按一定速率下降，則稱

7、為非時(shí)齊算法。分析收斂性 3.2.2 模擬退火算法與馬爾科夫鏈3.3 模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì)智能優(yōu)化計(jì)算華東理工大學(xué)自動(dòng)化系 2007年 原則 產(chǎn)生的候選解應(yīng)遍布全部解空間方法 在當(dāng)前狀態(tài)的鄰域結(jié)構(gòu)內(nèi)以一定概率方式（均勻分布、正態(tài)分布、指數(shù)分布等）產(chǎn)生 3.3.1 狀態(tài)產(chǎn)生函數(shù)3.3 模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì)智能優(yōu)化計(jì)算華東理工大學(xué)自動(dòng)化系 2007年 時(shí)齊算法的溫度下降函數(shù) （1） ，越接近1溫度下降越慢，且其大小可以不斷變化； （2） ，其中t0為起始溫度，K為算法溫度下降的總次數(shù)。 3.3.4 溫度更新函數(shù)3.3 模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì)智能優(yōu)化計(jì)算華東理工大學(xué)

8、自動(dòng)化系 2007年 非時(shí)齊模擬退火算法 每個(gè)溫度下只產(chǎn)生一個(gè)或少量候選解時(shí)齊算法常用的Metropolis抽樣穩(wěn)定準(zhǔn)則 （1）檢驗(yàn)?zāi)繕?biāo)函數(shù)的均值是否穩(wěn)定； （2）連續(xù)若干步的目標(biāo)值變化較??； （3）按一定的步數(shù)抽樣。 3.3.5 內(nèi)循環(huán)終止準(zhǔn)則3.3 模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì)智能優(yōu)化計(jì)算華東理工大學(xué)自動(dòng)化系 2007年 常用方法 （1）設(shè)置終止溫度的閾值； （2）設(shè)置外循環(huán)迭代次數(shù)； （3）算法搜索到的最優(yōu)值連續(xù)若干步保持不變； （4）概率分析方法。 3.3.6 外循環(huán)終止準(zhǔn)則3.4 模擬退火算法的改進(jìn)智能優(yōu)化計(jì)算華東理工大學(xué)自動(dòng)化系 2007年 模擬退火算法的優(yōu)點(diǎn) 質(zhì)量高； 初值魯

9、棒性強(qiáng)； 簡(jiǎn)單、通用、易實(shí)現(xiàn)。模擬退火算法的缺點(diǎn) 由于要求較高的初始溫度、較慢的降溫速率、較低的終止溫度，以及各溫度下足夠多次的抽樣，因此優(yōu)化過程較長。 3.4.1 模擬退火算法的優(yōu)缺點(diǎn)3.4 模擬退火算法的改進(jìn)智能優(yōu)化計(jì)算華東理工大學(xué)自動(dòng)化系 2007年 改進(jìn)的可行方案 （1）設(shè)計(jì)合適的狀態(tài)產(chǎn)生函數(shù)； （2）設(shè)計(jì)高效的退火歷程； （3）避免狀態(tài)的迂回搜索； （4）采用并行搜索結(jié)構(gòu)； （5）避免陷入局部極小，改進(jìn)對(duì)溫度的控制方式； （6）選擇合適的初始狀態(tài)； （7）設(shè)計(jì)合適的算法終止準(zhǔn)則。 3.4.2 改進(jìn)內(nèi)容3.4 模擬退火算法的改進(jìn)智能優(yōu)化計(jì)算華東理工大學(xué)自動(dòng)化系 2007年 改進(jìn)的方式

10、（1）增加升溫或重升溫過程，避免陷入局部極??； （2）增加記憶功能（記憶“Best so far”狀態(tài)）； （3）增加補(bǔ)充搜索過程（以最優(yōu)結(jié)果為初始解）； （4）對(duì)每一當(dāng)前狀態(tài)，采用多次搜索策略，以概率接受區(qū)域內(nèi)的最優(yōu)狀態(tài)； （5）結(jié)合其它搜索機(jī)制的算法； （6）上述各方法的綜合。 3.4.2 改進(jìn)內(nèi)容3.4 模擬退火算法的改進(jìn)智能優(yōu)化計(jì)算華東理工大學(xué)自動(dòng)化系 2007年 改進(jìn)的思路 （1）記錄“Best so far”狀態(tài)，并即時(shí)更新； （2）設(shè)置雙閾值，使得在盡量保持最優(yōu)性的前提下減少計(jì)算量，即在各溫度下當(dāng)前狀態(tài)連續(xù) m1 步保持不變則認(rèn)為Metropolis抽樣穩(wěn)定，若連續(xù) m2 次退溫

11、過程中所得最優(yōu)解不變則認(rèn)為算法收斂。 3.4.3 一種改進(jìn)的模擬退火算法3.4 模擬退火算法的改進(jìn)智能優(yōu)化計(jì)算華東理工大學(xué)自動(dòng)化系 2007年 改進(jìn)的退火過程 （1）給定初溫t0，隨機(jī)產(chǎn)生初始狀態(tài)s，令初始最優(yōu)解s*=s，當(dāng)前狀態(tài)為s(0)=s，i=p=0； （2）令t=ti，以t，s*和s(i)調(diào)用改進(jìn)的抽樣過程，返回其所得最優(yōu)解s*和當(dāng)前狀態(tài)s(k)，令當(dāng)前狀態(tài)s(i)=s(k)； （3）判斷C(s*)m2? 若是，則轉(zhuǎn)第(6)步；否則，返回第(2)步； （6）以最優(yōu)解s*作為最終解輸出，停止算法。 3.4.3 一種改進(jìn)的模擬退火算法3.4 模擬退火算法的改進(jìn)智能優(yōu)化計(jì)算華東理工大學(xué)自動(dòng)化

12、系 2007年 改進(jìn)的抽樣過程 （1）令k=0時(shí)的初始當(dāng)前狀態(tài)為s(0)=s(i)，q=0； （2）由狀態(tài)s通過狀態(tài)產(chǎn)生函數(shù)產(chǎn)生新狀態(tài)s，計(jì)算增量C=C(s)-C(s)； （3）若CC(s)? 若是，則令s*=s，q=0；否則，令q=q+1。若C0，則以概率exp(-C/t)接受s作為下一當(dāng)前狀態(tài)； （4）令k=k+1，判斷qm1? 若是，則轉(zhuǎn)第(5)步；否則，返回第(2)步； （5）將當(dāng)前最優(yōu)解s*和當(dāng)前狀態(tài)s(k)返回改進(jìn)退火過程。 3.4.3 一種改進(jìn)的模擬退火算法3.5 模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算華東理工大學(xué)自動(dòng)化系 2007年 初始溫度的計(jì)算 for i=1:100 rou

13、te=randperm(CityNum); fval0(i)=CalDist(dislist,route); end t0=-(max(fval0)-min(fval0)/log(0.9); 3.5.1 30城市TSP問題（d*=423.741 by D B Fogel） 3.5 模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算華東理工大學(xué)自動(dòng)化系 2007年 狀態(tài)產(chǎn)生函數(shù)的設(shè)計(jì) （1）互換操作，隨機(jī)交換兩個(gè)城市的順序； （2）逆序操作，兩個(gè)隨機(jī)位置間的城市逆序； （3）插入操作，隨機(jī)選擇某點(diǎn)插入某隨機(jī)位置。 3.5.1 30城市TSP問題（d*=423.741 by D B Fogel） 2835914

14、672835914672835914672815934672834195672359814673.5 模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算華東理工大學(xué)自動(dòng)化系 2007年 參數(shù)設(shè)定 截止溫度 tf=0.01; 退溫系數(shù) alpha=0.90; 內(nèi)循環(huán)次數(shù) L=200*CityNum; 3.5.1 30城市TSP問題（d*=423.741 by D B Fogel） 3.5 模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算華東理工大學(xué)自動(dòng)化系 2007年 運(yùn)行過程 3.5.1 30城市TSP問題（d*=423.741 by D B Fogel） 3.5 模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算華東理工大學(xué)自動(dòng)化

15、系 2007年 運(yùn)行過程 3.5.1 30城市TSP問題（d*=423.741 by D B Fogel） 3.5 模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算華東理工大學(xué)自動(dòng)化系 2007年 運(yùn)行過程 3.5.1 30城市TSP問題（d*=423.741 by D B Fogel） 3.5 模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算華東理工大學(xué)自動(dòng)化系 2007年 運(yùn)行過程 3.5.1 30城市TSP問題（d*=423.741 by D B Fogel） 3.5 模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算華東理工大學(xué)自動(dòng)化系 2007年 運(yùn)行過程 3.5.1 30城市TSP問題（d*=423.741 by D

16、B Fogel） 3.5 模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算華東理工大學(xué)自動(dòng)化系 2007年 運(yùn)行結(jié)果 3.5.1 30城市TSP問題（d*=423.741 by D B Fogel） 3.5 模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算華東理工大學(xué)自動(dòng)化系 2007年 換熱器模型 兩級(jí)管殼式換熱器組成的換熱器系統(tǒng)，數(shù)學(xué)模型高度非線性，其目標(biāo)函數(shù)通常是多峰(谷)的，具有很多局部最優(yōu)解。 3.5.2 模擬退火算法在管殼式換熱器優(yōu)化設(shè)計(jì)中的應(yīng)用3.5 模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算華東理工大學(xué)自動(dòng)化系 2007年 優(yōu)化目標(biāo) 以換熱器系統(tǒng)的總費(fèi)用年值最小作為優(yōu)化設(shè)計(jì)的目標(biāo)。 其中，f1 (X)是兩級(jí)

17、換熱器的初始投資， f2 (X)是兩級(jí)換熱器年維護(hù)費(fèi)(包括除垢、保養(yǎng)、維修等)， f3 (X)是冷卻水資源費(fèi)以及管程壓降能耗費(fèi)， f4 (X)是殼程壓降能耗費(fèi)。 3.5.2 模擬退火算法在管殼式換熱器優(yōu)化設(shè)計(jì)中的應(yīng)用3.5 模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算華東理工大學(xué)自動(dòng)化系 2007年 優(yōu)化目標(biāo) 經(jīng)過分析，優(yōu)化問題的獨(dú)立變量共12個(gè)，分別是一級(jí)換熱器煤油出口溫度t2、冷卻水流量G1、兩個(gè)換熱器的管內(nèi)徑d1，d2和管間距S1，S2、折流板間距B1，B2、折流板開口角1，2、單管長度L1，L2。 3.5.2 模擬退火算法在管殼式換熱器優(yōu)化設(shè)計(jì)中的應(yīng)用3.5 模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算華東理工大學(xué)自動(dòng)化系 2007年 應(yīng)用模擬退火算法解決優(yōu)化設(shè)計(jì) 狀態(tài)表示12個(gè)變量的實(shí)數(shù)表示； 初始溫度100； 結(jié)束溫度0.001； 狀態(tài)產(chǎn)生函數(shù) ，為擾動(dòng)幅度參數(shù)，為隨機(jī)擾動(dòng)變量，隨機(jī)擾動(dòng)可服從柯西、高斯、均勻分布。 降溫因子0.98； 馬氏鏈長度1200。 3.