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

1、精品文檔TSP問題的遺傳算法實驗報告一實驗題目TSP問題的遺傳算法實現二實驗目的熟悉和掌握遺傳算法的基本概念和基本思想；加深對遺傳算法的理解，理解和掌握遺傳算法的各個操作算子；理解和掌握利用遺傳算法進行問題求解的基本技能。三實驗要求1 以10/30個結點的TSP問題為例，用遺傳算法加以求解；2掌握遺傳算法的基本原理、各個遺傳操作和算法步驟；3能求出問題最優(yōu)解，若得不出最優(yōu)解，請分析原因；4要求界面顯示每次迭代求出的局部最優(yōu)解和最終求出的全局最優(yō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說明算法中對染色體的編碼方法，適應度函數定義方法；染色體的編碼方法：09 一個排列組合為一條染色體。適應度函數的定義方法：取路徑長度的倒數。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實驗中采用的算法參數的最佳選擇值是多少。由于我是隨機抽取參加交叉的染色體，沒有選擇性的抽取那些適應度大的染色體，故交叉率pc很難確定最佳最佳值。我的取值是：POPSIZE = 20 PCROSS = 0.6 PMUTATION =