蟻群算法與模擬退火算法對旅游路線問題的探究(附matlab程序)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上蟻群算法與模擬退火算法對旅游路線問題的探究張煊 張恒偉 徐曉輝摘要： 本文針對旅游中國34個城市的路線最優(yōu)化問題，收集各城市經(jīng)緯度坐標和實際城市間火車票與飛機票，在此大量數(shù)據(jù)的基礎之上，采用蟻群算法和模擬退火算法進行啟發(fā)式搜索，就實際問題給出了合理最優(yōu)的旅行路線和訂票方案。按照問題要求，首先建立了城市旅行網(wǎng)絡，同時對網(wǎng)絡圖賦權，對數(shù)據(jù)進行了收集和簡單的處理，得到了經(jīng)緯度坐標、火車票矩陣、飛機票矩陣及其對應的時間矩陣。對于問題（1），我們根據(jù)各城市經(jīng)緯度坐標，利用經(jīng)緯度知識和球體的幾何知識，計算出各城市之間的距離，得到各個城市之間的距離矩陣，分別采用蟻群算法與模擬退火算

2、法搜索，將結果比較得到最短旅行路線為：哈爾濱長春沈陽天津北京呼和浩特太原石家莊濟南鄭州西安銀川蘭州西寧烏魯木齊拉薩昆明成都重慶貴陽南寧海口廣州澳門香港臺北福州南昌長沙武漢合肥南京杭州上海哈爾濱，旅行路線總長為1.6013萬千米。在問題（2）的求解中，首先用城市旅行網(wǎng)絡的車費價格代替城市之間距離，重新賦權，在模型的基礎上，利用最小費用矩陣，采用蟻群算法和模擬退火算法搜索，比較計算結果得到最經(jīng)濟的訂票方案為：哈爾濱1489長春1416天津1416濟南1462南京1462上海1374杭州2002福州1216南昌K162合肥D3024武漢MU517臺北CZ6997澳門MU2790西寧1282拉薩K91

3、8蘭州1043烏魯木齊1043西安2612鄭州T201?？赥201廣州T99香港T98長沙2514南寧2058昆明1236貴陽1248重慶1271成都1718銀川2636呼和浩特2464太原2610石家莊4410北京1138沈陽1122哈爾濱，費用7212元。針對問題（3）中所述的經(jīng)濟、省時又方便的原則，我們建立了旅行路線評價指標Q，綜合考慮各方面因素，并以人為本修正指標參數(shù)，最終得到指標表達式Q=0.6M+8t，并以此為權，處理數(shù)據(jù)得到指標矩陣，在模型的基礎上得到最優(yōu)旅行路線：哈爾濱2096長春1490天津1394濟南1085鄭州1150西安1085蘭州T27拉薩T21西寧MU2790澳門C

4、Z6997臺北CA4912武漢D3024合肥D3020南京D5401上海D5655杭州D3107福州1216南昌T147長沙T98香港T99廣州T201海口GS7441南寧2058昆明1236貴陽K9518重慶D5111成都K452烏魯木齊SC4912銀川1718呼和浩特2462太原2610石家莊4408北京D25沈陽K19哈爾濱，Q值為6532,總費用為8092元。本文綜合采用了蟻群算法和模擬退火算法，計算得到的最優(yōu)路線能滿足問題的需要。就周先生的外出旅行提供了參考方案，搜集了大量的數(shù)據(jù)，緊密的與實際相結合，得到的方案可行性強，能很好地解決旅行方案的優(yōu)化問題及類似的組合優(yōu)化問題，并可以廣泛的

5、應用于其它領域。關鍵詞： 模擬退火算法 蟻群算法 旅行路線評價指標 1.問題重述計算從哈爾濱走遍全國34個城市的最短距離，設計出合理算法規(guī)劃出不同約束條件下的不同最優(yōu)方案：1首先在不考慮外部因素的情況下，利用地球的經(jīng)緯度，計算各個城市之間距離，建立數(shù)學模型，并規(guī)劃出最優(yōu)游遍34座城市的最短路線。2若2010年5月1日從哈爾濱市出發(fā)，在每個城市停留3天，利用航空、鐵路（快車臥鋪或動車）交通工具，考慮到車次、航班情況，設計出游遍34座城市的最經(jīng)濟的旅行互聯(lián)網(wǎng)上訂票方案。3在綜合實際情況下考慮省錢、省時又方便，設定出相應的評價準則和指標，建立相應改進后的數(shù)學模型，并在此前提下修訂上述兩種方案。4對本

6、文所用到的算法作復雜性、可行性及誤差分析。5針對旅行商問題提出對自己所采用的算法的理解及評價。2 模型假設與符號說明 2.1 模型假設（1） 近期內(nèi)火車票視為定值；（2） 飛機票的取值均取自打折后的；（3） 飛機票均取自近期內(nèi)的；（4） 估算城市之間的距離時忽略地形如丘陵盆地等自然因素對估算結果的影響； 2.2 符號說明A、B兩市之間的距離加權圖定點（城市）的集合賦權邊的集合緯度經(jīng)度第i個城市到第j個城市的距離i個城市構成的環(huán)路矩陣第k時刻的溫度（k=1,2, ，m）a溫度控制系數(shù)L退火算法內(nèi)循環(huán)循環(huán)次數(shù) （k=1，2，m ）禁忌表，記錄螞蟻k當前已走過的城市表示城市i轉移到城市j的期望程度m

