MPST问题MATLAB程序

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=

3、cross(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

4、:);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(x1,y1,-or);xlabel(x axis), ylabel(y axis), title(最短路径);axis(0,1,0,1);axis(0,30,0,20);axis on距离函数mat

5、lab代码：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);mmi

6、n=zeros(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

8、)+1:t); pop(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=crossp

9、oint(2)+1: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:cro

10、sspoint(2)=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=dist

11、ance1(pop);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-

12、0.5); for j=1: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) 5 clr = hsv(salesmen);end % 开始遗传算法global_min = inf; %初始化最短路径total_dist = zeros(1,pop_size);dist_history = zeros(1,num_

13、iter);tmp_pop_rte = zeros(8,n); %当前的路径设置tmp_pop_brk = zeros(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 %评价每一代的种群 适应情况并作出选择 f

14、or p = 1:pop_size p_rte = pop_rte(p,:); p_brk = pop_brk(p,:); 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)-1 d = d + dmat(p_rte(k),p_rte(k+1); w = w + d*a(p_rte(k+1)*3; h

15、= h + a(p_rte(1+k); end h = h + a(p_rte(k+1); d = d + (dmat(p_rte(rng(s,2),1); w = w + (dmat(p_rte(rng(s,2),1)*2; % 添加结束路径 if h25 w=inf; end end total_dist(p) = w; end % 在每代种群中找到最好路径 min_dist,index = min(total_dist); dist_history(iter) = min_dist; if min_dist global_min global_min = min_dist; opt_rt

16、e = pop_rte(index,:); opt_brk = pop_brk(index,:); rng = 1 opt_brk+1;opt_brk 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(xy(rte,1),xy(rte,2),.-,color,clr(s,:); title(sprintf(total distance = %1.4f, iteration = %d,min_dist,iter);精品.

17、hold on end plot(xy(1,1),xy(1,2),ko); hold off end end % 遗传算法操作集合 rand_grouping = 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,idx = min(dists); best_of_8_rte = rtes(idx,:); be

18、st_of_8_brk = brks(idx,:); rte_ins_pts = sort(ceil(n*rand(1,2); i = rte_ins_pts(1); 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 k case 2 % 倒置操作 tmp_pop_rte(k,i:j) = fliplr(tmp_pop_rte(k,i:j); case 3 % 互换操作 tmp_pop_rte(k,i j) = tmp

19、_pop_rte(k,j i); case 4 % 滑动平移操作 tmp_pop_rte(k,i:j) = tmp_pop_rte(k,i+1:j i); case 5 % 更新断点 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,:) =

20、randbreaks(); case 8 % 评议并更新断点 tmp_pop_rte(k,i:j) = tmp_pop_rte(k,i+1:j i); tmp_pop_brk(k,:) = randbreaks(); otherwise end end 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

21、(1,salesmen); for s = 1:salesmen dis_e(s)=mylength(dmat,opt_rte(rng(s,1):rng(s,2);end if nargout varargout1 = 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(xy(:,1),xy(:,2),k.); tit

22、le(city locations); subplot(2,2,2); imagesc(dmat(1 opt_rte,1 opt_rte); title(distance matrix); subplot(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(xy(rte,1),xy(rte,2),.-,color,clr(s,:); title(sprintf(total distance = %1.4f,min_dist); hold on; end

23、 plot(xy(1,1),xy(1,2),ko); subplot(2,2,4); plot(dist_history,b,linewidth,2); title(best solution history); set(gca,xlim,0 num_iter+1,ylim,0 1.1*max(1 dist_history);end % 随机产生一套断点的集合 function breaks = randbreaks() if min_tour = 1 %一个旅行商时没有设置断点精品. tmp_brks = randperm(n-1); breaks = sort(tmp_brks(1:num

24、_brks); else % 强制断点至少找到最短路径的长度 num_adjust = find(rand cum_prob,1)-1; spaces = ceil(num_brks*rand(1,num_adjust); adjust = zeros(1,num_brks); for kk = 1:num_brks adjust(kk) = sum(spaces = kk); end breaks = min_tour*(1:num_brks) + cumsum(adjust); end endend%bestl=min(pop(:,t)j=pop(:,t);fi=1./j; oderfi,

25、indexfi=sort(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:);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=len

26、temp+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程序:二：x=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.1 4.2;m,n=size(x);x=x;y=y;xy=x y;salesmen = 9;min_tour = 8;pop_size = 80;num_iter = 5e3;suma=sum(