資源描述：
《模擬退火算法解決TSP問題-Read.docx》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、模擬退火算法解決TSP問題周虹辰一、代碼介紹:這段代碼使用了模擬退火的思想解決TSP問題。在這個(gè)仿真實(shí)驗(yàn)中解決了自定義的20個(gè)城市的TSP問題，在設(shè)定合適參數(shù)后每次的運(yùn)行中都能得到一個(gè)比較理想的結(jié)果。Main.m文件是程序入口。Data_file.m文件設(shè)置自定義的城市數(shù)據(jù)。Swapcities.m文件中包含隨機(jī)交換兩個(gè)城市的函數(shù)。Plotcities.m文件中包含將城市數(shù)據(jù)在二維平面上表示的函數(shù)。Distance.m文件中包含計(jì)算城市距離的函數(shù)，用來解決旅行商問題。Simulatedannealing
2、.m文件中包含模擬退火算法。這部分是程序的主體，我參考了許多討論關(guān)于模擬退火算法方面的論文。二、模擬退火算法原理：模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。根據(jù)Metropolis準(zhǔn)則，粒子在溫度T時(shí)趨于平衡的概率為e-AE/(kT),其中E為溫度T時(shí)的內(nèi)能，AE為其改變量，k為Boltzmann常數(shù)。用固體退火模擬組合優(yōu)化問題，將內(nèi)能E模擬為目
3、標(biāo)函數(shù)值f，溫度T演化成控制參數(shù)t,即得到解組合優(yōu)化問題的模擬退火算法：由初始解i和控制參數(shù)初值t開始，對當(dāng)前解重復(fù)產(chǎn)生新解t計(jì)算目標(biāo)函數(shù)差t接受或舍棄”的迭代，并逐步衰減t值，算法終止時(shí)的當(dāng)前解即為所得近似最優(yōu)解,這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機(jī)搜索過程。退火過程由冷卻進(jìn)度表(CoolingSchedule)控制，包括控制參數(shù)的初值t及其衰減因子At每個(gè)t值時(shí)的迭代次數(shù)L和停止條件S。三、模擬退火的基本思想:(1)初始化：初始溫度T(充分大)，初始解狀態(tài)S(是算法迭代的起點(diǎn))，每個(gè)T值的迭代
4、次數(shù)L。(2)對k=1,……,L做第⑶至第6步：(3)產(chǎn)生新解S'⑷計(jì)算增量At'=C(9()，其中C(S)為評價(jià)函數(shù)(5)若At'則接受S'作為新的當(dāng)前解，否則以概率exp(-At'接受S'作為新的當(dāng)前解.(6)如果滿足終止條件則輸出當(dāng)前解作為最優(yōu)解，結(jié)束程序。終止條件通常取為連續(xù)若干個(gè)新解都沒有被接受時(shí)終止算法。(7)T逐漸減少，且T->0,然后轉(zhuǎn)第2步。四、求解TSP的模擬退火算法：解空間解空間S是遍訪每個(gè)城市恰好一次的所有回路，是{1,……,n}的所有循環(huán)排列的集合，S中的成員記為(w1,w2,
5、,wn),并記wn+仁w1。初始解可選為(1,,n)目標(biāo)函數(shù)此時(shí)的目標(biāo)函數(shù)即為訪問所有城市的路徑總長度或稱為代價(jià)函數(shù)：我們要求此代價(jià)函數(shù)的最小值。新解的產(chǎn)生隨機(jī)產(chǎn)生1和n之間的兩相異數(shù)k和m,若k(w1,w2,…wk,wk+1,…,wm,…，wn)變?yōu)椋?w1,w2,…，wm,wm-1,…，wk+1,wk,…，wn).如果是k>m，則將(w1,w2,…；wk,wk+1,…，wm，…，wn)變?yōu)椋?wm,wm-1,…，w1,wm+1,…，wk-1,wn,wn-1,?…wk).五、模擬退火算法的參數(shù)控制問題
6、：模擬退火算法的應(yīng)用很廣泛，可以求解NP完全問題，但其參數(shù)難以控制，其主要問題有以下三點(diǎn)：(1)溫度T的初始值設(shè)置問題。溫度T的初始值設(shè)置是影響模擬退火算法全局搜索性能的重要因素之一、初始溫度高，則搜索到全局最優(yōu)解的可能性大，但因此要花費(fèi)大量的計(jì)算時(shí)間；反之，則可節(jié)約計(jì)算時(shí)間，但全局搜索性能可能受到影響。實(shí)際應(yīng)用過程中，初始溫度一般需要依據(jù)實(shí)驗(yàn)結(jié)果進(jìn)行若干次調(diào)整。(2)退火速度問題。模擬退火算法的全局搜索性能也與退火速度密切相關(guān)。一般來說，同一溫度下的充分搜索(退火)是相當(dāng)必要的，但這需要計(jì)算時(shí)間。實(shí)際
7、應(yīng)用中，要針對具體問題的性質(zhì)和特征設(shè)置合理的退火平衡條件。(3)溫度管理問題。溫度管理問題也是模擬退火算法難以處理的問題之一。實(shí)際應(yīng)用中，由于必須考慮計(jì)算復(fù)雜度的切實(shí)可行性等問題，常采用如下所示的降溫方式：T(t+1)=kXT(t)式中k為正的略小于1.00的常數(shù)，t為降溫的次數(shù)。一次實(shí)驗(yàn)的結(jié)果：rrW-R*PWdIfMm-MM叫!■*?砂1阿*1；mrlWImolNiAT*1￡]as：a-
8、kki-4*1[mI31T
9、?LiItlpaBJbB^rkmr□注???「21￡h?UEiI￡t?uiflHa*
10、-Krin497ES4J_DDQD-D-V-O*i□FM田□]Hff□八