7、蟻群算法中，螞蟻總數(shù)表示t時刻在路徑（i，j）連線上殘留的信息量蟻群算法的循環(huán)次數(shù)第k只螞蟻在本次循環(huán)中所走路徑的總長度M旅行費用t旅行時間Q旅行評價指標3. 問題分析 該問題是一個旅行路徑的組合優(yōu)化問題，其形式化描述為：用節(jié)點來表示34個城市,連接兩節(jié)點之間的邊表示旅行路線,并將路線的長度等屬性表示為該邊的權值,那么就可以把城市旅行網(wǎng)絡抽象為一個帶權有向圖。給定一個帶權有向圖G為二元組G=(V,E),其中V是包含n個節(jié)點的集合,E是包含h條邊(弧段)的集合,（i, j）是E 中從節(jié)點i 至j 的邊,是邊（i,j）的非負權值。設S,T 分別為 V中的起始節(jié)點和目標節(jié)點,則最優(yōu)路徑問題就是指在帶

8、權有向圖G中,尋找從指定起始節(jié)點到目標節(jié)點的一條具有最小權值總和的路徑。，則最優(yōu)路徑問題就是指在帶權有向圖G中,尋找從指定起始節(jié)點到目標節(jié)點的一條具有最小權值總和的路徑。在不同需求條件的影響下，城市旅行路線網(wǎng)不僅有道路路線等物理屬性,同時也具有路線長度、旅行時間、車票價格等各種其它邏輯屬性，因而改變著旅行的最優(yōu)路線。問題（1）中，我們根據(jù)實際的地理位置經(jīng)緯度，利用幾何知識計算出每兩個城市之間的距離，并以距離為權，進而建立模型，求解。設定出游遍34座城市的最優(yōu)旅行路線。問題（2）中，設定方案針對各個城市之間交通條件的不同，考慮實際情況，通過互聯(lián)網(wǎng)上的票務查詢得到近期城市間的火車票價與飛機票價，并

9、以價格為權，建立相應數(shù)學模型得到有關費用最低的最優(yōu)旅行路線。問題（3）中，在問題（1）、（2）分析的基礎之上，建立經(jīng)濟、省時又方便的評價準則，提出自己觀點，以此修訂最優(yōu)旅行方案。問題（4）中，對所用算法進行復雜性、可行性及誤差分析討論；問題（5）中，關于旅行商問題提出求解所采用的相應算法的理解及評價。 本問題屬于旅行商（TSP）的一類問題，可以采用模擬退火算法和蟻群算法來對數(shù)據(jù)進行搜索解決，得到合理的優(yōu)化路線。4.模型的建立與求解4.1 模型的建立與求解根據(jù)問題分析，我們首先創(chuàng)建城市旅行網(wǎng)絡圖，給定加權圖，其中表示頂點（城市）的集合表示為：。為賦權邊(表示兩個城市間的距離)的集合，即兩地間距離

10、（km）。表示為。Hamilton路徑圖可以表示為：；其中 ，且對，有。記為中所有Hamilton回路的集合，定義；目的是要尋找一條最短的Hamilton回路， 使得。分別利用蟻群算法和模擬退火式算法對所得數(shù)據(jù)進行搜索計算。4.1.1 城市間距離的估算34個城市經(jīng)緯度具體數(shù)值（如表1）所示：表1 各個城市經(jīng)緯度編號省會緯度(北緯)經(jīng)度(東經(jīng))1哈爾濱2烏魯木齊3長春4沈陽5呼和浩特6北京7天津8銀川9石家莊10太原11濟南12西寧13蘭州14鄭州15西安16南京17合肥18上海19武漢20成都21杭州22重慶23拉薩24南昌25長沙26貴陽27福州28昆明29臺北30廣州31南寧32香港33澳

11、門34?？赟（南極）首子午線緯線赤道經(jīng)線N(北極)圖1. 地球幾何解析圖首先把地球看成是標準球體，球心為點O，把任意兩個城市看成是A 、B兩點，則地球上的兩個點A、 B在赤道面上的投影點分別為、 。假設地球平均半徑為R，A點北緯，東經(jīng)，B點北緯，東經(jīng)，基于球體幾何知識因此可以得到：， （1） 投影下來的 = （2）OZYXBA1BA圖2 地球經(jīng)緯度利用余弦定理可得到： （3） （4）利用勾股定理得到： （5）將（3）、（4）代入（5）式中：= （6）令AOB為，同樣利用余弦定理可得到： （7）化簡得： （8）則地球上兩點AB之間距離即AB弧長為 （9）即為兩地之間的實際路徑。因此我們根據(jù)表一中

12、所示的各城市經(jīng)緯度經(jīng)過計算得到各城市間的距離（詳見附錄1）。4.1.2 蟻群算法建立模型蟻群覓食的過程與此組合優(yōu)化問題的求解相似，找到一條只經(jīng)過每個城市一次且回到起點的、最短路徑的回路。設城市i和j之間的距離為。求解中，假設蟻群算法中的每只螞蟻是具有下列特征的簡單智能體。（1）每次周游，每只螞蟻在其經(jīng)過的支路（i，j）上都留下信息素。（2）螞蟻選擇城市的概率與城市之間的距離和當前連接支路上所包含的信息素余量有關。（3）為了強制螞蟻進行合法的周游，知道一次周游完成后，才允許螞蟻游走已訪問過的城市（這可由禁忌表來控制）。蟻群算法中的基本變量和常數(shù)有：m，蟻群中螞蟻的總數(shù)；n，TSP問題中城市的個數(shù)

