MPST问题MATLAB程序

《MPST问题MATLAB程序》由会员分享，可在线阅读，更多相关《MPST问题MATLAB程序（12页珍藏版）》请在装配图网上搜索。

1、-基于遗传算法的TSP算法 matlab代码主程序：clc;clear all;close all;global * y*=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); %初始化种群endfor k=1:1:G %GA开场if mod(k,50)=1 kendpop=distance1(pop); %调用距离函数pop=select(pop,c); %调用选择函数p1=rand;if p1=pc pop=cro

3、ss(pop); %调用交配函数endp2=rand;if p2=pm pop=mutate(pop); %调用变异函数endend%GA完毕%bestL=min(pop(:,t)J=pop(:,t);fi=1./J;Oderfi,Inde*fi=sort(fi); %对fi进展排序BestS=pop(Inde*fi(s),:); %得到最短路径I=BestS;for i=1:1:t-1 *1(i)=*(I(i); y1(i)=y(I(i);end*1(t)=*(I(1);y1(t)=y(I(1);cities_new=*1;y1;disp(Best Route is:);disp(citie

4、s_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(*1,y1,-or);*label(* a*is), ylabel(Y a*is), title(最短路径);a*is(0,1,0,1);a*is(0,30,0,20);a*is on距离函数matlab代码：function

5、pop=distance1(pop)global * 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(*(m)-*(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;mma*=zeros(1,c);mmin=zeros(1,c);num=1;wh

6、ile numc+1 %取距离大的C个样本 a,mma*(num)=ma*(m11); m11(mma*(num)=0; num=num+1;endnum=1;while numc+1 %取距离小的C个样本 b,mmin(num)=min(m11); m11(mmin(num)=a; num=num+1;endfor i=1:c pop(mma*(i),:)=pop(mmin(i),:); end交配函数matlab代码：function pop=cross(pop)s,t=size(pop);pop_1=pop;n=randperm(s); %将种群随机排序for i=1:2:s%随机选择两

7、个穿插点 m=randperm(t-3)+1; crosspoint(1)=min(m(1),m(2); crosspoint(2)=ma*(m(1),m(2);%任意两行穿插 *1=n(i); *2=n(i+1);%将*1左边与*2的左边互换 middle=pop(*1,1:crosspoint(1); pop(*1,1:crosspoint(1)=pop(*2,1:crosspoint(1); pop(*2,1:crosspoint(1)=middle;%将*1右边与*2的右边互换 middle=pop(*1,crosspoint(2)+1:t); pop(*1,crosspoint(2)

8、+1:t)=pop(*2,crosspoint(2)+1:t); pop(*2,crosspoint(2)+1:t)=middle;for j=1:crosspoint(1)while find(pop(*1,crosspoint(1)+1:crosspoint(2)=pop(*1,j) zhi=find(pop(*1,crosspoint(1)+1:crosspoint(2)=pop(*1,j); temp=pop(*2,crosspoint(1)+zhi); pop(*1,j)=temp;endendfor j=crosspoint(2)+1:t-1while find(pop(*1,cr

9、osspoint(1)+1:crosspoint(2)=pop(*1,j) zhi=find(pop(*1,crosspoint(1)+1:crosspoint(2)=pop(*1,j); temp=pop(*2,crosspoint(1)+zhi); pop(*1,j)=temp;endendfor j=1:crosspoint(1)while find(pop(*2,crosspoint(1)+1:crosspoint(2)=pop(*2,j) zhi=find(pop(*2,crosspoint(1)+1:crosspoint(2)=pop(*2,j); temp=pop(*1,cros

10、spoint(1)+zhi); pop(*2,j)=temp;endendfor j=crosspoint(2)+1:t-1while find(pop(*2,crosspoint(1)+1:crosspoint(2)=pop(*2,j) zhi=find(pop(*2,crosspoint(1)+1:crosspoint(2)=pop(*2,j); temp=pop(*1,crosspoint(1)+zhi); pop(*2,j)=temp;endendend%生成新的种群与穿插前相比拟 pop=distance1(pop);for i=1:sif pop_1(i,t)pop(i,t) po

11、p(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)=ma*(m(1),m(2);%用倒置变异的方法倒置两个点中间局部的位置 mutate=round(mutatepoint(2)-mutatepoint(1)/2-0.5);for j=1:mutate zhong=pop(i,mutatepoint(1)+j);

12、 pop(i,mutatepoint(1)+j)=pop(i,mutatepoint(2)-j); pop(i,mutatepoint(2)-j)=zhong;endendpop=distance1(pop);for i=1:sif pop_1(i,t) 5 clr = hsv(salesmen);end% 开场遗传算法global_min = Inf; %初始化最短路径total_dist = zeros(1,pop_size);dist_history = zeros(1,num_iter);tmp_pop_rte = zeros(8,n); %当前的路径设置tmp_pop_brk = z

13、eros(8,num_brks); %当前的断点设置new_pop_rte = zeros(pop_size,n); %更新的路径设置new_pop_brk = zeros(pop_size,num_brks);%更新的断点设置if show_prog pfig = figure(Name,MTSPF_GA | Current Best Solution,Numbertitle,off);endfor iter = 1:num_iter%评价每一代的种群适应情况并作出选择for p = 1:pop_size p_rte = pop_rte(p,:); p_brk = pop_brk(p,:);

14、 rng = 1 p_brk+1;p_brk n; w=0;for s = 1:salesmen h=0;d=0; d = d + dmat(1,p_rte(rng(s,1); w = w + dmat(1,p_rte(rng(s,1)*a(p_rte(rng(s,1)*3; % 添加初始路径for k = rng(s,1):rng(s,2)-1d = d + dmat(p_rte(k),p_rte(k+1);w = w + d*a(p_rte(k+1)*3; h = h + a(p_rte(1+k);end h = h + a(p_rte(k+1); d = d + (dmat(p_rte(

15、rng(s,2),1); w = w + (dmat(p_rte(rng(s,2),1)*2; % 添加完毕路径if h25 w=inf;endend total_dist(p) = w;end% 在每代种群中找到最好路径 min_dist,inde* = min(total_dist);dist_history(iter) = min_dist; if min_dist global_min global_min = min_dist;opt_rte = pop_rte(inde*,:); opt_brk = pop_brk(inde*,:); rng = 1 opt_brk+1;opt_b

16、rk n; if show_prog% Plot the Best Route figure(pfig);for s = 1:salesmen rte = 1 opt_rte(rng(s,1):rng(s,2) 1; plot(*y(rte,1),*y(rte,2),.-,Color,clr(s,:); title(sprintf(Total Distance = %1.4f, Iteration = %d,min_dist,iter); hold onend plot(*y(1,1),*y(1,2),ko); hold offendend% 遗传算法操作集合 rand_grouping =

17、randperm(pop_size);for p = 8:8:pop_size rtes = pop_rte(rand_grouping(p-7:p),:); brks = pop_brk(rand_grouping(p-7:p),:); dists = total_dist(rand_grouping(p-7:p); ignore,id* = min(dists); best_of_8_rte = rtes(id*,:); best_of_8_brk = brks(id*,:);rte_ins_pts = sort(ceil(n*rand(1,2); I = rte_ins_pts(1);

18、J = rte_ins_pts(2);for k = 1:8 %产生新方案 tmp_pop_rte(k,:) = best_of_8_rte; tmp_pop_brk(k,:) = best_of_8_brk;switch kcase 2 % 倒置操作 tmp_pop_rte(k,I:J) = fliplr(tmp_pop_rte(k,I:J);case 3 % 互换操作 tmp_pop_rte(k,I J) = tmp_pop_rte(k,J I);case 4 % 滑动平移操作 tmp_pop_rte(k,I:J) = tmp_pop_rte(k,I+1:J I);case 5 % 更新断

19、点 tmp_pop_brk(k,:) = randbreaks();case 6 % 倒置并更新断点 tmp_pop_rte(k,I:J) = fliplr(tmp_pop_rte(k,I:J); tmp_pop_brk(k,:) = randbreaks();case 7 % 互换并更新断点 tmp_pop_rte(k,I J) = tmp_pop_rte(k,J I); tmp_pop_brk(k,:) = randbreaks();case 8 % 评议并更新断点 tmp_pop_rte(k,I:J) = tmp_pop_rte(k,I+1:J I); tmp_pop_brk(k,:)

20、= randbreaks();otherwiseendend new_pop_rte(p-7:p,:) = tmp_pop_rte; new_pop_brk(p-7:p,:) = tmp_pop_brk;end pop_rte = new_pop_rte; pop_brk = new_pop_brk;end% 返回结果rng = 1 opt_brk+1;opt_brk n;dis_e=zeros(1,salesmen); for s = 1:salesmen dis_e(s)=myLength(dmat,opt_rte(rng(s,1):rng(s,2);endif nargout varar

21、gout1 = opt_rte; varargout2 = opt_brk; varargout3 = min_dist; varargout4 = dis_e;endif show_res% Plots figure(Name,MTSPF_GA | Results,Numbertitle,off); subplot(2,2,1); plot(*y(:,1),*y(:,2),k.); title(City Locations); subplot(2,2,2); imagesc(dmat(1 opt_rte,1 opt_rte); title(Distance Matri*); subplot(

22、2,2,3); rng = 1 opt_brk+1;opt_brk n;for s = 1:salesmen rte = 1 opt_rte(rng(s,1):rng(s,2) 1; plot(*y(rte,1),*y(rte,2),.-,Color,clr(s,:); title(sprintf(Total Distance = %1.4f,min_dist); hold on;end plot(*y(1,1),*y(1,2),ko); subplot(2,2,4); plot(dist_history,b,LineWidth,2); title(Best Solution History)

23、; set(gca,*Lim,0 num_iter+1,YLim,0 1.1*ma*(1 dist_history);end% 随机产生一套断点的集合function breaks = randbreaks()if min_tour = 1 %一个旅行商时没有设置断点 tmp_brks = randperm(n-1); breaks = sort(tmp_brks(1:num_brks);else% 强制断点至少找到最短路径的长度 num_adjust = find(rand cum_prob,1)-1; spaces = ceil(num_brks*rand(1,num_adjust); a

24、djust = zeros(1,num_brks);for kk = 1:num_brks adjust(kk) = sum(spaces = kk);end breaks = min_tour*(1:num_brks) + cumsum(adjust);endendend%bestL=min(pop(:,t)J=pop(:,t);fi=1./J;Oderfi,Inde*fi=sort(fi); BestS=pop(Inde*fi(s),:); I=BestS;for i=1:1:t-1 *1(i)=*(I(i); y1(i)=y(I(i);end*1(t)=*(I(1);y1(t)=y(I(

25、1);cities_new=*1;y1;disp(Best Route is:);disp(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(*1,y1,-or);*label(* a*is), ylabel(Y a*is), title();a*is(0,1,0,1

26、);a*is(0,30,0,20);a*is on程序:二：*=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=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.

27、1 4.2;m,n=size(*);*=*;y=y;*y=* y;salesmen = 9;min_tour = 8;pop_size = 80;num_iter = 5e3;suma=sum(a);for i=1:nfor j=1:n dmat(i,j) = abs(*(i)-*(j)+abs(y(i)-y(j);endendopt_rte,opt_brk,min_dist = mtspf_ga(*y,dmat,salesmen,min_tour,pop_size,num_iter,1,1)m1,n1=size(opt_brk);for i=1:n1-1 z=0;for j=opt_brk(

28、i):opt_brk(i+1) z=z+a(opt_rte(j+1);end zend以点0表示旅行商的出发城市，称为源点，点表示个旅行商需访问的城市。MTSP问题的数学模型可以表示为：令模型表示如下：没有编号了？式中：为增广费用。假设用表示旅行商经过对应弧度所花的费用，如时间、距离、花费等，则给增加行和列，每一新的行或列是的最后一行或列的复制，增广矩阵的其他元素为无穷大，由此构成了增广费用。一般MTSP中，旅行商访问个城市必须满足以下2个条件。条件1：从指定城市出发，对其他所有城市严格访问一次后返回原出发城市。条件2：一条有效路径严格由条非平凡子路径(Nontrivial Subtours)

29、组成。所谓非平凡子路径是指该路径中除出发城市外，至少访问一个其他城市。用遗传算法求解MTSP，可通过附加虚拟城市的方法把MTSP转化为TSP。将另外个旅行商理解为个虚拟城市，这个虚拟城市标号分别为，它们与城市0具有一样的坐标(即一样位置)。在旅行商访问路径中出现的每一个虚拟城市均表示旅行商返回出发城市，从而组成一个回路。每个回路表示MTSP中一个旅行商的旅行路径。需注意的是，为了防止出现平凡子路径，必须假设个虚拟城市到原点的距离为为一无穷大的正数即永远不能到达，到其他各点距离与原点一致，这样遗传算法就不会出现0-0-0的途径。将源点0复制个，个源点编号为每一个同源点0一样与其他点相连，而个源点互相不连接，这样在结点集上，可得到TSP线路，然后各源点合并成一个点。这样MTSP线路就分解成个分线路。. z.