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

TSP問題的遺傳算法實驗報告一實驗題目ＴＳP問題的遺傳算法實現(xiàn)二實驗目的熟悉和掌握遺傳算法的基本概念和基本思想；加深對遺傳算法的理解，理解和掌握遺傳算法的各個操作算子；理解和掌握運用遺傳算法進行問題求解的基本技能。三實驗規(guī)定1以10/30個結點的TSＰ問題為例，用遺傳算法加以求解；2掌握遺傳算法的基本原理、各個遺傳操作和算法環(huán)節(jié)；3能求出問題最優(yōu)解,若得不出最優(yōu)解,請分析因素；4規(guī)定界面顯示每次迭代求出的局部最優(yōu)解和最終求出的全局最優(yōu)解。四數(shù)據(jù)結構請說明染色體個體和群體的定義方法。ｔｙpedefsｔruｃt{?intｃolｏｎy[PＯPSIＺE][CITＹ_NUＭ+１];/／城市種群,默認出發(fā)城市編號為0，則城市編號的最后一個城市還應當為0每CITY_NUＭ個城市的排列組合為一個染色體 doublefitnesｓ[PＯPＳIＺE];／/途徑適應值 ｄouｂlｅDistance[ＰOPSＩZE];//途徑實際長度 inｔBｅｓtRｏotｉng[ＣＩTY＿NUM+1];/／最優(yōu)城市途徑序列 doubleBｅstFitnｅｓs;//最優(yōu)途徑適應值 dｏubleＢｅstValue;／／最優(yōu)途徑長度｝ＴSＰ,*PＴSP；五實驗算法１說明算法中對染色體的編碼方法,適應度函數(shù)定義方法；染色體的編碼方法：0～9一個排列組合為一條染色體。適應度函數(shù)的定義方法：取途徑長度的倒數(shù)。vｏｉdCaｌFitnｅss(PTSPciｔｙ，ｉnｔｍ){?iｎｔｉ,ｊ,t=0; intsｔａrt,end;?for（i=0；ｉ<ＰOPSIZE;i++)｛/／求適應值 ?city->Disｔancｅ[i]=０；??for(ｊ=１;j<=CIＴY_NUM；ｊ++）{???sｔaｒt=city－>colonｙ［i]［j－1］;end=citｙ－>ｃoloｎｙ［ｉ］[ｊ］； ?city->Distａｎｃe[i]=city－＞Diｓtaｎce[ｉ]＋CityDistａnce[sｔaｒt][eｎd];??} city->fitｎesｓ[i］=N/(city-＞Ｄiｓtance［i])；?}｝2采用的選擇、交叉、變異操作算子的具體操作；voｉdSelect(PTＳPcity）｛//選擇算子?inti,ｊ;?dｏubｌesum=０,r,t; doｕblep［POPＳIＺE]，q[POPSIZE＋１];?inｔｃopeｙ[ＰOPSIZE][CITY＿ＮUM+1］;?q［0]=０；?for(i＝0;ｉ<PＯPSIＺＥ；ｉ+＋)? sｕｍ+=city->ｆitnesｓ[i]; for(ｉ=0;i＜ＰOPSIZＥ;ｉ++）?{??ｐ［ｉ]=ｃity->ｆitｎess[i]／sｕm；? q[ｉ+1]=ｑ[i］＋p[i］; ｝ ｆor（i=0;i<POPSIZＥ;i＋＋) { ?t＝rａnｄ(）％(１0０00); ?ｒ=t/1０0００； for（j=0；j＜POＰSIZE;j++) ??ｉf(r＜=q[j+1]) ??｛ ??*copey[ｉ］=*ciｔy->colonｙ[ｊ］；?? ?ｂreaｋ;?? } }?ｆor(ｉ=0;i＜POＰＳIZE；i++) *ｃｉtｙ->colony[ｉ］=*copeｙ[i]；}vｏiｄAOX(PTＳPcity,intｎ,iｎtｍ)//改善啟發(fā)式算法{?intA［CIＴＹ_NUＭ-1],Ｂ［CITY_ＮＵM-１];?ｉnｔi,j; intk＝1+CRＯSS＿NUＭ,t=１＋CROSS_ＮUM； for(i=0;i<CITY_NUM-1；i+＋）?{??A［i］=ｃity->colony［n][i+1]; ?Ｂ［i]=cｉty->cｏloｎy[ｍ][i+１］;?} for（ｉ＝３;i<CＲOSＳ_NUM+３；i++） { ?citｙ-＞cｏｌoｎy［n][i－2]＝B[i］; ?ｃity-＞coloｎy[ｍ][i-2]=A［ｉ]；?} for(i＝0;i<CITY＿NUM-1;i++) { ?ｆｏｒ(j=0;j<CROＳS_ＮUM;j++)? ?if(A[ｉ]==B[j+3])? breａｋ; ?if(j=＝CROSＳ_NＵＭ)???cｉtｙ－>ｃolｏny［ｎ]［k＋+]=A[i];? ｆor(j=0；ｊ<CＲＯSＳ_NUM；j++)?? ｉf(Ｂ[i]=＝Ａ[j+3])? ?break；??if(j＝=CRＯSS_NUM) ??cｉｔy-＞colonｙ［ｍ][ｔ+＋]=B[i];?｝}intcheck１（iｎtr[],intn)／／判重{?inti; fｏr(ｉ=０;i＜n；ｉ++) if(ｒ[ｉ]=＝r[ｎ］)??｛???rｅｔuｒntrue； ?}?returnfalse;}vｏidCross(PTＳＰｃｉty，doublepc){/／交叉概率是p?inti； intｒ［20];?foｒ(ｉ=0;i<ＰOPＳIZE*pc;i+＋）?{??r[i]＝rand()%(PＯPSIＺE);? whilｅ(cｈeｃk1(r,i)）? r[i］=raｎd()%（PＯPＳIZE)； }?foｒ(i=0；i＜PＯPSIＺE*ｐc;i=ｉ＋2)??AOX(city,r[i],r[ｉ+1]);}ｖｏｉdXＣＨ(PTSPcity，inｔn)//對換變異{?ｉｎtr，t;?ｉnｔc； ｒ=ranｄ(）%(ＣＩＴY_NUＭ－1)+１; ｔ＝ｒanｄ()%(CITY＿ＮUM-１)+1;?ｗhile(ｒ==t) t＝rａnd(）%(CＩTY＿NUM－1）＋1；?c=city－>colｏny[n］[r];?cｉty－>ｃolony［n][ｒ]=city->ｃoloｎy[n］［ｔ]; ｃｉｔｙ-＞colony[ｎ][t]=c;}voidMｕtaｔioｎ(PTSPｃity,dｏuｂｌeｐｍ){//變異概率是pm?intｉ; ｉｎtｒ［2０]; fｏr(ｉ=0;i<ＰOPSＩＺＥ*ｐm;i+＋） { ?ｒ[ｉ]＝rａnd()％(ＰOPSIZE); wｈｉｌe(chｅck1(r,i）) r［ｉ]=rａnｄ()％(POＰSIＺE）； ?XCＨ（ciｔy,r[ｉ]);?}}3實驗中采用的算法參數(shù)的最佳選擇