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

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

2、认出发城市编号为0,则城市编号的最后一个城市还应该为0每CITY_NUM个城市的排列组合为一个染色体double fitnessPOPSIZE; 路径适应值double DistancePOPSIZE; 路径实际长度int BestRooti ngCITY_NUM+1; 最优城市路径序列double BestFit ness;/最优路径适应值double BestValue;/最优路径长度TSP,*PTSP;五实验算法1说明算法中对染色体的编码方法，适应度函数定义方法；染色体的编码方法：09一个排列组合为一条染色体。适应度函数的定义方法：取路径长度的倒数。void CalFit ness(PT

3、SP city,i nt m)int i,j,t=0;int start,e nd;for(i=0;iDista ncei=0;for(j=1;jco Ion yij-1;e nd=city-co Ion yij;city-Dista ncei=city-Dista ncei+CityDista ncestarte nd;city-fit nessi=N/(city-Dista ncei);2采用的选择、交叉、变异操作算子的具体操作；void Select(PTSP city)/选择算子int i,j;double sum=0,r,t;double pPOPSIZE,qPOPSIZE+1;in

4、t copeyPOPSIZECITY_NUM+1;q0 = 0;for (i=0;ifit nessi;for (i=0;ifit nessi/sum;qi+1 = qi+pi;for (i=0;iPOPSIZE;i+)t = ran d()%(10000);r = t/10000;for (j=O;jPOPSIZE;j+)if (rco lon yj;break;for (i=0;ico lon yi = *copeyi;精品文档void AOX(PTSP city,i nt n,i nt m)/改进启发式算法int ACITY_NUM-1,BCITY_NUM-1;int i,j；int k

5、=1+CR0SS_NUM,t=1+CR0SS_NUM;for (i=0;icolo ny n i+1;Bi = city-colo nymi+1;for (i=3;icolo ny ni-2 = Bi;city-colo nymi-2 = Ai;for (i=0;iCITY_NUM-1;i+)for (j=O;jcolo ny nk+ = Ai;for (j=0;jcolo nymt+ = Bi;int check1(int r,int n)/ int i;for (i=0;i n;i+)if (ri = rn)return true;判重精品文档return false;void Cross

6、(PTSP city,double pc)/交叉概率是pint i;int r20;for (i=0; iPOPSIZE*pc;i+)ri = ran d()%(POPSIZE); while (check1(r,i)ri = ran d()%(POPSIZE); for (i=0;ico lonyn r;city-co lonyn r = city-co lonyn t; city-co lonyn t = c;void Mutation(PTSP city,double pm) /变异概率是pmint i;int r20;for (i=0; iPOPSIZE*pm;i+)精品文档0ri =

7、 ran d()%(POPSIZE); while (check1(r,i)ri = ran d()%(POPSIZE); XCH(city,ri);3实验中采用的算法参数的最佳选择值是多少。由于我是随机抽取参加交叉的染色体，没有选择性的抽取那些适应度大的染色体，故交叉率pc很难确定最佳最佳值。我的取值是：POPSIZE = 20 PCROSS = 0.6 PMUTATION = 0.05六实验结果1要求有实验运行结果截图，以及必要的说明;01394&區畧怨厚已的局部最优豁好 巒倏1最君出器局话最: 幽径描怀妇下*0317S946S2聲密務搏出的局部最优路径长度231.4708031769&2选代丄3反后得到兰局最ft路径咬龙：175.302076H3549?fel Pres