利用遺傳算法解決TSP問(wèn)題

1、課程實(shí)驗(yàn)報(bào)告1. 實(shí)驗(yàn)?zāi)康睦眠z傳算法獲得TSP問(wèn)題的近似解。2.實(shí)驗(yàn)要求要求學(xué)生了解遺傳算法解決問(wèn)題的基本流程。對(duì)TSP問(wèn)題有所了解,知道TSP問(wèn)題的難點(diǎn)在什么地方,如何使用遺傳算法來(lái)獲得一個(gè)較好的近似解。3.實(shí)驗(yàn)內(nèi)容已知n個(gè)城市之間的相互距離，現(xiàn)有一個(gè)推銷員必須遍訪這n個(gè)城市，并且每個(gè)城市只能訪問(wèn)一次，最后又必須返回出發(fā)城市。如何安排他對(duì)這些城市的訪問(wèn)次序，可使其旅行路線的總長(zhǎng)度最短？用圖論的術(shù)語(yǔ)來(lái)說(shuō)，假設(shè)有一個(gè)圖g=(v,e)，其中v是頂點(diǎn)集，e是邊集，設(shè)d=(dij)是由頂點(diǎn)i和頂點(diǎn)j之間的距離所組成的距離矩陣，旅行商問(wèn)題就是求出一條通過(guò)所有頂點(diǎn)且每個(gè)頂點(diǎn)只通過(guò)一次的具有最短

2、距離的回路。4.實(shí)驗(yàn)軟硬件環(huán)境基本W(wǎng)indows系統(tǒng)基本運(yùn)行環(huán)境，VS20125. 實(shí)驗(yàn)方案（1）遺傳算法是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過(guò)程的計(jì)算模型，是一種通過(guò)模擬自然進(jìn)化過(guò)程搜索最優(yōu)解的方法遺傳算法的基本運(yùn)算過(guò)程如下：a)初始化：設(shè)置進(jìn)化代數(shù)計(jì)數(shù)器t=0，設(shè)置最大進(jìn)化代數(shù)T，隨機(jī)生成M個(gè)個(gè)體作為初始群體P(0)。b)個(gè)體評(píng)價(jià)：計(jì)算群體P(t)中各個(gè)個(gè)體的適應(yīng)度。c)選擇運(yùn)算:將選擇算子作用于群體。選擇的目的是把優(yōu)化的個(gè)體直接遺傳到下一代或通過(guò)配對(duì)交叉產(chǎn)生新的個(gè)體再遺傳到下一代。選擇操作是建立在群體中個(gè)體的適應(yīng)度評(píng)估基礎(chǔ)上的。d)交叉運(yùn)算：將交叉算子作用于群體。所謂交

3、叉是指把兩個(gè)父代個(gè)體的部分結(jié)構(gòu)加以替換重組而生成新個(gè)體的操作。遺傳算法中起核心作用的就是交叉算子。e)變異運(yùn)算：將變異算子作用于群體。即是對(duì)群體中的個(gè)體串的某些基因座上的基因值作變動(dòng)。群體P(t)經(jīng)過(guò)選擇、交叉、變異運(yùn)算之后得到下一代群體P(t 1)。f)終止條件判斷:若t=T,則以進(jìn)化過(guò)程中所得到的具有最大適應(yīng)度個(gè)體作為最優(yōu)解輸出，終止計(jì)算。（2）用遺傳算法模擬TSP問(wèn)題TSP問(wèn)題及旅行商問(wèn)題,假設(shè)有一個(gè)旅行商人要拜訪n個(gè)城市，他必須選擇所要走的路徑，路徑的限制是每個(gè)城市只能拜訪一次，而且最后要回到原來(lái)出發(fā)的城市。路徑的選擇目標(biāo)是要求得的路徑路程為所有路徑之中的最小值這個(gè)問(wèn)題可分為對(duì)稱旅行商

