旅行商問題(TSP)的改進模擬退火算法

1、旅行商問題(TSP)的改進模擬退火算法AnimprovedSimulatedAnnealingAlgorithmtoTSP摘要：旅行商問題是一種典型的求解多局部最優(yōu)的最優(yōu)化問題：有n個城市，一個旅行者從其中的一個城市出發(fā)，經(jīng)過所有的城市一次并返回出發(fā)的城市，求最短的路線。在使用普通的模擬退火算法解決TSP時，一般采用2-opt算法來產(chǎn)生新的解空間，導(dǎo)致算法效率低下。本文提出引入多種算子(如：移位，交換，倒置等等)來產(chǎn)生新解空間。算法的分析和測試結(jié)果表明，改進后的模擬退火算法效率明顯提高，在收斂性和運算結(jié)果上都有較大的進步。關(guān)鍵字：模擬退火；旅行商問題；多種算子；最優(yōu)化問題Abstract:Tr

2、avellingSalesmanProblem(TSP)isatypicalcombinatorialoptimisationproblem.Themainideaoftheproblemisthatgivenanumberofcitiesandthedistancesbetweeneachcityandtriestogettheshortestpaththatvisitseachcityexactlyonceandbacktothestartingpoint.Inmostsimulatedannealingalgorithms,2-optalgorithmisusedtogeneratene

3、wpath,whichgivesalowefficiency.Thisreportintroducesmultiplearithmeticoperators(e.g.transportation,switchingandinversion).Theresultshowsthattheimprovedsimulatedannealingalgorithmisquitemoreefficientthattheformerone.Keywords:SimulatedAnnealing;TSP;multiplearithmeticoperator;combinatorialoptimisation0引

4、言旅行商問題(TSP)是一種典型的組合最優(yōu)化問題，計算途經(jīng)n個城市的最短距離。對于城市數(shù)目為n的地圖，共有n!種不同的路徑。城市越多，可能的路徑也越多。而且路徑的增加速度非?？烨沂欠蔷€形的。當(dāng)n很大時，去嘗試每一種可能的路徑是不可能的，所以需要設(shè)計一個有效的算法去尋找最短的路徑。模擬退火算法是一種基于MonteCarlo迭代求解法的啟發(fā)式隨機搜索算法。模擬退火算法具有漸進收斂性，是收斂于全局最優(yōu)解的全局優(yōu)化算法。本文著重討論如何提高模擬退火算法的收斂速度和效率，在短時間內(nèi)可以找出最佳路徑。旅行商問題簡介旅行商問題(TravelingSalesmanProblem,TSP),也稱為貨郎擔(dān)問題,由

5、愛爾蘭數(shù)學(xué)家SirWilliamRowanHamilton和英國數(shù)學(xué)家ThomasPenyngtonKirkman在19世紀(jì)提出的數(shù)學(xué)問題，它是指給定n個城市并給出每兩個城市之間的距離,旅行商必須以最短路徑訪問所有的城市一次且僅一次，并回到原出發(fā)地，現(xiàn)已證明它屬于NP難題。歷史上的第一個正式用來解決TSP問題的算法誕生于1954年,它被用來計算49個城市的TSP問題。到現(xiàn)在為止，運用目前最先進的計算機技術(shù)可解決找出游歷24,978個城市的TSP問題。由于該問題的描述簡單,而其實際模型在印刷電路板的鉆孔路線方案、連鎖店的貨物配送、網(wǎng)絡(luò)布線等優(yōu)化問題中又有著廣泛的應(yīng)用,故長期以來一直吸引著國內(nèi)外許

6、多研究人員進行研究,他們嘗試著用各種算法來求解TSP問題,歸納起來有2:近似解法、局部搜索法、神經(jīng)網(wǎng)絡(luò)、遺傳算法、克隆算法、模擬退火算法、混合遺傳算法等。模擬退火算法介紹模擬退火算法(SimulatedAnnealing)最早見于IBM托馬斯.J.沃森研究中心的S.Kirkpatrick等人的文章,他們在對組合優(yōu)化進行研究后,根據(jù)迭代改進的思想提出了“模擬退火算法”,模擬退火算法具有很強的局部搜索能力1。模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其緩慢降溫(即退火)，使之達(dá)到能量最低點。反之，如果急速降溫(即淬火)則不能達(dá)到最低點。加溫時，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，

