资源描述：
《遗传算法解TSP问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、遗传算法解TSP问题一、实验目的掌握遗传算法求解TSP问题的实现过程。二、实验内容: 用遗传算法求解TSP。 由于其任一可能解——一个合法的城市序列，即n个城市的一个排列，都可以事先构造出来。于是，我们就可以直接在解空间（所有合法的城市序列）中搜索最佳解。这正适合用遗传算法求解。三、实验步骤（1）编码路径表示是表示旅程对应的基因编码的最自然、最简单的表示方法。例如，旅程(5—1—7—8—9—4—6—2—3)可以直接表示为(517894623)，基于路径表示的编码方法，要求个个体(即一条旅程)的染色体编码中不允许有重复的基因码，也就是说要满足任
2、一个城市必须而且只能访问一次的约束。（2）定义适应度函数我们将一个合法的城市序列s=（c1,c2,…,cn）作为一个个体。这个序列中相邻两城市之间的距离之和的倒数就可作为相应个体s的适应度，从而适应度函数就是：例如，对于9个城市的TSP，我们用符号1、2、3、4、5、6、7、8、9代表相应的城市，用这9个符号的序列表示可能解即染色体。然后进行遗传操作用部分匹配交叉PMX方法：匹配操作要求随机选取两个交叉点，确定一个匹配段，根据两个父个体中两个交叉点之间的中间段给出的映射关系生成两个子个体.例如，对下面两个父个体的表示,随机选择两个交义点P1:12
3、3456789o1:423187659P2:45218769302:182456793交叉方法:随机选取染色体上两个元，然后交换它们的位置．例如:452187693交换后：456187293（３）求解的Tsp问题的城市坐标如下： 38.2420.4239.5726.1540.5625.3236.2623.1233.4810.5437.5612.1938.4213.1137.5220.4441.239.1041.1713.0536.08-5.2138.4715.1338.1515.3537.5115.1735.4914.3239.3619.5638
4、.0924.3636.0923.0040.4413.5740.3314.1540.3714.2337.5722.56四、实验结果1）实验源程序：（1）主程序：%testst22=[38.2420.4239.5726.1540.5625.3236.2623.1233.4810.5437.5612.1938.4213.1137.5220.4441.239.1041.1713.0536.08-5.2138.4715.1338.1515.3537.5115.1735.4914.3239.3619.5638.0924.3636.0923.0040.4413
5、.5740.3314.1540.3714.2337.5722.56];MaxIter=20;SizeScale=500;pm=0.1;%交换概率pc=0.8;%匹配概率viprate=0.1;[time,opt,fval]=suanfa(st22,MaxIter,SizeScale,pc,pm,viprate)%////////////////////////（2）用双交叉交配的遗传算法：function[time,opt,fval]=suanfa(Map,MaxIter,SizeScale,pc,pm,viprate)%Thisisfuncti
6、on%Input:%Output:lminroad=[];t=cputime;%MaxIter=100;%SizeScale=100;n=max(size(Map));%computetheroadmatrixDistMatrix=zeros(n,n);fori=1:nforj=1:nDistMatrix(i,j)=distance(Map(i,:),Map(j,:));endend%toinitaltheroad(oderthecites)Road=ones(SizeScale,n);fori=1:SizeScaleRoad(i,:)=rand
7、perm(n);end%Dist=zeros(SizeScale,1);fori=1:SizeScaleforj=1:(n-1)Dist(i)=Dist(i)+DistMatrix(Road(i,j),Road(i,j+1));endend[MinRoad,II]=min(Dist);foriter=1:MaxIter%计算适应度MinRoad=min(Dist);MaxRoad=max(Dist);fori=1:SizeScalefit(i)=fitness(MinRoad,MaxRoad,Dist(i));end%双交叉交配childRoad
8、=[];fori=1:SizeScaley1=select(rand,fit);y2=select(rand,fit);ifrand
