搜索
基于遗传算法的TSP算法matlab代码主程序：clc;clearall;closeall;globalxyx=[03154037910141714121019261115722212715152021242528];y=[025478119620369129161817121450919141713201618];a=[88.265.534.57.22.31.46.54.112.75.83.83.43.55.87.57.84.66.26.82.47.69.6101268.14.2];h=0:30;t=31+1;%送货点数s=1500;%初始中群数G=500;%最大迭代次数c=25;%一次选取25个样本pc=0.80;%交配率pm=0.01;%变异率pop=zeros(s,t);fori=1:spop(i,1:t-1)=randperm(t-1);%初始化种群endfork=1:1:G%GA开始¼ifmod(k,50)==1kendpop=distance1(pop);%调用距离函数pop=select(pop,c);%调用选择函数p1=rand;ifp1=pcpop=cross(pop);%调用交配函数endp2=rand;ifp2=pmpop=mutate(pop);%调用变异函数endend%GA结束%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%bestL=min(pop(:,t))J=pop(:,t);fi=1./J;[Oderfi,Indexfi]=sort(fi);%对fi进行排序BestS=pop(Indexfi(s),:);%得到最短路径I=BestS;fori=1:1:t-1x1(i)=x(I(i));y1(i)=y(I(i));endx1(t)=x(I(1));y1(t)=y(I(1));cities_new=[x1;y1];disp('BestRouteis:');disp(cities_new);pos=[cities_newcities_new(:,1)];lentemp=0;fori=1:1:t-1temp=(abs(pos(1,i)-pos(1,i+1))+abs(pos(2,i)-pos(2,i+1)));lentemp=lentemp+temp;enddisp('ShortestLengthis:');disp(lentemp);plot(x1,y1,'-or');xlabel('Xaxis'),ylabel('Yaxis'),title('最短路径');axis([0,1,0,1]);axis([0,30,0,20]);axison距离函数matlab代码：function[pop]=distance1(pop)globalxy[s,t]=size(pop);fori=1:1:sdd=0;pos=pop(i,1:t-1);pos=[pospos(:,1)];forj=1:1:t-1m=pos(j);n=pos(j+1);dd=dd+(abs(x(m)-x(n))+abs(y(m)-y(n)));endpop(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(1,c);num=1;whilenumc+1%取距离大的C个样本[a,mmax(num)]=max(m11);m11(mmax(num))=0;num=num+1;endnum=1;whilenumc+1%取距离小的C个样本[b,mmin(num)]=min(m11);m11(mmin(num))=a;num=num+1;endfori=1:cpop(mmax(i),:)=pop(mmin(i),:);end交配函数matlab代码：function[pop]=cross(pop)[s,t]=size(pop);pop_1=pop;n=randperm(s);%将种群随机排序fori=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);pop(x1,crosspoint(2)+1:t)=pop(x2,crosspoint(2)+1:t);pop(x2,crosspoint(2)+1:t)=middle;forj=1:crosspoint(1)whilefind(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;endendforj=crosspoint(2)+1:t-1whilefind(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;endendforj=1:crosspoint(1)whilefind(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;endendforj=crosspoint(2)+1:t-1whilefind(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;endendend%生成新的种群与交叉前相比较[pop]=distance1(pop);fori=1:sifpop_1(i,t)pop(i,t)pop(i,:)=pop_1(i,:);endend变异函数matlab代码：function[pop]=mutate(pop)[s,t]=size(pop);pop_1=pop;fori=1:2:sm=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);forj=1:mutatezhong=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);fori=1:sifpop_1(i,t)pop(i,t)pop(i,:)=pop_1(i,:);endend附录二：遗传算法MTSPmatlab代码程序一：functionvarargout=mtspf_ga(xy,dmat,salesmen,min_tour,pop_size,num_iter,show_prog,show_res)%xy各个送货点坐标%dmat送货点之间距离%salesmen路径数%min_tour派送员最少到底派送点数%pop_size种群个体数%num_iter迭代代数%show_prog,show_res显示参数设定a=[088.265.534.57.22.31.46.54.112.75.83.83.43.55.87.57.84.66.26.82.47.69.6101268.14.2];[nr,nc]=size(dmat);ifnr~=ncerror('InvalidXYorDMATinputs!')endn=nr-1;%送货点数%输入参数检查salesmen=max(1,min(n,round(real(salesmen(1)))));min_tour=max(1,min(floor(n/salesmen),round(real(min_tour(1)))));pop_size=max(8,8*ceil(pop_size(1)/8));num_iter=max(1,round(real(num_iter(1))));show_prog=logical(show_prog(1));show_res=logical(show_res(1));%初始化路线，断点num_brks=salesmen-1;dof=n-min_tour*salesmen;addto=ones(1,dof+1);fork=2:num_brksaddto=cumsum(addto);endcum_prob=cumsum(addto)/sum(addto);%初始化种群pop_rte=zeros(pop_size,n);%路径集合的种群pop_brk=zeros(pop_size,num_brks);%断点集合的种群fork=1:pop_sizepop_rte(k,:)=randperm(n)+1;pop_brk(k,:)=randbreaks();endclr=[100;001;0.6701;010;10.50];ifsalesmen5clr=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=zeros(8,num_brks);%当前的断点设置new_pop_rte=zeros(pop_size,n);%更新的路径设置new_pop_brk=zeros(pop_size,num_brks);%更新的断点设置ifshow_progpfig=figure('Name','MTSPF_GA|CurrentBestSolution','Numbertitle','off');endforiter=1:num_iter%评价每一代的种群适应情况并作出选择forp=1:pop_sizep_rte=pop_rte(p,:);p_brk=pop_brk(p,:);rng=[[1p_brk+1];[p_brkn]]';w=0;fors=1:salesmenh=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;%添加初始路径fork=r