模擬退火算法的旅行商問(wèn)題

1、人工智能原理實(shí)驗(yàn)報(bào)告模擬退火算法解決TSP問(wèn)題目 錄1 旅行商問(wèn)題和模擬退火算法11.1 旅行商問(wèn)題11.1.1 旅行商問(wèn)題的描述11.2 模擬退火算法11.2.1 基本思想12 TSP模擬退火算法的實(shí)現(xiàn)22.1 TSP算法實(shí)現(xiàn)22.1.1 TSP算法描述22.1.2 TSP算法流程32.2 TSP的C實(shí)現(xiàn)42.2.1 加載數(shù)據(jù)文件42.2.2 計(jì)算總距離的函數(shù)52.2.3 交換城市的函數(shù)52.2.4 執(zhí)行模擬退火的函數(shù)52.3實(shí)驗(yàn)結(jié)果62.4小結(jié)63源代碼6111 旅行商問(wèn)題和模擬退火算法1.1 旅行商問(wèn)題1.1.1 旅行商問(wèn)題的描述旅行商問(wèn)題（Traveling Salesman Prob

2、lem，簡(jiǎn)稱TSP）又名貨郎擔(dān)問(wèn)題，是威廉哈密爾頓爵士和英國(guó)數(shù)學(xué)家克克曼(T.P.Kirkman)于19世紀(jì)初提出的一個(gè)數(shù)學(xué)問(wèn)題，也是著名的組合優(yōu)化問(wèn)題。問(wèn)題是這樣描述的：一名商人要到若干城市去推銷商品，已知城市個(gè)數(shù)和各城市間的路程（或旅費(fèi)），要求找到一條從城市1出發(fā)，經(jīng)過(guò)所有城市且每個(gè)城市只能訪問(wèn)一次，最后回到城市1的路線，使總的路程（或旅費(fèi)）最小。TSP剛提出時(shí)，不少人認(rèn)為這個(gè)問(wèn)題很簡(jiǎn)單。后來(lái)人們才逐步意識(shí)到這個(gè)問(wèn)題只是表述簡(jiǎn)單，易于為人們所理解，而其計(jì)算復(fù)雜性卻是問(wèn)題的輸入規(guī)模的指數(shù)函數(shù)，屬于相當(dāng)難解的問(wèn)題。這個(gè)問(wèn)題數(shù)學(xué)描述為：假設(shè)有n個(gè)城市，并分別編號(hào)，給定一個(gè)完全無(wú)向圖G=（V，E）

3、，V=1，2，n，n1。其每一邊(i,j)E有一非負(fù)整數(shù)耗費(fèi) Ci,j(即上的權(quán)記為Ci,j，i，jV)。并設(shè) G的一條巡回路線是經(jīng)過(guò)V中的每個(gè)頂點(diǎn)恰好一次的回路。一條巡回路線的耗費(fèi)是這條路線上所有邊的權(quán)值之和。TSP問(wèn)題就是要找出G的最小耗費(fèi)回路。1.2 模擬退火算法 模擬退火算法由KirkPatrick于1982提出7，他將退火思想引入到組合優(yōu)化領(lǐng)域,提出一種求解大規(guī)模組合優(yōu)化問(wèn)題的方法，對(duì)于NP-完全組合優(yōu)化問(wèn)題尤其有效。模擬退火算法來(lái)源于固體退火原理，將固體加溫至充分高，再讓其緩慢降溫(即退火)，使之達(dá)到能量最低點(diǎn)。反之，如果急速降溫(即淬火)則不能達(dá)到最低點(diǎn)。加溫時(shí)，固體內(nèi)部粒子隨溫

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

5、ling Schedule)控制，包括控制參數(shù)的初值t及其衰減因子a、每個(gè)t值時(shí)的迭代次數(shù)L和停止條件C。1.2.1 基本思想 模擬退火算法可以分解為解空間、目標(biāo)函數(shù)和初始解3部分。其基本思想是：(1)初始化：初始溫度T(充分大)，初始解狀態(tài)s(是算法迭代的起點(diǎn))，每個(gè)T值的迭代次數(shù)L；(2)對(duì)k=1，L做第(3)至第6步；(3)產(chǎn)生新解s；(4)計(jì)算增量cost=cost(s)-cost(s)，其中cost(s)為評(píng)價(jià)函數(shù)；(5)若t0則接受s作為新的當(dāng)前解，否則以概率exp(-t/T)接受s作為新的當(dāng)前解；(6)如果滿足終止條件則輸出當(dāng)前解作為最優(yōu)解，結(jié)束程序。終止條件通常取為連續(xù)若干個(gè)新

