求解TSP的貪心模擬退火算法

李金旭，黃悅悅

(1.鄭州幼兒師范高等專(zhuān)科學(xué)校 信息網(wǎng)絡(luò)部，河南 鄭州 450001;

2.黃河科技學(xué)院 國(guó)際學(xué)院，河南 鄭州 450001)

?

求解TSP的貪心模擬退火算法

李金旭1，黃悅悅2

(1.鄭州幼兒師范高等專(zhuān)科學(xué)校 信息網(wǎng)絡(luò)部，河南 鄭州 450001;

2.黃河科技學(xué)院 國(guó)際學(xué)院，河南 鄭州 450001)

摘要：通過(guò)分析傳統(tǒng)模擬退火算法的不足和可行的改進(jìn)方案，提出了一個(gè)用于求解TSP問(wèn)題的貪心模擬退火算法.新算法在改進(jìn)的模擬退火算法的基礎(chǔ)上結(jié)合改進(jìn)的貪心算法，增加了算法的解的質(zhì)量.實(shí)驗(yàn)表明，新的算法比傳統(tǒng)的模擬退火算法和貪心算法有更優(yōu)的解.

關(guān)鍵詞：模擬退火算法；貪心算法；TSP；組合優(yōu)化

TSP(Traveling Salesman Problem，旅行商問(wèn)題)是數(shù)學(xué)領(lǐng)域著名的問(wèn)題之一，又被稱(chēng)為旅行銷(xiāo)售員問(wèn)題或貨郎擔(dān)問(wèn)題.TSP問(wèn)題是一個(gè)組合優(yōu)化問(wèn)題,任何能使該問(wèn)題的求解得以簡(jiǎn)化的方法都會(huì)受到高度的關(guān)注和評(píng)價(jià).目前,用來(lái)求解TSP問(wèn)題的主要算法有遺傳算法[1]、模擬退火算法[2]、蟻群算法[3]、神經(jīng)網(wǎng)絡(luò)算法[4]和混合策略算法[5].

模擬退火算法(Simulated Annealing, SA)[6]最早是由Metropolis于1953年提出的.1983 年,Kirkpatrick 成功地將退火思想引入組合優(yōu)化領(lǐng)域.它是基于Monte-Carlo迭代求解策略的一種隨機(jī)尋優(yōu)算法，出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過(guò)程與一般組合優(yōu)化問(wèn)題之間的相似性.本研究分析了傳統(tǒng)SA算法的原理和不足，提出了一個(gè)結(jié)合貪心算法和模擬退火算法的貪心模擬退火算法.實(shí)驗(yàn)證明，改進(jìn)的算法是有效的.

1貪心模擬退火算法

1.1傳統(tǒng)SA算法的缺點(diǎn)和改進(jìn)策略

模擬退火的基本思想如下:

(1) 初始化：初始溫度T(充分大)，初始解狀態(tài)S(是算法迭代的起點(diǎn))，每個(gè)T值的迭代次數(shù)L，n=0.

(2) 對(duì)k=1，…，L,做第(3)至第(6)步.

(3) 產(chǎn)生新解S′.

(4) 計(jì)算增量Δt′=C(S′)-C(S)，其中C(S)為評(píng)價(jià)函數(shù).

(5) 若Δt′<0則接受S′作為新的當(dāng)前解，否則以概率exp(-Δt′/T)接受S′作為新的當(dāng)前解.

(6) n=n+1，若n

(7) 如果滿(mǎn)足終止條件則輸出當(dāng)前解作為最優(yōu)解，結(jié)束程序,終止條件通常取連續(xù)若干個(gè)新解都沒(méi)有被接受時(shí)終止算法.

(8) n=0, T逐漸減少且T→0，然后轉(zhuǎn)第(2)步.

模擬退火算法包含內(nèi)外兩個(gè)循環(huán)，可以分解為解空間、目標(biāo)函數(shù)和初始解3部分。

傳統(tǒng)模擬退火算法的優(yōu)點(diǎn)有以一定的概率接受惡化解,引進(jìn)了算法控制參數(shù)T,可使用對(duì)象函數(shù)值進(jìn)行搜索,隱含并行性并可搜索復(fù)雜區(qū)域.但是傳統(tǒng)模擬退火算法的優(yōu)點(diǎn)在某些情況下反而會(huì)成為算法的缺點(diǎn),比如求解時(shí)間太長(zhǎng),溫度T參數(shù)的初始值和衰減程度較難確定,接受概率是隨機(jī)的或者是不確定的，使得有可能丟失全局最優(yōu)解.

通過(guò)對(duì)模擬退火算法的過(guò)程、優(yōu)點(diǎn)和缺點(diǎn)的研究分析，可行的改進(jìn)方案組如下：

(1)賦予合適的初始狀態(tài)值，增加最終解的質(zhì)量；

