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

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

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

3、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 copeyPOPSIZE

4、CITY_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=1+C

5、ROSS_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)/交叉

6、概率是pint 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 =