6、解都沒(méi)有被接受時(shí)終止算法；(7)T逐漸減少，且T趨于0，然后轉(zhuǎn)第2步運(yùn)算。 具體如下（1）新解的產(chǎn)生和接受模擬退火算法新解的產(chǎn)生和接受可分為如下4個(gè)步驟：由一個(gè)函數(shù)從當(dāng)前解產(chǎn)生一個(gè)位于解空間的新解。為便于后續(xù)的計(jì)算和接受，減少算法耗時(shí)，常選擇由當(dāng)前新解經(jīng)過(guò)簡(jiǎn)單地變換即可產(chǎn)生新解的方法，如對(duì)構(gòu)成新解的全部或部分元素進(jìn)行置換、互換等。產(chǎn)生新解的變換方法決定了當(dāng)前新解的鄰域結(jié)構(gòu)，因而對(duì)冷卻進(jìn)度表的選取有一定的影響。計(jì)算與新解所對(duì)應(yīng)的目標(biāo)函數(shù)差。因?yàn)槟繕?biāo)函數(shù)差僅由變換部分產(chǎn)生，所以目標(biāo)函數(shù)差的計(jì)算最好按增量計(jì)算。事實(shí)表明，對(duì)大多數(shù)應(yīng)用而言，這是計(jì)算目標(biāo)函數(shù)差的最快方法。判斷新解是否被接受。判斷的依據(jù)是

7、一個(gè)接受準(zhǔn)則，最常用的接受準(zhǔn)則是Metropo1is準(zhǔn)則：若t0則接受S作為新的當(dāng)前解S，否則以概率exp(-t/T)接受S作為新的當(dāng)前解S。當(dāng)新解被確定接受時(shí)，用新解代替當(dāng)前解。這只需將當(dāng)前解中對(duì)應(yīng)于產(chǎn)生新解時(shí)的變換部分予以實(shí)現(xiàn)，同時(shí)修正目標(biāo)函數(shù)值即可。此時(shí)，當(dāng)前解實(shí)現(xiàn)了一次迭代，可在此基礎(chǔ)上開(kāi)始下一輪試驗(yàn)。而當(dāng)新解被判定為舍棄時(shí)，則在原當(dāng)前解的基礎(chǔ)上繼續(xù)下一輪試驗(yàn)。模擬退火算法與初始值無(wú)關(guān)，算法求得的解與初始解狀態(tài)S(是算法迭代的起點(diǎn))無(wú)關(guān)；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以概率收斂于全局最優(yōu)解的全局優(yōu)化算法；模擬退火算法具有并行性。（2）參數(shù)控制問(wèn)題模擬退火算法的應(yīng)用很

8、廣泛，可以求解NP完全問(wèn)題，但其參數(shù)難以控制，其主要問(wèn)題有以下3點(diǎn)7：溫度T的初始值設(shè)置。溫度T的初始值設(shè)置是影響模擬退火算法全局搜索性能的重要因素之一。初始溫度高，則搜索到全局最優(yōu)解的可能性大，但因此要花費(fèi)大量的計(jì)算時(shí)間；反之，則可節(jié)約計(jì)算時(shí)間，但全局搜索性能可能受到影響。實(shí)際應(yīng)用過(guò)程中，初始溫度一般需要依據(jù)實(shí)驗(yàn)結(jié)果進(jìn)行若干次調(diào)整。溫度衰減函數(shù)的選取。衰減函數(shù)用于控制溫度的退火速度，一個(gè)常用的函數(shù)為： 式中是一個(gè)非常接近于1的常數(shù)，t為降溫的次數(shù)。馬爾可夫鏈長(zhǎng)度L的選取。通常的原則是：在衰減參數(shù)T的衰減函數(shù)已選定的前提下，L的選取應(yīng)遵循在控制參數(shù)的每一取值上都能恢復(fù)準(zhǔn)平衡的原則。2 TSP模

