基于MATLAB退火算法模擬

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

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

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

4、保留狀態(tài)為當前狀態(tài)；若不成立則保留狀態(tài) i 為當為當前狀態(tài)。前狀態(tài)。模擬退火算法及模型相似性比較相似性比較應用舉例用模擬退火算法解決如下10個城市的TSP問題模擬退火算法關鍵參數(shù)和操作的設計模擬退火算法關鍵參數(shù)和操作的設計狀態(tài)產(chǎn)生函數(shù)的設計狀態(tài)產(chǎn)生函數(shù)的設計（1）互換操作，隨機交換兩個城市的順序；）互換操作，隨機交換兩個城市的順序；（2）逆序操作，兩個隨機位置間的城市逆序；）逆序操作，兩個隨機位置間的城市逆序；（3）插入操作，隨機選擇某點插入某隨機位置。）插入操作，隨機選擇某點插入某隨機位置。283591467281593467模擬退火算法關鍵參數(shù)和操作的設計參數(shù)設定參數(shù)設定 截止溫度截止溫度 tf=0.01; 退溫系數(shù)退溫系數(shù) lam=0.95; 內(nèi)循環(huán)次數(shù)內(nèi)循環(huán)次數(shù) iLk=20運行過程模擬退火算法的優(yōu)缺點模擬退火算法的優(yōu)點模擬退火算法的優(yōu)點 質(zhì)量高；質(zhì)量高； 初值魯棒性強；初值魯棒性強； 簡單、通用、易實現(xiàn)。簡單、通用、易實現(xiàn)。模擬退火算法的缺點模擬退火算法的缺點 由于要求較高的初始溫度、較慢的降溫速率、較低的終由于要求較高