人工智能TSP旅行商问题实验报告剖析

1、人工智能实验三实验报告班级：姓名：学号：实验题目TSP问题的遗传算法实现旅行商问题（TravelingSalesmanProblem,TSP）,又译为旅行推销员问题、货担郎问题，简称为TSP问题，是最基本的路线问题。假设有n个可直达的城市，一销售商从其中的某一城市出发，不重复地走完其余n-1个城市并回到原出发点，在所有可能的路径中求出路径长度最短的一条。应用遗传算法求解30/10个节点的TSP（旅行商问题）问题，求问题的最优解。实验目的熟悉和掌握遗传算法的基本概念和基本思想；理解和掌握遗传算法的各个操作算子，能够用选定的编程语言设计简单的遗传优化系统；通过实验培养学生利用遗传算法进行问题求解的

2、基本技能。实验要求掌握遗传算法的基本原理、各个遗传操作和算法步骤；要求求出问题最优解，若得不出最优解，请分析原因；对实验中的几个算法控制参数进行仔细定义，并能通过实验选择参数的最佳值；要求界面显示每次迭代求出的局部最优解和最终求出的全局最优解。数据结构请说明染色体个体和群体的定义方法。structRanSeTi/染色体的个体的定义方法intcitycities;/基因的排列（即城市的顺序，路径的组织）intadapt;/记录适应度doublep;/记录其在种群中的幸存概率RanSeTinum,RanSeTitempnum;/用数组来存储染色体群体方法实验算法说明算法中对染色体的编码方法，适应度

3、函数定义方法1）染色体的编码方法:即为染色体个体定义过程中生成的基因排列（路径中城市的顺序）structRanSeTi/染色体的个体的定义方法intcitycities;/基因的排列（即城市的顺序，路径的组织）intadapt;/记录适应度doublep;/记录其在种群中的幸存概率RanSeTinum,RanSeTitempnum;/用数组来存储染色体群体方法2）适应度函数定义方法：评价函数即适应度函数，在遗传算法中用来计算一个染色体优劣的函数。在进行遗传操作和种群进化的时候，每个染色体的适应值是决定它是否进入下一轮种群进化的关键因素。适应值高的函数被选作新一代个体的可能性就会大。TSP问题中

