《MPST问题MATLAB程序--精选文档》由会员分享，可在线阅读，更多相关《MPST问题MATLAB程序--精选文档（12页珍藏版）》请在金锄头文库上搜索。
1、基于遗传算法的TSP算法 matlab代码主程序：clc;clear all;close all;global x yx=0 3 1 5 4 0 3 7 9 10 14 17 14 12 10 19 2 6 11 15 7 22 21 27 15 15 20 21 24 25 28;y=0 2 5 4 7 8 11 9 6 2 0 3 6 9 12 9 16 18 17 12 14 5 0 9 19 14 17 13 20 16 18;a=8 8.2 6 5.5 3 4.5 7.2 2.3 1.4 6.5 4.1 12.7 5.8 3.8 3.4 3.5 5.8 7.5 7.8 4.6 6.2
2、 6.8 2.4 7.6 9.6 10 12 6 8.1 4.2;h=0:30;t=31+1; %送货点数s=1500; %初始中群数G=500; %最大迭代次数c=25; %一次选取25个样本pc=0.80; %交配率pm=0.01; %变异率pop=zeros(s,t); for i=1:s pop(i,1:t-1)=randperm(t-1); %初始化种群end for k=1:1:G %GA开始if mod(k,50)=1 kendpop=distance1(pop); %调用距离函数 pop=select(pop,c); %调用选择函数 p1=rand;if p1=pc pop=c
3、ross(pop); %调用交配函数end p2=rand;if p2=pm pop=mutate(pop); %调用变异函数end end %GA结束%bestL=min(pop(:,t)J=pop(:,t);fi=1./J; Oderfi,Indexfi=sort(fi); %对fi进行排序BestS=pop(Indexfi(s),:); %得到最短路径 I=BestS; for i=1:1:t-1 x1(i)=x(I(i); y1(i)=y(I(i);endx1(t)=x(I(1);y1(t)=y(I(1); cities_new=x1;y1;disp(Best Route is:);d
4、isp(cities_new);pos=cities_new cities_new(:,1); lentemp=0;for i=1:1:t-1 temp=(abs(pos(1,i)-pos(1,i+1)+abs(pos(2,i)-pos(2,i+1); lentemp=lentemp+temp;enddisp(Shortest Length is:);disp(lentemp); plot(x1,y1,-or);xlabel(X axis), ylabel(Y axis), title(最短路径);axis(0,1,0,1);axis(0,30,0,20);axis on距离函数matlab代
5、码：function pop=distance1(pop)global x ys,t=size(pop); for i=1:1:s dd=0; pos=pop(i,1:t-1); pos=pos pos(:,1); for j=1:1:t-1 m=pos(j); n=pos(j+1); dd=dd+(abs(x(m)-x(n)+abs(y(m)-y(n); end pop(i,t)=dd;end选择函数matlab代码：function pop=select(pop,c)s,t=size(pop);m11=(pop(:,t);m11=m11;mmax=zeros(1,c);mmin=zeros
6、(1,c); num=1;while numc+1 %取距离大的C个样本 a,mmax(num)=max(m11); m11(mmax(num)=0; num=num+1;end num=1;while numc+1 %取距离小的C个样本 b,mmin(num)=min(m11); m11(mmin(num)=a; num=num+1;end for i=1:c pop(mmax(i),:)=pop(mmin(i),:); end交配函数matlab代码：function pop=cross(pop)s,t=size(pop);pop_1=pop;n=randperm(s); %将种群随机排序
7、for i=1:2:s %随机选择两个交叉点 m=randperm(t-3)+1; crosspoint(1)=min(m(1),m(2); crosspoint(2)=max(m(1),m(2);%任意两行交叉 x1=n(i); x2=n(i+1);%将X1左边与X2的左边互换 middle=pop(x1,1:crosspoint(1); pop(x1,1:crosspoint(1)=pop(x2,1:crosspoint(1); pop(x2,1:crosspoint(1)=middle;%将X1右边与X2的右边互换 middle=pop(x1,crosspoint(2)+1:t); po
8、p(x1,crosspoint(2)+1:t)=pop(x2,crosspoint(2)+1:t); pop(x2,crosspoint(2)+1:t)=middle; for j=1:crosspoint(1) while find(pop(x1,crosspoint(1)+1:crosspoint(2)=pop(x1,j) zhi=find(pop(x1,crosspoint(1)+1:crosspoint(2)=pop(x1,j); temp=pop(x2,crosspoint(1)+zhi); pop(x1,j)=temp; end end for j=crosspoint(2)+1:
9、t-1 while find(pop(x1,crosspoint(1)+1:crosspoint(2)=pop(x1,j) zhi=find(pop(x1,crosspoint(1)+1:crosspoint(2)=pop(x1,j); temp=pop(x2,crosspoint(1)+zhi); pop(x1,j)=temp; end end for j=1:crosspoint(1) while find(pop(x2,crosspoint(1)+1:crosspoint(2)=pop(x2,j) zhi=find(pop(x2,crosspoint(1)+1:crosspoint(2)
10、=pop(x2,j); temp=pop(x1,crosspoint(1)+zhi); pop(x2,j)=temp; end end for j=crosspoint(2)+1:t-1 while find(pop(x2,crosspoint(1)+1:crosspoint(2)=pop(x2,j) zhi=find(pop(x2,crosspoint(1)+1:crosspoint(2)=pop(x2,j); temp=pop(x1,crosspoint(1)+zhi); pop(x2,j)=temp; end endend%生成新的种群与交叉前相比较 pop=distance1(pop)
11、;for i=1:s if pop_1(i,t)pop(i,t) pop(i,:)=pop_1(i,:); endend变异函数matlab代码：function pop=mutate(pop)s,t=size(pop); pop_1=pop;for i=1:2:s m=randperm(t-3)+1;%随机选取两个点 mutatepoint(1)=min(m(1),m(2); mutatepoint(2)=max(m(1),m(2);%用倒置变异的方法倒置两个点中间部分的位置 mutate=round(mutatepoint(2)-mutatepoint(1)/2-0.5); for j=1
12、:mutate zhong=pop(i,mutatepoint(1)+j); pop(i,mutatepoint(1)+j)=pop(i,mutatepoint(2)-j); pop(i,mutatepoint(2)-j)=zhong; endend pop=distance1(pop);for i=1:s if pop_1(i,t)pop(i,t) pop(i,:)=pop_1(i,:); endend附录二：遗传算法MTSP matlab代码程序一：function varargout = mtspf_ga(xy,dmat,salesmen,min_tour,pop_size,num_it
13、er,show_prog,show_res)%xy 各个送货点坐标%dmat 送货点之间距离%salesmen 路径数%min_tour 派送员最少到底派送点数%pop_size 种群个体数%num_iter 迭代代数%show_prog,show_res 显示参数设定a=0 8 8.2 6 5.5 3 4.5 7.2 2.3 1.4 6.5 4.1 12.7 5.8 3.8 3.4 3.5 5.8 7.5 7.8 4.6 6.2 6.8 2.4 7.6 9.6 10 12 6 8.1 4.2; nr,nc = size(dmat);if nr = nc error(Invalid XY or DMAT inputs!)endn = nr - 1; %送货点数 % 输入参数
