模擬退火算法精品課件

1、模擬退火算法第1頁(yè)，共47頁(yè)，2022年，5月20日，6點(diǎn)42分，星期四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ì)算第2頁(yè)，共47頁(yè)，2022年，5月20日，6點(diǎn)42分，星期四3.4 模擬退火算法的改進(jìn)

2、3.4.1 模擬退火算法的優(yōu)缺點(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ì)算第3頁(yè)，共47頁(yè)，2022年，5月20日，6點(diǎn)42分，星期四3.1 模擬退火算法及模型 智能優(yōu)化計(jì)算算法的提出 模擬退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等將其應(yīng)用于組合優(yōu)化。算法的目的 解決NP復(fù)雜性問題； 克服優(yōu)化過程陷入局部極小； 克服初值依賴性。 3.1.1 物理退火

3、過程第4頁(yè)，共47頁(yè)，2022年，5月20日，6點(diǎn)42分，星期四3.1 模擬退火算法及模型 智能優(yōu)化計(jì)算物理退火過程 什么是退火： 退火是指將固體加熱到足夠高的溫度，使分子呈隨機(jī)排列狀態(tài)，然后逐步降溫使之冷卻，最后分子以低能狀態(tài)排列，固體達(dá)到某種穩(wěn)定狀態(tài)。 3.1.1 物理退火過程第5頁(yè)，共47頁(yè)，2022年，5月20日，6點(diǎn)42分，星期四3.1 模擬退火算法及模型 智能優(yōu)化計(jì)算物理退火過程 加溫過程增強(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)； 冷卻過程使粒子熱

4、運(yùn)動(dòng)減弱并漸趨有序，系統(tǒng)能量逐漸下降，從而得到低能的晶體結(jié)構(gòu)。 3.1.1 物理退火過程第6頁(yè)，共47頁(yè)，2022年，5月20日，6點(diǎn)42分，星期四3.1 模擬退火算法及模型 智能優(yōu)化計(jì)算數(shù)學(xué)表述 在溫度T，分子停留在狀態(tài)r滿足Boltzmann概率分布 3.1.1 物理退火過程第7頁(yè)，共47頁(yè)，2022年，5月20日，6點(diǎn)42分，星期四3.1 模擬退火算法及模型 智能優(yōu)化計(jì)算數(shù)學(xué)表述 在同一個(gè)溫度T，選定兩個(gè)能量E1E2，有 在同一個(gè)溫度，分子停留在能量小的狀態(tài)的概率比停留在能量大的狀態(tài)的概率要大。 3.1.1 物理退火過程0第8頁(yè)，共47頁(yè)，2022年，5月20日，6點(diǎn)42分，星期四3.1

5、 模擬退火算法及模型 智能優(yōu)化計(jì)算數(shù)學(xué)表述 若|D|為狀態(tài)空間D中狀態(tài)的個(gè)數(shù)，D0是具有最低能量的狀態(tài)集合： 當(dāng)溫度很高時(shí)，每個(gè)狀態(tài)概率基本相同，接近平均值1/|D|； 狀態(tài)空間存在超過兩個(gè)不同能量時(shí)，具有最低能量狀態(tài)的概率超出平均值1/|D| ； 當(dāng)溫度趨于0時(shí)，分子停留在最低能量狀態(tài)的概率趨于1。 3.1.1 物理退火過程能量最低狀態(tài) 非能量最低狀態(tài)第9頁(yè)，共47頁(yè)，2022年，5月20日，6點(diǎn)42分，星期四3.1 模擬退火算法及模型 智能優(yōu)化計(jì)算Metropolis準(zhǔn)則（1953）以概率接受新狀態(tài) 固體在恒定溫度下達(dá)到熱平衡的過程可以用Monte Carlo方法（計(jì)算機(jī)隨機(jī)模擬方法）加以

