基于MATLAB的退火算法的模擬

1、模擬退火算法（MATLAB實(shí)現(xiàn)） xx目錄目錄模擬退火算法及模型1.1 物理退火過程 退火是指將固體加熱到足夠高的溫度，使分子呈隨機(jī)排列狀態(tài)，然后逐步降溫使之冷卻，最后分子以低能狀態(tài)排列，固體達(dá)到某種穩(wěn)定狀態(tài)。 模仿自然界退火現(xiàn)象而得，利用了物理中固體物質(zhì)的退火過程與一般優(yōu)化問題的相似性 從某一初始溫度開始，伴隨溫度的不斷下降，結(jié)合概率突跳特性在解空間中隨機(jī)尋找全局最優(yōu)解模擬退火算法及模型1.2 數(shù)學(xué)表述在溫度T，分子停留在狀態(tài)r滿足Boltzmann概率分布模擬退火算法及模型在在同一個(gè)溫度同一個(gè)溫度T，選定兩個(gè)能量，選定兩個(gè)能量E1E2，有，有模擬退火算法基本思想模擬退火算法基本思想：在一定

2、溫度下，搜索從一個(gè)狀態(tài)：在一定溫度下，搜索從一個(gè)狀態(tài)隨機(jī)地變化到另一個(gè)狀態(tài)；隨著溫度的不斷下降直到最低隨機(jī)地變化到另一個(gè)狀態(tài)；隨著溫度的不斷下降直到最低溫度，搜索過程以概率溫度，搜索過程以概率1停留在最優(yōu)解停留在最優(yōu)解TkEETkETZEEPEEPBB12121exp1exp)(1模擬退火算法及模型BoltzmanBoltzman概率分布概率分布告訴我們：告訴我們： （1）在同一個(gè)溫度，分子停留在能量小狀態(tài)的概率大于停）在同一個(gè)溫度，分子停留在能量小狀態(tài)的概率大于停留在能量大狀態(tài)的概率留在能量大狀態(tài)的概率 （2）溫度越高，不同能量狀態(tài)對應(yīng)的概率相差越小；溫度）溫度越高，不同能量狀態(tài)對應(yīng)的概率相

3、差越??；溫度足夠高時(shí)，各狀態(tài)對應(yīng)概率基本相同。足夠高時(shí)，各狀態(tài)對應(yīng)概率基本相同。 （3）隨著溫度的下降，能量最低狀態(tài)對應(yīng)概率越來越大；）隨著溫度的下降，能量最低狀態(tài)對應(yīng)概率越來越大；溫度趨于溫度趨于0時(shí)，其狀態(tài)趨于時(shí)，其狀態(tài)趨于1模擬退火算法及模型Metropolis準(zhǔn)則（準(zhǔn)則（1953）以概率接受新狀態(tài)以概率接受新狀態(tài) 若在溫度若在溫度T，當(dāng)前狀態(tài)，當(dāng)前狀態(tài)i 新狀態(tài)新狀態(tài)j 若若EjEi，則接受，則接受 j 為當(dāng)前狀態(tài)；為當(dāng)前狀態(tài)； 否則，若概率否則，若概率 p=exp-(Ej-Ei)/kBT 大于大于0,1)區(qū)間的隨機(jī)數(shù)，區(qū)間的隨機(jī)數(shù)，則仍接受狀態(tài)則仍接受狀態(tài) j 為當(dāng)前狀態(tài)；若不成立則

4、保留狀態(tài)為當(dāng)前狀態(tài)；若不成立則保留狀態(tài) i 為當(dāng)為當(dāng)前狀態(tài)。前狀態(tài)。模擬退火算法及模型相似性比較相似性比較應(yīng)用舉例用模擬退火算法解決如下10個(gè)城市的TSP問題模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì)模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì)狀態(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ī)位置。283591467281593467模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì)參數(shù)設(shè)定參數(shù)設(shè)定 截止溫度截止溫度 tf=0.01; 退溫系數(shù)退溫系數(shù) lam=0.95; 內(nèi)循環(huán)次數(shù)內(nèi)循環(huán)次數(shù) iLk=20運(yùn)行過程模擬退火算法的優(yōu)缺點(diǎn)模擬退火算法的優(yōu)點(diǎn)模擬退火算法的優(yōu)點(diǎn) 質(zhì)量高；質(zhì)量高； 初值魯棒性強(qiáng)；初值魯棒性強(qiáng)； 簡單、通用、易實(shí)現(xiàn)。簡單、通用、易實(shí)現(xiàn)。模擬退火算法的缺點(diǎn)模擬退火算法的缺點(diǎn) 由于要求較高的初始溫度、較慢的降溫速率、較低的終由于要求較高