13、；為城市i和j之間的距離，其中；，表示t時刻在路徑（i，j）連線上殘留的信息量。在初始時刻各條路徑上信息量相等，并設=const（const為常數(shù)）。 螞蟻k（k=1，2，m ）在運動過程中，根據(jù)各條路徑上的信息量決定其轉移方向。表示在t時刻螞蟻k由城市i轉移到城市j的狀態(tài)轉移概率，根據(jù)各條路徑上殘留的信息量及路徑的啟發(fā)信息來計算的，如（10）所示。表示螞蟻在選擇路徑時會盡量選擇離自己距離較近且信息素濃度較大的方向。= （10） 式中，表示在t時刻螞蟻k下一步允許選擇的城市（即還沒有訪問的城市）； （k=1，2，m ）表示禁忌表，記錄螞蟻k當前已走過的城市； 信息啟發(fā)式因子，反映了蟻群在運動過

14、程中所殘留信息量相對重要程度； 表示期望啟發(fā)式因子，反應了期望值的相對重要程度； 表示城市i轉移到城市j的期望程度，具體計算公式如下 （11）對螞蟻k而言，越小，則越大，也就越大。 為了避免殘留信息素過多而淹沒啟發(fā)信息，在每只螞蟻走完一步或者完成對所有n個城市的遍歷后，要對殘留信息素進行更新處理。（t+n）時刻在路徑（i，j）上信息量可按式（3）和式（4）所示的規(guī)則進行調(diào)整。 （12） （13） 式中，表示信息素揮發(fā)系數(shù)。模仿人類記憶特點，舊的信息將逐步忘卻、削弱。為了防止信息的無限積累，的取值范圍為0，1），用1表示信息的殘留系數(shù)。 表示本次循環(huán)中路徑（i，j）上的信息量增量，初始時刻。表示

15、第k只螞蟻在本次循環(huán)中留在路徑（i，j）上的信息量。根據(jù)信息素更新策略 （14）表示第k只螞蟻在本次循環(huán)中所走路徑的總長度。這里的基本蟻群算法具體算法步驟為：第1步：初始化參數(shù)。時間t=0，循環(huán)次數(shù)，設置最大循環(huán)次數(shù)，令路徑（i，j）的初始化信息量=const，初始時刻。第2步：將m只螞蟻隨機放在n個城市上。第3步：循環(huán)次數(shù)。第4步：令螞蟻禁忌表索引號k=1。第5步：k=k+1。 第6步：根據(jù)狀態(tài)轉移概率計算螞蟻選擇城市j的概率，。第7步：選擇最大狀態(tài)轉移概率城市，將螞蟻移動，把該城市計入禁忌表中。第8步：若沒有訪問完集合C中的所有城市，即，跳轉至第5步；否則，轉第9步。第9步：根據(jù)式（13）

16、和式（14）更新每條路徑上的信息量。第10步：若滿足結束條件，循環(huán)結束輸出計算結果；否則清空禁忌表并跳轉到第3步。YNNY開始參數(shù)初始化，=0； k=1k=k+1計算狀態(tài)轉移概率，選擇下一個轉移城市修改禁忌表km更新每條路徑上的信息量滿足條件？輸出結果結束圖（6） 基本蟻群算法的算法框圖根據(jù)以上算法我們利用matlab軟件編程（程序見附錄5），得到最優(yōu)旅行路徑為哈爾濱長春沈陽天津北京呼和浩特太原石家莊濟南鄭州西安銀川蘭州西寧烏魯木齊拉薩昆明成都重慶貴陽南寧?？趶V州澳門香港臺北福州南昌長沙武漢合肥南京杭州上海哈爾濱，旅行路線總長為1.6013萬千米。圖 8 蟻群算法的最優(yōu)路線圖圖 7 蟻群算法的

17、路徑演化過程圖413模擬退火算法模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其緩慢降溫（即退火），使之達到能量最低點。反之，如果急速降溫（即淬火）則不能達到最低點。加溫時，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而緩慢降溫時粒子漸趨有序，在每個溫度上都達到平衡態(tài)，最后在常溫時達到基態(tài)，內(nèi)能減為最小。根據(jù)Metropolis準則，粒子在溫度T時趨于平衡的概率為，其中E為溫度T時的內(nèi)能，e為其改變量，b為Boltzman常數(shù)。應用到本問題中，優(yōu)化問題的一條旅行途徑route及目標函數(shù)f（route）分別可以看成物體的一個狀態(tài)和物體的能量函數(shù)，而其最優(yōu)解就是最低能量狀態(tài)。因而對應的設定的

