TSP問題的遺傳算法實驗報告

1、精品文檔TSP 問題的遺傳算法實驗報告一實驗題目TSP問題的遺傳算法實現(xiàn)二實驗?zāi)康?熟悉和掌握遺傳算法的基本概念和基本思想；2加深對遺傳算法的理解，理解和掌握遺傳算法的各個操作算子；3理解和掌握利用遺傳算法進行問題求解的基本技能。三實驗要求1以10/30個結(jié)點的TSP問題為例，用遺傳算法加以求解；2掌握遺傳算法的基本原理、各個遺傳操作和算法步驟；3能求出問題最優(yōu)解，若得不出最優(yōu)解，請分析原因；4要求界面顯示每次迭代求出的局部最優(yōu)解和最終求出的全局最優(yōu)解。四數(shù)據(jù)結(jié)構(gòu)請說明染色體個體和群體的定義方法。typedef structint colonyPOPSIZECITY_NUM+1; 城市種群，默

2、認(rèn)出發(fā)城市編號為0,則城市編號的最后一個城市還應(yīng)該為0每CITY_NUM個城市的排列組合為一個染色體double fitnessPOPSIZE; 路徑適應(yīng)值double DistancePOPSIZE; 路徑實際長度int BestRooti ngCITY_NUM+1; 最優(yōu)城市路徑序列double BestFit ness;/最優(yōu)路徑適應(yīng)值double BestValue;/最優(yōu)路徑長度TSP,*PTSP;五實驗算法1說明算法中對染色體的編碼方法，適應(yīng)度函數(shù)定義方法；染色體的編碼方法：09一個排列組合為一條染色體。適應(yīng)度函數(shù)的定義方法：取路徑長度的倒數(shù)。void CalFit ness(PT

3、SP city,i nt m)int i,j,t=0;int start,e nd;for(i=0;iDista ncei=0;for(j=1;jco Ion yij-1;e nd=city-co Ion yij;city-Dista ncei=city-Dista ncei+CityDista ncestarte nd;city-fit nessi=N/(city-Dista ncei);2采用的選擇、交叉、變異操作算子的具體操作；void Select(PTSP city)/選擇算子int i,j;double sum=0,r,t;double pPOPSIZE,qPOPSIZE+1;in

4、t copeyPOPSIZECITY_NUM+1;q0 = 0;for (i=0;ifit nessi;for (i=0;ifit nessi/sum;qi+1 = qi+pi;for (i=0;iPOPSIZE;i+)t = ran d()%(10000);r = t/10000;for (j=O;jPOPSIZE;j+)if (rco lon yj;break;for (i=0;ico lon yi = *copeyi;精品文檔void AOX(PTSP city,i nt n,i nt m)/改進啟發(fā)式算法int ACITY_NUM-1,BCITY_NUM-1;int i,j；int k

5、=1+CR0SS_NUM,t=1+CR0SS_NUM;for (i=0;icolo ny n i+1;Bi = city-colo nymi+1;for (i=3;icolo ny ni-2 = Bi;city-colo nymi-2 = Ai;for (i=0;iCITY_NUM-1;i+)for (j=O;jcolo ny nk+ = Ai;for (j=0;jcolo nymt+ = Bi;int check1(int r,int n)/ int i;for (i=0;i n;i+)if (ri = rn)return true;判重精品文檔return false;void Cross

6、(PTSP city,double pc)/交叉概率是pint i;int r20;for (i=0; iPOPSIZE*pc;i+)ri = ran d()%(POPSIZE); while (check1(r,i)ri = ran d()%(POPSIZE); for (i=0;ico lonyn r;city-co lonyn r = city-co lonyn t; city-co lonyn t = c;void Mutation(PTSP city,double pm) /變異概率是pmint i;int r20;for (i=0; iPOPSIZE*pm;i+)精品文檔0ri =

7、 ran d()%(POPSIZE); while (check1(r,i)ri = ran d()%(POPSIZE); XCH(city,ri);3實驗中采用的算法參數(shù)的最佳選擇值是多少。由于我是隨機抽取參加交叉的染色體，沒有選擇性的抽取那些適應(yīng)度大的染色體，故交叉率pc很難確定最佳最佳值。我的取值是：POPSIZE = 20 PCROSS = 0.6 PMUTATION = 0.05六實驗結(jié)果1要求有實驗運行結(jié)果截圖，以及必要的說明;01394&區(qū)畧怨厚已的局部最優(yōu)豁好 巒倏1最君出器局話最: 幽徑描懷婦下*0317S946S2聲密務(wù)搏出的局部最優(yōu)路徑長度231.4708031769&2選代丄3反后得到蘭局最ft路徑咬龍：175.302076H3549?fel Pres