6、模擬，雖然該方法簡(jiǎn)單，但必須大量采樣才能得到比較精確的結(jié)果，計(jì)算量很大。 3.1.1 物理退火過程第10頁(yè)，共47頁(yè)，2022年，5月20日，6點(diǎn)42分，星期四3.1 模擬退火算法及模型 智能優(yōu)化計(jì)算Metropolis準(zhǔn)則（1953）以概率接受新狀態(tài) 若在溫度T，當(dāng)前狀態(tài)i 新狀態(tài)j 若Ej=randrom0,1 s=sj; Until 抽樣穩(wěn)定準(zhǔn)則滿足； 退溫tk+1=update(tk)并令k=k+1； Until 算法終止準(zhǔn)則滿足； 輸出算法搜索結(jié)果。 3.1.3 模擬退火算法的基本思想和步驟第14頁(yè)，共47頁(yè)，2022年，5月20日，6點(diǎn)42分，星期四3.1 模擬退火算法及模型 智能

7、優(yōu)化計(jì)算影響優(yōu)化結(jié)果的主要因素 給定初溫t=t0，隨機(jī)產(chǎn)生初始狀態(tài)s=s0，令k=0； Repeat Repeat 產(chǎn)生新狀態(tài)sj=Genete(s)； if min1,exp-(C(sj)-C(s)/tk=randrom0,1 s=sj; Until 抽樣穩(wěn)定準(zhǔn)則滿足； 退溫tk+1=update(tk)并令k=k+1； Until 算法終止準(zhǔn)則滿足； 輸出算法搜索結(jié)果。 3.1.3 模擬退火算法的基本思想和步驟三函數(shù)兩準(zhǔn)則初始溫度第15頁(yè)，共47頁(yè)，2022年，5月20日，6點(diǎn)42分，星期四3.2 模擬退火算法的馬氏鏈描述 智能優(yōu)化計(jì)算定義 3.2.1 馬爾科夫鏈第16頁(yè)，共47頁(yè)，202

8、2年，5月20日，6點(diǎn)42分，星期四3.2 模擬退火算法的馬氏鏈描述 智能優(yōu)化計(jì)算定義 一步轉(zhuǎn)移概率： n步轉(zhuǎn)移概率： 若解空間有限，稱馬爾可夫鏈為有限狀態(tài)； 若 ，稱馬爾可夫鏈為時(shí)齊的。 3.2.1 馬爾科夫鏈第17頁(yè)，共47頁(yè)，2022年，5月20日，6點(diǎn)42分，星期四3.2 模擬退火算法的馬氏鏈描述 智能優(yōu)化計(jì)算模擬退火算法對(duì)應(yīng)了一個(gè)馬爾可夫鏈 模擬退火算法：新狀態(tài)接受概率僅依賴于新狀態(tài)和當(dāng)前狀態(tài)，并由溫度加以控制。 若固定每一溫度，算法均計(jì)算馬氏鏈的變化直至平穩(wěn)分布，然后下降溫度，則稱為時(shí)齊算法； 若無需各溫度下算法均達(dá)到平穩(wěn)分布，但溫度需按一定速率下降，則稱為非時(shí)齊算法。分析收斂性

9、3.2.2 模擬退火算法與馬爾科夫鏈第18頁(yè)，共47頁(yè)，2022年，5月20日，6點(diǎn)42分，星期四3.3 模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì)智能優(yōu)化計(jì)算原則 產(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ù)第19頁(yè)，共47頁(yè)，2022年，5月20日，6點(diǎn)42分，星期四3.3 模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì)智能優(yōu)化計(jì)算原則 (1)在固定溫度下，接受使目標(biāo)函數(shù)下降的候選解的概率要大于使目標(biāo)函數(shù)上升的候選解概率； (2)隨溫度的下降，接受使目標(biāo)函數(shù)上升的解的概率要逐漸減小； (3)當(dāng)溫度趨于零時(shí)，只能接受目標(biāo)函數(shù)下