9、擬退火算法的實(shí)現(xiàn) TSP是典型的組合優(yōu)化問(wèn)題，模擬退火算法是一種隨機(jī)性解決組合優(yōu)化方法。將TSP與模擬退火算法相結(jié)合，以實(shí)現(xiàn)對(duì)其求解。2.1 TSP算法實(shí)現(xiàn)2.1.1 TSP算法描述 （1）TSP問(wèn)題的解空間和初始解 TSP的解空間S是遍訪每個(gè)城市恰好一次的所有回路，是所有城市排列的集合。TSP問(wèn)題的解空間S可表示為1,2,n的所有排列的集合，即S = (c1,c2,cn) | (c1,c2,cn)為1,2,n的排列），其中每一個(gè)排列Si表示遍訪n個(gè)城市的一個(gè)路徑，ci= j表示在第i次訪問(wèn)城市j。模擬退火算法的最優(yōu)解與初始狀態(tài)無(wú)關(guān)，故初始解為隨機(jī)函數(shù)生成一個(gè)1,2,n的隨機(jī)排列作為S0。（2

10、）目標(biāo)函數(shù) TSP問(wèn)題的目標(biāo)函數(shù)即為訪問(wèn)所有城市的路徑總長(zhǎng)度，也可稱為代價(jià)函數(shù)： 現(xiàn)在TSP問(wèn)題的求解就是通過(guò)模擬退火算法求出目標(biāo)函數(shù)C(c1,c2,cn)的最小值，相應(yīng)地，s*= (c*1,c*2,c*n)即為TSP問(wèn)題的最優(yōu)解。 （3）新解產(chǎn)生新解的產(chǎn)生對(duì)問(wèn)題的求解非常重要。新解可通過(guò)分別或者交替用以下2種方法產(chǎn)生：二變換法：任選序號(hào)u,v(設(shè)uvn)，交換u和v之間的訪問(wèn)順序，若交換前的解為si= (c1,c2,cu,cv,cn),交換后的路徑為新路徑，即：si= (c1,cu-1,cv,cv-1,cu+1,cu,cv+1,cn)三變換法：任選序號(hào)u,v和(uv)，將u和v之間的路徑插到

11、之后訪問(wèn)，若交換前的解為si= (c1,c2,cu,cv,c,cn)，交換后的路徑為的新路徑為：si= (c1,cu-1,cv+1,c,cu,cv,c+1,cn)（4）目標(biāo)函數(shù)差計(jì)算變換前的解和變換后目標(biāo)函數(shù)的差值：c= c(si)- c(si)（5）Metropolis接受準(zhǔn)則根據(jù)目標(biāo)函數(shù)的差值和概率exp(-C/T)接受si作為新的當(dāng)前解si，接受準(zhǔn)則： 2.1.2 TSP算法流程 根據(jù)以上對(duì)TSP的算法描述，可以寫出用模擬退火算法解TSP問(wèn)題的流程圖2-1所示：圖 2-1 TSP的模擬退火流程2.2 TSP的C實(shí)現(xiàn)2.2.1 加載數(shù)據(jù)文件下面是加載數(shù)據(jù)文件的一個(gè)例子：中國(guó)31省會(huì)城市數(shù)據(jù)

12、： 1304 2312;3639 1315;4177 2244;3712 1399;3488 1535;3326 1556; 3238 1229;4196 1044;4312 790;4386 570;3007 1970;2562 1756; 2788 1491;2381 1676;1332 695;3715 1678;3918 2179;4061 2370; 3780 2212;3676 2578;4029 2838;4263 2931;3429 1908;3507 2376 3394 2643;3439 3201;2935 3240;3140 3550;2545 2357;2778 282

