利用遺傳算法解決TSP問答

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

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

3、。d)交叉運算：將交叉算子作用于群體。所謂交叉是指把兩個父代個體的部分結(jié)構(gòu)加以替換重組而生成新個體的操作。遺傳算法中起核心作用的就是交叉算子。(1 )初始化過程：用 v1,v2,v3,vn代表所選n個城市。定義整數(shù)pop-size 作為染作變動。P(t 1)。群體P(t)經(jīng)過選擇、交叉、變異運算之后得到下一代群體f)終止條件判斷：若t=T,則以進(jìn)化過程中所得到的具有最大適應(yīng)度個體作為最優(yōu)解輸出,終止計算。(2 )用遺傳算法模擬 TSP問題TSP問題及旅行商問題，假設(shè)有一個旅行商人要拜訪 n個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最后要回到原來出發(fā)的城市。路徑的選擇

4、目 標(biāo)是要求得的路徑路程為所有路徑之中的最小值這個問題可分為對稱旅行商問題(dij=dji,任意i,j=1,2,3，,n)和非對稱旅行商問題(dij 勿ji” 任意 i,j=1,2,3，,n)。若對于城市v=v1,v2,v3,vn的一個訪問順序為t=(t1,t2,t3,ti,tn),其中ti v(i=1,2,3，,n)，且記tn +1= t1，則旅行商問題的數(shù)學(xué)模型為:minl= od(t(i),t(i+1)(i=1,n)旅行商問題是一個典型的組合優(yōu)化問題，并且是一個np難問題，其可能的路徑數(shù)與城市數(shù)目n是成指數(shù)型增長的，所以一般很難精確地求出其最優(yōu)解，本文采用遺傳 算法求其近似解。6. 實驗

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

6、個染色體。賭輪是按每個染色體的適應(yīng)度進(jìn)行選擇染色體的。step1、對每個染色體 vi,計算累計概率 qi , q0=0;qi=ffeval(vj)j=1,i;i=1,pop-size.ste p2、從區(qū)間(0,pop-size)中產(chǎn)生一個隨機(jī)數(shù) r;ste p3、若 qi-1ste p4、重復(fù)step2和step3共pop-size 次，這樣可以得到pop-size 個復(fù)制的染 色體。(5)交叉過程：本文采用常規(guī)單點交叉。為確定交叉操作的父代，從至U pop-size 重復(fù)以下過程：從0, 1中產(chǎn)生一個隨機(jī)數(shù)r，如果r將所選的父代兩兩組隊，隨機(jī)產(chǎn)生一個位置進(jìn)行交叉，如:8 14 2 13 8

7、6 3 2 5 7 3 4 3 2 4 2 2 16 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 16 12 3 5 6 8 5 6 3 7 3 4 3 2 4 2 2 1r選擇(6)變異過程：本文采用均勻多點變異。類似交叉操作中選擇父代的過程，在多個染色體vi作為父代。對每一個選擇的父代，隨機(jī)選擇多個位置，使其在每位置按均勻 變異(該變異點xk的取值范圍為ukmin,ukmax,產(chǎn)生一個0 , 1中隨機(jī)數(shù)r，該點變異為)操作。如:x'k=ukm in+r(ukmax-ukm in

8、)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è)定的代數(shù)xzome，否，則跳入適應(yīng)度f的計算；是,結(jié)束遺傳操作，跳出。實驗代碼:#in cludevstdio.h>#include<string.h>#include<stdlib.h>#include<math.h>#include<time.h>#define cities 10 / 城市的個數(shù)#define MAXX 100/ 迭代次數(shù)#defi

9、ne 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 個城市之間的相互距離void init()int i,j;memset(distance,0,sizeof(distance);srand(uns

10、igned)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 i,j,t,k,flag;f

11、or(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 個不相同的數(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");for(i=0;i<num;i+)

12、for(j=0;j<cities;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;i<num;i+)sumdistance=0;for(j=1;j<cities;j+)n1=groupi.cityj-1;n2=groupi.cityj;每條染色體的路徑總和種群的總路徑sumdistance+=dis

13、tancen1n2;groupi.adapt=sumdistance; /biggestsum+=sumdistance; / 計算染色體的幸存能力 ,路勁越短生存概率越大 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/ 求最佳路勁bestsolution=0;if(groupi.p>groupbestsolution.p)b

14、estsolution=i;/ 打印適應(yīng)度for(i=0;i<num;i+)printf（" 染色體 %d 的路徑之和與生存概率分別為 %4d %.4fn",i,groupi.adapt,groupi.p);printf（" 當(dāng)前種群的最優(yōu)染色體是 %d 號染色體 n",bestsolution）;/ 選擇void xuanze()int i,j,temp;double gradientnum;/ 梯度概率double xuanzenum;/ 選擇染色體的隨機(jī)概率int xuannum;/ 選擇了的染色體/ 初始化梯度概率for(i=0;i<

15、num;i+)gradienti=0.0;xuanzei=0.0;gradient0=group0.p;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;i+)for(j=0;j<num;j+)if(xuanzei<gradientj)xuani=j; / 第 i 個位置存放第 j 個染色體break;/ 拷貝種群for(i=3;

16、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=grouptemptemp.p;for(j=0;j<cities;j+) groupi.cityj=grouptemptemp.cityj;/ 用于測試/*>n");printf(&q

17、uot;<for(i=0;i<num;i+)printf("%4d",groupi.cityj);for(j=0;j<cities;j+)printf("n");printf(" 染色體 %d 的路徑之和與生存概率分別為 %4d %.4fn",i,groupi.adapt,groupi.p);*/ 交配 ,對每個染色體產(chǎn)生交配概率 ,滿足交配率的染色體進(jìn)行交配 void jiaopei()int i,j,k,kk;int t;/ 參與交配的染色體的個數(shù)int point1,point2,temp;/ 交配斷點int

18、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);for(i=0;i<num;i+)jiaopeipi=(rand()%100);jiaopeipi/=100;/ 確定可以交配的染色體t=0;for(i=0;i<num;i+)if(jiaopeipi<pc)j

19、iaopeiflagi=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;i<t/2;i+)point1=rand()%cities;point2=rand()%cities;for(j=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(p

20、oint1>point2) / 保證 point1<=point2temp=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;k<point1;k+)temp=grouptemp1

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

