模擬退火算法的旅行商問(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.1tsp算法描述22.1.2 tsp算法流程32.2 tsp的c實(shí)現(xiàn)52.2.1加載數(shù)據(jù)文件52.2.2計(jì)算總距離的函數(shù)52.2.3交換城市的函數(shù)52.2.4執(zhí)行模擬退火的函數(shù)52.3實(shí)驗(yàn)結(jié)果72.4小結(jié)73源代碼81旅行商問(wèn)題和模擬退火算法1.1旅行商問(wèn)題111旅行商問(wèn)題的描述旅行商問(wèn)題(traveling salesman problem,簡(jiǎn)稱tsp)又名貨郎擔(dān)問(wèn)題，

2、是威廉哈 密爾頓爵士和英國(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),v=1, 2,n,

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

4、。加溫時(shí)，固體內(nèi)部粒子隨 溫升變?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)能，a 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開始, 對(duì)當(dāng)前解重復(fù)產(chǎn)生“新解-計(jì)算目標(biāo)函數(shù)差-接受或舍棄”的迭代，并逐步衰減t值，算 法終止時(shí)的當(dāng)前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種

5、啟發(fā)式隨 機(jī)搜索過(guò)程。退火過(guò)程rfl冷卻進(jìn)度表(cooling schedule)控制，包括控制參數(shù)的初值t及 其衰減因子a、每個(gè)t值時(shí)的迭代次數(shù)l和停止條件co1.2.1基本思想模擬退火算法可以分解為解空間、目標(biāo)函數(shù)和初始解3部分。其基本思想是：(1) 初始化：初始溫度t(充分大)，初始解狀態(tài)s(是算法迭代的起點(diǎn))，每個(gè)t值的迭 代次數(shù)l；(2) 對(duì)k=l,l做第(3)至第6步；(3) 產(chǎn)生新解sz；(4) 計(jì)算增量cost=cost(s/)-cost(s),其屮cost(s)為評(píng)價(jià)函數(shù)；(5) 若f<0則接受s作為新的當(dāng)前解，否則以概率exp(-tvt)接受s作為新的當(dāng)前解;(6)

6、如果滿足終止條件則輸出當(dāng)前解作為最優(yōu)解，結(jié)束程序。終止條件通常取為連續(xù) 若干個(gè)新解都沒有被接受時(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ì)算

7、。事實(shí)表明，對(duì)大多數(shù)應(yīng)用而言，這是計(jì)算目標(biāo)函數(shù) 差的最快方法。判斷新解是否被接受。判斷的依據(jù)是一個(gè)接受準(zhǔn)則，最常用的接受準(zhǔn) 則是metropolis準(zhǔn)則：若f<0則接受s作為新的當(dāng)前解s,否則以概率cxp(-t7t)接受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ǔ)上開始下一輪試驗(yàn)。而當(dāng)新解被判定為舍棄吋，則在原當(dāng)前解的 基礎(chǔ)上繼續(xù)下一輪試驗(yàn)。模擬退火算法與初始值無(wú)關(guān)，算法求得的解與初始解狀態(tài)s(是算法迭代的起點(diǎn))無(wú) 關(guān)；模擬退火算法具有漸近收斂性，已在理

8、論上被證明是一種以概率收斂于全局最優(yōu)解 的全局優(yōu)化算法；模擬退火算法貝有并行性。(2) 參數(shù)控制問(wèn)題模擬退火算法的應(yīng)用很廣泛，可以求解np完全問(wèn)題，但其參數(shù)難以控制，其主要 問(wèn)題有以下3點(diǎn)：溫度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ù)為：t(t + y) = at(t)(1-2)式中是一個(gè)非常接近于1的常