18、初始溫度、基于Metropolis準則的搜索和控制溫度參數(shù)t控制的下降過程也就相當于物理退火過程的加溫、等溫和冷卻過程。等溫的過程中，我們采用Metropolis準則鄰域搜索移動方法，也就是說根據(jù)一定概率決定當前解是否移向新解。由初始解由初始假設路徑和控制參數(shù)初值t開始，對當前解重復產(chǎn)生“新解計算目標函數(shù)差接受或舍棄”的迭代，并逐步衰減t的值，算法終止時的當前解即為所得近似最優(yōu)解，這是基于Metropolis的一種啟發(fā)式隨機搜索過程。退火過程由冷卻進度表控制，包括控制參數(shù)的初值t及其衰減因子，每個t值時的迭代次數(shù)L和控制溫度系數(shù)a，因而我們所以我們可以通過上面的思想寫出解決最短路徑的模擬退火算

19、法。算法步驟如下：(1)初始化：初始溫度（充分大），初始解狀態(tài)（隨機選取一條旅行路線，算出走完此路線的長度作為目標函數(shù)，這是算法迭代的起點），每個T值的迭代次數(shù)L；(2)對k=1至k=L最第(3)至第(6)步;(3)產(chǎn)生新解 (利用矩陣翻轉來產(chǎn)生新的路徑)；(4)計算增量，其中為目標函數(shù)； (5)若則接受作為新的當前解，否則以概率exp（）接受作為新當前解；(6)如果滿足終止條件則輸出當前解作為最優(yōu)解，結束程序。終止條件通常取為連續(xù)若干個新解都沒有被接受時終止算法；(7)逐漸衰減，因而趨于最低溫度，然后轉第2步運算。如下圖所示（模擬退火算法框圖）：圖3 模擬退火算法框圖NYNYNN開始Exp（

20、）產(chǎn)生is，k=0，初始溫度設定，L=0產(chǎn)生js，LL+1計算i=jkk+1,降溫結束YY圖4 退火算法迭代運算圖根據(jù)以上算法我們利用matlab軟件編程（程序見附錄6），得到最優(yōu)旅行路徑為：哈爾濱長春沈陽北京天津濟南石家莊太原呼和浩特銀川西寧蘭州成都重慶西安鄭州武漢長沙南昌合肥南京上海杭州福州臺北香港澳門廣州海口南寧貴陽昆明拉薩烏魯木齊哈爾濱，旅行路線總長為1.6676萬千米。圖5 退火算法求得的最佳路徑圖4.2 模型的建立與求解首先，我們利用火車票網(wǎng)查詢到每兩個城市之間的最經(jīng)濟火車票矩陣與最經(jīng)濟的飛機票矩陣，將二者每個對應元素取最小組成新的費用矩陣。（如附錄2所示）對問題（2）所求的最優(yōu)訂

21、票方案在一定程度上相似于模型的所得的最短路徑，所以我們利用原有的旅行網(wǎng)絡的城市之間車費的邏輯屬性代替原有的城市之間的路線長度的物理屬性。所以在城市旅行網(wǎng)絡加權圖上，我們將賦權邊改為表示兩個城市間的最經(jīng)濟的旅行方式的費用，表示為：； Hamilton路徑可以表示為：；其中，且對，有。記為中所有Hamilton回路的集合，定義；目的是要尋找一條最短的Hamilton回路， 使得，即可得到旅行價格最經(jīng)濟的訂票方案。圖 9 退火算法總費用計算圖在模擬退火算法與蟻群算法的基礎上，我們利用新的矩陣計算得到最經(jīng)濟的旅行互聯(lián)網(wǎng)上的訂票方案，即為：哈爾濱1489長春1416天津1416濟南1462南京1462上

22、海1374杭州2002福州1216南昌K162合肥D3024武漢臺北澳門西寧1282拉薩K918蘭州1043烏魯木齊1043西安2612鄭州T201?？赥201廣州T99香港T98長沙2514南寧2058昆明1236貴陽1248重慶1271成都1718銀川2636呼和浩特2464太原2610石家莊4410北京1138沈陽1122哈爾濱，總費用為7212元。圖 10 問題2中最佳旅行路線圖4.3 模型 的建立與求解我們針對綜合省錢、省時又方便的條件，建立旅行評價指標。首先我們考慮方便的原則，在通過互聯(lián)網(wǎng)查詢每個車次航班時，優(yōu)先考慮直達火車與直飛航班，避免在旅途中可能出現(xiàn)的轉機與轉車，在最大限度上

23、確保旅途中的方便性原則。在此基礎上得到，城市之間的費用矩陣與旅行時間矩陣。然后在經(jīng)濟與省時的考慮下，我們假設出旅行指標Q=fM+qt （15）其中： f為費用啟發(fā)因子，反映了旅行中所花費的車費的相對重要程度； q為時間啟發(fā)因子，反映了旅行中所花費的時間的相對重要程度；根據(jù)部分實際的火車票的旅行時間和車票費用，我們得到下表：表 2 部分火車車票價格與行時對應表車次發(fā)站到站車票價錢歷時票價時間2008哈爾濱長春5402：4819.29K339北京沈陽北17209：1418.63T164上海蘭州41020：3919.85T253天津鄭州19509：0321.55T118西安南京26312：2421.

