實驗三10個城的TSP問題

1、實驗三10個城市的TSP問題一、問題描述旅行商問題旅行商按一定的順序訪問N個城市的每個城市，使得每個城市都能被訪問且僅能被訪問 一次，最后回到起點，而使花費的代價最小。二、設計思想1、算法的選擇這是一個NP完全問題，窮舉法顯然是不可取的。由于初始態(tài)和最終態(tài)無法界 定，因此沒有采用了 A*算法。通過查閱資料，發(fā)現模擬退火算法能較好地解決這 一問題。2、算法思想模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫 時，固體內部粒子隨溫升變?yōu)闊o序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個 溫度都達到平衡態(tài)，最后在常溫時達到基態(tài)，內能減為最小。用固體退火模擬組合優(yōu)化 問題，將內

2、能模擬為目標函數值f，溫度T演化成控制參數t即得到解組合優(yōu)化問 題的模擬退火算法：由初始解i和控制參數初值t開始，對當前解重復“產生新解計 算目標函數差f接受或舍棄”的迭代，并逐步衰減t值，算法終止時的當前解即為所得 近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機搜索過程。3、算法描述模擬退火算法與初始值無關，算法求得的解與初始解狀態(tài)S（是算法迭代的起點）無 關；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以概率？收斂于全局最 優(yōu)解的全局優(yōu)化算法。接受概率p=exp（f/Ti求解TSP的模擬退火算法模型可描述如下：解空間:解空間S是遍訪每個城市恰好一次的所有路經，解可以表示為w1

3、,w2 , wn , w1, , wn是 1,2, ,n的一個排列，表明w1城市出發(fā)，依次經過w2, , wn城市，再返回可1城市。初始解可選為（1, ，n）；目標函數：目標函數為訪問所有城市的路徑總長度；我們要求的最優(yōu)路徑為目標函數為最小值時對應的路徑。新路徑的產生：隨機產生1和n之間的兩相異數k和m,不妨假設km，則將原 路徑（w1,w2,，wk,wk+1,，wm,wm+1, ，wn）變?yōu)樾侣窂剑海╳1,w2,wm,wk+1,wk,wm+1,wn）上述變換方法就是將k和m對應的兩個城 市在路徑序列中交換位置,稱為2-opt映射。根據上述描述，模擬退火算法求解TSP問 題的流程框圖如下三、程

4、序設計1、編譯環(huán)境使用C#語言編寫，編譯器為VS2008，運行環(huán)境為Windows+.NetFramework3.52、程序運行流程程序的輸入通過文件，在graph.tx文件中將城市矩陣輸入，每一行列表示一個城 市序號，對應的元素值為兩城市之間的路程代價。輸入文件后運行程序，進行搜索計算，監(jiān)視正在搜索的路徑，當找到最佳路徑后顯 示路徑以及總路程代價數，退出。3、類設計程序為控制臺應用程序，算法的主要過程在主類Program中實現，包括的功能函數 有:讀入城市圖 InitGraph；初始化溫度 InitTemperature溫度管理 DiclineTemperature() Main()函數中實

5、現上述算法流程圖。Route類實現路徑的定義與操作。它能夠創(chuàng)建一條路徑，計算路徑的路程代價。函 數SelRoute()實現按換位方法隨機選擇一條新路徑。4、初始溫度設置溫度值對應了物體內能的一個平衡態(tài)，因此我選取的1000個路徑樣本，分別計算 其路程(即能量)，計算樣本的方差，用它作為溫度的初始值。5、退火速度控制在某一溫度下要盡量完全地進行搜索，但是同時要考慮到運算的效率，通過取多個 值驗證，當每溫度搜索次數為10000次時結果已經穩(wěn)定，無需更多。6、溫度管理在算法的每一次外循環(huán)，溫度應進行降低，直至冷卻，這里我選擇的是函數L 1)其中t是夕卜循環(huán)的次數。這樣，溫度在剛開始時下降快，保證住

6、1) lgt 1) t了收斂速度，在接近冷卻時下降慢，確保充分搜索。四、程序運行截圖1、輸入的城市圖:r .食 graph.txt -記事本，口 回文件舊端輯舊格式查春凹蒂助CWOOOOOOOOO9765432101234567890oooooooo O86543210 O1234567809ooooooo OO7543210 O11234567088oooooo OOO643210 012 1234560777ooooo OOOO53210 0123 1234506666o o o o o o o o O 4210 01234 12340555550 0 03 1012 3 00 0 0 012 3 44 4 4 4o o O 2 0 O 12 0 3