7、而緩慢降溫時粒子漸趨有序，在每個溫度上都達(dá)到平衡態(tài)，最后在常溫時達(dá)到基態(tài)，內(nèi)能減為最小。根據(jù)Metropolis準(zhǔn)則，粒子在溫度T時趨于平衡的概率為exp(-E/(kT),其中E為溫度T時的內(nèi)能，E為其改變量，k為Boltzman常數(shù)4。用固體退火模擬組合優(yōu)化問題，將內(nèi)能E模擬為目標(biāo)函數(shù)值f,溫度T演化成控制參數(shù)t,即得到解組合優(yōu)化問題的模擬退火算法：由初始解i和控制參數(shù)初值t開始，對當(dāng)前解重復(fù)產(chǎn)生“新解一計算目標(biāo)函數(shù)差一接受或舍棄”的迭代，并逐步衰減t值，算法終止時的當(dāng)前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機搜索過程。退火過程由冷卻進度表(CoolingSchedu

8、le)控制，包括控制參數(shù)的初值t及其衰減因子a、每個t值時的迭代次數(shù)L和停止條件c。所以我們可以通過上面的思想寫出解決TSP問題的模擬退火算法。步驟如下3：初始化：初始溫度T(充分大)，初始解狀態(tài)s(隨機選取一條TSP路線，算出走完此路線的長度Cost(s)作為評價函數(shù)，這是算法迭代的起點)，每個T值的迭代次數(shù)L；對k=1至k=L做第(3)至第6步；產(chǎn)生新解s(般利用2-opt算法來產(chǎn)生新的路徑)；計算增量Cost=Cost(s)-Cost(s),其中Cost(s)為評價函數(shù)；若t0則接受s作為新的當(dāng)前解，否則以概率exp(-1/T)接受s作為新當(dāng)前解；如果滿足終止條件則輸出當(dāng)前解作為最優(yōu)解，

9、結(jié)束程序。終止條件通常取為連續(xù)若干個新解都沒有被接受時終止算法；T逐漸減少，且T趨于0，然后轉(zhuǎn)第2步運算。模擬退火算法在TSP上的應(yīng)用31基于2-OPT的普通模擬退火算法從上一部分可知，用2-OPT算法來產(chǎn)生新的路徑，2-OPT算法的主要思想是在所有城市中隨機選取兩個城市，然后將兩個城市在路徑中的序列交換位置產(chǎn)生新的路徑。如下例：解空間S是遍訪每個城市恰好一次的所有路經(jīng)，解可以表示為w1,w2,wn，w1,wn是1,2,n的一個排列，表明w1城市出發(fā)，依次經(jīng)過w2,wn城市，再返回w1城市。新路徑的產(chǎn)生：隨機產(chǎn)生1和n之間的兩相異數(shù)k和m，不妨假設(shè)km，則將原路徑(wl,w2,，wk,wk+l

10、,wm,wm+1,wn)變?yōu)樾侣窂剑?w1,w2,wm,wk+1,wk,wm+1,wn)。32改進的模擬退火算法這種改進的模擬退火算法的改進之處在于引入多種算子(如：移位，交換，倒置等等)來產(chǎn)生新解空間。并且以一定的概率來決定運用哪種算子來產(chǎn)生新的解空間。在算子中，倒置的主要思想是：隨機在路徑中選出兩個城市，然后將兩個城市之間的城市順序完全倒置得出新的路徑。如上例：產(chǎn)生兩相異數(shù)k和m(假設(shè)km),則將原路徑(w1,w2,wk-1,wk,wk+1,wm-1,wm,wm+1,wn)變?yōu)樾侣窂剑?w1,w2,wk-1,wm,wm-1,wk+1,wk,wm+1,wn)。移位的主要思想是隨機選出兩城市，