24、21由上表大致可以得到f與q比值約為20.0，即在一定程度上一個小時與20元是等價的。因而我們得到旅行評價指標=M+20t （16） 可理解為對于A城與B城的一種旅行方案，旅行指標越小，對于周先生來說，就越有價值，越可能選擇。假設一個退休的旅行者，由于收入的制約，旅行費用會相對重視一點，所以我們對原有的指標進行修訂，因而我們在原有的費用啟發(fā)因子與時間啟發(fā)因子的基礎上分別乘以0.6與0.4的平衡系數(shù)得到新的費用啟發(fā)因子與時間啟發(fā)因子，最終得到旅行評價指標QQ=0.6M+8t （17） 在旅行評價指標的基礎之上，我們將賦權邊改為表示兩市之間最小的旅行費用指標，并根據(jù)公式（17）得到指標矩陣(見附表

25、3），表示為：； Hamilton路徑可以表示為：；其中，且對，有。記為中所有Hamilton回路的集合，定義；目的是要尋找一條最短的Hamilton回路， 使得，求解結果即為旅行經(jīng)濟、省時又方便的訂票方案。 優(yōu)化方案為：哈爾濱2096長春1490天津1394濟南1085鄭州1150西安1085蘭州T27拉薩T21西寧MU2790澳門CZ6997臺北CA4912武漢D3024合肥D3020南京D5401上海D5655杭州D3107福州1216南昌T147長沙T98香港T99廣州T201海口GS7441南寧2058昆明1236貴陽K9518重慶D5111成都K452烏魯木齊SC4912銀川171

26、8呼和浩特2462太原2610石家莊4408北京D25沈陽K19哈爾濱，Q值為6532,總費用為8092元。圖 11 問題3中優(yōu)化旅行方案圖5模型的復雜性與可行性分析51 復雜度分析模型、模型、模型都是在蟻群算法與模擬退火算法的基礎上，全國34個城市旅行條件下建立的TSP問題的模型。假設此問題通過枚舉的辦法得到最優(yōu)解，但是將以大量的時間為代價，造成理論上的可解而實際上的不可解。本題中的可行路徑共有條，若以路經(jīng)比較為基本操作，則需次比較才可獲得最優(yōu)解，可能會需要上百年的時間。作為比較，以下我們對蟻群算法與模擬退火算法的復雜性進行分析。5.1.1蟻群算法的復雜度分析蟻群算法的復雜度分析是在理論上對

27、蟻群算法的算法效率的分析。對于上述模型中的蟻群算法，34個城市是TSP的規(guī)模，m為螞蟻的數(shù)量，為算法的循環(huán)次數(shù)，從蟻群的算法過程我們得到各環(huán)節(jié)的時間復雜度，如下表所示：Step內(nèi)容T(n)1初始化：set t=0；set =0set = const，=0；2設置螞蟻禁忌表 set s=0；for k= 1 to m do 置第k個螞蟻的起始城市到禁忌表O(m)3每只螞蟻單獨構造解循環(huán)計算直到禁忌表滿set s=s+1；for k= 1 to m do根據(jù)轉移概率選擇下一個城市將城市序號j加入禁忌表O()4解的評價和軌跡更新量的計算將第k只螞蟻在從禁忌表轉移到 計算第k只螞蟻在本次循環(huán)中的路徑長

28、度更新最優(yōu)路徑計算各條路徑的信息數(shù)反饋量O()5信息數(shù)軌跡濃度的更新計算各條路徑在下一輪循環(huán)前的信息數(shù)強度set t =t+n; set =+1O()6判定是否達到終止條件如果,且搜索出現(xiàn)停止現(xiàn)象 清空全部禁忌表 返回step2否則 輸出最短路徑結束O(nm)5.1.2模擬退火算法的復雜度分析模擬退火算法的復雜度分析是在理論上對模擬退火算法的算法效率的分析。對于上述模型中的模擬退火算法，34個城市是TSP的規(guī)模,每個t值時的迭代次數(shù)L是內(nèi)循環(huán)的循環(huán)次數(shù)，由降溫過程我們得到控溫循環(huán)次數(shù)，從模擬退火的算法過程我們得到各環(huán)節(jié)的時間復雜度，如下表所示：STEP內(nèi)容T（n）1初始化：設定初始溫度 ，終止

29、溫度;set k =0 =;O(1)2每個t值時的迭代次數(shù)L;for j=1 to L do；O(m)3翻轉矩陣得到新的路徑;計算;若則接受作為新的當前解，否則以概率exp（）接受作為新當前解；O(L)4判斷是否滿足內(nèi)循環(huán)終止條件L若滿足，則跳出循環(huán)；若不滿足，則回到step2;O()5降溫過程：=a； k=k+1;O() 6判斷是否達到終止溫度如果沒有滿足或搜索沒有出現(xiàn)停止現(xiàn)象返回step2否則 打印最短路徑 O()5.2 可行性分析旅行路線最優(yōu)化問題是一種TSP問題，不存在多項式時間內(nèi)找到最優(yōu)解。蟻群算法和模擬退火算法是解決組合優(yōu)化問題的有效方法，本文分別采用蟻群算法和模擬退火算法來解決3

30、4個城市的TSP問題。（1）模擬退火算法的可行性模擬退火算法用于解決組合優(yōu)化問題的想法，是基于物理中固體的退火過程與一般組合優(yōu)化問題間的相似性。在對固體物質(zhì)進行退火處理時，通常先將它加溫溶化，使其中的粒子可自由運動。然后隨著溫度的逐漸下降，粒子也逐漸形成了低能態(tài)的晶格。若在凝結點附近的溫度下降速度足夠慢，則固體物質(zhì)一定會形成最低能量的基態(tài)。對于組合優(yōu)化問題來說，它也有這樣類似的過程。組合優(yōu)化問題解空間中的每一點都代表一個解，不同的解有著不同的成本函數(shù)值，所謂優(yōu)化，就是在解空間中尋找成本函數(shù)值最小（或最大）的解。模擬退火算法是一種通用、高效、健壯、可行的擬物行隨機近似算法，并且可以叫容易地并行實

31、現(xiàn)以進一步提高運行效率，適合求解大規(guī)模組合優(yōu)化問題特別是NP完全問題（如本文中旅行路線最優(yōu)化問題），因此具有很大的實用價值。經(jīng)過計算可以發(fā)現(xiàn)模擬退火算法在瀕臨算法結束時，多次發(fā)現(xiàn)不錯的解，又多次接受惡化。所以，降低接受解的惡化的概率或許可以取得更好的解。但是，事實上也可能因為太早地陷入局部最優(yōu)而取得更壞的解。所以，模擬退火算法在搜索過程中需要精確調(diào)整接受退化結果的條件才可能取得較優(yōu)解。（2）蟻群算法的可行性蟻群算法是受自然界中真實蟻群的集體行為的啟發(fā)而提出的一種基于群體的模擬進化算法，屬于隨機搜索算法。它是一種并行算法，所有螞蟻（ 智能體）獨立行動，沒有監(jiān)督機構，從而使其避開局部最優(yōu)；它是一種

32、協(xié)作算法，每一只螞蟻選擇路徑時，有較多信息素的路徑被選中的可能性要比較少信息素的路徑大得多，由于采用了正反饋機制，加快了該算法的收斂速度；它是一種構造性的貪婪算法，能在搜索的早期階段找到較好的可接受解；它是一種魯棒算法，因為只要對算法作小小的修改，就可以運用于別的組合優(yōu)化問題。我們充分利用了蟻群搜索食物的過程與旅行路線最優(yōu)化問題之間的相似性，通過人工模擬蟻群搜索食物的行為（即螞蟻個體之間通過間接通訊與相互協(xié)作最終找到從蟻穴到食物源的最短路徑）來求解TSP問題。像螞蟻這類群居動物，雖然個體的行為極其簡單，但由這些簡單的個體所組成的蟻群卻表現(xiàn)出極其復雜的行為特征，能夠完成復雜的任務；不僅如此，螞蟻

33、還能夠適應環(huán)境的變化，如在蟻群運動路線上突然出現(xiàn)障礙物時，螞蟻能夠很快地重新找到最優(yōu)路徑。蟻群算法已在組合優(yōu)化、計算機網(wǎng)絡路由、連續(xù)函數(shù)優(yōu)化、機器人路徑規(guī)劃、數(shù)據(jù)挖掘、電網(wǎng)優(yōu)化等領域取得了突出的成果。6 誤差分析基于蟻群算法和模擬退火算法的模型、模型、模型的誤差主要體現(xiàn)在兩個方面，一個是數(shù)據(jù)搜集方面，另一個是算法程序方面。6.1基于數(shù)據(jù)收集的誤差分析首先在數(shù)據(jù)收集方面，上文中各城市的經(jīng)緯度精確到小數(shù)點后4位，地球半徑取自地球平均半徑，由于地球橢球體的特征和地球表面丘陵和盆地等地貌，估算出的城市之間的距離與實際距離存在2%的誤差?；疖嚻睌?shù)據(jù)均由相關火車票查詢網(wǎng)站得到，不考慮臨時變動，誤差不會太大

