TSP问题的遗传算法实验报告.doc

《TSP问题的遗传算法实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、TSP问题的遗传算法实验报告一实验题目TSP问题的遗传算法实现二实验目的1熟悉和掌握遗传算法的基本概念和基本思想；2加深对遗传算法的理解，理解和掌握遗传算法的各个操作算子；3理解和掌握利用遗传算法进行问题求解的基本技能。三实验要求1以10/30个结点的TSP问题为例,用遗传算法加以求解；2掌握遗传算法的基本原理、各个遗传操作和算法步骤；3能求出问题最优解，若得不出最优解，请分析原因；4要求界面显示每次迭代求出的局部最优解和最终求出的全局最优解。四数据结构请说明染色体个体和群体的定义方法。typedefstr

2、uct{intcolony[POPSIZE][CITY_NUM+1];//城市种群,默认出发城市编号为0，则城市编号的最后一个城市还应该为0每CITY_NUM个城市的排列组合为一个染色体doublefitness[POPSIZE];//路径适应值doubleDistance[POPSIZE];//路径实际长度intBestRooting[CITY_NUM+1];//最优城市路径序列doubleBestFitness;//最优路径适应值doubleBestValue;//最优路径长度}TSP,*PTSP;五实

3、验算法1说明算法中对染色体的编码方法，适应度函数定义方法；染色体的编码方法：0～9一个排列组合为一条染色体。适应度函数的定义方法：取路径长度的倒数。voidCalFitness(PTSPcity,intm){inti,j,t=0;intstart,end;for(i=0;iDistance[i]=0;for(j=1;j<=CITY_NUM;j++){start=city->colony[i][j-1];end=city->colony[i][j];city

4、->Distance[i]=city->Distance[i]+CityDistance[start][end];}city->fitness[i]=N/(city->Distance[i]);}｝2采用的选择、交叉、变异操作算子的具体操作；voidSelect(PTSPcity){//选择算子inti,j;doublesum=0,r,t;doublep[POPSIZE],q[POPSIZE+1];intcopey[POPSIZE][CITY_NUM+1];q[0]=0;for(i=0;i

5、i++)sum+=city->fitness[i];for(i=0;ifitness[i]/sum;q[i+1]=q[i]+p[i];}for(i=0;icolony[j];break;}}for(i=0;icolony[i]=*co

6、pey[i];}voidAOX(PTSPcity,intn,intm)//改进启发式算法{intA[CITY_NUM-1],B[CITY_NUM-1];inti,j;intk=1+CROSS_NUM,t=1+CROSS_NUM;for(i=0;icolony[n][i+1];B[i]=city->colony[m][i+1];}for(i=3;icolony[n][i-2]=B[i];city->colo

7、ny[m][i-2]=A[i];}for(i=0;icolony[n][k++]=A[i];for(j=0;jcolony[m][t++]=B[i];}}intcheck1(intr[],intn)//判重{inti;for

8、(i=0;i