MATLAB多旅行商問題源代碼

1、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%eachsa

2、lesmantotravelfromthestartlocationtoindividualcities%andbacktotheoriginalstartingplace)%Summary:%1.Eachsalesmanstartsatthefirstpoint,andendsatthefirst%point,buttravelstoauniquesetofcitiesinbetween%2.Exceptforthefirst,eachcityisvisitedbyexactlyonesalesman%Note:TheFixedStart/Endlocationistakentobethef

3、irstXYpoint%Input:%XY(float)isanNx2matrixofcitylocations,whereNisthenumberofcities%DMAT(float)isanNxNmatrixofcity-to-citydistancesorcosts%SALESMEN(scalarinteger)isthenumberofsalesmentovisitthecities%MIN_TOUR(scalarinteger)istheminimumtourlengthforanyofthe%salesmen,NOTincludingthestart/endpoint%POP_S

4、IZE(scalarinteger)isthesizeofthepopulation(shouldbedivisibleby8)%NUM_ITER(scalarinteger)isthenumberofdesirediterationsforthealgorithmtorun%SHOW_PROG(scalarlogical)showstheGAprogressiftrue%SHOW_RES(scalarlogical)showstheGAresultsiftrue%Output:%OPT_RTE(integerarray)isthebestroutefoundbythealgorithm%OP

5、T_BRK(integerarray)isthelistofroutebreakpoints(thesespecifytheindices%intotherouteusedtoobtaintheindividualsalesmanroutes)%MIN_DIST(scalarfloat)isthetotaldistancetraveledbythesalesmen%Route/BreakpointDetails:%Ifthereare10citiesand3salesmen,apossibleroute/break%combinationmightbe:rte=5694281037,brks=

6、37%Takentogether,theserepresentthesolution1569114281110371,%whichdesignatestheroutesforthe3salesmenasfollows:%.Salesman1travelsfromcity1to5to6to9andbackto1%.Salesman2travelsfromcity1to4to2to8andbackto1%.Salesman3travelsfromcity1to10to3to7andbackto1%2DExample:%n=35;%xy=10*rand(n,2);%salesmen=5;%min_t

7、our=3;%pop_size=80;%num_iter=5e3;%a=meshgrid(1:n);%dmat=reshape(sqrt(sum(xy(a,:)-xy(a',:).A2,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=

8、reshape(sqrt(sum(xyz(a,:)-xyz(a',:).A2,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

9、=nargin:nargs-1switchkcase0xy=10*rand(40,2);case 1N=size(xy,1);a=meshgrid(1:N);dmat=reshape(sqrt(sum(xy(a,:)-xy(a',:).A2,2),N,N);case 2salesmen=5;case 3min_tour=2;case 4pop_size=80;case 5num_iter=5e3;case 6show_prog=1;case 7show_res=1;otherwiseendend%VerifyInputsN,dims=size(xy);nr,nc=size(dmat);

10、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

11、(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);cum_prob=cumsum(addto)/sum(addto);%InitializethePopulationspop_rte=zeros(pop_size,n);%populationofroutespop_

12、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_

13、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_prog| Current Best Solution','Numbertitle','off')pfig=figure('Name','MTSPF_GAendforiter=1:num_iter%EvaluateMembersofthePopulationforp=1:pop_sized

14、=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%FindtheBestRouteinthePopulationmin_dist,index=min(total_

15、dist);dist_history(iter)=min_dist;ifmin_dist<global_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;ifdimsplot3(xy(rte,1),xy(rte,2),xy(rte,3),'.-',&

16、#39;Color',clr(s,:);elseplot(xy(rte,1),xy(rte,2),'.-','Color',clr(s,:);endtitle(sprintf('TotalDistance=%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%,Iteration3,%GeneticAlgorithmOpe

17、ratorsrand_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_rte=rtes(idx,:);best_of_8_brk=brks(idx,:);rte_ins_pts=sort(ceil(n*rand(1,2);I=rte_ins_pts(1);J=rte_i

18、ns_pts(2);fork=1:8%GenerateNewSolutionstmp_pop_rte(k,:)=best_of_8_rte;tmp_pop_brk(k,:)=best_of_8_brk;switchkcase2%Fliptmp_pop_rte(k,I:J)=fliplr(tmp_pop_rte(k,I:J);case 8 %Swaptmp_pop_rte(k,IJ)=tmp_pop_rte(k,JI);case 9 %Slidetmp_pop_rte(k,I:J)=tmp_pop_rte(k,I+1:JI);case 10 %ModifyBreakstmp_pop_brk(k,

19、:)=randbreaks();case 11 %Flip,ModifyBreakstmp_pop_rte(k,I:J)=fliplr(tmp_pop_rte(k,I:J);tmp_pop_brk(k,:)=randbreaks();case 12 %Swap,ModifyBreakstmp_pop_rte(k,IJ)=tmp_pop_rte(k,JI);tmp_pop_brk(k,:)=randbreaks();case 13 %Slide,ModifyBreakstmp_pop_rte(k,I:J)=tmp_pop_rte(k,I+1:JI);tmp_pop_brk(k,:)=randbr

20、eaks();otherwise%DoNothingendendnew_pop_rte(p-7:p,:)=tmp_pop_rte;new_pop_brk(p-7:p,:)=tmp_pop_brk;endpop_rte=new_pop_rte;pop_brk=new_pop_brk;endifshow_res%Plotsfigure('Name','MTSPF_GA|Results','Numbertitle','off');subplot(2,2,1);ifdims=3,plot3(xy(:,1),xy(:,2),xy(:,3),

21、'k.');elseplot(xy(:,1),xy(:,2),'k.');endtitle('CityLocations');subplot(2,2,2);imagesc(dmat(1opt_rte,1opt_rte);title('DistanceMatrix');subplot(2,2,3);rng=1opt_brk+1;opt_brkn'fors=1:salesmenrte=1opt_rte(rng(s,1):rng(s,2)1;ifdims=3,plot3(xy(rte,1),xy(rte,2),xy(rte,3)

22、,'.-','Color',clr(s,:);elseplot(xy(rte,1),xy(rte,2),'.-','Color',clr(s,:);endtitle(sprintf('TotalDistance=%',min_dist);holdon;ifdims=3,plot3(xy(1,1),xy(1,2),xy(1,3),'ko');elseplot(xy(1,1),xy(1,2),'ko');endsubplot(2,2,4);plot(dist_history,'b&#