34、?？紤]到實際情況中飛機票存在不可忽略的折扣情況，且隨時間的變化存在一定的不確定性，因此我們在考慮飛機票時，根據(jù)近期內(nèi)的票價波動曲線獲得，在最大限度內(nèi)減小誤差。6.2 基于算法程序的誤差分析（1）有關模擬退火算法的誤差分析1.溫度T的初始值設置是影響模擬退火算法全局搜索性能的重要因素之一。初始溫度高，則搜索到全局最優(yōu)解的可能性大，但因此要花費大量的計算時間；反之，則可節(jié)約計算時間，但全局搜索性能可能受到影響。2.退火速度問題模擬退火算法全局搜索性能也與退火速度密切相關。一般來說，同一溫度下的“充分”搜索（退火）是相當必要的，但這需要計算時間。3.溫度管理問題溫度管理問題也是模擬退火算法難以處理的

35、問題之一。在實際應用中，由于必須考慮計算復雜度的切實可行性等問題，常采用如下所示的降溫方式： 式中為正的略小于1.00的常數(shù)，t為降溫的次數(shù)。因此為保證迭代次數(shù)，減小誤差，我們?nèi)?.99 以下是改變相關參數(shù)時收斂性變化的比較： 圖 12 退火算法在不同參數(shù)下比較收斂性對比（2）有關蟻群算法的誤差分析蟻群算法中容易出現(xiàn)停滯現(xiàn)象，出現(xiàn)早熟收斂。也就是當搜索到一定時間后，所有螞蟻個體所發(fā)現(xiàn)的解完全一致，不能對解進行搜索，所以不利于發(fā)現(xiàn)更好的解。由于改進了基本螞蟻算法的信息素更新方式，對最優(yōu)螞蟻經(jīng)過的路徑的信息素進行更新新，加快了算法收斂的速度。7 算法與模型評價7.1旅行商問題簡述旅行商問題(Tr

36、aveling Salesman Problem,TSP),也稱為貨郎擔問題,由愛爾蘭數(shù)學家Sir William Rowan Hamilton和英國數(shù)學家Thomas Penyngton Kirkman在19世紀提出的數(shù)學問題，它是指給定n個城市并給出每兩個城市之間的距離,旅行商必須以最短路徑訪問所有的城市一次且僅一次,并回到原出發(fā)地,現(xiàn)已證明它屬于NP難題。歷史上的第一個正式用來解決TSP問題的算法誕生于1954年，它被用來計算49個城市的TSP問題。到現(xiàn)在為止，運用目前最先進的計算機技術可解決找出游歷24978個城市的TSP問題。由于該問題的描述簡單, 而其實際模型在印刷電路板的鉆孔路線