11、將兩城市之間的城市統(tǒng)一向右移一位。例如：隨機選出城市wk和wm(假設(shè)km),則將原路徑(w1,w2,wk-1,wk,wk+1,wm-1,wm,wm+1,wm+2,wn)變?yōu)樾侣窂剑?w1,w2,wk-1,wm+1,wk,wk+1,wm-1,wm,wm+2,wn)。交換的思想與2-OPT算法相同，隨機產(chǎn)生兩城市并將兩城市交換來產(chǎn)生新的解空間。改進算法與普通算法的比較41實驗器材及實驗數(shù)據(jù)用來測試算法性能的TSP文件berlin52.tsp是一張具有52個城市的TSP地圖，可以從TSP問題的數(shù)據(jù)庫中下載得到。下載TSP測試文件的地址為： HYPERLINK http:/www.iwr.uni-he

12、idelberg.de/groups/comopt/software/TSPLIB95/tsp/ http:/www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/測試的硬件平臺主要配置為PentiumM1.6Ghz處理器,333MhzDDR256M內(nèi)存，測試算法的軟件選用Matlab7.0。4.2實驗結(jié)果為準(zhǔn)確比較兩算法的效率，算法中其他的參數(shù)必須相同，由于算法要求初始溫度必須充分大，所以在兩算法中我們設(shè)置初始溫度都為290000，降溫速率都為0.95，迭代次數(shù)均為1500次。在所有參數(shù)相同的情況下，用兩種算法得到的結(jié)果分

13、別為：2-OPT模擬退火算法：總路線長度為8868.2，運算時間為23.11秒。改進的模擬退火算法：總路線長度為7746.9,運算時間為3.29秒。圖一比較了用兩種算法畫出的解決Berlin52.tsp的路線圖可以看出在相同參數(shù)圖二比較了兩種算法的收斂性，可以看出：雖然在一開始的收斂速度上2-OPT與改進后的算法相近，但是隨著迭代次數(shù)的增加，改進后的算法的收斂性明顯好與2-OPT模擬退火算法。并且改進后的模擬退火算法消耗的時間少于2-OPT模擬退火算法。軸：迭代次數(shù).I:苧改送的模擬退火算法|-|IIIII0123+52-opt模擬退災(zāi)算法圖二：兩種算法收斂性的比較43實驗結(jié)果分析雖然兩算法都

14、可以通過加大迭代次數(shù)來得到Berlin52.tsp的最優(yōu)解。但是從上面的結(jié)果來看，改進后的算法在運算效率，收斂性和運算時間上都優(yōu)于2-OPT的模擬退火算法。并且我們發(fā)現(xiàn)，在改進的算法中調(diào)整使用移位，交換，倒置的概率對算法的效率也有影響。經(jīng)過多次實驗，我們總結(jié)出：在改進的算法中，以50%的概率選擇位移，25%的概率選擇置換和25%的概率選擇倒置來產(chǎn)生新解空間可以使算法的效果比較好。通過多次實驗及以上的實驗數(shù)據(jù)，我們可以得出結(jié)論：用增加產(chǎn)生新解空間的隨機性的方法改進的模擬退火算法確實可以增進模擬退火算法解決TSP問題的效率。結(jié)束語本文作者的創(chuàng)新點在于：改進普通的模擬退火算法解決TSP問題，通過增加產(chǎn)生新解空間的隨機性的方法來改進模擬退火算法，從而求得問題的最優(yōu)解。改進模擬退火算法解決TSP問題在對鉆孔路線方案、連鎖店的貨物配送、網(wǎng)絡(luò)布線，鐵路網(wǎng)優(yōu)化等問題中有著廣泛的應(yīng)用，所以改進和研究解決TSP問題算法對實際的工業(yè)生產(chǎn)是有重要意義的。實驗結(jié)果表明，該算法性能良好。另外，初始溫度、衰減因子和馬爾可夫鏈長度等參數(shù)的控制，還需要做進一步研究。今后應(yīng)在更先進的硬件平臺的基礎(chǔ)上嘗試較大的TSP地圖（