人工智能TSP旅行商問題實(shí)驗(yàn)報(bào)告剖析

1、人工智能實(shí)驗(yàn)三實(shí)驗(yàn)報(bào)告班級(jí)：姓名：學(xué)號(hào)：實(shí)驗(yàn)題目TSP問題的遺傳算法實(shí)現(xiàn)旅行商問題（TravelingSalesmanProblem,TSP）,又譯為旅行推銷員問題、貨擔(dān)郎問題，簡(jiǎn)稱為TSP問題，是最基本的路線問題。假設(shè)有n個(gè)可直達(dá)的城市，一銷售商從其中的某一城市出發(fā)，不重復(fù)地走完其余n-1個(gè)城市并回到原出發(fā)點(diǎn)，在所有可能的路徑中求出路徑長(zhǎng)度最短的一條。應(yīng)用遺傳算法求解30/10個(gè)節(jié)點(diǎn)的TSP（旅行商問題）問題，求問題的最優(yōu)解。實(shí)驗(yàn)?zāi)康氖煜ず驼莆者z傳算法的基本概念和基本思想；理解和掌握遺傳算法的各個(gè)操作算子，能夠用選定的編程語言設(shè)計(jì)簡(jiǎn)單的遺傳優(yōu)化系統(tǒng)；通過實(shí)驗(yàn)培養(yǎng)學(xué)生利用遺傳算法進(jìn)行問題求解的

2、基本技能。實(shí)驗(yàn)要求掌握遺傳算法的基本原理、各個(gè)遺傳操作和算法步驟；要求求出問題最優(yōu)解，若得不出最優(yōu)解，請(qǐng)分析原因；對(duì)實(shí)驗(yàn)中的幾個(gè)算法控制參數(shù)進(jìn)行仔細(xì)定義，并能通過實(shí)驗(yàn)選擇參數(shù)的最佳值；要求界面顯示每次迭代求出的局部最優(yōu)解和最終求出的全局最優(yōu)解。數(shù)據(jù)結(jié)構(gòu)請(qǐng)說明染色體個(gè)體和群體的定義方法。structRanSeTi/染色體的個(gè)體的定義方法intcitycities;/基因的排列（即城市的順序，路徑的組織）intadapt;/記錄適應(yīng)度doublep;/記錄其在種群中的幸存概率RanSeTinum,RanSeTitempnum;/用數(shù)組來存儲(chǔ)染色體群體方法實(shí)驗(yàn)算法說明算法中對(duì)染色體的編碼方法，適應(yīng)度

3、函數(shù)定義方法1）染色體的編碼方法:即為染色體個(gè)體定義過程中生成的基因排列（路徑中城市的順序）structRanSeTi/染色體的個(gè)體的定義方法intcitycities;/基因的排列（即城市的順序，路徑的組織）intadapt;/記錄適應(yīng)度doublep;/記錄其在種群中的幸存概率RanSeTinum,RanSeTitempnum;/用數(shù)組來存儲(chǔ)染色體群體方法2）適應(yīng)度函數(shù)定義方法：評(píng)價(jià)函數(shù)即適應(yīng)度函數(shù)，在遺傳算法中用來計(jì)算一個(gè)染色體優(yōu)劣的函數(shù)。在進(jìn)行遺傳操作和種群進(jìn)化的時(shí)候，每個(gè)染色體的適應(yīng)值是決定它是否進(jìn)入下一輪種群進(jìn)化的關(guān)鍵因素。適應(yīng)值高的函數(shù)被選作新一代個(gè)體的可能性就會(huì)大。TSP問題中