37、方案、連鎖店的貨物配送、網(wǎng)絡布線等優(yōu)化問題中又有著廣泛的應用, 故長期以來一直吸引著國內(nèi)外許多研究人員進行研究, 他們嘗試著用各種算法來求解TSP問題, 歸納起來有: 近似解法、局部搜索法、神經(jīng)網(wǎng)絡、遺傳算法、克隆算法、模擬退火算法、混合遺傳算法等。7.2 算法的理解與評價 從圖論的角度看，該問題實質(zhì)是在一個帶權完全無向圖中，找一個權值最小的Hemilton回路。本文嘗試著采用模擬退火算法和蟻群算法來求解TSP問題。螞蟻算法的生物基礎是生物界中螞蟻的尋食規(guī)律。其優(yōu)點在于：強啟發(fā)式，能在早期的尋優(yōu)中迅速找到合適的解決方案；搜索能力強、魯棒性好，易與其他方法結合。模擬退火算法的核心思想來自熱力學原

38、理，是解決大規(guī)模組合優(yōu)化問題的通用、有效的全局優(yōu)化方法。7.2.1 蟻群算法蟻群算法是一種原理相對簡單的新興仿生進化算法，在眾多領域中已展現(xiàn)出它的特點和魅力，但蟻群算法理論與遺傳算法、禁忌搜索算法等理論相比還遠不成熟，實際應用也遠未挖掘出其真正潛力還有許多亟待解決的課題。加強蟻群算法的基礎理論研究，進一步發(fā)展新的數(shù)學分析和建模工具，尤其對算法的基礎理論研究非常重要，包括對解決不同優(yōu)化問題時收斂性和收斂速度的估計、避免陷入局部最優(yōu)值、魯棒性分析以及參數(shù)的設計。目前尚未發(fā)現(xiàn)有關合理選擇螞蟻數(shù)量已經(jīng)算法運行時間數(shù)學分析的論述?？蓪⑾伻核惴ㄅc其他類型方法綜合使用以開發(fā)混合優(yōu)化方法，進而發(fā)展思想更先進、

39、功能更強大、解決更復雜系統(tǒng)的智能行為。蟻群算法在求解復雜優(yōu)化問題時具有快速性、分布式和全局優(yōu)化的特征。其中，尋找最優(yōu)解的快速性是通過信息素的正反饋機制來完成的，而其分布式計算的特征又避免了算法的早熟性收斂。同時，具有貪婪啟發(fā)式搜索特征的蟻群系統(tǒng)又能在搜索過程的早期就找到可接受的解。從復雜系統(tǒng)和復雜性科學的角度看，蟻群系統(tǒng)是一個復雜系統(tǒng)。蟻群系統(tǒng)尋找蟻穴到食物源最短路徑的過程，是整個蟻群之間相互作用、相互影響、相互聯(lián)系、相互協(xié)調(diào)的結果。蟻群算法本質(zhì)上具有概率搜索的特征。對于蟻群算法理論問題的深入研究，可以為推廣蟻群算法的應用領域奠定重要的理論基礎。比如機器人系統(tǒng)、圖像處理、制造系統(tǒng)、車輛路徑系統(tǒng)

40、、通信系統(tǒng)等領域。7.2.2 模擬退火算法模擬退火算法的隨機優(yōu)化思想，算法實現(xiàn)的質(zhì)量和效率是與城市的坐標、城市之間的距離以及城市的個數(shù)密切相關的，要根據(jù)具體的情況選擇合適的參數(shù)(初始溫度、溫度迭代參數(shù)、溫度終止條件、內(nèi)層循環(huán)次數(shù)、城市個數(shù)等)，然后對參數(shù)進行合理的優(yōu)化，才能得到最理想的結果?？梢哉f，這些參數(shù)的設置才是算法好壞的關鍵。本文主要是對模擬退火算法中的幾個重要參數(shù)做了比較研究，并選擇了經(jīng)典的TSP問題作為求解對象得出了一組比較有效的參數(shù)組合。 大量實踐表明模擬退火算法非常適合求解組合優(yōu)化問題。它在一定程度上解決了旅游商問題，值得指出，模擬退火算法以二個引入注目的特性躋身于眾多優(yōu)化算法之

