《TSP问题的遗传算法实验报告.docx》由会员分享，可在线阅读，更多相关《TSP问题的遗传算法实验报告.docx（5页珍藏版）》请在三一文库上搜索。
1、TSP问题的遗传算法实验报告一 实验题目 TSP问题的遗传算法实现二 实验目的1 熟悉和掌握遗传算法的基本概念和基本思想； 2 加深对遗传算法的理解，理解和掌握遗传算法的各个操作算子；3 理解和掌握利用遗传算法进行问题求解的基本技能。三 实验要求 1 以10/30个结点的TSP问题为例,用遗传算法加以求解；2 掌握遗传算法的基本原理、各个遗传操作和算法步骤；3 能求出问题最优解，若得不出最优解，请分析原因； 4 要求界面显示每次迭代求出的局部最优解和最终求出的全局最优解。四 数据结构请说明染色体个体和群体的定义方法。typedef structint colonyPOPSIZECITY_NUM
2、+1;/城市种群,默认出发城市编号为0，则城市编号的最后一个城市还应该为0 每CITY_NUM个城市的排列组合为一个染色体double fitnessPOPSIZE;/ 路径适应值double DistancePOPSIZE;/路径实际长度int BestRootingCITY_NUM+1;/最优城市路径序列double BestFitness;/最优路径适应值double BestValue;/最优路径长度TSP,*PTSP;五 实验算法1 说明算法中对染色体的编码方法，适应度函数定义方法；染色体的编码方法：09一个排列组合为一条染色体。适应度函数的定义方法：取路径长度的倒数。void Ca
3、lFitness(PTSP city,int m)int i,j,t=0;int start,end;for(i=0;iDistancei=0;for(j=1;jcolonyij-1;end=city-colonyij;city-Distancei=city-Distancei+CityDistancestartend;city-fitnessi=N/(city-Distancei);2 采用的选择、交叉、变异操作算子的具体操作；void Select(PTSP city)/选择算子int i,j;double sum=0,r,t;double pPOPSIZE,qPOPSIZE+1;int
4、copeyPOPSIZECITY_NUM+1;q0 = 0;for (i=0;ifitnessi;for (i=0;ifitnessi/sum;qi+1 = qi+pi;for (i=0;iPOPSIZE;i+)t = rand()%(10000);r = t/10000;for (j=0;jPOPSIZE;j+)if (rcolonyj;break;for (i=0;icolonyi = *copeyi;void AOX(PTSP city,int n,int m)/改进启发式算法int ACITY_NUM-1,BCITY_NUM-1;int i,j;int k=1+CROSS_NUM,t=
5、1+CROSS_NUM;for (i=0;icolonyni+1;Bi = city-colonymi+1;for (i=3;icolonyni-2 = Bi;city-colonymi-2 = Ai;for (i=0;iCITY_NUM-1;i+)for (j=0;jcolonynk+ = Ai;for (j=0;jcolonymt+ = Bi;int check1(int r,int n)/判重int i;for (i=0;in;i+)if (ri = rn)return true;return false;void Cross(PTSP city,double pc)/交叉概率是pint
6、 i;int r20;for (i=0; iPOPSIZE*pc;i+)ri = rand()%(POPSIZE);while (check1(r,i)ri = rand()%(POPSIZE);for (i=0;icolonynr;city-colonynr = city-colonynt;city-colonynt = c;void Mutation(PTSP city,double pm)/变异概率是pmint i;int r20;for (i=0; iPOPSIZE*pm;i+)ri = rand()%(POPSIZE);while (check1(r,i)ri = rand()%(POPSIZE);XCH(city,ri);3 实验中采用的算法参数的最佳选择值是多少。由于我是随机抽取参加交叉的染色体，没有选择性的抽取那些适应度大的染色体，故交叉率pc很难确定最佳最佳值。我的取值是：POPSIZE = 20 PCROSS = 0.6 PMUTATION = 0.05六 实验结果1 要求有实验运行结果截图，以及必要的说明；需要输入进化次数。 （注：可编辑下载，若有不当之处，请指正，谢谢!）