4、問(wèn)題(dij=dji,任意i,j=1,2,3，,n)和非對(duì)稱旅行商問(wèn)題(dijdji,任意i,j=1,2,3，,n)。 若對(duì)于城市v=v1,v2,v3,vn的一個(gè)訪問(wèn)順序?yàn)閠=(t1,t2,t3,ti,tn),其中tiv(i=1,2,3,n)，且記tn+1= t1，則旅行商問(wèn)題的數(shù)學(xué)模型為： min l=d(t(i),t(i+1) （i=1,n） 旅行商問(wèn)題是一個(gè)典型的組合優(yōu)化問(wèn)題，并且是一個(gè)np難問(wèn)題，其可能的路徑數(shù)目與城市數(shù)目n是成指數(shù)型增長(zhǎng)的，所以一般很難精確地求出其最優(yōu)解，本文采用遺傳算法求其近似解。6.實(shí)驗(yàn)步驟：（1）初始化過(guò)程：用v1,v2,v3,vn代表所選n個(gè)城市。定義整數(shù)po

5、p-size作為染色體的個(gè)數(shù)，并且隨機(jī)產(chǎn)生pop-size個(gè)初始染色體，每個(gè)染色體為1到18的整數(shù)組成的隨機(jī)序列。（2）適應(yīng)度f(wàn)的計(jì)算：對(duì)種群中的每個(gè)染色體vi，計(jì)算其適應(yīng)度，f=d(t(i),t(i+1)。（3）評(píng)價(jià)函數(shù)eval(vi)：用來(lái)對(duì)種群中的每個(gè)染色體vi設(shè)定一個(gè)概率，以使該染色體被選中的可能性與其種群中其它染色體的適應(yīng)性成比例，既通過(guò)輪盤賭，適應(yīng)性強(qiáng)的染色體被選擇產(chǎn)生后臺(tái)的機(jī)會(huì)要大，設(shè)alpha(0,1)，本文定義基于序的評(píng)價(jià)函數(shù)為eval(vi)=alpha*(1-alpha).(i-1) 。（4）選擇過(guò)程：選擇過(guò)程是以旋轉(zhuǎn)賭輪pop-size次為基礎(chǔ)，每次旋轉(zhuǎn)都為新的種群選擇

6、一個(gè)染色體。賭輪是按每個(gè)染色體的適應(yīng)度進(jìn)行選擇染色體的。 step1 、對(duì)每個(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-1 step4、重復(fù)step2和step3共pop-size次，這樣可以得到pop-size個(gè)復(fù)制的染色體。（5）交叉過(guò)程：本文采用常規(guī)單點(diǎn)交叉。為確定交叉操作的父代，從 到pop-size重復(fù)以下過(guò)程：從0，1中產(chǎn)生一個(gè)隨機(jī)數(shù)r，如果r 將所選的父代兩兩組隊(duì)，隨機(jī)產(chǎn)生一個(gè)位置進(jìn)行交叉，如： 8 14 2 13 8 6 3 2 5

7、7 3 4 3 2 4 2 2 1 6 12 3 5 6 8 5 6 3 1 8 5 6 3 3 2 1 1交叉后為： 8 14 2 13 8 6 3 2 5 1 8 5 6 3 3 2 1 1 6 12 3 5 6 8 5 6 3 7 3 4 3 2 4 2 2 1（6）變異過(guò)程：本文采用均勻多點(diǎn)變異。類似交叉操作中選擇父代的過(guò)程，在r選擇多個(gè)染色體vi作為父代。對(duì)每一個(gè)選擇的父代，隨機(jī)選擇多個(gè)位置，使其在每位置按均勻變異（該變異點(diǎn)xk的取值范圍為ukmin,ukmax,產(chǎn)生一個(gè)0，1中隨機(jī)數(shù)r，該點(diǎn)變異為x'k=ukmin+r(ukmax-ukmin)）操作。如： 8 14 2 1

8、3 8 6 3 2 5 7 3 4 3 2 4 2 2 1 變異后： 8 14 2 13 10 6 3 2 2 7 3 4 5 2 4 1 2 1 （7）循環(huán)操作：判斷是否滿足設(shè)定的代數(shù)xzome，否，則跳入適應(yīng)度f(wàn)的計(jì)算；是，結(jié)束遺傳操作，跳出。實(shí)驗(yàn)代碼：#include<stdio.h> #include<string.h> #include<stdlib.h> #include<math.h> #include<time.h> #define cities 10 /城市的個(gè)數(shù) #define MAXX 100/迭代次數(shù) #def

9、ine pc 0.8 /交配概率 #define pm 0.05 /變異概率 #define num 10/種群的大小 int bestsolution;/最優(yōu)染色體 int distancecitiescities;/城市之間的距離 struct group /染色體的結(jié)構(gòu) int citycities;/城市的順序 int adapt;/適應(yīng)度 double p;/在種群中的幸存概率 groupnum,grouptempnum; /隨機(jī)產(chǎn)生cities個(gè)城市之間的相互距離 void init() int i,j; memset(distance,0,sizeof(distance); sr

10、and(unsigned)time(NULL); for(i=0;i<cities;i+) for(j=i+1;j<cities;j+) distanceij=rand()%100; distanceji=distanceij; /打印距離矩陣 printf("城市的距離矩陣如下n"); for(i=0;i<cities;i+) for(j=0;j<cities;j+) printf("%4d",distanceij); printf("n"); /隨機(jī)產(chǎn)生初試群 void groupproduce() int

11、 i,j,t,k,flag; for(i=0;i<num;i+) /初始化 for(j=0;j<cities;j+) groupi.cityj=-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(groupi.cityk=t) flag=0; break; if(flag) groupi.cityj=t; j+; /打印種群基因 printf("初始的種群n&

12、quot;); for(i=0;i<num;i+) for(j=0;j<cities;j+) printf("%4d",groupi.cityj); printf("n"); /評(píng)價(jià)函數(shù),找出最優(yōu)染色體 void pingjia() int i,j; int n1,n2; int sumdistance,biggestsum=0; double biggestp=0; for(i=0;i<num;i+) sumdistance=0; for(j=1;j<cities;j+) n1=groupi.cityj-1; n2=groupi

13、.cityj; sumdistance+=distancen1n2; groupi.adapt=sumdistance; /每條染色體的路徑總和 biggestsum+=sumdistance; /種群的總路徑 /計(jì)算染色體的幸存能力,路勁越短生存概率越大 for(i=0;i<num;i+) groupi.p=1-(double)groupi.adapt/(double)biggestsum; biggestp+=groupi.p; for(i=0;i<num;i+) groupi.p=groupi.p/biggestp; /在種群中的幸存概率,總和為1 /求最佳路勁 bestso

14、lution=0; for(i=0;i<num;i+) if(groupi.p>groupbestsolution.p) bestsolution=i; /打印適應(yīng)度 for(i=0;i<num;i+) printf("染色體%d的路徑之和與生存概率分別為%4d %.4fn",i,groupi.adapt,groupi.p); printf("當(dāng)前種群的最優(yōu)染色體是%d號(hào)染色體n",bestsolution); /選擇 void xuanze() int i,j,temp; double gradientnum;/梯度概率 double

15、 xuanzenum;/選擇染色體的隨機(jī)概率 int xuannum;/選擇了的染色體 /初始化梯度概率 for(i=0;i<num;i+) gradienti=0.0; xuanzei=0.0; gradient0=group0.p; for(i=1;i<num;i+) gradienti=gradienti-1+groupi.p; srand(unsigned)time(NULL); /隨機(jī)產(chǎn)生染色體的存活概率 for(i=0;i<num;i+) xuanzei=(rand()%100); xuanzei/=100; /選擇能生存的染色體 for(i=0;i<num

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

17、grouptemptemp.p; for(j=0;j<cities;j+) groupi.cityj=grouptemptemp.cityj; /用于測(cè)試 /* printf("<->n"); for(i=0;i<num;i+) for(j=0;j<cities;j+) printf("%4d",groupi.cityj); printf("n"); printf("染色體%d的路徑之和與生存概率分別為%4d %.4fn",i,groupi.adapt,groupi.p); */ /交

18、配,對(duì)每個(gè)染色體產(chǎn)生交配概率,滿足交配率的染色體進(jìn)行交配 void jiaopei() int i,j,k,kk; int t;/參與交配的染色體的個(gè)數(shù) int point1,point2,temp;/交配斷點(diǎn) int pointnum; int temp1,temp2; int map1cities,map2cities; double jiaopeipnum;/染色體的交配概率 int jiaopeiflagnum;/染色體的可交配情況 for(i=0;i<num;i+)/初始化 jiaopeiflagi=0; /隨機(jī)產(chǎn)生交配概率 srand(unsigned)time(NULL);

19、 for(i=0;i<num;i+) jiaopeipi=(rand()%100); jiaopeipi/=100; /確定可以交配的染色體 t=0; for(i=0;i<num;i+) if(jiaopeipi<pc) jiaopeiflagi=1; t+; t=t/2*2;/t必須為偶數(shù) /產(chǎn)生t/2個(gè)0-9交配斷點(diǎn) srand(unsigned)time(NULL); temp1=0; /temp1號(hào)染色體和temp2染色體交配 for(i=0;i<t/2;i+) point1=rand()%cities; point2=rand()%cities; for(j=

20、temp1;j<num;j+) if(jiaopeiflagj=1) temp1=j; break; for(j=temp1+1;j<num;j+) if(jiaopeiflagj=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<=poi

21、nt2;k+) map1grouptemp1.cityk=grouptemp2.cityk; map2grouptemp2.cityk=grouptemp1.cityk; /斷點(diǎn)兩邊的基因互換 for(k=0;k<point1;k+) temp=grouptemp1.cityk; grouptemp1.cityk=grouptemp2.cityk; grouptemp2.cityk=temp; for(k=point2+1;k<cities;k+) temp=grouptemp1.cityk; grouptemp1.cityk=grouptemp2.cityk; grouptemp

22、2.cityk=temp; /處理產(chǎn)生的沖突基因 for(k=0;k<point1;k+) for(kk=point1;kk<=point2;kk+) if(grouptemp1.cityk=grouptemp1.citykk) grouptemp1.cityk=map1grouptemp1.cityk; break; for(k=point2+1;k<cities;k+) for(kk=point1;kk<=point2;kk+) if(grouptemp1.cityk=grouptemp1.citykk) grouptemp1.cityk=map1grouptemp

23、1.cityk; break; for(k=0;k<point1;k+) for(kk=point1;kk<=point2;kk+) if(grouptemp2.cityk=grouptemp2.citykk) grouptemp2.cityk=map2grouptemp2.cityk; break; for(k=point2+1;k<cities;k+) for(kk=point1;kk<=point2;kk+) if(grouptemp2.cityk=grouptemp2.citykk) grouptemp2.cityk=map2grouptemp2.cityk; break; temp1=temp2+1; /變異 void bianyi() int i,j; int t; int temp1,temp2,point; double bianyipnum; /染色體的變異概率 int bianyiflagnum;/染色體的變異情況 for(i=0;i<num;i+)/初始化 bianyiflagi=0; /隨機(jī)產(chǎn)生變異概率 srand(unsigned)time(NULL); for(i=0;i<