利用遺傳算法解決TSP問題.doc

課程實驗報告1.實驗目的利用遺傳算法獲得TSP問題的近似解。2.實驗要求要求學生了解遺傳算法解決問題的基本流程。對TSP問題有所了解,知道TSP問題的難點在什么地方,如何使用遺傳算法來獲得一個較好的近似解。3.實驗內(nèi)容已知n個城市之間的相互距離，現(xiàn)有一個推銷員必須遍訪這n個城市，并且每個城市只能訪問一次，最后又必須返回出發(fā)城市。如何安排他對這些城市的訪問次序，可使其旅行路線的總長度最短？用圖論的術語來說，假設有一個圖g=(v,e)，其中v是頂點集，e是邊集，設d=(dij)是由頂點i和頂點j之間的距離所組成的距離矩陣，旅行商問題就是求出一條通過所有頂點且每個頂點只通過一次的具有最短距離的回路。4.實驗軟硬件環(huán)境基本W(wǎng)indows系統(tǒng)基本運行環(huán)境，VS20125. 實驗方案（1）遺傳算法是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優(yōu)解的方法遺傳算法的基本運算過程如下：a)初始化：設置進化代數(shù)計數(shù)器t=0，設置最大進化代數(shù)T，隨機生成M個個體作為初始群體P(0)。b)個體評價：計算群體P(t)中各個個體的適應度。c)選擇運算:將選擇算子作用于群體。選擇的目的是把優(yōu)化的個體直接遺傳到下一代或通過配對交叉產(chǎn)生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的適應度評估基礎上的。d)交叉運算：將交叉算子作用于群體。所謂交叉是指把兩個父代個體的部分結構加以替換重組而生成新個體的操作。遺傳算法中起核心作用的就是交叉算子。e)變異運算：將變異算子作用于群體。即是對群體中的個體串的某些基因座上的基因值作變動。群體P(t)經(jīng)過選擇、交叉、變異運算之后得到下一代群體P(t 1)。f)終止條件判斷:若t=T,則以進化過程中所得到的具有最大適應度個體作為最優(yōu)解輸出，終止計算。（2）用遺傳算法模擬TSP問題TSP問題及旅行商問題,假設有一個旅行商人要拜訪n個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最后要回到原來出發(fā)的城市。路徑的選擇目標是要求得的路徑路程為所有路徑之中的最小值這個問題可分為對稱旅行商問題(dij=dji,任意i,j=1,2,3，,n)和非對稱旅行商問題(dijdji,任意i,j=1,2,3，,n)。 若對于城市v=v1,v2,v3,vn的一個訪問順序為t=(t1,t2,t3,ti,tn),其中tiv(i=1,2,3,n)，且記tn+1= t1，則旅行商問題的數(shù)學模型為： min l=d(t(i),t(i+1) （i=1,n） 旅行商問題是一個典型的組合優(yōu)化問題，并且是一個np難問題，其可能的路徑數(shù)目與城市數(shù)目n是成指數(shù)型增長的，所以一般很難精確地求出其最優(yōu)解，本文采用遺傳算法求其近似解。6.實驗步驟：（1）初始化過程：用v1,v2,v3,vn代表所選n個城市。定義整數(shù)pop-size作為染色體的個數(shù)，并且隨機產(chǎn)生pop-size個初始染色體，每個染色體為1到18的整數(shù)組成的隨機序列。（2）適應度f的計算：對種群中的每個染色體vi，計算其適應度，f=d(t(i),t(i+1)。（3）評價函數(shù)eval(vi)：用來對種群中的每個染色體vi設定一個概率，以使該染色體被選中的可能性與其種群中其它染色體的適應性成比例，既通過輪盤賭，適應性強的染色體被選擇產(chǎn)生后臺的機會要大，設alpha(0,1)，本文定義基于序的評價函數(shù)為eval(vi)=alpha*(1-alpha).(i-1) 。（4）選擇過程：選擇過程是以旋轉賭輪pop-size次為基礎，每次旋轉都為新的種群選擇一個染色體。賭輪是按每個染色體的適應度進行選擇染色體的。 step1 、對每個染色體vi,計算累計概率qi，q0=0;qi=eval(vj) j=1,i;i=1,pop-size. step2、從區(qū)間(0,pop-size)中產(chǎn)生一個隨機數(shù)r； step3、若qi-1 step4、重復step2和step3共pop-size次，這樣可以得到pop-size個復制的染色體。（5）交叉過程：本文采用常規(guī)單點交叉。為確定交叉操作的父代，從 到pop-size重復以下過程：從0，1中產(chǎn)生一個隨機數(shù)r，如果r 將所選的父代兩兩組隊，隨機產(chǎn)生一個位置進行交叉，如： 8 14 2 13 8 6 3 2 5 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）變異過程：本文采用均勻多點變異。類似交叉操作中選擇父代的過程，在r選擇多個染色體vi作為父代。對每一個選擇的父代，隨機選擇多個位置，使其在每位置按均勻變異（該變異點xk的取值范圍為ukmin,ukmax,產(chǎn)生一個0，1中隨機數(shù)r，該點變異為xk=ukmin+r(ukmax-ukmin)）操作。如： 8 14 2 13 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ù)xzome，否，則跳入適應度f的計算；是，結束遺傳操作，跳出。實驗代碼：#include #include #include #include #include #define cities 10 /城市的個數(shù) #define MAXX 100/迭代次數(shù) #define pc 0.8 /交配概率 #define pm 0.05 /變異概率 #define num 10/種群的大小 int bestsolution;/最優(yōu)染色體 int distancecitiescities;/城市之間的距離 struct group /染色體的結構 int citycities;/城市的順序 int adapt;/適應度 double p;/在種群中的幸存概率 groupnum,grouptempnum; /隨機產(chǎn)生cities個城市之間的相互距離 void init() int i,j; memset(distance,0,sizeof(distance); srand(unsigned)time(NULL); for(i=0;icities;i+) for(j=i+1;jcities;j+) distanceij=rand()%100; distanceji=distanceij; /打印距離矩陣 printf(城市的距離矩陣如下n); for(i=0;icities;i+) for(j=0;jcities;j+) printf(%4d,distanceij); printf(n); /隨機產(chǎn)生初試群 void groupproduce() int i,j,t,k,flag; for(i=0;inum;i+) /初始化 for(j=0;jcities;j+) groupi.cityj=-1; srand(unsigned)time(NULL); for(i=0;inum;i+) /產(chǎn)生10個不相同的數(shù)字 for(j=0;jcities;) t=rand()%cities; flag=1; for(k=0;kj;k+) if(groupi.cityk=t) flag=0; break; if(flag) groupi.cityj=t; j+; /打印種群基因 printf(初始的種群n); for(i=0;inum;i+) for(j=0;jcities;j+) printf(%4d,groupi.cityj); printf(n); /評價函數(shù),找出最優(yōu)染色體 void pingjia() int i,j; int n1,n2; int sumdistance,biggestsum=0; double biggestp=0; for(i=0;inum;i+) sumdistance=0; for(j=1;jcities;j+) n1=groupi.cityj-1; n2=groupi.cityj; sumdistance+=distancen1n2; groupi.adapt=sumdistance; /每條染色體的路徑總和 biggestsum+=sumdistance; /種群的總路徑 /計算染色體的幸存能力,路勁越短生存概率越大 for(i=0;inum;i+) groupi.p=1-(double)groupi.adapt/(double)biggestsum; biggestp+=groupi.p; for(i=0;inum;i+) groupi.p=groupi.p/biggestp; /在種群中的幸存概率,總和為1 /求最佳路勁 bestsolution=0; for(i=0;igroupbestsolution.p) bestsolution=i; /打印適應度 for(i=0;inum;i+) printf(染色體%d的路徑之和與生存概率分別為%4d %.4fn,i,groupi.adapt,groupi.p); printf(當前種群的最優(yōu)染色體是%d號染色體n,bestsolution); /選擇 void xuanze() int i,j,temp; double gradientnum;/梯度概率 double xuanzenum;/選擇染色體的隨機概率 int xuannum;/選擇了的染色體 /初始化梯度概率 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); /隨機產(chǎn)生染色體的存活概率 for(i=0;inum;i+) xuanzei=(rand()%100); xuanzei/=100; /選擇能生存的染色體 for(i=0;inum;i+) for(j=0;jnum;j+) if(xuanzeigradientj) xuani=j; /第i個位置存放第j個染色體 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.cityj; /用于測試 /* printf(n); for(i=0;inum;i+) for(j=0;jcities;j+) printf(%4d,groupi.cityj); printf(n); printf(染色體%d的路徑之和與生存概率分別為%4d %.4fn,i,groupi.adapt,groupi.p); */ /交配,對每個染色體產(chǎn)生交配概率,滿足交配率的染色體進行交配 void jiaopei() int i,j,k,kk; int t;/參與交配的染色體的個數(shù) int point1,point2,temp;/交配斷點 int pointnum; int temp1,temp2; int map1cities,map2cities; double jiaopeipnum;/染色體的交配概率 int jiaopeiflagnum;/染色體的可交配情況 for(i=0;inum;i+)/初始化 jiaopeiflagi=0; /隨機產(chǎn)生交配概率 srand(unsigned)time(NULL); for(i=0;inum;i+) jiaopeipi=(rand()%100); jiaopeipi/=100; /確定可以交配的染色體 t=0; for(i=0;inum;i+) if(jiaopeipipc) jiaopeiflagi=1; t+; t=t/2*2;/t必須為偶數(shù) /產(chǎn)生t/2個0-9交配斷點 srand(unsigned)time(NULL); temp1=0; /temp1號染色體和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=point2 temp=point1; point1=point2; point2=temp; memset(map1,-1,sizeof(map1); memset(map2,-1,sizeof(map2); /斷點之間的基因產(chǎn)生映射 for(k=point1;k=point2;k+) map1grouptemp1.cityk=grouptemp2.cityk; map2grouptemp2.cityk=grouptemp1.cityk; /斷點兩邊的基因互換 for(k=0;kpoint1;k+) temp=grouptemp1.cityk; grouptemp1.cityk=grouptemp2.cityk; grouptemp2.cityk=temp; for(k=point2+1;kcities;k+) temp=grouptemp1.cityk; grouptemp1.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=map1grouptemp1.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=temp2+1; /變異 void bianyi() int i,j; int t; int temp1,temp2,point; double bianyipnum; /染色體的變異概率 int bianyiflagnum;/染色體的變異情況 for(i=0;inum;i+)/初始化 bianyiflagi=0; /隨機產(chǎn)生變異概率 srand(unsigned)time(NUL