(2)改進(jìn)溫度更新的方式，加快收斂速度，避免陷入局部最優(yōu)解；

(3)改進(jìn)狀態(tài)產(chǎn)生函數(shù)，避免遺漏最優(yōu)解；

(4)采用并行數(shù)據(jù)結(jié)構(gòu)，加快運(yùn)算速度；

(5)設(shè)計(jì)精確的算法終止規(guī)則，提高解的質(zhì)量和收斂速度.

圖1　貪心算法的計(jì)算過(guò)程Fig.1　The calculation process of greedy algorithm

1.2改進(jìn)的貪心算法

貪心算法是指在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇,它對(duì)范圍相當(dāng)廣泛的許多問(wèn)題都能產(chǎn)生整體最優(yōu)解或者整體最優(yōu)解的近似解.貪心算法求解TSP問(wèn)題的計(jì)算過(guò)程如圖1所示.

算法訪問(wèn)節(jié)點(diǎn)的順序就是TSP的最終解，但由于算法本身的缺點(diǎn)，最終解并不是最優(yōu)解.因此，提出采用隨機(jī)函數(shù)產(chǎn)生1~N的正整數(shù)M(N為城市的個(gè)數(shù))來(lái)隨機(jī)開(kāi)始第一次訪問(wèn)的節(jié)點(diǎn)，改進(jìn)后的算法思想如下：

(1)首先構(gòu)造城市距離的對(duì)稱(chēng)矩陣A，任意節(jié)點(diǎn)到自身的距離為無(wú)窮大；

(2)隨機(jī)函數(shù)產(chǎn)生1~N的正整數(shù)M(N為城市的個(gè)數(shù)，1≤M≤N)；

(3)先在第M行找到最小項(xiàng)a[M][j],跳到第j行；

(4)再找到最小值a[j][k],跳到第k行進(jìn)行查找；

(5)遍歷全部節(jié)點(diǎn)；

(6)算法結(jié)束.

1.3改進(jìn)的模擬退火算法

基于傳統(tǒng)模擬退火算法的不足，提出了改進(jìn)的模擬退火算法.在改進(jìn)的模擬退火算法中，采用雙閾值iLK,oLK,lam，istd,ostd(iLK為內(nèi)循環(huán)最大迭代次數(shù)，oLK為外循環(huán)最大迭代次數(shù)，lam為溫度衰減系數(shù)，istd為內(nèi)循環(huán)結(jié)束標(biāo)準(zhǔn)，ostd為外循環(huán)結(jié)束標(biāo)準(zhǔn))來(lái)確保算法的精確性，采用雙存儲(chǔ)ilen,olen(ilen為內(nèi)循環(huán)保存的目標(biāo)函數(shù)值的個(gè)數(shù)，olen為外循環(huán)保存的目標(biāo)函數(shù)值的個(gè)數(shù))來(lái)保證算法在迭代過(guò)程中不會(huì)丟失最優(yōu)解，采取新的退火方案T=T0exp(-lam(oLK-1)-1/2)，使算法更適應(yīng)TSP問(wèn)題的求解，其中T0為初始溫度.

1.4貪心模擬退火算法

根據(jù)前文的分析，提出了結(jié)合貪心算法和模擬退火算法的貪心模擬退火算法，其思想是先采用改進(jìn)的貪心算法產(chǎn)生初始狀態(tài)解，然后運(yùn)用改進(jìn)的模擬退火算法求解.具體的算法步驟如下：

(1)令i=0,初始化參數(shù)T0,iLK,oLK,lam,istd,ostd,ilen,olen；

(2)調(diào)用改進(jìn)的貪心算法產(chǎn)生初始訪問(wèn)序列x(0)；

(3)由x(1)隨機(jī)擾動(dòng)產(chǎn)生一個(gè)新的候選解x(i+1)；

(4)計(jì)算Δf=f(x(i+1))-f(x(i))；

(6)如果Δf≤0，接受新解；否則給出一個(gè)服從均勻分布0~1的隨機(jī)數(shù)r，如果exp(-Δf)>r，則接受新解；

(7)i=i+1,如果i≤L，返回到第(3)步；

(8)令i=0，根據(jù)溫度衰減方案使T變小，T=T0exp(-lam(oLK-1)-1/2)；

(9)如果不滿(mǎn)足終止條件，返回到第(3)步，否則終止算法；

(10)當(dāng)前解為最優(yōu)解輸出.

2仿真實(shí)驗(yàn)

采用普通辦公用計(jì)算機(jī)，處理器為InterCorei5 2.67GHz,內(nèi)存為2G，操作系統(tǒng)為32位Windows7，采用Matlab7.1編程實(shí)現(xiàn).實(shí)驗(yàn)數(shù)據(jù)來(lái)自國(guó)際通用的TSP實(shí)例庫(kù)TSPLIB，選取3組數(shù)據(jù),分別為31cities,70cities和100cities.每組數(shù)據(jù)均迭代100次，記錄每次的TSP實(shí)驗(yàn)結(jié)果.

