利用遺傳算法解決TSP問答

,.課程實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)?zāi)康睦眠z傳算法獲得TSP問題的近似解。2.實(shí)驗(yàn)要求要求學(xué)生了解遺傳算法解決問題的基本流程。對TSP問題有所了解,知道精品文檔放心下載TSP問題的難點(diǎn)在什么地方,如何使用遺傳算法來獲得一個(gè)較好的近似解。感謝閱讀3.實(shí)驗(yàn)內(nèi)容,.已知n個(gè)城市之間的相互距離，現(xiàn)有一個(gè)推銷員必須遍訪這n個(gè)城市，并且每謝謝閱讀個(gè)城市只能訪問一次，最后又必須返回出發(fā)城市。如何安排他對這些城市的訪問精品文檔放心下載次序，可使其旅行路線的總長度最短？用圖論的術(shù)語來說，假設(shè)有一個(gè)圖謝謝閱讀g=(v,e)，其中v是頂點(diǎn)集，e是邊集，設(shè)d=(dij)是由頂點(diǎn)i和頂點(diǎn)j之間的距謝謝閱讀離所組成的距離矩陣，旅行商問題就是求出一條通過所有頂點(diǎn)且每個(gè)頂點(diǎn)只通過精品文檔放心下載一次的具有最短距離的回路。4.實(shí)驗(yàn)軟硬件環(huán)境基本W(wǎng)indows系統(tǒng)基本運(yùn)行環(huán)境，VS2012謝謝閱讀5.實(shí)驗(yàn)方案（1）遺傳算法是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過程的計(jì)算模型，是一種謝謝閱讀通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法遺傳算法的基本運(yùn)算過程如下：a)初始化：設(shè)置進(jìn)化代數(shù)計(jì)數(shù)器t=0，設(shè)置最大進(jìn)化代數(shù)T，隨機(jī)生成M個(gè)個(gè)體作為精品文檔放心下載初始群體P(0)。b)個(gè)體評價(jià)：計(jì)算群體P(t)中各個(gè)個(gè)體的適應(yīng)度。感謝閱讀c)選擇運(yùn)算:將選擇算子作用于群體。選擇的目的是把優(yōu)化的個(gè)體直接遺傳到下一代或謝謝閱讀通過配對交叉產(chǎn)生新的個(gè)體再遺傳到下一代。選擇操作是建立在群體中個(gè)體的適應(yīng)度評估基感謝閱讀礎(chǔ)上的。d)交叉運(yùn)算：將交叉算子作用于群體。所謂交叉是指把兩個(gè)父代個(gè)體的部分結(jié)構(gòu)加以替謝謝閱讀換重組而生成新個(gè)體的操作。遺傳算法中起核心作用的就是交叉算子。精品文檔放心下載,.e)變異運(yùn)算：將變異算子作用于群體。即是對群體中的個(gè)體串的某些基因座上的基因值感謝閱讀作變動。群體P(t)經(jīng)過選擇、交叉、變異運(yùn)算之后得到下一代群體P(t1)。精品文檔放心下載f)終止條件判斷:若t=T,則以進(jìn)化過程中所得到的具有最大適應(yīng)度個(gè)體作為最優(yōu)解輸出，精品文檔放心下載終止計(jì)算。（2）用遺傳算法模擬TSP問題TSP問題及旅行商問題,假設(shè)有一個(gè)旅行商人要拜訪n個(gè)城市，他必須選擇所要走的路感謝閱讀徑，路徑的限制是每個(gè)城市只能拜訪一次，而且最后要回到原來出發(fā)的城市。路徑的選擇目感謝閱讀標(biāo)是要求得的路徑路程為所有路徑之中的最小值這個(gè)問題可分為對稱旅行商問題(dij=dji,,任意i,j=1,2,3，…,n)和非對稱旅行商精品文檔放心下載問題(dij≠dji,,任意i,j=1,2,3，…,n)。精品文檔放心下載若對于城市v={v1,v2,v3,…,vn}的一個(gè)訪問順序?yàn)閠=(t1,t2,t3,…,ti,…,tn),其中感謝閱讀ti∈v(i=1,2,3,…,n)，且記tn+1=t1，則旅行商問題的數(shù)學(xué)模型為：感謝閱讀min l=σd(t(i),t(i+1)) （i=1,…,n）謝謝閱讀旅行商問題是一個(gè)典型的組合優(yōu)化問題，并且是一個(gè)np難問題，其可能的路徑數(shù)謝謝閱讀目與城市數(shù)目n是成指數(shù)型增長的，所以一般很難精確地求出其最優(yōu)解，本文采用遺傳謝謝閱讀算法求其近似解。6.實(shí)驗(yàn)步驟：,.（1）初始化過程：用v1,v2,v3,…,vn代表所選n個(gè)城市。定義整數(shù)pop-size作為染謝謝閱讀色體的個(gè)數(shù)，并且隨機(jī)產(chǎn)生pop-size個(gè)初始染色體，每個(gè)染色體為1到18的整數(shù)組成的感謝閱讀隨機(jī)序列。（2）適應(yīng)度f的計(jì)算：對種群中的每個(gè)染色體vi，計(jì)算其適應(yīng)度，f=σd(t(i),t(i+1))。感謝閱讀（3）評價(jià)函數(shù)eval(vi)：用來對種群中的每個(gè)染色體vi設(shè)定一個(gè)概率，以使該染色體謝謝閱讀被選中的可能性與其種群中其它染色體的適應(yīng)性成比例，既通過輪盤賭，適應(yīng)性強(qiáng)的染色體感謝閱讀被選擇產(chǎn)生后臺的機(jī)會要大，設(shè)alpha∈(0,1)，本文定義基于序的評價(jià)函數(shù)為eval(vi)=al感謝閱讀pha*(1-alpha).^(i-1)。（4）選擇過程：選擇過程是以旋轉(zhuǎn)賭輪pop-size次為基礎(chǔ)，每次旋轉(zhuǎn)都為新的種群感謝閱讀選擇一個(gè)染色體。賭輪是按每個(gè)染色體的適應(yīng)度進(jìn)行選擇染色體的。精品文檔放心下載step1、對每個(gè)染色體vi,計(jì)算累計(jì)概率qi，q0=0;qi=σeval(vj)精品文檔放心下載j=1,…,i;i=1,…,pop-size.step2、從區(qū)間(0,pop-size)中產(chǎn)生一個(gè)隨機(jī)數(shù)r；感謝閱讀step3、若qi-1step4、重復(fù)step2和step3共pop-size次，這樣可以得到pop-size個(gè)復(fù)制的染謝謝閱讀色體。,.（5）交叉過程：本文采用常規(guī)單點(diǎn)交叉。為確定交叉操作的父代，從到pop-size重謝謝閱讀復(fù)以下過程：從[0，1]中產(chǎn)生一個(gè)隨機(jī)數(shù)r，如果r將所選的父代兩兩組隊(duì)，隨機(jī)產(chǎn)生一個(gè)精品文檔放心下載位置進(jìn)行交叉，如：81421386325734324221感謝閱讀6123568563185633211精品文檔放心下載交叉后為：81421386325185633211精品文檔放心下載6123568563734324221精品文檔放心下載（6）變異過程：本文采用均勻多點(diǎn)變異。類似交叉操作中選擇父代的過程，在r選擇謝謝閱讀多個(gè)染色體vi作為父代。對每一個(gè)選擇的父代，隨機(jī)選擇多個(gè)位置，使其在每位置按均勻精品文檔放心下載變異（該變異點(diǎn)xk的取值范圍為[ukmin,ukmax],產(chǎn)生一個(gè)[0，1]中隨機(jī)數(shù)r，該點(diǎn)變異為感謝閱讀x'k=ukmin+r(ukmax-ukmin)）操作。如：謝謝閱讀81421386325734324221謝謝閱讀變異后：814213106322734524121謝謝閱讀（7）循環(huán)操作：判斷是否滿足設(shè)定的代數(shù)xzome，否，則跳入適應(yīng)度f的計(jì)算；是，感謝閱讀結(jié)束遺傳操作，跳出。實(shí)驗(yàn)代碼：#include<stdio.h>,.#include<string.h>#include<stdlib.h>#include<math.h>#include<time.h>#definecities10 //城市的個(gè)數(shù)#defineMAXX100//迭代次數(shù)#definepc0.8//交配概率#definepm0.05//變異概率#definenum10//種群的大小intbestsolution;//最優(yōu)染色體intdistance[cities][cities];//城市之間的距離感謝閱讀structgroup //染色體的結(jié)構(gòu){intcity[cities];//城市的順序intadapt;//適應(yīng)度doublep;//在種群中的幸存概率}group[num],grouptemp[num];感謝閱讀//隨機(jī)產(chǎn)生cities個(gè)城市之間的相互距離voidinit(){inti,j;memset(distance,0,sizeof(distance));謝謝閱讀,.srand((unsigned)time(NULL));謝謝閱讀for(i=0;i<cities;i++){for(j=i+1;j<cities;j++){distance[i][j]=rand()%100;感謝閱讀distance[j][i]=distance[i][j];精品文檔放心下載}}//打印距離矩陣printf("城市的距離矩陣如下\n");for(i=0;i<cities;i++){for(j=0;j<cities;j++)printf("%4d",distance[i][j]);感謝閱讀printf("\n");}}//隨機(jī)產(chǎn)生初試群voidgroupproduce(){inti,j,t,k,flag;,.for(i=0;i<num;i++) //初始化for(j=0;j<cities;j++)group[i].city[j]=-1;srand((unsigned)time(NULL));感謝閱讀for(i=0;i<num;i++){//產(chǎn)生10個(gè)不相同的數(shù)字for(j=0;j<cities;){t=rand()%cities;flag=1;for(k=0;k<j;k++){if(group[i].city[k]==t){flag=0;break;}}if(flag){group[i].city[j]=t;,.j++;}}}//打印種群基因printf("初始的種群\n");for(i=0;i<num;i++){for(j=0;j<cities;j++)printf("%4d",group[i].city[j]);感謝閱讀printf("\n");}}//評價(jià)函數(shù),找出最優(yōu)染色體voidpingjia(){inti,j;intn1,n2;intsumdistance,biggestsum=0;感謝閱讀doublebiggestp=0;for(i=0;i<num;i++){,.sumdistance=0;for(j=1;j<cities;j++){n1=group[i].city[j-1];n2=group[i].city[j];sumdistance+=distance[n1][n2];精品文檔放心下載}group[i].adapt=sumdistance;//每條染色體的路徑總和biggestsum+=sumdistance;//種群的總路徑精品文檔放心下載}//計(jì)算染色體的幸存能力,路勁越短生存概率越大for(i=0;i<num;i++){group[i].p=1-(double)group[i].adapt/(double)biggestsum;精品文檔放心下載biggestp+=group[i].p;}for(i=0;i<num;i++)group[i].p=group[i].p/biggestp; //在種群中的幸存概率,總和為1感謝閱讀//求最佳路勁bestsolution=0;for(i=0;i<num;i++)if(group[i].p>group[bestsolution].p)謝謝閱讀,.bestsolution=i;//打印適應(yīng)度for(i=0;i<num;i++)printf("染色體%d的路徑之和與生存概率分別感謝閱讀為%4d %.4f\n",i,group[i].adapt,group[i].p);謝謝閱讀printf("當(dāng)前種群的最優(yōu)染色體是%d號染色體\n",bestsolution);謝謝閱讀}//選擇voidxuanze(){inti,j,temp;doublegradient[num];//梯度概率感謝閱讀doublexuanze[num];//選擇染色體的隨機(jī)概率感謝閱讀intxuan[num];//選擇了的染色體//初始化梯度概率for(i=0;i<num;i++){gradient[i]=0.0;xuanze[i]=0.0;}gradient[0]=group[0].p;for(i=1;i<num;i++),.gradient[i]=gradient[i-1]+group[i].p;感謝閱讀srand((unsigned)time(NULL));精品文檔放心下載//隨機(jī)產(chǎn)生染色體的存活概率for(i=0;i<num;i++){xuanze[i]=(rand()%100);xuanze[i]/=100;}//選擇能生存的染色體for(i=0;i<num;i++){for(j=0;j<num;j++){if(xuanze[i]<gradient[j]){xuan[i]=j;//第i個(gè)位置存放第j個(gè)染色體謝謝閱讀break;}}}//拷貝種群for(i=0;i<num;i++),.{grouptemp[i].adapt=group[i].adapt;精品文檔放心下載grouptemp[i].p=group[i].p;謝謝閱讀for(j=0;j<cities;j++)grouptemp[i].city[j]=group[i].city[j];感謝閱讀}//數(shù)據(jù)更新for(i=0;i<num;i++){temp=xuan[i];group[i].adapt=grouptemp[temp].adapt;精品文檔放心下載group[i].p=grouptemp[temp].p;精品文檔放心下載for(j=0;j<cities;j++)group[i].city[j]=grouptemp[temp].city[j];感謝閱讀}//用于測試/*printf("<------------------------------->\n");精品文檔放心下載for(i=0;i<num;i++){for(j=0;j<cities;j++)printf("%4d",group[i].city[j]);謝謝閱讀,.printf("\n");printf("染色體%d的路徑之和與生存概率分別謝謝閱讀為%4d %.4f\n",i,group[i].adapt,group[i].p);感謝閱讀}*/}//交配,對每個(gè)染色體產(chǎn)生交配概率,滿足交配率的染色體進(jìn)行交配精品文檔放心下載void jiaopei(){inti,j,k,kk;intt;//參與交配的染色體的個(gè)數(shù)intpoint1,point2,temp;//交配斷點(diǎn)精品文檔放心下載intpointnum;inttemp1,temp2;intmap1[cities],map2[cities];精品文檔放心下載doublejiaopeip[num];//染色體的交配概率感謝閱讀intjiaopeiflag[num];//染色體的可交配情況精品文檔放心下載for(i=0;i<num;i++)//初始化jiaopeiflag[i]=0;//隨機(jī)產(chǎn)生交配概率srand((unsigned)time(NULL));謝謝閱讀for(i=0;i<num;i++),.{jiaopeip[i]=(rand()%100);jiaopeip[i]/=100;}//確定可以交配的染色體t=0;for(i=0;i<num;i++){if(jiaopeip[i]<pc){jiaopeiflag[i]=1;t++;}}t=t/2*2;//t必須為偶數(shù)//產(chǎn)生t/2個(gè)0-9交配斷點(diǎn)srand((unsigned)time(NULL));感謝閱讀temp1=0;//temp1號染色體和temp2染色體交配for(i=0;i<t/2;i++){point1=rand()%cities;,.point2=rand()%cities;for(j=temp1;j<num;j++)if(jiaopeiflag[j]==1){temp1=j;break;}for(j=temp1+1;j<num;j++)if(jiaopeiflag[j]==1){temp2=j;break;}//進(jìn)行基因交配if(point1>point2)//保證point1<=point2精品文檔放心下載{temp=point1;point1=point2;point2=temp;}memset(map1,-1,sizeof(map1));精品文檔放心下載memset(map2,-1,sizeof(map2));精品文檔放心下載,.//斷點(diǎn)之間的基因產(chǎn)生映射for(k=point1;k<=point2;k++)精品文檔放心下載{map1[group[temp1].city[k]]=group[temp2].city[k];精品文檔放心下載map2[group[temp2].city[k]]=group[temp1].city[k];感謝閱讀}//斷點(diǎn)兩邊的基因互換for(k=0;k<point1;k++){temp=group[temp1].city[k];謝謝閱讀group[temp1].city[k]=group[temp2].city[k];精品文檔放心下載group[temp2].city[k]=temp;謝謝閱讀}for(k=point2+1;k<cities;k++)精品文檔放心下載{temp=group[temp1].city[k];感謝閱讀group[temp1].city[k]=group[temp2].city[k];謝謝閱讀group[temp2].city[k]=temp;感謝閱讀}//處理產(chǎn)生的沖突基因for(k=0;k<point1;k++){,.for(kk=point1;kk<=point2;kk++)謝謝閱讀if(group[temp1].city[k]==group[temp1].city[kk])精品文檔放心下載{group[temp1].city[k]=map1[group[temp1].city[k]];精品文檔放心下載break;}}for(k=point2+1;k<cities;k++)謝謝閱讀{for(kk=point1;kk<=point2;kk++)謝謝閱讀if(group[temp1].city[k]==group[temp1].city[kk])感謝閱讀{group[temp1].city[k]=map1[group[temp1].city[k]];精品文檔放心下載break;}}for(k=0;k<point1;k++){for(kk=point1;kk<=point2;kk++)精品文檔放心下載if(group[temp2].city[k]==group[temp2].city[kk])感謝閱讀{group[temp2].city[k]=map2[group[temp2].city[k]];感謝閱讀,.break;}}for(k=point2+1;k<cities;k++)謝謝閱讀{for(kk=point1;kk<=point2;kk++)感謝閱讀if(group[temp2].city[k]==group[temp2].city[kk])謝謝閱讀{group[temp2].city[k]=map2[group[temp2].city[k]];精品文檔放心下載break;}}temp1=temp2+1;}}//變異voidbianyi(){inti,j;intt;inttemp1,temp2,point;doublebianyip[num];//染色體的變異概率精品文檔放心下載,.intbianyiflag[num];//染色體的變異情況感謝閱讀for(i=0;i<num;i++)//初始化bianyiflag[i]=0;//