《基于遗传算法的TSP问题解决.docx》由会员分享，可在线阅读，更多相关《基于遗传算法的TSP问题解决.docx（8页珍藏版）》请在课桌文档上搜索。
1、实验题目：的遗传算法解决TSP问题姓名：谢稳文班级：智能IOol学号：20230840126一:问题描述旅行商问题，即TSP问题(TravellingSalesmanProblem)又译为旅行商问题，货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。因此，任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。二:遗传算法的根本原理遗传算法是由美国JHoll
2、and教授于1975年在他的专著自然界和人工系统的适应性中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保存一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。遗传算法，在本质上是一种不依赖具体问题的直接搜索方法，是一种求解问题的高效并行全局搜索方法。遗传算法在模式识别、神经网络、图像处理、机器学习、工业优化控制、自适应控制、负载平衡、电磁系统设计、生物科学、社会科学等方面都得到了应
3、用。在人工智能研究中，现在人们认为“遗传算法、自适应系统、细胞自动控制、混沌理论与人工智一样，都是对今后十年的计算技术有重大影响的关键技术。根本步骤为：标准的遗传算法包括群体的初始化，选择，交叉，变异操作。所示，其主要步骤可描述如下:(1)随机产生一组初始个体构成的初始种群，并评价每一个个体的适配值。(2)判断算法的收敛准那么是否满足。假设满足输出搜索结果；否那么执行以下步骤。(3)根据适配值大小以一定方式执行选择操作。(4)按交叉概率PC执行交叉操作。(5)按变异概率PnI执行变异操作。(6)返回步骤算法流程图为：三:TSP问题的遗传算法设计初始种群：对于个城市的问题，每个个体即每个解的长度
4、为A,用S行，列的POP矩阵表示初始群体，S表示初始群体的个数，为加1,矩阵的每一行的前A个元素表示城市编码，最后一个元素表示这一路径的长度。这一算法通过start.血呈序实现。适应度：在TSP的求解中，可以直接用距离总和作为适应度函数。个体的路径长度越小，所得个体优越，以POP矩阵的每一行最后一个元素作为个体适应值。选择：选择就是从群体中选择优胜个体、淘汰劣质个体的操作，它是建立在群体中个体适应度评估根底上。这里采用方法是最优保存方法。算法就是首先将群体中适应度最大的k个个体直接替换适应度最小的k个体。交叉：受贪婪算法的启发，本文设计一种有目的使适应值上升的交叉算子。两al(mil,ml2,
5、ml3,.,mln),a2(m21,m22,m23,.,m2n),算法产生后代al和a2的过程如下：(1)随机产生一个城市d作为交叉起点，把d作为al和a2的起始点(2)分别从al和a2中找出d的右城市drl和dr2,并计算(d,drl)和(d,dr2)的距离JI和J2。(3)如果jkj2,那么把drl作为al的第二个点,从al和a2中删除d,并且把当前点改为drL转步骤(5)。(4)如果jlj2,那么把dr2作为al的第二个点,从al和a2中删除d,并且把当前点改为dr2。(5)假设此时PI和p2的个数为1,结束，否那么回到第二步继续执行。同理，把第二步中的右城市改成左城市dlel和dle2
6、,通过计算(d,dlel)和(d,dle2)的距离并比拟大小来确定子代a2。变异：变异操作是以变异概率Pm对群体中个体串某些基因位上的基因值作变动，假设变异后子代的适应度值更加优异，那么保存子代染色体，否那么，仍保存父代染色体。这里采用的方法是倒置变异法。假设当前个体X为(1374805962)o如果Pmrand,那么随机选择来自同一个体的两个点mutatepoint(1)和Iiiutatepoint(2),比方说3和7,倒置Pl和P之间的局部，产生下面的子体X为(1375084962)o四：实验代码1主函数局部clc;clearall;closeall;globalxycityfile=fo
7、pen(city30.txtt,*rt)；宅取30个城市的样本cities=fscanf(cityfile,f%f,2,inf)；fclose(cityfile);t=30+l;舍城市的数目是3。个s=1500;金样本的数目是1400个G=300;*运算的代数c=25;%选择算子中每次替代的样本的数量x=cities(1,:);y=cities(2,:);pc=o.10;金交叉的概率pm=0.8;留变异的概率pop-zeros(srt);宅得初始的p。P矩阵，矩阵的最后列袋小所在打的样本的路径距离fori=l:spop(i,lzt-l)=randperm(t-l);宅随机产生工一(t-l)的t
8、-1个数endfork=l:l:G宅GA开始ifmod(k,50)=1kendpop=distance(pop);；调用距离函数求距离pop=select(pop,c)；当调用选择函数pl=rand;ifpl=pcpop=cross(pop);%调用交叉函数endp2=rand;ifp2=pmpop=mutate(pop);调用变异函数endend为GA结束%bestL=min(pop(:,t)j=pop(:,t)；fi=l./J;Oderfi,Indexfi=sort(fi);宅对于fi进彳j排序BestS=PopfIndexfi(s),:);彩得到最短路I=BestS;fori=l:1:t
9、-1xl(i)=xIi);yl(i)=yI(i);endxl(t)三x(I(1);yl(t)=y(I(l);cities_new=xl;yl;disp(BestRouteis:);disp(cities_new);pos=cities_newcitiesnew(:,1);Ientemp=O;fori=l;l;t=ltemp=sqrt(pos(1zi)-pos(1,i+1)2+(pos(2,i)-pos(2,i+1)2)Ientemp=Ientemp+temp;enddisp(ShortestLengthis:);disp(Ientemp);figure(1);subplot(lr2rl；舍窗口
10、分割的左边局部x(t)=x(l);y(t)=y(l);plot(x,y,-or);label(Xaxis),ylabel(tYaxis),title原始路径，)；axiw(0,1,0,1)；axis(0,100,0,100);axisonholdon;subplot(1,2,2);%窗目分割的右边局部plot(xl,yl,-or);label(Xaxis),ylabel(tYaxis，)，title最新的路径，)；axis(0,1,0,1);axis(0,100,0,100);axison2距离函数functionpop=distance(pop)globalxys,t=size(pop);f
11、ori=l:1:sdd=0;POS=Pop(i,1:t-1);pos=pospos(:r1);forj=l:l:t-1m=os(j);n=pos(j+1);dd=dd+sqrt(x(m)-x(n)2+(y(m)-y(n)2);endpop(i/t)=dd;end3选择函数unctionpop=select(poprc)s,t=size(pop);mil=(pop(:,t);mll=mll;mmax=zeros(1,c);mmin=zeros(1,c);num=l;whilenumc+l舍取距离大的C个样本armmax(num)=max(mll);*选取当前样本的最大值并记录样本编号给TnmaX
12、(num)ml1(mmax(num)=O;11um=11um+1;end11urt=l;whilenumc+l年取距离小的C个样本b,mmin(num)=min(ml1);mil(mmin(num)=a;num=num+l;endfori=l:cpop(mma(i)z:)=pop(mmin(i),:);用距离小的C个样本3J卜end4交叉函数functionpop=cross(pop)s,t=size(pop);pop_l=pop;n=randperm(s);*将种群随机排序fori=l:2:$%随机选择两个交叉点m=randperm(t-3)+1;crosspoint(1)=min(m(1)
13、zm(2);crosspoint(2)=max(m(1)zm(2);用任意两行交叉xl=n(i);x2=n(i+l);%将xl左边与x2的左边互换middle=pop(xl,1:crosspoint(I);pop(xl,1:crosspoint(1)=pop(x2,1:crosspoint(1);pop(x2z1:crosspoint(1)=middle;%将xl右边与x2的右边互换middle=pop(xl,crosspoint(2)+1:t);pop(xl,crosspoint(2)1:t)=pop(x2,crosspoint(2)+1:t);pop(x2zcrosspoint(2)+1:
14、t)=middle;t检查xl左边的重复性并得到xl的左边forj=l:crosspoint(1)W确定重复位置whilefind(pop(xl,crosspoint(1)+1:crosspoint(2)=pop(xl,j)zhi=find(pop(xlzcrosspoint(1)+1:crosspoint)=pop(1,j);temp=pop(2,crosspoint(1)zhi);pop(xl,j)=temp;endend当检查xl的右边的重狂性并得到xl的右边forj=Crosspoint(2)1:t-1whilefind(pop(xl,crosspoint(1)+1:crosspoin
15、t(2)=po(xlzj)zhi=find(pop(xl,crosspoint(1)+1:crosspoint(2)=pop(1,j);i确定IE复的位置tem=po(x2,crosspoint(1)+zhi);o(xl,j)=tem;endend%检查x2左边的重复性并得到x2的左边forj=l:crosspoint(1)whilefind(pop(x2,crosspoint(1)1:crosspoint(2)=pop(x2,j)zhi=find(pop(2zcrosspoint(1)+1:crosspoint(2)=pop(2,j);确定重复位置tem=po(xlzcrosspoint(1
16、)+zhi);POP(X2,j)=tem;endend%检查x2的右边的重复性并得到x2的右边forj=Crosspoint(2)+1:t-1whilefind(pop(x2,crosspoint(1)1:crosspoint(2)=pop(x2,j)zhi=find(pop(*2,crosspoint(1)+1:crosspoint(2)=pop(x2,j);带确定IE复的位置temp=po(xl,crosspoint(1)+zhi);POP(X2,j)=temp;endendend%生成的新的种群与交叉前进行比拟，并取两者最优pop=distance(pop);fori=l:sifpop_
17、l(i,t)pop(i,t)pop(i,：)=pop_l(ir:);endend5变异函数functionpop=mutate(pop)s,t=size(pop);pop_l=pop;fori=l:2:sm=randperm(t-3)+1;务随机取两个点mtatepoint(1)=min(m(1)m(2);mtatepoint(2)=max(m(1),m(2);%用倒置变异的方法倒置两个点中间局部的位置mtate=rond(mtatepoint(2)-mtatepoint(1)/2-0.5);forj=l:mutatezhong=op(i,mutateoint(1)+j);pop(i,muta
18、tepoint(1)+j)=pop(i,mutateoint(2)-j);pop(i,mutatepoint(2)-j)=zhong;endendpop=distance(pop)尸生成的新的种群与变异前比拟，并取两者最优fori=l;$ifpop_l(i,t)pp(i,t)pop(i,:)=PoP_1(i,:);endend用上面的贪婪算法在mat：Lab里运算的结果如下：五：实验心得本实验利用遗传算法解决了小规模的TSP问题。文章首先介绍了TSP问题，并给出TSP问题的数学定义，然后介绍了遗传算法的原理以及算法的根本过程。本文程序解决小规模的TSP问题还可以，随着城市数目的增大，计算精度有所下降，计算时间增长很快，效率较低较快，这也是下一步需要改良的地方。