4、適應(yīng)度函數(shù)常取路徑長(zhǎng)度的倒數(shù)（或倒數(shù)的相關(guān)函數(shù)），如：f(x,x,其中，N是個(gè)調(diào)節(jié)參數(shù)，根據(jù)實(shí)驗(yàn)情況進(jìn)行確定。for(i=0;inum;i+)sumdistance=0;for(j=1;jcities;j+)n1=RanSeTii.cityj-1;n2=RanSeTii.cityj;sumdistance+=distancen1n2;RanSeTii.adapt=sumdistance;/每條染色體的路徑總和biggestsum+=sumdistance;/種群的總路徑采用的選擇、交叉、變異操作算子的具體操作1）選擇操作我們定義f（xp為第i（i=l,2,3.popsize）個(gè)染色體的適應(yīng)度，

5、則每個(gè)個(gè)體被選中的概率是：P(x.)=f(xV廿f(x.)本題中具體使用的是期望值方法/初始化梯度概率for(i=0;inum;i+)gradienti=0.0;xuanzei=0.0;gradient0=group0.p;for(i=1;inum;i+)gradienti=gradienti-1+groupi.p;srand(unsigned)time(NULL);/隨機(jī)產(chǎn)生染色體的存活概率for(i=0;inum;i+)xuanzei=(rand()%100);xuanzei/=100;/選擇能生存的染色體for(i=0;inum;i+)for(j=0;jnum;j+)if(xuanzei

6、gradientj)xuani=j;/第i個(gè)位置存放第j個(gè)染色體break;/拷貝種群for(i=0;inum;i+)grouptempi.adapt=groupi.adapt;grouptempi.p=groupi.p;for(j=0;jcities;j+)grouptempi.cityj=groupi.cityj;/數(shù)據(jù)更新for(i=0;inum;i+)temp=xuani;groupi.adapt=grouptemptemp.adapt;groupi.p=grouptemptemp.p;for(j=0;jcities;j+)groupi.cityj=grouptemptemp.city

7、j;2)交叉操作：交叉算子就是把兩個(gè)父代個(gè)體的部分結(jié)構(gòu)加以替換重組而生成新個(gè)體的操作部分匹配交叉、順序交叉、改進(jìn)的啟發(fā)式順序交叉/temp1號(hào)染色體和temp2染色體交配for(i=0;it/2;i+)point1=rand()%cities;point2=rand()%cities;for(j=temp1;jnum;j+)if(jiaopeiflagj=1)temp1=j;break;for(j=temp1+1;jpoint2)/保證point1=point2temp=point1;point1=point2;point2=temp;memset(map1,-1,sizeof(map1);m

8、emset(map2,-1,sizeof(map2);/斷點(diǎn)之間的基因產(chǎn)生映射for(k=point1;k=point2;k+)map1grouptemp1.cityk=grouptemp2.cityk;map2grouptemp2.cityk=grouptemp1.cityk;/斷點(diǎn)兩邊的基因互換for(k=0;kpoint1;k+)temp=grouptemp1.cityk;grouptemp1.cityk=grouptemp2.cityk;grouptemp2.cityk=temp;for(k=point2+1;kcities;k+)temp=grouptemp1.cityk;group

9、temp1.cityk=grouptemp2.cityk;grouptemp2.cityk=temp;/處理產(chǎn)生的沖突基因for(k=0;kpoint1;k+)for(kk=point1;kk=point2;kk+)if(grouptemp1.cityk=grouptemp1.citykk)grouptemp1.cityk=map1grouptemp1.cityk;break;for(k=point2+1;kcities;k+)for(kk=point1;kk=point2;kk+)if(grouptemp1.cityk=grouptemp1.citykk)grouptemp1.cityk=m

10、ap1grouptemp1.cityk;break;for(k=0;kpoint1;k+)for(kk=point1;kk=point2;kk+)if(grouptemp2.cityk=grouptemp2.citykk)grouptemp2.cityk=map2grouptemp2.cityk;break;for(k=point2+1;kcities;k+)for(kk=point1;kk=point2;kk+)if(grouptemp2.cityk=grouptemp2.citykk)grouptemp2.cityk=map2grouptemp2.cityk;break;temp1=tem

11、p2+1;變異操作TSP問題中，經(jīng)常采取的變異操作主要有：位點(diǎn)變異、逆轉(zhuǎn)變異、對(duì)換變異、插入變異。/隨機(jī)產(chǎn)生變異概率srand(unsigned)time(NULL);for(i=0;inum;i+)bianyipi=(rand()%100);bianyipi/=100;/確定可以變異的染色體t=0;for(i=0;inum;i+)if(bianyipipm)bianyiflagi=1;t+;/變異操作,即交換染色體的兩個(gè)節(jié)點(diǎn)srand(unsigned)time(NULL);for(i=0;inum;i+)if(bianyiflagi=1)temp1=rand()%10;temp2=rand

12、()%10;point=groupi.citytemp1;groupi.citytemp1=groupi.citytemp2;groupi.citytemp2=point;實(shí)驗(yàn)中采用的算法參數(shù)的最佳選擇值是多少#definecities10/30/城市的個(gè)數(shù)#defineMAXX150/迭代次數(shù)#definepc0.72/交配概率#definepm0.02/變異概率#definenum20/種群的大小實(shí)驗(yàn)結(jié)果1要求有實(shí)驗(yàn)運(yùn)行結(jié)果截圖，以及必要的說明0.05070.05078.04988.04980.04980.04980.04980.04970.05070.04980.04980.04978.

13、04980.05070.04980.04980.04980.04980.05070.0497B.05070.0507915VVVVTTVV4F=._LF=.-LF=.-LF=.-LF=.4P-CP-CP-CF=.-LF習(xí).-斗.斗.斗.斗/斗.-斗.-斗.-斗.斗.-軒售glsgg豊IFlflfir唱墾stMjlsl營(yíng)脣關(guān)腸a二t-4.-iii_.f_nnnnnnnnn口丿_.T.丿_!J_!亠_!-!*_!丿_!丿_盧丿-盧丿_!丿_.T._-F_之之染之之之之之之之之之之染ZHd.n-耳.l-.?:-.口.l-./:-.口.-h.-.口.L./:-.口J:m:-:-:-.口.l-.?:-.

14、口.l-./:-.口CHd.UHdiD-yin-yilZHdilZHdilZHdilZHdillHdiD-JPV141111454454115999999919919991535555363363556種ZOEff-ff-ff-ff-ffffffffff-ff-ff-ff-ff-ffffffff!l種&前邑邑邑邑邑邑邑邑邑邑邑邑邑邑邑邑邑邑邑&刖邂雪養(yǎng)聚棗棗聚聚聚棗棗聚雪以上部分是每次迭代的步驟結(jié)果，通過染色體群體中個(gè)體的交配、變異，從而更改染色體的具體基因組成，通過不斷進(jìn)行適應(yīng)度計(jì)算、存活率的計(jì)算，更新已有數(shù)值；前岀最終的種群評(píng)價(jià)4617259380adapt:591.P0049846172

15、59380adapt:591.P004984617259380adapt:591,P004984617259380adapt:591.P004984617259380adapt:591.P00498462715938Qadapt:615,P00497569a237841adapt:394,P005074617259380adapt:591.P004984617259380adapt:591.P004984627159380adapt:615,P004974617259380adapt:591,P004985690237841adapt:394.P00507461725938Qadapt:591

16、,P004984617259380adapt:591,P004984617259380adapt:591.P004984617259380adapt:591.P004985690237841adapt:394,P005074627159380adapt:615,P004975690237841adapt:394.P00507*應(yīng)解焉號(hào)泰色和237841adapt:394,P00507以上部分為迭代之后的總結(jié)果，輸出最終的種群評(píng)價(jià)，從染色體種群里面取出最佳的染色體，并進(jìn)行輸出。2要求說明是否搜索到了最優(yōu)解，如果沒有，請(qǐng)分析原因本題中根據(jù)隨機(jī)生成的cities個(gè)城市之間的相互距離、隨機(jī)產(chǎn)生初試群，

17、通過TSP算法，通過以下步驟：(1)初始化群體;(2)計(jì)算群體上每個(gè)個(gè)體的適應(yīng)度值;(3)按由個(gè)體適應(yīng)度值所決定的某個(gè)規(guī)則選擇將進(jìn)入下一代的個(gè)體;按概率Pc進(jìn)行交叉操作；按概率Pm進(jìn)行變異操作;沒有滿足某種停止條件，則轉(zhuǎn)第(2)步，否則進(jìn)入(7)；輸出種群中適應(yīng)度值最優(yōu)的染色體作為問題的滿意解或最優(yōu)解。成功找到種群中適應(yīng)度值最優(yōu)的染色體作為問題的滿意解或最優(yōu)解。若失敗，分析可得失敗原因?yàn)椋弘S機(jī)生成的cities個(gè)城市之間的相互距離、隨機(jī)產(chǎn)生初試群有可能不存在適應(yīng)度值最優(yōu)的染色體實(shí)驗(yàn)總結(jié)及體會(huì)同一問題可能有不同的幾種算法相對(duì)應(yīng)解決：對(duì)于此類旅行者問題，原在數(shù)據(jù)結(jié)構(gòu)和算法課中學(xué)過迪杰斯特拉算法，也可以高效快速的解決給定好初值的最短路徑問題；在本課中，有學(xué)到了新的算法：TSP算法，此算法從遺傳學(xué)角度，開辟了一個(gè)新的視野。通過每次迭代求出的局部最優(yōu)解和最終求出的全局最優(yōu)解。兩種不同的算法可以求解同