22、uptemp1.cityk;break;for(k=point2+1;k<cities;k+)for(kk=point1;kk<=point2;kk+) if(grouptemp1.cityk=grouptemp1.citykk)grouptemp1.cityk=map1grouptemp1.cityk;break;for(k=0;k<point1;k+)for(kk=point1;kk<=point2;kk+) if(grouptemp2.cityk=grouptemp2.citykk)grouptemp2.cityk=map2grouptemp2.cityk;bre

23、ak;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+)/ 初始化bian

24、yiflagi=0;/ 隨機(jī)產(chǎn)生變異概率srand(unsigned)time(NULL);for(i=0;i<num;i+)bianyipi=(rand()%100);bianyipi/=100;/ 確定可以變異的染色體t=0;for(i=0;i<num;i+)if(bianyipi<pm)bianyiflagi=1;t+;/ 變異操作 ,即交換染色體的兩個節(jié)點srand(unsigned)time(NULL);for(i=0;i<num;i+)if(bianyiflagi=1)temp1=rand()%10;temp2=rand()%10;point=groupi.

25、citytemp1;groupi.citytemp1=groupi.citytemp2;groupi.citytemp2=point;int main()int i,j,t;init();groupproduce();/ 初始種群評價pingjia();t=0;while(t+<MAXX)xuanze();/jiaopei();bianyi();pingjia();/ 最終種群的評價printf（"n 輸出最終的種群評價 n"）;for(i=0;i<num;i+)for(j=0;j<cities;j+)printf("%4d",grou

26、pi.cityj);printf(" adapt:%4d, p:%.4fn",groupi.adapt,groupi.p);printf(" 最優(yōu)解為 %d 號染色體 n",bestsolution);return 0;7.實驗結(jié)果i" : D；佼習(xí)機(jī)試tsp.g=,國 n0.10330.10330.09560.10220.10330-10340.095?0.09570.1023 0-0?57 0.1023 0.1034e-10340-09570.10230.1028B.103S0.Q966e-e?G66.10380.09660.10380.1

27、0200.09660.Q9660.1028B.1038O.Q7660-10283.Q9G6B.10386.Q7660.10380.09G66.Q7560.0?56i 4z?y/y4ziiisiiisi£ii¥(siiiiiii 砒礫概髒襯嘅號楓祗概鷹楓祗嘅嘅號既嘅苞嘅嘅號概哉嘅粧概哉嘅恍嘅嘅號爺粧爺 存存存存存一 存存存存存存存存廳存存存迂暮存存 生生生生生生生生生生生生生牛生生生生主生生®生生生生生生生主生 與與與與與與抽與與與與與與與與與與邛與與與與與與與與與與前與與與與與與與JW與與與 nu nu _u nu nu cn-tJU nununununununu

28、nMnn 口XU nMnnnununnnnunun" 口 4JU n nu nu n n n -u nu nu nu.sl_- nu nu nu 之之之之之之；之之之之之之之之之之肱懇N之之之之之之之之加之之亠上之之之亠二之之之畛之之之 衛(wèi)上 c-y D-y 衛(wèi)上 _n-t4 上 n-ti c-ti D-tl 上 n-t n-ti £ 芷-_芒0-!4 n-y n-y ¥ n-y n-y cm n-y n-y-CHZl n-y n-H n-y CH=i n-y n-ti 住 £ 衛(wèi) n-y £nJTr JtTJTl.fTrJTrImJTTJTT

29、JTr.fTTJTT'QJJEnLEJnjulfrlr/Yr.rrr.rrrJvrJvr.rrr.fvTJVrJvrlJrr.Yr.tnJrrJvr.fY7 Jrrjrrjrr 寸mJYI 4 5 & 7 8 9 昔 012345 & 7s? ? 012345 & 7&?s-012345 & 789 0 12 色邑&日 色邑前色包邑色邑包包邑邑包"蹙邑色包電邑色 包各懸魚邑 色魚包魚色包包】 駁色包 i梁甥尻雪雜迅籍壽班蕖瓷雪染染瓷率染養(yǎng)Bmn畫査査集査蠻査畫雪罷橐2 10 24 8 9 43 6 3 3211010221048898944893663 & 3736362112120119 4-88484-988336636336s102101212189489848486336363636T 1CO OS6 6LD;夾習(xí)嘰Stsp.exeI 0 S孚概概嘅概酈鏘概概概啻嘅概楓嘅楓嘅口 B存存存存存存存存存存存存存存存岳 生生生生生生生生55生生生生生生生生譚 與與與與與與與與與與與與與與與與與與彌 Q