模擬退火算法的教程

1、 Simulated Annealing Algorithm 信息與計(jì)算科學(xué)信息與計(jì)算科學(xué) 卿卿 銘銘 模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻；加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到某種穩(wěn)定狀態(tài)，某種穩(wěn)定狀態(tài)，基態(tài)，內(nèi)能減為最小。 v物理退火過程物理退火過程 加溫過程增強(qiáng)粒子的熱運(yùn)動，消除系統(tǒng)原先可能存在的非均勻態(tài)； 等溫過程對于與環(huán)境換熱而溫度不變的封閉系統(tǒng)，系統(tǒng)狀態(tài)的自發(fā)變化總是朝自由能減少的方向進(jìn)行，當(dāng)自由能達(dá)到最小時(shí)，系統(tǒng)達(dá)到平衡態(tài)； 冷卻過程使粒子熱運(yùn)動減弱并漸趨有序，系統(tǒng)能量逐漸

2、下降，從而得到低能的晶體結(jié)構(gòu)。 v緩慢降溫（退火，annealing）時(shí)，可達(dá)到最低能量狀態(tài)，較為柔韌；但如果快速降溫（淬火，quenching），會導(dǎo)致不是最低能態(tài)的非晶形，。v大自然知道慢工出細(xì)活： 緩緩降溫，使得物體分子在每一溫度時(shí)，能夠有足夠時(shí)間找到安頓位置，則逐漸地，到最后可得到最低能態(tài)，系統(tǒng)最穩(wěn)定。 模擬退火算法(Simulated Annealing，SA)最早的思想是由N. Metropolis等人于1953年提出。1983 年,S. Kirkpatrick 等成功地將退火思想引入到組合優(yōu)化領(lǐng)域。它是基于Monte-Carlo迭代求解策略的一種隨機(jī)尋優(yōu)算法，其出發(fā)點(diǎn)是基于物理中

3、固體物質(zhì)的退火過程與一般組合優(yōu)化問題之間的相似性。模擬退火算法從某一較高初溫出發(fā)，伴隨溫度參數(shù)的不斷下降,結(jié)合概率突跳特性在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解，即在局部最優(yōu)解能概率性地跳出并最終趨于全局最優(yōu)。v模擬退火算法是通過賦予搜索過程一種時(shí)變且最終趨于零的概率突跳性，從而可有效避免陷入局部極小并最終趨于全局最優(yōu)的串行結(jié)構(gòu)的優(yōu)化算法。v模擬退火算法是一種通用的優(yōu)化算法，理論上算法具有概率的全局優(yōu)化性能,目前已在工程中得到了廣泛應(yīng)用。相似性比較相似性比較 組合優(yōu)化問題組合優(yōu)化問題金屬物體金屬物體解解粒子狀態(tài)粒子狀態(tài)最優(yōu)解最優(yōu)解能量最低的狀態(tài)能量最低的狀態(tài)設(shè)定初溫設(shè)定初溫熔解過程熔解過程Me

