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

1、精品文檔TSP問題的遺傳算法實驗報告一實驗題目TSP問題的遺傳算法實現(xiàn)二實驗目的熟悉和掌握遺傳算法的基本概念和基本思想；加深對遺傳算法的理解，理解和掌握遺傳算法的各個操作算子；理解和掌握利用遺傳算法進行問題求解的基本技能。三實驗要求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;城市種群，默認出發(fā)

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

3、city,int m) int i,j,t=0;int start,end;for(i=0;iDistancei=0;for(j=1;jcolonyij-1;end=city-colonyij;city-Distancei=city-Distancei+CityDistancestartend;)city-fitnessi=N/(city-Distancei);)2采用的選擇、交叉、變異操作算子的具體操作；void Select(PTSP city)/選擇算子int i,j;double sum=0,r,t;double pPOPSIZE,qPOPSIZE+1;int copeyPOPSIZE

4、CITY_NUM+1;q0 = 0;for (i=0;ifitnessi;for (i=0;ifitnessi/sum;qi+1 = qi+pi;)for (i=0;iPOPSIZE;i+)t = rand()%(10000);r = t/10000;for (j=0;jPOPSIZE;j+)if (rcolonyj;break;)for (i=0;icolonyi = *copeyi;改進啟發(fā)式算法) void AOX(PTSP city,int n,int m)/精品文檔(int ACITY_NUM-1,BCITY_NUM-1;int i,j;int k=1+CROSS_NUM,t=1+C

5、ROSS_NUM;for (i=0;icolonyni+1;Bi = city-colonymi+1;for (i=3;icolonyni-2 = Bi;city-colonymi-2 = Ai;for (i=0;iCITY_NUM-1;i+)(for (j=0;jcolonynk+ = Ai;for (j=0;jcolonymt+ = Bi;判重int check1(int r,int n)/ (int i;for (i=0;in;i+)if (ri = rn) (return true;精品文檔return false;)void Cross(PTSP city,double pc)/交叉

6、概率是pint i;int r20;for (i=0; iPOPSIZE*pc;i+)ri = rand()%(POPSIZE);while (check1(r,i)ri = rand()%(POPSIZE);)for (i=0;icolonynr;city-colonynr = city-colonynt;city-colonynt = c;)void Mutation(PTSP city,double pm)/變異概率是pmint i;int r20;for (i=0; iPOPSIZE*pm;i+)精品文檔ri = rand()%(POPSIZE);while (check1(r,i)ri = rand()%(POPSIZE); XCH(city,ri);3實驗中采用的算法參數(shù)的最佳選擇值是多少。由于我是隨機抽取參加交叉的染色體，沒有選擇性的抽取那些適應度大的染色體，故交叉率pc很難確定最佳最佳值。我的取值是：POPSIZE = 20 PCROSS = 0.6 PMUTATION =