實(shí)驗(yàn)三10個(gè)城的TSP問題

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

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

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

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

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

6、1) lgt 1) t了收斂速度，在接近冷卻時(shí)下降慢，確保充分搜索。四、程序運(yùn)行截圖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