9、數(shù)，t為降溫的次數(shù)。馬爾可夫鏈長(zhǎng)度l的選取。 通常的原則是：在衰減參數(shù)t的衰減函數(shù)已選定的前提下，l的選取應(yīng)遵循在控制參數(shù) 的每一取值上都能恢復(fù)準(zhǔn)平衡的原則。2 tsp模擬退火算法的實(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可表示為l,2,n的所有排列的集合，即s = (c,c2,.,cn) | (ci,c2,.£n) 為l,2,.

10、,n的排列),其中每一個(gè)排列si表示遍訪n個(gè)城市的一個(gè)路徑，ci=j表示在 第i次訪問(wèn)城市j。模擬退火算法的最優(yōu)解與初始狀態(tài)無(wú)關(guān)，故初始解為隨機(jī)函數(shù)生成 一個(gè)l,2,.,n的隨機(jī)排列作為s()。(2)目標(biāo)函數(shù)tsp問(wèn)題的目標(biāo)函數(shù)即為訪問(wèn)所有城市的路徑總長(zhǎng)度，也可稱為代價(jià)函數(shù)：c(c/2,cj =(c,£+j + d(qcj(2-1)i=現(xiàn)在tsp問(wèn)題的求解就是通過(guò)模擬退火算法求出目標(biāo)函數(shù)c(c,c2,cn)的最小值，相應(yīng) 地，s*=(c*bc*2v.,c*n)即為tsp問(wèn)題的最優(yōu)解。(3) 新解產(chǎn)生新解的產(chǎn)生對(duì)問(wèn)題的求解非常重要。新解可通過(guò)分別或者交替用以下2種方法產(chǎn)生: 二變換法：

11、任選序號(hào)u,v(設(shè)u vv vn),交換u和v之間的訪問(wèn)順序，若交換前的 解為si=(ci,c2,.,cu,.,cv,cn)換后的路徑為新路徑，即：si (ci,.,cu,cv,cv-l,.,cu-l,cu,cv+i,.,cn) 三變換法：任選序號(hào)u,v和co(u<v <(0),將u和v之間的路徑插到(0之后訪問(wèn)， 若交換前的解為sj=(c1 £2,. ,cu,£v,cq), . ,cn),父換后的路徑為的新路徑為：si (ccu-l,cv+l,c®,cu,cv,c(j)+(4) 目標(biāo)函數(shù)茅計(jì)算變換前的解和變換后目標(biāo)函數(shù)的差值：ac - c(s/) c

12、(sj)(5) metropolis 接受準(zhǔn)則根據(jù)目標(biāo)函數(shù)的差值和概率exp(-ac7t)接受s/作為新的當(dāng)前解s,接受準(zhǔn)則：(1, -ac <0(exp(-ac /t) , -ac >02.1.2 tsp算法流程根據(jù)以上對(duì)tsp的算法描述，可以寫出用模擬退火算法解tsp問(wèn)題的流程圖21所示:(2-2)圖2-1 tsp的模擬退火流程2.2 tsp的c實(shí)現(xiàn)2.2.1加載數(shù)據(jù)文件下面是加載數(shù)據(jù)文件的一個(gè)例子：中國(guó)31省會(huì)城市數(shù)據(jù)：1304 2312;3639 1315;4177 2244;3712 1399;3488 1535;3326 1556;3238 1229;4196 1044

13、;4312790;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 23763394 2643;3439 3201;2935 3240;3140 3550;2545 2357;2778 2826;2370 2975; 當(dāng)調(diào)用數(shù)據(jù)文件函數(shù)時(shí)，包含城市坐標(biāo)信息的矩陣載入到數(shù)組中。222計(jì)算總距離的函數(shù)這是一個(gè)城市間計(jì)算距離的函數(shù)，根據(jù)給定路徑計(jì)算該路徑對(duì)應(yīng)總路程。i

14、nline double dist(int xl, int yl, int x2, int y2)retumsqrt(double(x2-x 1 )*(x2-x 1 )+(y2-y 1 )*(y2-y 1);inline double totaldist(path p)inti;double cost = 0;for (i=l; i<n; i+)cost += dp.cityip.city i+1；cost += dp.citylp.cityn;return cost;tsp問(wèn)題的成木函數(shù)是城市z間的距離。調(diào)用此函數(shù)將計(jì)算n個(gè)城市z間的距離。2.2.3交換城市的函數(shù)這是一個(gè)用于城市交換的

15、函數(shù)，它從某路徑的鄰域中隨機(jī)的選擇一個(gè)新的路徑。pathgctncxt(path p) int x, y;path ret;ret = p;do x = rand() % n + 1;y = rand() % n + 1;while(x = y);swap(ret.cityx9 ret.cityfy);ret. length = totaldist(ret);return ret;2.2.4執(zhí)行模擬退火的函數(shù)void sa() / 退叫火e和降;i溫?過(guò)y程jdouble t;pathnewpath, curpath;inti, a_t=0;double delta;t = initt;cur

16、path = f_path;while(true)for (i=l; i<=in_k; i+) newpath = getnext(curpath);delta = newpath.length - curpath.length; if(delta<0.0)curpath = newpath;a_t = 0;" elsedoublcrnd = rand()% 10000 /10000.0; double p = exp(-delta/t);if(p >md)curpath = newpath;if (curp ath. length<f_path. lengt

17、h)f_path = curpath; if(t<final_t) break;t = t* rate;輸入?yún)?shù)：init_k則是開始模擬退火過(guò)程的起始溫度。rate是模擬退火過(guò)程的冷卻速率，冷卻速率應(yīng)該始終低丁 k final_t是模擬退火的停止條件。2.3實(shí)驗(yàn)結(jié)果tai c:windowssystem32cmd.:23308.90681-> 2-3-> 4-> 5-> 6-?-> 8-> 9-> 10-> 11-> 12-> 13-> 14-> 15-16-> 17-> 18-> 19->

18、 20-> 21-> 22-> 23-> 24-25-26-27-> 28-29-> 30-31-> 1 最優(yōu)路徑長(zhǎng)度:15448.23889-> 10-> 4-> 2-> 5-> 6-?-> 13-> 11-> 12-> 14-> 15-> 1-> 29-31-30-27-> 28-> 2625-> 2420-> 21-> 2218-> 3 > 17-> 19-> 23-> 16-> 8> 9 1.78100

19、0 seconds請(qǐng)按任意鍵繼續(xù)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 nstdafx.hh#include <iostream>#include <cmath>#include <time.h>using namespace std;constint maxn = 200;最人城市數(shù)

20、const double init t =100000; 初始溫度”const double rate = 0.05;溫度卜降率const double final t = constint in k = 10000;ie-10; 終1上溫度內(nèi)層循環(huán)數(shù)struct path int citymaxn; double length;定義路徑結(jié)構(gòu)類型依次遍歷的城市的序號(hào)所有城市的總長(zhǎng)度int n;double dmaxnmaxn; path f path;城市數(shù)量任意兩個(gè)城wz間的距離最優(yōu)的遍歷路徑inline double dist(int xl, int yl, int x2, int y2)

21、 /計(jì)算兩點(diǎn)之間的距離 returnsqrt(double(x2-x l)*(x2-x 1 )+(y2y 1 )*(y2-y 1);inline double totaldist(path p)計(jì)算遍丿力路徑總長(zhǎng)度inti;double cost = 0;for (i=l; i<n; i+-i-)cost += dp.cityip.cityi+l;cost += dp.citylp.cityn;return cost;讀數(shù)據(jù)，并初始化int cmaxn2;城市的坐標(biāo)inti,j;frcopcn(n城市坐標(biāo).txt”, "rn, stdin);scanff%d”，&n);

22、for (i=l; i<=n;汁+)scanf(”d%d”, &ci0, &cil);for (i=l; i<n;汁+)計(jì)號(hào)任意兩個(gè)城市之間的路徑長(zhǎng)度f(wàn)or(j=i+l; j<=n; j 卄)dij = dji = dist(ci0, cil, cjo, cjl)；for (i=l; i<=n; i+) 最優(yōu)解的初始狀態(tài)f_path.cityi = i;fpath. length = totaldist(fpath); srand(unsigned)time(null);path gctncxt(path p)新解產(chǎn)生函數(shù)int x, y;path re

23、t;ret = p;do x = rand() % n + 1;y = rand() % n + 1;while(x = y);swap(ret.cityx, ret.cityfy);交換兩城市之間位置順序ret. length = totaldist(rct);return ret;void sa() / 退火和降溫過(guò)程double t;溫度path newpath, curpath;當(dāng)前路徑和新路徑inti, a_t=0;double delta;t = init_t;賦值初始溫度curpath = fpath;while(tme)for (i=l; i<=fn_k; i+) _newpath = ge