41、中，并獨樹一幟。 （1）模擬退火方法不“貪婪”，它在解優(yōu)化問題的過程中，解點可以在問題的局部極小的附近游蕩，正因為如此，算法不會被容易找到但不能滿足的局部極小點所蒙蔽，從而找到整體極小點。 （3）解點的決定具有邏輯傾向性，當控制參數(shù)T值大時，優(yōu)于新解的當前解被新解替代的可能性大，隨著T的減小，這種可能性隨之減小，特別當時，這種可能性趨向于0.模擬退火算法并不完善，雖然它具有較強的局部搜索能力，并能使搜索過程避免陷入局部最優(yōu)解，但其的運行效率不高，如果把模擬退火算法和其他算法融合，將是提高運行效率和求解質(zhì)量的有效手段。并且由于它是一種隨機優(yōu)化近似算法，一般只能求出近似最優(yōu)解，且性能受到所用隨機數(shù)

42、序列的影響，這一缺點是模擬方式帶來的，目前尚無法徹底解決。總之，雖然模擬退火算法還不完善，但在無法得到實際問題精確最優(yōu)解的情況下，無論從存儲空間還是計算效率考慮，模擬退火算法都不失為一種優(yōu)越的近似方法，特別是對解大規(guī)模NP難道問題更是如此。在問題規(guī)模較小時，螞蟻算法和模擬退火算法都能取得不錯的結果。在本文34個城市的TSP問題中，模擬退火算法的解的質(zhì)量甚至優(yōu)于螞蟻算法；但是，隨著問題規(guī)模的增大，模擬退火算法的解開始惡化，這與模擬退火算法參數(shù)的選擇有關。7.3 模型的評價本文分別對兩個算法進行了編程計算與比較。計算所得到的最優(yōu)解能很好的滿足問題的需要。對于周先生的外出旅行提供了良好的參考方案。模

43、型的優(yōu)點：（1） 搜集了大量的數(shù)據(jù)，緊密的與實際相結合，得到的方案可行性強，能很好的解決旅行方案的優(yōu)化問題。（2） 能較好的解決類似的組合優(yōu)化問題。（3） 對模型稍加修改，就可以應用于印刷電路板的鉆孔路線方案、連鎖店的貨物配送、網(wǎng)絡布線等其他問題。（4） 綜合采用了蟻群算法與模擬退火算法，并進行收斂性與計算結果上的比較分析，改進了算法的性能，提高了求解精度。模型的缺點：（1） 對于大規(guī)模優(yōu)化問題，算法需要較長的搜索時間。（2） 容易出現(xiàn)局部最優(yōu)的情況參考文獻1 韓忠庚.數(shù)學建模競賽.北京:科學出版社，2007. 2 姜啟源，謝金星，葉俊.北京:高等教育出版社,2005.3 鄭寶東.線性代數(shù)與空

44、間解析幾何.北京:高等教育出版社,2003.4 張志涌，楊祖櫻.matlab教程.北京：北京航空航天大學出版社,2006. 5 葉其孝.大學生數(shù)學建模輔導教材.長沙：湖南教育出版社，1993.6 韓中庚.實用運籌學.北京：清華大學出版社，2007.附錄附錄1（34個城市任意兩地距離km）：哈爾濱烏魯木齊長春沈陽呼和浩特北京哈爾濱03057.659229.2761506.51041323.8811051.705烏魯木齊3057.65902999.5982908.7052001.2152412.133長春229.27612999.5980278.67291170.237858.3496沈陽506.

45、51042908.705278.67290985.7115625.1615呼和浩特1323.8812001.2151170.237985.71150412.3302北京1051.7052412.133858.3496625.1615412.33020天津1074.2482511.585866.8073611.3712511.2822122.4083銀川1856.0181667.0151700.4741502.224532.3225888.861石家莊1319.052337.2191119.416870.9716393.2382270.655太原1453.0942189.8311262.7131

46、024.81334.5909404.3859濟南1287.0692602.2231067.426794.0775650.8628365.0478西寧2296.181439.5262142.9581942.888973.82881324.883蘭州2200.4961614.6362035.651822.152878.96091198.305鄭州1637.4842441.8711423.7511155.487692.7576622.4047西安1962.1952114.711765.2231514.599763.5625910.4911南京1668.9413007.7321439.6661165.

47、0781165.014905.4264合肥1737.7082901.7921509.0831231.2551112.236898.5974上海1671.8513267.6791446.2511187.5591379.6131068.572武漢1994.2092762.2331768.8131490.4621159.9461055.586成都2573.6012048.3832378.9322128.5321321.851522.558杭州1808.3743228.4781580.7491315.0991398.8251125.893重慶2448.3552289.8182241.631978.64

48、1278.0261402.227拉薩3565.1531596.5673408.63198.0842242.0042573.821南昌2116.1393020.6181887.2781609.8531403.1071251.824長沙2285.7552843.6512060.0041781.511404.2551338.547貴陽2762.72568.6552547.9682276.8761645.5451732.594福州2288.363467.352061.371796.9581789.3661570.582昆明3139.9432494.5082932.2762667.3611944.126

49、2093.541臺北2350.1513704.8482128.111876.4211978.4091725.226廣州2800.893288.862572.0362294.5671984.5221904.6南寧3037.7413004.8052814.2142536.5592026.2882050.335香港2899.5183556.2922670.3792397.12184.4332064.1澳門2888.4523528.9542659.2492385.4252163.32046.73海口3225.4533379.6442997.6192719.1342316.4662289.241天津銀川石家莊太原濟南西寧哈爾濱1074.2481856.0181319.051453.0941287.0692296.18烏魯木齊2511.585