數(shù)學(xué)實(shí)驗(yàn)綜合實(shí)驗(yàn)Word版

1、傳播優(yōu)秀word版文檔 ，希望對(duì)您有幫助，可雙擊去除！課程名稱：數(shù)學(xué)軟件與實(shí)驗(yàn) 成績(jī)：旅行商問(wèn)題課 程 號(hào)：50c11033課 序 號(hào)：01任課教師：邢紅杰班 級(jí)：5008信計(jì)姓 名：郝杰學(xué) 號(hào)：2008477042 填寫(xiě)日期: 2011-5-24旅行商問(wèn)題5008信息與計(jì)算科學(xué) 郝杰 20084770421、實(shí)驗(yàn)問(wèn)題已知30個(gè)城市的坐標(biāo)如下： 41 94;37 84;54 67;25 62; 7 64;2 99;68 58;71 44;54 62;83 69;64 60;18 54;22 60;83 46;91 38;25 38;24 42;58 69;71 71;74 78;87 76;1

2、8 40;13 40;82 7;62 32; 58 35;45 21;41 26;44 35;4 50一名推銷員要拜訪多個(gè)地點(diǎn)時(shí)，如何找到在拜訪每個(gè)地點(diǎn)一次后再回到起點(diǎn)的最短路徑。2、符號(hào)說(shuō)明location 儲(chǔ)存的是個(gè)城市的坐標(biāo)d（i，j） 代表城市 i和城市j之間的距離len 路徑總距離pc 交叉概率pm 變異概率3、問(wèn)題分析與建模3.1 問(wèn)題分析 本題中設(shè)定了我國(guó)30城市，當(dāng)一個(gè)推銷員拜訪所有城市后回到起點(diǎn)， 31個(gè)地點(diǎn)所有路徑個(gè)數(shù)是30 ！個(gè)。由于其全局搜索的特性，遺傳算法在解決tsp問(wèn)題中有著其他算法所沒(méi)有的優(yōu)勢(shì)。tsp 問(wèn)題就是尋找一條最短的遍歷n 個(gè)城市的最短路徑, 或者說(shuō)搜索子

3、集v=v1,v2,v3,vn ( vi的元素表示對(duì)n 個(gè)城市的編號(hào)) 的一個(gè)排列t=(t1,t2,t3,ti,tn),其中tiv(i=1,2,3,n)，且記tn+1= t1， , 使len = d ( vi , vi+1) + d ( v1 , vn)取最小值, 式中的d ( vi , vi+1) 表示城市vi 到城市vi + 1的距離.標(biāo)準(zhǔn)的遺傳算法包括群體的初始化，選擇，交叉，變異操作。其主要步驟可描述如下1： （1）隨機(jī)產(chǎn)生一組初始個(gè)體構(gòu)成的初始種群，并評(píng)價(jià)每一個(gè)個(gè)體的適配值。 （2）判斷算法的收斂準(zhǔn)則是否滿足。若滿足輸出搜索結(jié)果；否則執(zhí)行以下步驟。 （3）根據(jù)適配值大小以一定方式執(zhí)行選

4、擇操作。 （4）按交叉概率pc執(zhí)行交叉操作. （5）按變異概率pm執(zhí)行變異操作。 （6）返回步驟（2）。3.2 程序設(shè)計(jì)3.2.1坐標(biāo)系中畫(huà)出個(gè)城市的坐標(biāo)點(diǎn)矩陣location儲(chǔ)存的是個(gè)城市的坐標(biāo)（設(shè)：推銷員出發(fā)點(diǎn)的坐標(biāo)為（0,0）如下圖所示：locations= 0 0;41 94;37 84;54 67;25 62; 7 64;2 99;68 58;71 44;54 62;83 69;64 60;18 54;22 60;83 46;91 38;25 38;24 42;58 69;71 71;74 78;87 76;18 40;13 40;82 7;62 32; 58 35;45 21;41

