《TSP问题的遗传算法实验报告.doc》由会员分享，可在线阅读，更多相关《TSP问题的遗传算法实验报告.doc（6页珍藏版）》请在三一文库上搜索。
1、精品文档 TSP 问题的遗传算法实验报告 一实验题目 TSP问题的遗传算法实现 二实验目的 1 熟悉和掌握遗传算法的基本概念和基本思想； 2 加深对遗传算法的理解，理解和掌握遗传算法的各个操作算子； 3 理解和掌握利用遗传算法进行问题求解的基本技能。 三实验要求 1 以10/30个结点的TSP问题为例，用遗传算法加以求解； 2掌握遗传算法的基本原理、各个遗传操作和算法步骤； 3能求出问题最优解，若得不出最优解，请分析原因； 4要求界面显示每次迭代求出的局部最优解和最终求出的全局最优解。 四数据结构 请说明染色体个体和群体的定义方法。 typedef struct int colonyPOPSI
2、ZECITY_NUM+1; 城市种群，默认出发城市编号为 0,则城市编 号的最后一个城市还应该为 0 每CITY_NUM个城市的排列组合为一个染色体 double fitnessPOPSIZE; 路径适应值 double DistancePOPSIZE; 路径实际长度 int BestRooti ngCITY_NUM+1; 最优城市路径序列 double BestFit ness;/最优路径适应值 double BestValue;/最优路径长度 TSP,*PTSP; 五实验算法 1说明算法中对染色体的编码方法，适应度函数定义方法； 染色体的编码方法：09 一个排列组合为一条染色体。 适应度函
3、数的定义方法：取路径长度的倒数。 void CalFit ness(PTSP 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;
4、 double sum=0,r,t; double pPOPSIZE,qPOPSIZE+1; int 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
5、nt n,i nt m)/ 改进启发式算法 int ACITY_NUM-1,BCITY_NUM-1; int i,j； int k=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)/ in
6、t i; for (i=0;i n;i+) if (ri = rn) return true;判重 精品文档 return false; void Cross(PTSP city,double pc) /交叉概率是p int 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
7、 Mutation(PTSP city,double pm) /变异概率是pm int i; int r20; for (i=0; iPOPSIZE*pm;i+) 精品文档 0 ri = 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要求有实验运行结果截图，以及必要的说明; 0 1 3 9 4 & 區畧怨厚已的局部最优豁好 巒倏1最君出器局话最: 幽径描怀妇下* 0317S946S2 聲密務搏出的局部最优路径长度231.4708 0 3 17 6 9 & 2 选代丄3反后得到兰局最ft路径咬龙：175.302076 H3549?fel Press any key to continue. 妄岀的局部最优路径长岌：240,761320 J * C: Dacu*cxi s and Sc t ingsAd*inis r at 文杵夹(2) .T5P| f 的遺 需要输入进化次数。