基于模擬退火算法的TSP問題研究報(bào)告附MATLAB程序

1、TSP問題的模擬退火算法如需程序，點(diǎn)擊上傳者，見如需程序，點(diǎn)擊上傳者，見“我的文檔我的文檔”。1. 模擬退火簡介1.1 問題討論2. 模擬退火算法步驟3. 參數(shù)選取4. 模擬退火算法求解TSP問題1模擬退火簡介模擬退火簡介 物理解釋：材料中的原子原來會(huì)停留在使內(nèi)能有局部最小值的位置，加熱使能量變大，原子會(huì)離開原來位置，而隨機(jī)在其他位置中移動(dòng)。退火冷卻時(shí)速度較慢，使得原子有較多可能可以找到內(nèi)能比原先更低的位置。 統(tǒng)計(jì)學(xué)解釋：我們將熱力學(xué)的理論套用到統(tǒng)計(jì)學(xué)上，將搜尋空間內(nèi)每一點(diǎn)想像成空氣內(nèi)的分子；搜尋空間內(nèi)的每一點(diǎn)，也像空氣分子一樣帶有“動(dòng)能”，以表示該點(diǎn)對(duì)命題的合適程度。算法先以搜尋空間內(nèi)一個(gè)任

2、意點(diǎn)作起始：每一步先選擇一個(gè)“鄰居”，然后再計(jì)算從現(xiàn)有位置到達(dá)“鄰居”的概率。1.模擬退火簡介模擬退火簡介 假設(shè)物體在加熱一定溫度后，它的所有分子存在D種狀態(tài)空間。隨著溫度的下降，這些分子停留在不同的狀態(tài)，最終趨于穩(wěn)定狀態(tài)。 由統(tǒng)計(jì)力學(xué)研究表明，在溫度T，分子停留在狀態(tài)r的概率滿足波茲曼(Boltzmann)概率分布 其中，E(r)是狀態(tài)r的能量，Z(T)是概率分布的標(biāo)準(zhǔn)化因子1.1 問題討論問題討論 在同一個(gè)溫度T下，能量高的狀態(tài)概率大還是??？ 設(shè)E1 random(0,1)時(shí)，則i=j ；重 復(fù)Step2；Step3：若在該tk+1=d(tk),k=k+1; 若滿足外循環(huán)停 止條件，終止計(jì)

3、算；否則，回到Step2.2.模擬退火算法步驟模擬退火算法步驟 內(nèi)循環(huán)：Step2表示在同一溫度tk時(shí)，在一些狀態(tài) 的隨機(jī)搜索。當(dāng)溫度很低tk0時(shí)， exp(-fij /tk)0. 停止條件：內(nèi)循環(huán)次數(shù)step maxstep ? 若是，轉(zhuǎn)到Step3，且降溫tk+1=*tk, step=0，k=k+1增加新溫度tk下的 maxstep=maxstep+a 。 若否，step=step+1，反復(fù)Step2. 外循環(huán)：停止條件是溫度tk足夠低，tk e ？ 若是，算法結(jié)束，輸出結(jié)果。 若否，回到Step2。3. 參數(shù)選取參數(shù)選取 t0 tk+1=*tk maxstep=maxstep+a t0太

4、大，計(jì)算時(shí)間增加；t0太小，會(huì)過早陷入局部最優(yōu)。4.模擬退火算法求模擬退火算法求TSP問題問題 解的表示：用一個(gè)訪問序列T=(t1,t2,t3,tn,t1)來表示經(jīng)過n個(gè)城市的順序。 距離矩陣：D=(dij)是由城市i和城市j之間的距離所組成的距離矩陣。 數(shù)學(xué)模型： 解的鄰域：隨機(jī)產(chǎn)生2個(gè)位置，讓序列T上對(duì)應(yīng)的兩個(gè)位置上的城市順序?qū)Q。11min( )i int tiL Tdniniijijnjijdnjijd11,1,|min,1,|max4.模擬退火算法求模擬退火算法求TSP問題問題 Tips：訪問序列T=(t1,t2,t3,tn,t1)簡化為 T=(t2,t3,tn) 減小解空間的冗余！4.模擬退火算法求模擬退火算法求TSP問題問題 TSP問題實(shí)例：TSP問題標(biāo)準(zhǔn)測試數(shù)據(jù)burma14.tsp141618202224269293949596979899burma14城 市 的 TSP最 短 路 徑141618202224269293949596979899burma14的 城 市 分 布測試數(shù)據(jù)下載