2023年TSP问题的遗传算法实验报告

TSP问题的遗传算法实验报告一实验题目ＴＳP问题的遗传算法实现二实验目的熟悉和掌握遗传算法的基本概念和基本思想；加深对遗传算法的理解，理解和掌握遗传算法的各个操作算子；理解和掌握运用遗传算法进行问题求解的基本技能。三实验规定1以10/30个结点的TSＰ问题为例，用遗传算法加以求解；2掌握遗传算法的基本原理、各个遗传操作和算法环节；3能求出问题最优解,若得不出最优解,请分析因素；4规定界面显示每次迭代求出的局部最优解和最终求出的全局最优解。四数据结构请说明染色体个体和群体的定义方法。ｔｙpedefsｔruｃt{ﻩintｃolｏｎy[PＯPSIＺE][CITＹ_NUＭ+１];/／城市种群,默认出发城市编号为0，则城市编号的最后一个城市还应当为0每CITY_NUＭ个城市的排列组合为一个染色体 doublefitnesｓ[PＯPＳIＺE];／/途径适应值 ｄouｂlｅDistance[ＰOPSＩZE];//途径实际长度 inｔBｅｓtRｏotｉng[ＣＩTY＿NUM+1];/／最优城市途径序列 doubleBｅstFitnｅｓs;//最优途径适应值 dｏubleＢｅstValue;／／最优途径长度｝ＴSＰ,*PＴSP；五实验算法１说明算法中对染色体的编码方法,适应度函数定义方法；染色体的编码方法：0～9一个排列组合为一条染色体。适应度函数的定义方法：取途径长度的倒数。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ｍ)//改善启发式算法{ﻩ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实验中采用的算法参数的最佳选择