用遗传算法解决TSP问地的题目

1、实用标准文案用遗传算法解决TSP 问题设计思路：1.初始化城市距离采用以城市编号（i,j=1 代表北京， =2 代表上海， =3 代表天津， =4 代表重庆， =5 代表乌鲁木齐）为矩阵行列标的方法，输入任意两个城市之间的距离，用矩阵city表示，矩阵中的元素city(i,j) 代表第 i 个城市与第j 个城市间的距离。2.初始化种群通过 randperm函数，生成一个一维随机向量（是整数1， 2 ，3 ，4 ， 5 的任意排列），然后将其赋给二维数组group的第一列，作为一个个体。如此循环N 次（本例生成了50个个体），生成了第一代种群，种群的每个个体代表一条路径。3. 计算适应度采用的适

2、应度函数为个体巡回路径的总长度的函数。具体为adapt(1,i)=(5*maxdis-dis)(1)在式（1 ）中，adapt(1,i)表示第 i 个个体的适应度函数，maxdis为城市间的最大距离，为 4077km,dis 为个体巡回路径的总长度， 这样定义的适应度， 当路经越短时适应度值越大。在适应度值的基础上，给出的计算个体期望复制数的表达式为adaptnum(1,i)=(N*adapt(1,i)/sumadapt)(2)其中， sumadapt为种群适应度之和。4. 复制采用优秀个体的大比例保护基础上的随机数复制法。具体做法为在生成下一代个体时，精彩文档实用标准文案先将最大适应度对应的

3、路径个体以较大的比例复制到下一代，然后再用随机数复制法生成下一代的其他个体。其中，有一个问题必须考虑，即若某一次生成的随机数过大，结果能复制一个或极少个样本。为了避免这一情况，采用了限制措施，即压低了随机数的上限。5. 交叉采用的方法为按步长的单点交叉，为随机选择一对样本，再随机选择一个交叉点位置，按一定的步长进行交叉点的选择。选择一个步长而不是将其设为1 ，是因为若某一位置处的城市代码因为进行了交叉而发生了改变，则其经过该处的两个距离都会改变。这种交叉兼有遗传和变异两方面的作用，因为若交叉点处的城市编号都相同，则对两个个体而言交叉后样本无变化，否则样本有变化。6. 变异方法为随机两点I，J

4、的交互位置法。对于A= 1 2 3 4 5 6 7 8 9 10，若 I= 3, J=8，则变异后B= 1 2 8 4 5 6 7 3 9 10虽然是简单的随机两点交互，但实际上已经有40% 的距离发生了改变。 若用 d ij 表示城市i 与 j 之间的距离， 则变异后与变异前样本路径的距离差为B23 十 B34 + B78十 B89 一 A23 十 A34 + A78 + A89可见， 随机两点交互足以产生新的模式样本。较大地提高变异率就会产生大量的新样本，全局最优样本出现的概率随之提高。为了收敛到最优解， 借鉴模拟退火算法的思想，采取了变异率由很大逐渐衰减到较小的数量，这样做也利于找到全局

5、最优解。7. 将复制，交叉，变异后得到的种群group1 重新赋给 group, 然后重复 3 ， 4 ， 5， 6 步操作。直至满足循环停止条件，即找到最优路径。程序实现：精彩文档实用标准文案clcclear allcity=0 1453 157 2087 3768;1453 0 1326 2523 4077;157 1326 0 2300 3900;2087 2523 2300 0 3358;3768 4077 3900 3358 0% 初始化城市距离maxdis=4077;% 城市间最大距离N=50;% 每一代种群中的个体数maxlun=100;% 迭代次数设为100for i=1:Nt

6、temp=randperm(5);% 初始化种群，即随机产生50 种路径，放在5行， N 列的矩阵group中for j=1:5group(j,i)=ttemp(j);endendfor lun=1:maxlun% 迭代循环maxlun次sumadapt=0;% 适度值之和maxadapt(1,lun)=0;% 最大适度值初值精彩文档实用标准文案minadapt(1,lun)=100;% 最小适度值初值viprate=0.1;% 最优个体复制率copyrate=0.02;% 复制率参数maxadaptloc=0;% 最大适应值对应的个体号码初值mindisiii(1,lun)=100000;%

