MATLAB多旅行商问题源代码

MATLAB多旅行商问题源代码functionvarargout=mtspf_ga(xy,dmat,salesmen,min_tour,pop_size,num_iter,show_prog,show_res)%MTSPF_GAFixedMultipleTravelingSalesmenProblem(M-TSP)GeneticAlgorithm(GA)%Findsa(near)optimalsolutiontoavariationoftheM-TSPbysetting%upaGAtosearchfortheshortestroute(leastdistanceneededfor%eachsalesmantotravelfromthestartlocationtoindividualcities%andbacktotheoriginalstartingplace)%%Summary:%1.Eachsalesmanstartsatthefirstpoint,andendsatthefirst%point,buttravelstoauniquesetofcitiesinbetween%2.Exceptforthefirst,eachcityisvisitedbyexactlyonesalesman%%Note:TheFixedStart/EndlocationistakentobethefirstXYpoint%%Input:%XY(float)isanNx2matrixofcitylocations,whereNisthenumberofcities%DMAT(float)isanNxNmatrixofcity-to-citydistancesorcosts%SALESMEN(scalarinteger)isthenumberofsalesmentovisitthecities%MIN_TOUR(scalarinteger)istheminimumtourlengthforanyofthe%salesmen,NOTincludingthestart/endpoint%POP_SIZE(scalarinteger)isthesizeofthepopulation(shouldbedivisibleby8)%NUM_ITER(scalarinteger)isthenumberofdesirediterationsforthealgorithmtorun%SHOW_PROG(scalarlogical)showstheGAprogressiftrue%SHOW_RES(scalarlogical)showstheGAresultsiftrue%%Output:%OPT_RTE(integerarray)isthebestroutefoundbythealgorithm%OPT_BRK(integerarray)isthelistofroutebreakpoints(thesespecifytheindices%intotherouteusedtoobtaintheindividualsalesmanroutes)%MIN_DIST(scalarfloat)isthetotaldistancetraveledbythesalesmen%%Route/BreakpointDetails:%Ifthereare10citiesand3salesmen,apossibleroute/break%combinationmightbe:rte=[5694281037],brks=[37]%Takentogether,theserepresentthesolution[15691][14281][110371],%whichdesignatestheroutesforthe3salesmenasfollows:%.Salesman1travelsfromcity1to5to6to9andbackto1%.Salesman2travelsfromcity1to4to2to8andbackto1%.Salesman3travelsfromcity1to10to3to7andbackto1%%2DExample:%n=35;%xy=10*rand(n,2);%salesmen=5;%min_tour=3;%pop_size=80;%num_iter=5e3;%a=meshgrid(1:n);%dmat=reshape(sqrt(sum((xy(a,:)-xy(a',:)).^2,2)),n,n);%[opt_rte,opt_brk,min_dist]=mtspf_ga(xy,dmat,salesmen,min_tour,...%pop_size,num_iter,1,1);%%3DExample:%n=35;%xyz=10*rand(n,3);%salesmen=5;%min_tour=3;%pop_size=80;%num_iter=5e3;%a=meshgrid(1:n);%dmat=reshape(sqrt(sum((xyz(a,:)-xyz(a',:)).^2,2)),n,n);%[opt_rte,opt_brk,min_dist]=mtspf_ga(xyz,dmat,salesmen,min_tour,...%pop_size,num_iter,1,1);%%Seealso:mtsp_ga,mtspo_ga,mtspof_ga,mtspofs_ga,mtspv_ga,distmat%%Author:JosephKirk%Email:[e-mail]%Release:1.3%ReleaseDate:6/2/09%ProcessInputsandInitializeDefaultsnargs=8;fork=nargin:nargs-1switchkcase0xy=10*rand(40,2);case1N=size(xy,1);a=meshgrid(1:N);dmat=reshape(sqrt(sum((xy(a,:)-xy(a',:)).^2,2)),N,N);case2salesmen=5;case3min_tour=2;case4pop_size=80;case5num_iter=5e3;case6show_prog=1;case7show_res=1;otherwiseendend%VerifyInputs[N,dims]=size(xy);[nr,nc]=size(dmat);ifN~=nr||N~=ncerror('InvalidXYorDMATinputs!')endn=N-1;%SeparateStart/EndCity%SanityCheckssalesmen=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));%InitializationsforRouteBreakPointSelectionnum_brks=salesmen-1;dof=n-min_tour*salesmen;%degreesoffreedomaddto=ones(1,dof+1);fork=2:num_brksaddto=cumsum(addto);endcum_prob=cumsum(addto)/sum(addto);%InitializethePopulationspop_rte=zeros(pop_size,n);%populationofroutespop_brk=zeros(pop_size,num_brks);%populationofbreaksfork=1:pop_sizepop_rte(k,:)=randperm(n)+1;pop_brk(k,:)=randbreaks();end%SelecttheColorsforthePlottedRoutesclr=[100;001;0.6701;010;10.50];ifsalesmen5clr=hsv(salesmen);end%RuntheGAglobal_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%EvaluateMembersofthePopulationforp=1:pop_sized=0;p_rte=pop_rte(p,:);p_brk=pop_brk(p,:);rng=[[1p_brk+1];[p_brkn]]';fors=1:salesmend=d+dmat(1,p_rte(rng(s,1)));%AddStartDistancefork=rng(s,1):rng(s,2)-1d=d+dmat(p_rte(k),p_rte(k+1));endd=d+dmat(p_rte(rng(s,2)),1);%AddEndDistanceendtotal_dist(p)=d;end%FindtheBestRouteinthePopulation[min_dist,index]=min(total_dist);dist_history(iter)=min_dist;ifmin_distglobal_minglobal_min=min_dist;opt_rte=pop_rte(index,:);opt_brk=pop_brk(index,:);rng=[[1opt_brk+1];[opt_brkn]]';ifshow_prog%PlottheBestRoutefigure(pfig);fors=1:salesmenrte=[1opt_rte(rng(s,1):rng(s,2))1];ifdims==3,plot3(xy(rte,1),xy(rte,2),xy(rte,3),'.-','Color',clr(s,:));elseplot(xy(rte,1),xy(rte,2),'.-','Color',clr(s,:));endtitle(sprintf('TotalDistance=%1.4f,Iteration=%d',min_dist,iter));holdonendifdims==3,plot3(xy(1,1),xy(1,2),xy(1,3),'ko');elseplot(xy(1,1),xy(1,2),'ko');endholdoffendend%GeneticAlgorithmOperatorsrand_grouping=randperm(pop_size);forp=8:8:pop_sizertes=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_rt