10、降的解。方法 具體形式對(duì)算法影響不大 一般采用min1,exp(-C/t) 3.3.2 狀態(tài)接受函數(shù)第20頁(yè)，共47頁(yè)，2022年，5月20日，6點(diǎn)42分，星期四3.3 模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì)智能優(yōu)化計(jì)算收斂性分析 通過理論分析可以得到初溫的解析式，但解決實(shí)際問題時(shí)難以得到精確的參數(shù)； 初溫應(yīng)充分大；實(shí)驗(yàn)表明 初溫越大，獲得高質(zhì)量解的機(jī)率越大，但花費(fèi)較多的計(jì)算時(shí)間； 3.3.3 初溫第21頁(yè)，共47頁(yè)，2022年，5月20日，6點(diǎn)42分，星期四3.3 模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì)智能優(yōu)化計(jì)算方法 （1）均勻抽樣一組狀態(tài)，以各狀態(tài)目標(biāo)值得方差為初溫； （2）隨機(jī)產(chǎn)生一組狀態(tài)，確定兩

11、兩狀態(tài)間的最大目標(biāo)值差，根據(jù)差值，利用一定的函數(shù)確定初溫； （3）利用經(jīng)驗(yàn)公式。 3.3.3 初溫第22頁(yè)，共47頁(yè)，2022年，5月20日，6點(diǎn)42分，星期四3.3 模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì)智能優(yōu)化計(jì)算時(shí)齊算法的溫度下降函數(shù) （1） ，越接近1溫度下降越慢，且其大小可以不斷變化； （2） ，其中t0為起始溫度，K為算法溫度下降的總次數(shù)。 3.3.4 溫度更新函數(shù)第23頁(yè)，共47頁(yè)，2022年，5月20日，6點(diǎn)42分，星期四3.3 模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì)智能優(yōu)化計(jì)算非時(shí)齊模擬退火算法 每個(gè)溫度下只產(chǎn)生一個(gè)或少量候選解時(shí)齊算法常用的Metropolis抽樣穩(wěn)定準(zhǔn)則 （1）檢驗(yàn)?zāi)?/p>

12、標(biāo)函數(shù)的均值是否穩(wěn)定； （2）連續(xù)若干步的目標(biāo)值變化較??； （3）按一定的步數(shù)抽樣。 3.3.5 內(nèi)循環(huán)終止準(zhǔn)則第24頁(yè)，共47頁(yè)，2022年，5月20日，6點(diǎn)42分，星期四3.3 模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì)智能優(yōu)化計(jì)算常用方法 （1）設(shè)置終止溫度的閾值； （2）設(shè)置外循環(huán)迭代次數(shù)； （3）算法搜索到的最優(yōu)值連續(xù)若干步保持不變； （4）概率分析方法。 3.3.6 外循環(huán)終止準(zhǔn)則第25頁(yè)，共47頁(yè)，2022年，5月20日，6點(diǎn)42分，星期四3.4 模擬退火算法的改進(jìn)智能優(yōu)化計(jì)算模擬退火算法的優(yōu)點(diǎn) 質(zhì)量高； 初值魯棒性強(qiáng)； 簡(jiǎn)單、通用、易實(shí)現(xiàn)。模擬退火算法的缺點(diǎn) 由于要求較高的初始溫度、較慢

13、的降溫速率、較低的終止溫度，以及各溫度下足夠多次的抽樣，因此優(yōu)化過程較長(zhǎng)。 3.4.1 模擬退火算法的優(yōu)缺點(diǎn)第26頁(yè)，共47頁(yè)，2022年，5月20日，6點(diǎn)42分，星期四3.4 模擬退火算法的改進(jìn)智能優(yōu)化計(jì)算改進(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)容第27頁(yè)，共47頁(yè)，2022年，5月20日，6點(diǎn)42分，星期四3.4 模擬退火算法的改進(jìn)智能優(yōu)化計(jì)算改進(jìn)的方式 （1）增加升溫或重升溫