7、 每一代的最忧路径对应的旅行距离总和初值for i=1:Ndis(1,i)=0;for j=1:4dis(1,i)=dis(1,i)+city(group(j,i),group(j+1,i);enddis(1,i)=dis(1,i)+city(group(1,i),group(5,i);% 求一次旅行个体的总长度adapt(1,i)=5*maxdis-dis(1,i);% 第 i 个个体的适应度函数sumadapt=sumadapt+adapt(1,i);% 适应度函数总和if dis(1,i)<mindisiii(1,lun)mindisiii(1,lun)=dis(1,i);ende

8、ndfor i=1:Nadaptnum(1,i)=(N*adapt(1,i)/sumadapt);% 第 i 个个体的期望复制数if adaptnum(1,i)>maxadapt(1,lun)maxadapt(1,lun)=adaptnum(1,i);% 求本代最大适应值精彩文档实用标准文案maxadaptloc=i;% 求最大适应值对应的个体号码endif adaptnum(1,i)<minadapt(1,lun)minadapt(1,lun)=adaptnum(1,i);% 求本代最小适应值endend%.% 复制操作tcopy50=0;% 复制个数初值num=(maxadap

9、t(1,lun)-copyrate-minadapt(1,lun)*rand(1)+minadapt(1,lun);% 生成随机数vipnum=viprate*N;%N=50，确定最优个体复制个数fortcopy50=1:vipnum% 先复制vipnum个最优个体至中间矩阵group1fori=1:5group1(i,tcopy50)=group(i,maxadaptloc);endend精彩文档实用标准文案whiletcopy50<N% 再复制其余N-vipnum个fori=1:Nifadaptnum(1,i)>num&tcopy50<Ntcopy50=tcopy

10、50+1;fork=1:5% 由于针对5 个城市，故每个个体有五个元素group1(k,tcopy50)=group(k,i);endendendend% 交叉操作pc=0.5-(0.5-0.1)*(lun-1)/(maxlun-1);% 交叉率pair=pc*N/2;% 最多交叉对数step=2;% 交叉步长取为2pairno=0;% 当前交叉过的个体数while pairno<pair精彩文档实用标准文案a=floor(N*rand(1)+1);% 随机产生两个交叉个体，floor为向负无穷取整函数b=floor(N*rand(1)+1);marri(1,a)=2;% 参与交叉的个体

11、标记初值marri(1,b)=3;if marri(1,a)=1&marri(1,b)=1&a=bmarri(1,a)=1;marri(1,b)=1;% 参与交叉的个体标记为1pairno=pairno+1;location=floor(5*rand(1)+1);% 用随机数确定个体中单交叉点位置l1=0;l2=0;fori=location:step:5% 以下按步长step 进行交叉forj=1:5% 用 for 确定交叉位置ifgroup1(i,a)=group1(j,b)l1=j;endendforj=1:5ifgroup1(i,b)=group1(j,a)l2=j;e

12、nd精彩文档实用标准文案endtemp=group1(i,a);group1(i,a)=group1(l2,a);group1(l2,a)=temp;temp=group1(i,b);group1(i,b)=group1(l1,b);group1(l1,b)=temp;endendend% 变异操作pb=0.02;% 个体变异率bnum=pb*N;% 变异个体数for i=1:bnum% 逐个取个体，随机选择位置进行变异a1=floor(5*rand(1)+1);a2=floor(5*rand(1)+1);b=floor(N*rand(1)+1);temp=group1(a1,b);group

13、1(a1,b)=group1(a2,b);group1(a2,b)=temp;精彩文档实用标准文案end%fori=1:Nfor j=1:5group(j,i)=group1(j,i);% 构造经过复制，交叉，变异后的矩阵，group, 准备下次循环endendendgroupdisp(' 最优路径为： ')for i=1:5switch group(i,1)case 1,disp('北京 ')case 2,disp('上海 ')case 3,disp('天津 ')case 4,disp('重庆 ')otherwi

14、se,disp('乌鲁木齐 ')% 用文字列出最优路径endend精彩文档实用标准文案disp(' 更多精彩，即将出现，请稍等.')figure(1);lun=1:1:50;mindis=mindisiii(1,lun);plot(lun,mindis);grid on;figure(2);worldmap('china','patch');for i=1:5switch group(i,1)case 1,x(1,i)=0.12;y(1,i)=0.72;case 2,x(1,i)=0.23;y(1,i)=0.54;% 在地图中定出五个城市的坐标case 3,x(1,i)=0.15;y(1,i)=0.7;case 4,x(1,i)=0;y(1,i)=0.53;otherwise,x(1,i)=-0.2;y(1,i)=0.73;endendfor i=1:4u(1,i+1)=x(1,i);v(1,i+1)=y(1,i);endu(1,1)=x(1,5);精彩文档实用标准文案v(1,1)=y(1,5);for i=1:5u(1,i)=u(1,i)-x(1,i);v(1,i)=v(1,i)-y(1,i);endquiver(x,y,u,v,0);% 画矢量图x=