13、6;2370 2975;當(dāng)調(diào)用數(shù)據(jù)文件函數(shù)時(shí)，包含城市坐標(biāo)信息的矩陣載入到數(shù)組中。2.2.2 計(jì)算總距離的函數(shù)這是一個(gè)城市間計(jì)算距離的函數(shù)，根據(jù)給定路徑計(jì)算該路徑對(duì)應(yīng)總路程。inline double dist(int x1, int y1, int x2, int y2) return sqrt(double(x2-x1)*(x2-x1)+(y2-y1)*(y2-y1);inline double totaldist(path p) int i; double cost = 0; for (i=1; iN; i+) cost += Dp.Cityip.Cityi+1; cost += Dp.

14、City1p.CityN; return cost; TSP問(wèn)題的成本函數(shù)是城市之間的距離。調(diào)用此函數(shù)將計(jì)算n個(gè)城市之間的距離。2.2.3 交換城市的函數(shù) 這是一個(gè)用于城市交換的函數(shù)，它從某路徑的鄰域中隨機(jī)的選擇一個(gè)新的路徑。 path getnext(path p) int x, y; path ret; ret = p; do x = rand() % N + 1; y = rand() % N + 1; while(x = y); swap(ret.Cityx, ret.Cityy); ret.Length = totaldist(ret);return ret;2.2.4 執(zhí)行模擬退火

15、的函數(shù) void sa() / 退?火e和降溫?過(guò)y程 double T; path newpath, curpath; int i, A_t=0; double delta; T = INIT_T; curpath = F_Path; while(true) for (i=1; i=IN_K; i+) newpath = getnext(curpath); delta = newpath.Length - curpath.Length; if (delta rnd) curpath = newpath; if (curpath.LengthF_Path.Length) F_Path = cu

16、rpath; if (T FINAL_T) break; T = T * RATE; 輸入?yún)?shù)：INIT_K則是開(kāi)始模擬退火過(guò)程的起始溫度。 RATE是模擬退火過(guò)程的冷卻速率，冷卻速率應(yīng)該始終低于1。 FINAL_T是模擬退火的停止條件。2.3實(shí)驗(yàn)結(jié)果2.4小結(jié)模擬退火算法是依據(jù)Metropolis準(zhǔn)則接受新解，該準(zhǔn)則除了接受優(yōu)化解外，還在一定的限定范圍內(nèi)接受劣解，此舉避免陷入局部極小值、提高解空間的搜索能力和擴(kuò)大搜索范圍方面具有明顯的優(yōu)越性；其次，初始溫度T，內(nèi)循環(huán)次數(shù)K，以及溫度衰減率t的選取對(duì)結(jié)果影響很大，適當(dāng)?shù)倪x取很重要。3源代碼#include stdafx.h#include #i

17、nclude #include using namespace std; const int MAXN = 200; /最大城市數(shù)const double INIT_T =100000; /初始溫度const double RATE = 0.05; /溫度下降率 const double FINAL_T = 1E-10; /終止溫度const int IN_K = 10000; /內(nèi)層循環(huán)數(shù)struct path /定義路徑結(jié)構(gòu)類型 int CityMAXN; /依次遍歷的城市的序號(hào) double Length; /所有城市的總長(zhǎng)度; int N; /城市數(shù)量double DMAXNMAXN;

18、 /任意兩個(gè)城市之間的距離path F_Path; /最優(yōu)的遍歷路徑inline double dist(int x1, int y1, int x2, int y2) /計(jì)算兩點(diǎn)之間的距離 return sqrt(double(x2-x1)*(x2-x1)+(y2-y1)*(y2-y1);inline double totaldist(path p) /計(jì)算遍歷路徑總長(zhǎng)度 int i; double cost = 0; for (i=1; iN; i+) cost += Dp.Cityip.Cityi+1; cost += Dp.City1p.CityN; return cost;void

19、init() /讀數(shù)據(jù)，并初始化 int CMAXN2; /城市的坐標(biāo) int i, j; freopen(城市坐標(biāo).txt, r, stdin); scanf(%d, &N); for (i=1; i=N; i+) scanf(%d%d, &Ci0, &Ci1); for (i=1; iN; i+) /計(jì)算任意兩個(gè)城市之間的路徑長(zhǎng)度 for (j=i+1; j=N; j+) Dij = Dji = dist(Ci0, Ci1, Cj0, Cj1); for (i=1; i=N; i+) /最優(yōu)解的初始狀態(tài) F_Path.Cityi = i; F_Path.Length = totaldist

20、(F_Path); srand(unsigned)time(NULL);path getnext(path p) /新解產(chǎn)生函數(shù) int x, y; path ret; ret = p; do x = rand() % N + 1; y = rand() % N + 1; while(x = y); swap(ret.Cityx, ret.Cityy); /交換兩城市之間位置順序 ret.Length = totaldist(ret);return ret; void sa() / 退火和降溫過(guò)程 double T; /溫度 path newpath, curpath; /當(dāng)前路徑和新路徑 int i, A_t=0; double delta; T = INIT_T; /賦值初始溫度 curpath = F_Path;