MATL新编多旅行商问题源代码

文件编码（TTU-UITID-GGBKT-POIU-WUUI-0089）MATL新编多旅行商问题源代码PAGEMATLAB多旅行商问题源代码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%Release:%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;01;010;10];ifsalesmen>5clr=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_dist