4、适应度函数常取路径长度的倒数（或倒数的相关函数），如：f(x,x,其中，N是个调节参数，根据实验情况进行确定。for(i=0;inum;i+)sumdistance=0;for(j=1;jcities;j+)n1=RanSeTii.cityj-1;n2=RanSeTii.cityj;sumdistance+=distancen1n2;RanSeTii.adapt=sumdistance;/每条染色体的路径总和biggestsum+=sumdistance;/种群的总路径采用的选择、交叉、变异操作算子的具体操作1）选择操作我们定义f（xp为第i（i=l,2,3.popsize）个染色体的适应度，

5、则每个个体被选中的概率是：P(x.)=f(xV廿f(x.)本题中具体使用的是期望值方法/初始化梯度概率for(i=0;inum;i+)gradienti=0.0;xuanzei=0.0;gradient0=group0.p;for(i=1;inum;i+)gradienti=gradienti-1+groupi.p;srand(unsigned)time(NULL);/随机产生染色体的存活概率for(i=0;inum;i+)xuanzei=(rand()%100);xuanzei/=100;/选择能生存的染色体for(i=0;inum;i+)for(j=0;jnum;j+)if(xuanzei

6、gradientj)xuani=j;/第i个位置存放第j个染色体break;/拷贝种群for(i=0;inum;i+)grouptempi.adapt=groupi.adapt;grouptempi.p=groupi.p;for(j=0;jcities;j+)grouptempi.cityj=groupi.cityj;/数据更新for(i=0;inum;i+)temp=xuani;groupi.adapt=grouptemptemp.adapt;groupi.p=grouptemptemp.p;for(j=0;jcities;j+)groupi.cityj=grouptemptemp.city

7、j;2)交叉操作：交叉算子就是把两个父代个体的部分结构加以替换重组而生成新个体的操作部分匹配交叉、顺序交叉、改进的启发式顺序交叉/temp1号染色体和temp2染色体交配for(i=0;it/2;i+)point1=rand()%cities;point2=rand()%cities;for(j=temp1;jnum;j+)if(jiaopeiflagj=1)temp1=j;break;for(j=temp1+1;jpoint2)/保证point1=point2temp=point1;point1=point2;point2=temp;memset(map1,-1,sizeof(map1);m

8、emset(map2,-1,sizeof(map2);/断点之间的基因产生映射for(k=point1;k=point2;k+)map1grouptemp1.cityk=grouptemp2.cityk;map2grouptemp2.cityk=grouptemp1.cityk;/断点两边的基因互换for(k=0;kpoint1;k+)temp=grouptemp1.cityk;grouptemp1.cityk=grouptemp2.cityk;grouptemp2.cityk=temp;for(k=point2+1;kcities;k+)temp=grouptemp1.cityk;group

9、temp1.cityk=grouptemp2.cityk;grouptemp2.cityk=temp;/处理产生的冲突基因for(k=0;kpoint1;k+)for(kk=point1;kk=point2;kk+)if(grouptemp1.cityk=grouptemp1.citykk)grouptemp1.cityk=map1grouptemp1.cityk;break;for(k=point2+1;kcities;k+)for(kk=point1;kk=point2;kk+)if(grouptemp1.cityk=grouptemp1.citykk)grouptemp1.cityk=m

10、ap1grouptemp1.cityk;break;for(k=0;kpoint1;k+)for(kk=point1;kk=point2;kk+)if(grouptemp2.cityk=grouptemp2.citykk)grouptemp2.cityk=map2grouptemp2.cityk;break;for(k=point2+1;kcities;k+)for(kk=point1;kk=point2;kk+)if(grouptemp2.cityk=grouptemp2.citykk)grouptemp2.cityk=map2grouptemp2.cityk;break;temp1=tem

11、p2+1;变异操作TSP问题中，经常采取的变异操作主要有：位点变异、逆转变异、对换变异、插入变异。/随机产生变异概率srand(unsigned)time(NULL);for(i=0;inum;i+)bianyipi=(rand()%100);bianyipi/=100;/确定可以变异的染色体t=0;for(i=0;inum;i+)if(bianyipipm)bianyiflagi=1;t+;/变异操作,即交换染色体的两个节点srand(unsigned)time(NULL);for(i=0;inum;i+)if(bianyiflagi=1)temp1=rand()%10;temp2=rand

12、()%10;point=groupi.citytemp1;groupi.citytemp1=groupi.citytemp2;groupi.citytemp2=point;实验中采用的算法参数的最佳选择值是多少#definecities10/30/城市的个数#defineMAXX150/迭代次数#definepc0.72/交配概率#definepm0.02/变异概率#definenum20/种群的大小实验结果1要求有实验运行结果截图，以及必要的说明0.05070.05078.04988.04980.04980.04980.04980.04970.05070.04980.04980.04978.

13、04980.05070.04980.04980.04980.04980.05070.0497B.05070.0507915VVVVTTVV4F=._LF=.-LF=.-LF=.-LF=.4P-CP-CP-CF=.-LF习.-斗.斗.斗.斗/斗.-斗.-斗.-斗.斗.-軒售glsgg豊IFlflfir唱墾stMjlsl营脣關腸a二t-4.-iii_.f_nnnnnnnnn口丿_.T.丿_!J_!亠_!-!*_!丿_!丿_卢丿-卢丿_!丿_.T._-F_之之染之之之之之之之之之之染ZHd.n-耳.l-.?:-.口.l-./:-.口.-h.-.口.L./:-.口J:m:-:-:-.口.l-.?:-.

14、口.l-./:-.口CHd.UHdiD-yin-yilZHdilZHdilZHdilZHdillHdiD-JPV141111454454115999999919919991535555363363556种ZOEff-ff-ff-ff-ffffffffff-ff-ff-ff-ff-ffffffff!l种&前邑邑邑邑邑邑邑邑邑邑邑邑邑邑邑邑邑邑邑&刖邂雪養聚棗棗聚聚聚棗棗聚雪以上部分是每次迭代的步骤结果，通过染色体群体中个体的交配、变异，从而更改染色体的具体基因组成，通过不断进行适应度计算、存活率的计算，更新已有数值；前岀最终的种群评价4617259380adapt:591.P0049846172

15、59380adapt:591.P004984617259380adapt:591,P004984617259380adapt:591.P004984617259380adapt:591.P00498462715938Qadapt:615,P00497569a237841adapt:394,P005074617259380adapt:591.P004984617259380adapt:591.P004984627159380adapt:615,P004974617259380adapt:591,P004985690237841adapt:394.P00507461725938Qadapt:591

16、,P004984617259380adapt:591,P004984617259380adapt:591.P004984617259380adapt:591.P004985690237841adapt:394,P005074627159380adapt:615,P004975690237841adapt:394.P00507*应解焉号泰色和237841adapt:394,P00507以上部分为迭代之后的总结果，输出最终的种群评价，从染色体种群里面取出最佳的染色体，并进行输出。2要求说明是否搜索到了最优解，如果没有，请分析原因本题中根据随机生成的cities个城市之间的相互距离、随机产生初试群，

17、通过TSP算法，通过以下步骤：(1)初始化群体;(2)计算群体上每个个体的适应度值;(3)按由个体适应度值所决定的某个规则选择将进入下一代的个体;按概率Pc进行交叉操作；按概率Pm进行变异操作;没有满足某种停止条件，则转第(2)步，否则进入(7)；输出种群中适应度值最优的染色体作为问题的满意解或最优解。成功找到种群中适应度值最优的染色体作为问题的满意解或最优解。若失败，分析可得失败原因为：随机生成的cities个城市之间的相互距离、随机产生初试群有可能不存在适应度值最优的染色体实验总结及体会同一问题可能有不同的几种算法相对应解决：对于此类旅行者问题，原在数据结构和算法课中学过迪杰斯特拉算法，也可以高效快速的解决给定好初值的最短路径问题；在本课中，有学到了新的算法：TSP算法，此算法从遗传学角度，开辟了一个新的视野。通过每次迭代求出的局部最优解和最终求出的全局最优解。两种不同的算法可以求解同