5、 26;44 35;4 50; plot(locations(:,1),locations(:,2),'b*');3.2.2 距離矩陣和適應(yīng)度函數(shù)距離矩陣使用一個(gè)n×n矩陣d存儲(chǔ)，d（i，j）代表城市 i和城市j之間的距離。 d（i，j）=sqrt(（xi-xj）.2+(yi-yj).2) 在該問(wèn)題的求解中，用距離的總和來(lái)衡量適應(yīng)度，距離的總和越大，適應(yīng)度越小，進(jìn)而探討求解結(jié)果是否最優(yōu)。 每個(gè)個(gè)體（每條路徑距離）總合計(jì)算公式為：len=d(1,n); for i=1:(n-1) len=len+d(i,i+); end len紀(jì)錄總路徑格式n×1 len(i

6、)代表第i個(gè)個(gè)體（路徑）距離總合。3.2.3 選擇操作選擇的目的是為了從當(dāng)前群體中選出優(yōu)良的個(gè)體，使他們有機(jī)會(huì)作為父代產(chǎn)生后代的個(gè)體。function seln=(s,p);inn=size(p,1);for i=1:2 r=rand; prand=p-r; j=1; while prand(j)<0 j=j+1; end seln(i)=j;endend3.2.4 交叉操作群體中的每個(gè)個(gè)體之間都以一定的概率 pc 交叉，即兩個(gè)個(gè)體從各自字符串的某一位置（一般是隨機(jī)確定）開(kāi)始互相交換，這類似生物進(jìn)化過(guò)程中的基因分裂與重組。例如，假設(shè)2個(gè)父代個(gè)體x1，x2為： x1=0100110 x2=

7、1010001 從每個(gè)個(gè)體的第3位開(kāi)始交叉，交又后得到2個(gè)新的子代個(gè)體y1，y2分別為： y10100001 y21010110這樣2個(gè)子代個(gè)體就分別具有了2個(gè)父代個(gè)體的某些特征。利用交又我們有可能由父代個(gè)體在子代組合成具有更高適合度的個(gè)體。function xoverkids = tsp_crossover_permutation(parents,options,nvars, . fitnessfcn,thisscore,thispopulation)nkids = length(parents)/2;xoverkids = cell(nkids,1);index = 1; for i=1:

8、nkids parent = thispopulationparents(index); index = index + 2; p1 = ceil(length(parent) -1) * rand); p2 = p1 + ceil(length(parent) - p1- 1) * rand); child = parent; child(p1:p2) = fliplr(child(p1:p2); xoverkidsi = child; end3.2.5 變異操作基因的突變普遍存在于生物的進(jìn)化過(guò)程中。變異是指父代中的每個(gè)個(gè)體的每一位都以概率 pm 翻轉(zhuǎn)，即由“1”變?yōu)椤?”，或由“0”變?yōu)椤?/p>

9、1”。遺傳算法的變異特性可以使求解過(guò)程隨機(jī)地搜索到解可能存在的整個(gè)空間，因此可以在一定程度上求得全局最優(yōu)解。functionmutationchildren = mutate_permutation(parents ,options,nvars, . fitnessfcn,state,thisscore,thispopulation,mutationrate)mutationchildren = cell(length(parents),1);for i=1:length(parents)parent = thispopulationparents(i); p = ceil(length(pa

10、rent) * rand(1,2); child = parent; child(p(1) = parent(p(2); child(p(2) = parent(p(1);mutationchildreni = child; end4、matlb求解迭代后的最優(yōu)路徑如下圖所示由上圖可知推銷員所走的最短路徑fval = 504.78885、總結(jié)體會(huì)tsp問(wèn)題還有很多其他算法，比如說(shuō)最臨近算法、模擬退火、粒子群算法、最小權(quán)匹配算法等等論文用遺傳算法對(duì)tsp問(wèn)題進(jìn)行了求解，熟悉遺傳算法地算法流程，證明了遺傳算法在求解tsp問(wèn)題時(shí)，具有可行性，matlab在進(jìn)行算法優(yōu)化編程時(shí)具有一定的優(yōu)勢(shì)。遺傳算法在設(shè)計(jì)過(guò)程中要照顧好兩個(gè)原則子代要具有父代優(yōu)良的基因信息即繼承性子代要保持群體的多樣性，即變異。雖然這兩個(gè)原則