14、過程，避免陷入局部極??； （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)容第28頁(yè)，共47頁(yè)，2022年，5月20日，6點(diǎn)42分，星期四3.4 模擬退火算法的改進(jìn)智能優(yōu)化計(jì)算改進(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

15、次退溫過程中所得最優(yōu)解不變則認(rèn)為算法收斂。 3.4.3 一種改進(jìn)的模擬退火算法第29頁(yè)，共47頁(yè)，2022年，5月20日，6點(diǎn)42分，星期四3.4 模擬退火算法的改進(jìn)智能優(yōu)化計(jì)算改進(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)的模擬退火算法第30頁(yè)，共47頁(yè)，2

16、022年，5月20日，6點(diǎn)42分，星期四3.4 模擬退火算法的改進(jìn)智能優(yōu)化計(jì)算改進(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)的模擬退火算法第31頁(yè)，共47頁(yè)，2022年，5月20日，6點(diǎn)42分，星期四

17、3.5 模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算 3.5.1 30城市TSP問題（d*=423.741 by D B Fogel） TSP 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 50第32頁(yè)，共47頁(yè)，2022年，5月20日，6點(diǎn)42分，星期四3.5 模擬退火算法的

18、實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算算法流程 3.5.1 30城市TSP問題（d*=423.741 by D B Fogel） 第33頁(yè)，共47頁(yè)，2022年，5月20日，6點(diǎn)42分，星期四3.5 模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算初始溫度的計(jì)算 for i=1:100 route=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） 第34頁(yè)，共47頁(yè)，2022年，5月20日，6點(diǎn)42分，星期

19、四3.5 模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算狀態(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） 283591467283591467283591467281593467283419567235981467第35頁(yè)，共47頁(yè)，2022年，5月20日，6點(diǎn)42分，星期四3.5 模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算參數(shù)設(shè)定 截止溫度 tf=0.01; 退溫系數(shù) alpha=0.90; 內(nèi)循環(huán)次數(shù) L=200*CityN

20、um; 3.5.1 30城市TSP問題（d*=423.741 by D B Fogel） 第36頁(yè)，共47頁(yè)，2022年，5月20日，6點(diǎn)42分，星期四3.5 模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算運(yùn)行過程 3.5.1 30城市TSP問題（d*=423.741 by D B Fogel） 第37頁(yè)，共47頁(yè)，2022年，5月20日，6點(diǎn)42分，星期四3.5 模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算運(yùn)行過程 3.5.1 30城市TSP問題（d*=423.741 by D B Fogel） 第38頁(yè)，共47頁(yè)，2022年，5月20日，6點(diǎn)42分，星期四3.5 模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算運(yùn)行過程

21、 3.5.1 30城市TSP問題（d*=423.741 by D B Fogel） 第39頁(yè)，共47頁(yè)，2022年，5月20日，6點(diǎn)42分，星期四3.5 模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算運(yùn)行過程 3.5.1 30城市TSP問題（d*=423.741 by D B Fogel） 第40頁(yè)，共47頁(yè)，2022年，5月20日，6點(diǎn)42分，星期四3.5 模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算運(yùn)行過程 3.5.1 30城市TSP問題（d*=423.741 by D B Fogel） 第41頁(yè)，共47頁(yè)，2022年，5月20日，6點(diǎn)42分，星期四3.5 模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算運(yùn)行結(jié)果 3.5.1 30城市TSP問題（d*=423.741 by D B Fogel） 第42頁(yè)，共47頁(yè)，2022年，5月20日，6點(diǎn)42分，星期四3.5 模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算換熱器模型 兩級(jí)管殼式換熱器組成的換熱器系統(tǒng)，數(shù)學(xué)模型高度非線性，其目標(biāo)函數(shù)通常是多峰(谷)的，具有很多局部最優(yōu)解。 3.5.2 模擬退火算法在管殼式換熱器優(yōu)化設(shè)計(jì)中的應(yīng)用第43頁(yè)，共47頁(yè)，2022年，5月20日，6點(diǎn)42分，星期四3.5 模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算優(yōu)化目標(biāo) 以換熱器系統(tǒng)的總費(fèi)用年值最小作為優(yōu)化設(shè)計(jì)的目標(biāo)。 其中，f1 (X)是兩級(jí)換熱器的初始投資， f2 (X)是兩級(jí)換熱器年維護(hù)