表1　31/70/100 cities結(jié)果比較

表1中優(yōu)化比的計(jì)算公式為

表示貪心模擬退火算法比傳統(tǒng)模擬退火算法有效的比率.

如表1所示，在同樣的城市規(guī)模中，貪心模擬退火算法比傳統(tǒng)的模擬退火算法要好，并且隨著組合優(yōu)化規(guī)模的增大，貪心模擬退火算法比傳統(tǒng)的模擬退火算法具有更大的優(yōu)勢(shì).圖2是100 cities在傳統(tǒng)模擬退火算法和貪心模擬退火算法下最優(yōu)路徑的比較.通過(guò)比較可以直觀地發(fā)現(xiàn)貪心模擬退火算法的優(yōu)勢(shì).

圖2　100 cities傳統(tǒng)SA與貪心模擬退火算法最優(yōu)路徑Fig.2　100 cities the optimal path of traditional SA and greedy simulated annealing algorithm

圖3　100 cities傳統(tǒng)SA與貪心模擬退火算法收斂曲線Fig.3　100 cities convergence curve of traditionalSA and greedy simulated annealing algorithm

圖3是實(shí)驗(yàn)數(shù)據(jù)100 cities在傳統(tǒng)的模擬退火算法和改進(jìn)后的貪心模擬退火算法中的收斂曲線圖.通過(guò)比較可以看出，改進(jìn)后的算法在大約40次退火實(shí)驗(yàn)后結(jié)果就趨于穩(wěn)定，而傳統(tǒng)的算法則需要大約80次的退火實(shí)驗(yàn)才會(huì)趨于穩(wěn)定后.通過(guò)觀察可以發(fā)現(xiàn)，改進(jìn)后的貪心模擬退火算法比傳統(tǒng)的模擬退火算法有較快的收斂速度.

3結(jié)語(yǔ)

改進(jìn)的貪心算法和傳統(tǒng)的模擬退火算法相結(jié)合后提出的貪心模擬退火算法比貪心算法和傳統(tǒng)的模擬退火算法更有效.在TSP問(wèn)題中，貪心模擬退火算法可以得出接近最優(yōu)解的解.另外,通過(guò)3組實(shí)驗(yàn)可以推斷出貪心模擬退火算法比較適合規(guī)模較大的TSP優(yōu)化組合問(wèn)題.

參考文獻(xiàn)：

[1]蘭兆青,白艷萍,李飛.遺傳算法解TSP問(wèn)題的程序設(shè)計(jì)[J].太原師范學(xué)院學(xué)報(bào):自然科學(xué)版,2008(2):30-32.

[2]Ingber L,Rosen B.Genetic algorithms and very fast simulated annealing:a comparison[J].Mathematical Computer Modeling,1992,16(11):87-100.

[3]盧冰,王夢(mèng)蘭.一種改進(jìn)螞蟻算法在TSP問(wèn)題中的應(yīng)用[J].科技創(chuàng)業(yè)月刊,2010(6):128-129.

[4]王艷春,王新.基于神經(jīng)網(wǎng)絡(luò)求解TSP問(wèn)題的研究[J].齊齊哈爾大學(xué)學(xué)報(bào),2006(1):65-67.

[5]杜宗宗,劉國(guó)棟.基于混合遺傳模擬退火算法求解TSP問(wèn)題[J].計(jì)算機(jī)工程與應(yīng)用,2010(29):40-42.

[6]Kirkpatrick S,Gelartt C D,Vecchi M P.Optimization by simulated annealing [J].Science,1983,220(11):650-671.

Solving TSP problem using greedy simulated annealing algorithm

LI Jinxu1，HUANG Yueyue2

(1.DepartmentofInformationandNetwork,ZhengzhouKindergartenTeachers′College,Zhengzhou450001,China;

2.InternationalSchool,YellowRiverInstituteofScienceandTechnology,Zhengzhou450001,China)

Abstract:By analyzing the shortage of the traditional simulated annealing algorithm and the feasible improvement scheme, we proposed a greedy simulated annealing algorithm for solving TSP problem. The new algorithm combines the improved simulated annealing algorithm and the improved greedy algorithm, and improved the quality of the solution of the algorithm. Experimental test results show that the new algorithm has better solution than that of traditional simulated annealing algorithm.

Key words:simulated annealing algorithm; greedy algorithm; TSP; combinatorial optimization

作者簡(jiǎn)介：李金旭(1986-)，男，河南鄭州人，助教，碩士，主要從事人工智能與智能算法方面的研究.

收稿日期：2014-12-02

中圖分類(lèi)號(hào)：TP312

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1674-330X(2015)01-0066-04