4、tropolis抽樣過程抽樣過程等溫過程等溫過程控制參數(shù)的下降控制參數(shù)的下降冷卻冷卻目標(biāo)函數(shù)目標(biāo)函數(shù)能量能量 從某一初始從某一初始溫度溫度開始，伴隨溫度的不斷下降，結(jié)合開始，伴隨溫度的不斷下降，結(jié)合概率突跳概率突跳特性在解空間中特性在解空間中隨機(jī)隨機(jī)尋找尋找全局最優(yōu)解全局最優(yōu)解v根據(jù)Metropolis準(zhǔn)則，粒子在溫度T時(shí)趨于平衡的概率為exp(-E/(kT)，其中E為溫度T時(shí)的內(nèi)能，E為其改變量，k為Boltzmann常數(shù)。用固體退火模擬組合優(yōu)化問題，將內(nèi)能E模擬為目標(biāo)函數(shù)值f，溫度T演化成控制參數(shù)t，即得到解組合優(yōu)化問題的模擬退火算法：由初始解i和控制參數(shù)初值t開始，對當(dāng)前解重復(fù)“產(chǎn)生新解

5、計(jì)算目標(biāo)函數(shù)差接受或舍棄”的迭代，并逐步衰減t值，算法終止時(shí)的當(dāng)前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機(jī)搜索過程。v退火過程由冷卻進(jìn)度表(Cooling Schedule)控制，包括控制參數(shù)的初值t及其衰減因子t、每個(gè)t值時(shí)的迭代次數(shù)L和停止條件S。 2模擬退火算法的原理模擬退火算法的原理 在溫度在溫度T，分子停留在狀態(tài)，分子停留在狀態(tài)r滿足滿足Boltzmann概率分布概率分布DsBBBTksETZTZkrrEETkrETZrEEP)(exp)()(Boltzmann0)()(exp)(1)(子：為概率分布的標(biāo)準(zhǔn)化因常數(shù)。為的能量，表示狀態(tài)機(jī)變量，表示分子能量的一個(gè)

6、隨 在在同一個(gè)溫度同一個(gè)溫度T，選定兩個(gè)能量，選定兩個(gè)能量E1E2，有，有TkEETkETZEEPEEPBB12121exp1exp)(10模擬退火算法基本思想模擬退火算法基本思想：在一定溫度下，搜索從一個(gè)狀態(tài)：在一定溫度下，搜索從一個(gè)狀態(tài)隨機(jī)地變化到另一個(gè)狀態(tài)；隨著溫度的不斷下降直到最低溫度，隨機(jī)地變化到另一個(gè)狀態(tài)；隨著溫度的不斷下降直到最低溫度，搜索過程以概率搜索過程以概率1停留在最優(yōu)解停留在最優(yōu)解可知： （1）在同一個(gè)溫度，分子停留在能量小狀態(tài)的概率大于停留在能量大狀態(tài)的概率 （2）溫度越高，不同能量狀態(tài)對應(yīng)的概率相差越??；溫度足夠高時(shí)，各狀態(tài)對應(yīng)概率基本相同。 （3）隨著溫度的下降，能

7、量最低狀態(tài)對應(yīng)概率越來越大；溫度趨于0時(shí)，其狀態(tài)趨于1 若|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。能量最低狀態(tài)能量最低狀態(tài) 非能量最低狀態(tài)非能量最低狀態(tài)vMetropolis準(zhǔn)則（準(zhǔn)則（1953）以概率接受新狀態(tài)以概率接受新狀態(tài) 固體在恒定溫度下達(dá)到熱平衡的過程可以用Monte Carlo方法（計(jì)算機(jī)隨機(jī)模擬方法）加以模擬，雖然該方法簡單，但必須大量采樣才能得到比較精確的結(jié)果，計(jì)算

8、量很大。vMetropolis準(zhǔn)則（1953）以概率接受新狀態(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)。 01-(Ej-Ei)/kTpvMetropolis準(zhǔn)則（準(zhǔn)則（1953）以概率接受新狀態(tài)以概率接受新狀態(tài) p=exp-(Ej-Ei)/kBT 在高溫下，可接受與當(dāng)前狀態(tài)能量差較大的新狀態(tài)；在高溫下，可接受與當(dāng)前狀態(tài)能量差較大的新狀態(tài)； 在低溫下，只接受與當(dāng)前狀態(tài)能量差較小的新狀態(tài)。在低溫下，只接受與當(dāng)前狀態(tài)能量差較小的

9、新狀態(tài)。v根據(jù)Metropolis準(zhǔn)則，粒子在溫度T時(shí)趨于平衡的概率為exp(-E/(kT)，其中E為溫度T時(shí)的內(nèi)能，E為其改變量，k為Boltzmann常數(shù)。用固體退火模擬組合優(yōu)化問題，將內(nèi)能E模擬為目標(biāo)函數(shù)值f，溫度T演化成控制參數(shù)t，即得到解組合優(yōu)化問題的模擬退火算法：由初始解i和控制參數(shù)初值t開始，對當(dāng)前解重復(fù)“產(chǎn)生新解計(jì)算目標(biāo)函數(shù)差接受或舍棄”的迭代，并逐步衰減t值，算法終止時(shí)的當(dāng)前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機(jī)搜索過程。v退火過程由冷卻進(jìn)度表(Cooling Schedule)控制，包括控制參數(shù)的初值t及其衰減因子t、每個(gè)t值時(shí)的迭代次數(shù)L和停止條

10、件S。 3模擬退火算法的原理模擬退火算法的原理v1模擬退火算法可以分解為解空間、目標(biāo)函數(shù)和初始解三部分。v2模擬退火的基本步驟:v(1) 初始化：初始溫度T(充分大)，初始解狀態(tài)S(是算法迭代的起點(diǎn))，每個(gè)T值的迭代次數(shù)L。v(2) 對k=1，L做第(3)至第6步：v(3) 產(chǎn)生新解Sv(4) 計(jì)算增量t=C(S)-C(S)，其中C(S)為評價(jià)函數(shù)v(5) 若t0，然后轉(zhuǎn)第2步。4模擬退火算法的模型與特點(diǎn)模擬退火算法的模型與特點(diǎn)模擬退火算法與初始值無關(guān)，算法求得的解與初始解狀態(tài)S(是算法迭代的起點(diǎn))無關(guān)；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以概率l 收斂于全局最優(yōu)解的全局優(yōu)化算法

11、；模擬退火算法具有并行性。 v基本步驟基本步驟 給定初溫給定初溫t=t0，隨機(jī)產(chǎn)生初始狀態(tài)，隨機(jī)產(chǎn)生初始狀態(tài)s=s0，令，令k=0； Repeat Repeat 產(chǎn)生新狀態(tài)產(chǎn)生新狀態(tài)sj=Genete(s)； if min1,exp-(C(sj)-C(s)/tk=randrom0,1 s=sj; Until 抽樣穩(wěn)定準(zhǔn)則滿足；抽樣穩(wěn)定準(zhǔn)則滿足； 退溫退溫tk+1=update(tk)并令并令k=k+1； Until 算法終止準(zhǔn)則滿足；算法終止準(zhǔn)則滿足； 輸出算法搜索結(jié)果。輸出算法搜索結(jié)果。v影響優(yōu)化結(jié)果的主要因素影響優(yōu)化結(jié)果的主要因素 給定初溫給定初溫t=t0，隨機(jī)產(chǎn)生初始狀態(tài)，隨機(jī)產(chǎn)生初始狀

12、態(tài)s=s0，令，令k=0； Repeat Repeat 產(chǎn)生新狀態(tài)產(chǎn)生新狀態(tài)sj=Genete(s)； if min1,exp-(C(sj)-C(s)/tk=randrom0,1 s=sj; Until 抽樣穩(wěn)定準(zhǔn)則滿足；抽樣穩(wěn)定準(zhǔn)則滿足； 退溫退溫tk+1=update(tk)并令并令k=k+1； Until 算法終止準(zhǔn)則滿足；算法終止準(zhǔn)則滿足； 輸出算法搜索結(jié)果。輸出算法搜索結(jié)果。三函數(shù)兩準(zhǔn)則三函數(shù)兩準(zhǔn)則初始溫度初始溫度Step1 設(shè)定初始溫度設(shè)定初始溫度t = tmax, 任選初始解任選初始解r = r0Step2 內(nèi)循環(huán)內(nèi)循環(huán) Step2.1 從從r的鄰域中隨機(jī)選一個(gè)解的鄰域中隨機(jī)選一

13、個(gè)解rt, 計(jì)算計(jì)算r和和rt對應(yīng)目標(biāo)對應(yīng)目標(biāo)函函 數(shù)值數(shù)值, 如如rt對應(yīng)目標(biāo)函數(shù)值較小，則令對應(yīng)目標(biāo)函數(shù)值較小，則令r = rt; 否則若否則若 exp(-(E(rt)-E(r)/t)random(0,1), 則令則令r=rt. Step2.2 不滿足內(nèi)循環(huán)停止條件時(shí)，重復(fù)不滿足內(nèi)循環(huán)停止條件時(shí)，重復(fù)Step2.1Step3 外循環(huán)外循環(huán) Step3.1 降溫降溫t = decrease(t) Step3.2 如不滿足外循環(huán)停止條件，則轉(zhuǎn)如不滿足外循環(huán)停止條件，則轉(zhuǎn)Step2；否則算；否則算法結(jié)束法結(jié)束1. 達(dá)到終止溫度達(dá)到終止溫度2. 達(dá)到迭代次數(shù)達(dá)到迭代次數(shù)3. 最優(yōu)值連續(xù)若干步最優(yōu)值

14、連續(xù)若干步保持不變保持不變1. 目標(biāo)函數(shù)均值穩(wěn)定目標(biāo)函數(shù)均值穩(wěn)定2. 連續(xù)若干步的目標(biāo)連續(xù)若干步的目標(biāo)值變化較小值變化較小3. 固定的抽樣步數(shù)固定的抽樣步數(shù)v模擬退火算法的步驟模擬退火算法的步驟v原則原則 產(chǎn)生的候選解應(yīng)遍布全部解空間產(chǎn)生的候選解應(yīng)遍布全部解空間v方法方法 在當(dāng)前狀態(tài)的鄰域結(jié)構(gòu)內(nèi)以一定概率方式（均勻分在當(dāng)前狀態(tài)的鄰域結(jié)構(gòu)內(nèi)以一定概率方式（均勻分布、正態(tài)分布、指數(shù)分布等）產(chǎn)生布、正態(tài)分布、指數(shù)分布等）產(chǎn)生v原則原則 (1)在固定溫度下，接受使目標(biāo)函數(shù)下降的候選解的在固定溫度下，接受使目標(biāo)函數(shù)下降的候選解的概率要大于使目標(biāo)函數(shù)上升的候選解概率；概率要大于使目標(biāo)函數(shù)上升的候選解概率；

15、 (2)隨溫度的下降，接受使目標(biāo)函數(shù)上升的解的概率隨溫度的下降，接受使目標(biāo)函數(shù)上升的解的概率要逐漸減??；要逐漸減??； (3)當(dāng)溫度趨于零時(shí)，只能接受目標(biāo)函數(shù)下降的解。當(dāng)溫度趨于零時(shí)，只能接受目標(biāo)函數(shù)下降的解。v方法方法 具體形式對算法影響不大具體形式對算法影響不大 一般采用一般采用min1,exp(-C/t)v收斂性分析收斂性分析 通過理論分析可以得到初溫的解析式，但解決實(shí)際通過理論分析可以得到初溫的解析式，但解決實(shí)際問題時(shí)難以得到精確的參數(shù)；問題時(shí)難以得到精確的參數(shù)； 初溫應(yīng)充分大；初溫應(yīng)充分大；v實(shí)驗(yàn)表明實(shí)驗(yàn)表明 初溫越大，獲得高質(zhì)量解的機(jī)率越大，但花費(fèi)較多初溫越大，獲得高質(zhì)量解的機(jī)率越大

16、，但花費(fèi)較多的計(jì)算時(shí)間；的計(jì)算時(shí)間；v方法方法 （1）均勻抽樣一組狀態(tài)，以各狀態(tài)目標(biāo)值得方差）均勻抽樣一組狀態(tài)，以各狀態(tài)目標(biāo)值得方差為初溫；為初溫； （2）隨機(jī)產(chǎn)生一組狀態(tài)，確定兩兩狀態(tài)間的最大）隨機(jī)產(chǎn)生一組狀態(tài)，確定兩兩狀態(tài)間的最大目標(biāo)值差，根據(jù)差值，利用一定的函數(shù)確定初溫；目標(biāo)值差，根據(jù)差值，利用一定的函數(shù)確定初溫； （3）利用經(jīng)驗(yàn)公式。）利用經(jīng)驗(yàn)公式。v溫度下降函數(shù)溫度下降函數(shù) （1） ，越接近越接近1 1溫度下降越溫度下降越慢，且其大小可以不斷變化；慢，且其大小可以不斷變化； （2） ，其中，其中t0為起始溫度，為起始溫度，K為算法溫度為算法溫度下降的總次數(shù)。下降的總次數(shù)。10 , 0

17、 ,1kttkk0tKkKtkv非時(shí)齊模擬退火算法非時(shí)齊模擬退火算法 每個(gè)溫度下只產(chǎn)生一個(gè)或少量候選解每個(gè)溫度下只產(chǎn)生一個(gè)或少量候選解v時(shí)齊算法時(shí)齊算法常用的常用的Metropolis抽樣穩(wěn)定準(zhǔn)則抽樣穩(wěn)定準(zhǔn)則 （1）檢驗(yàn)?zāi)繕?biāo)函數(shù)的均值是否穩(wěn)定；）檢驗(yàn)?zāi)繕?biāo)函數(shù)的均值是否穩(wěn)定； （2）連續(xù)若干步的目標(biāo)值變化較??；）連續(xù)若干步的目標(biāo)值變化較小； （3）按一定的步數(shù)抽樣。）按一定的步數(shù)抽樣。 模擬退火算法對應(yīng)了一個(gè)馬爾可夫鏈，新狀態(tài)接受概率僅依賴于新狀態(tài)和模擬退火算法對應(yīng)了一個(gè)馬爾可夫鏈，新狀態(tài)接受概率僅依賴于新狀態(tài)和當(dāng)前狀態(tài)，并由溫度加以控制。當(dāng)前狀態(tài)，并由溫度加以控制。 若固定每一溫度，算法均計(jì)算

18、馬氏鏈的變化直至平穩(wěn)分布，然后下降溫度，若固定每一溫度，算法均計(jì)算馬氏鏈的變化直至平穩(wěn)分布，然后下降溫度，則稱為時(shí)齊算法；則稱為時(shí)齊算法； 若無需各溫度下算法均達(dá)到平穩(wěn)分布，但溫度需按一定速率下降，則稱為若無需各溫度下算法均達(dá)到平穩(wěn)分布，但溫度需按一定速率下降，則稱為非時(shí)齊算法。非時(shí)齊算法。v常用方法常用方法 （1）設(shè)置終止溫度的閾值；）設(shè)置終止溫度的閾值； （2）設(shè)置外循環(huán)迭代次數(shù)；）設(shè)置外循環(huán)迭代次數(shù)； （3）算法搜索到的最優(yōu)值連續(xù)若干步保持不變；）算法搜索到的最優(yōu)值連續(xù)若干步保持不變； （4）概率分析方法。）概率分析方法。v模擬退火算法的優(yōu)點(diǎn)模擬退火算法的優(yōu)點(diǎn) 質(zhì)量高；質(zhì)量高； 初值魯棒

19、性強(qiáng)；初值魯棒性強(qiáng)； 簡單、通用、易實(shí)現(xiàn)。簡單、通用、易實(shí)現(xiàn)。v模擬退火算法的缺點(diǎn)模擬退火算法的缺點(diǎn) 由于要求較高的初始溫度、較慢的降溫速率、較低由于要求較高的初始溫度、較慢的降溫速率、較低的終止溫度，以及各溫度下足夠多次的抽樣，因此的終止溫度，以及各溫度下足夠多次的抽樣，因此優(yōu)化過程較長。優(yōu)化過程較長。v改進(jìn)的可行方案改進(jìn)的可行方案 （1）設(shè)計(jì)合適的狀態(tài)產(chǎn)生函數(shù)；）設(shè)計(jì)合適的狀態(tài)產(chǎn)生函數(shù)； （2）設(shè)計(jì)高效的退火歷程；）設(shè)計(jì)高效的退火歷程； （3）避免狀態(tài)的迂回搜索；）避免狀態(tài)的迂回搜索； （4）采用并行搜索結(jié)構(gòu)；）采用并行搜索結(jié)構(gòu)； （5）避免陷入局部極小，改進(jìn)對溫度的控制方式；）避免陷入局

20、部極小，改進(jìn)對溫度的控制方式； （6）選擇合適的初始狀態(tài)；）選擇合適的初始狀態(tài)； （7）設(shè)計(jì)合適的算法終止準(zhǔn)則。）設(shè)計(jì)合適的算法終止準(zhǔn)則。 v改進(jìn)的方式改進(jìn)的方式 （1）增加升溫或重升溫過程，避免陷入局部極?。唬┰黾由郎鼗蛑厣郎剡^程，避免陷入局部極??； （2）增加記憶功能（記憶）增加記憶功能（記憶“Best so far”狀態(tài)）；狀態(tài)）； （3）增加補(bǔ)充搜索過程（以最優(yōu)結(jié)果為初始解）；）增加補(bǔ)充搜索過程（以最優(yōu)結(jié)果為初始解）； （4）對每一當(dāng)前狀態(tài)，采用多次搜索策略，以概率）對每一當(dāng)前狀態(tài)，采用多次搜索策略，以概率接受區(qū)域內(nèi)的最優(yōu)狀態(tài)；接受區(qū)域內(nèi)的最優(yōu)狀態(tài)； （5）結(jié)合其它搜索機(jī)制的算法；）結(jié)

21、合其它搜索機(jī)制的算法； （6）上述各方法的綜合。）上述各方法的綜合。 v改進(jìn)的思路改進(jìn)的思路 （1）記錄）記錄“Best so far”狀態(tài)，并即時(shí)更新；狀態(tài)，并即時(shí)更新； （2）設(shè)置雙閾值，使得在盡量保持最優(yōu)性的前提下）設(shè)置雙閾值，使得在盡量保持最優(yōu)性的前提下減少計(jì)算量，即在各溫度下當(dāng)前狀態(tài)連續(xù)減少計(jì)算量，即在各溫度下當(dāng)前狀態(tài)連續(xù) m1 步保持步保持不變則認(rèn)為不變則認(rèn)為Metropolis抽樣穩(wěn)定，若連續(xù)抽樣穩(wěn)定，若連續(xù) m2 次退溫次退溫過程中所得最優(yōu)解不變則認(rèn)為算法收斂。過程中所得最優(yōu)解不變則認(rèn)為算法收斂。v v改進(jìn)的退火過程改進(jìn)的退火過程 （1）給定初溫）給定初溫t0，隨機(jī)產(chǎn)生初始狀態(tài)

22、，隨機(jī)產(chǎn)生初始狀態(tài)s，令初始最優(yōu)解，令初始最優(yōu)解s*=s，當(dāng)前狀態(tài)為當(dāng)前狀態(tài)為s(0)=s，i=p=0； （2）令）令t=ti，以，以t，s*和和s(i)調(diào)用改進(jìn)的抽樣過程，返回其所得調(diào)用改進(jìn)的抽樣過程，返回其所得最優(yōu)解最優(yōu)解s*和當(dāng)前狀態(tài)和當(dāng)前狀態(tài)s(k)，令當(dāng)前狀態(tài)，令當(dāng)前狀態(tài)s(i)=s(k)； （3）判斷）判斷C(s*)m2? 若是，則轉(zhuǎn)第若是，則轉(zhuǎn)第(6)步；否則，返回第步；否則，返回第(2)步；步； （6）以最優(yōu)解）以最優(yōu)解s*作為最終解輸出，停止算法。作為最終解輸出，停止算法。v v改進(jìn)的抽樣過程改進(jìn)的抽樣過程 （1）令）令k=0時(shí)的初始當(dāng)前狀態(tài)為時(shí)的初始當(dāng)前狀態(tài)為s(0)=s(

23、i)，q=0； （2）由狀態(tài)）由狀態(tài)s通過狀態(tài)產(chǎn)生函數(shù)產(chǎn)生新狀態(tài)通過狀態(tài)產(chǎn)生函數(shù)產(chǎn)生新狀態(tài)s，計(jì)算增量，計(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)；作為下一當(dāng)前狀態(tài)； （4）令）令k=k+1，判斷，判斷qm1? 若是，則轉(zhuǎn)第若是，則轉(zhuǎn)第(5)步；否則，返回步；否則，返回第第(2)步；步； （5）將當(dāng)前最優(yōu)解）將當(dāng)前最優(yōu)解s*和當(dāng)前狀態(tài)和當(dāng)前狀態(tài)s(k)返回改進(jìn)退火過程。返回改進(jìn)退火過程。 vTSP Benchmark 問題問題 41 9

24、4;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 50v算法流程算法流程 v初始溫度的計(jì)算初始溫度的計(jì)算 for i=1:100 route=randperm(CityNum); fval0(i)=CalDist(dislist,route); end t0=-(max(fval0)-min(fval0)/

25、log(0.9); v v狀態(tài)產(chǎn)生函數(shù)的設(shè)計(jì)狀態(tài)產(chǎn)生函數(shù)的設(shè)計(jì) （1）互換操作，隨機(jī)交換兩個(gè)城市的順序；）互換操作，隨機(jī)交換兩個(gè)城市的順序； （2）逆序操作，兩個(gè)隨機(jī)位置間的城市逆序；）逆序操作，兩個(gè)隨機(jī)位置間的城市逆序； （3）插入操作，隨機(jī)選擇某點(diǎn)插入某隨機(jī)位置。）插入操作，隨機(jī)選擇某點(diǎn)插入某隨機(jī)位置。 283591467283591467283591467281593467283419567235981467v v參數(shù)設(shè)定參數(shù)設(shè)定 截止溫度截止溫度 tf=0.01; 退溫系數(shù)退溫系數(shù) alpha=0.90; 內(nèi)循環(huán)次數(shù)內(nèi)循環(huán)次數(shù) L=200*CityNum; v v運(yùn)行過程運(yùn)行過程 v運(yùn)

26、行過程運(yùn)行過程 v運(yùn)行過程運(yùn)行過程 v運(yùn)行過程運(yùn)行過程 v運(yùn)行過程運(yùn)行過程 v運(yùn)行結(jié)果運(yùn)行結(jié)果 v換熱器模型換熱器模型 兩級管殼式換熱器組成的換熱器系統(tǒng)，數(shù)學(xué)模型高兩級管殼式換熱器組成的換熱器系統(tǒng)，數(shù)學(xué)模型高度非線性，其目標(biāo)函數(shù)通常是多峰度非線性，其目標(biāo)函數(shù)通常是多峰(谷谷)的，具有很的，具有很多局部最優(yōu)解。多局部最優(yōu)解。 v優(yōu)化目標(biāo)優(yōu)化目標(biāo) 以換熱器系統(tǒng)的總費(fèi)用年值最小作為優(yōu)化設(shè)計(jì)的目以換熱器系統(tǒng)的總費(fèi)用年值最小作為優(yōu)化設(shè)計(jì)的目標(biāo)。標(biāo)。 其中，其中，f1 (X)是兩級換熱器的初始投資，是兩級換熱器的初始投資， f2 (X)是兩是兩級換熱器年維護(hù)費(fèi)級換熱器年維護(hù)費(fèi)(包括除垢、保養(yǎng)、維修等包括除

27、垢、保養(yǎng)、維修等)， f3 (X)是冷卻水資源費(fèi)以及管程壓降能耗費(fèi)，是冷卻水資源費(fèi)以及管程壓降能耗費(fèi)， f4 (X)是是殼程壓降能耗費(fèi)。殼程壓降能耗費(fèi)。)()()(1)1 ()1 ()()(min4321XfXfXfiiiXfXfnnv優(yōu)化目標(biāo)優(yōu)化目標(biāo) 經(jīng)過分析，優(yōu)化問題的獨(dú)立變量共經(jīng)過分析，優(yōu)化問題的獨(dú)立變量共12個(gè)，分別是一個(gè)，分別是一級換熱器煤油出口溫度級換熱器煤油出口溫度t2、冷卻水流量、冷卻水流量G1、兩個(gè)換、兩個(gè)換熱器的管內(nèi)徑熱器的管內(nèi)徑d1，d2和管間距和管間距S1，S2、折流板間距、折流板間距B1，B2、折流板開口角、折流板開口角1，2、單管長度、單管長度L1，L2。),()(min212121212112LLBBSSddGtfXf v應(yīng)用模擬退火算法解決優(yōu)化設(shè)計(jì)應(yīng)用模擬退火算法解決優(yōu)化設(shè)計(jì) 狀態(tài)表示狀態(tài)表示12個(gè)變量的實(shí)數(shù)表示；