TSP旅行商问题matlab代码

functionga_TSP%mainlyamendedbyChenZhen,2012~2016CityNum=30;%youchanchoose10,30,50,75[dislist,Clist]=tsp(CityNum);inn=30;%³õʼÖÖȺ´óСgnmax=500;%×î´ó´úÊýpc=0.8;%½»²æ¸ÅÂÊpm=0.8;%±äÒì¸ÅÂÊ%²úÉú³õʼÖÖȺs=zeros(inn,CityNum);fori=1:inns(i,:)=randperm(CityNum);end[~,p]=objf(s,dislist);gn=1;ymean=zeros(gn,1);ymax=zeros(gn,1);xmax=zeros(inn,CityNum);scnew=zeros(inn,CityNum);smnew=zeros(inn,CityNum);whilegngnmax+1forj=1:2:innseln=sel(p);%Ñ¡Ôñ²Ù×÷scro=cro(s,seln,pc);%½»²æ²Ù×÷scnew(j,:)=scro(1,:);scnew(j+1,:)=scro(2,:);smnew(j,:)=mut(scnew(j,:),pm);%±äÒì²Ù×÷smnew(j+1,:)=mut(scnew(j+1,:),pm);ends=smnew;%²úÉúÁËеÄÖÖȺ[f,p]=objf(s,dislist);%¼ÆËãÐÂÖÖȺµÄÊÊÓ¦¶È%¼Ç¼µ±Ç°´ú×îºÃºÍƽ¾ùµÄÊÊÓ¦¶È[fmax,nmax]=max(f);ymean(gn)=1000/mean(f);ymax(gn)=1000/fmax;%¼Ç¼µ±Ç°´úµÄ×î¼Ñ¸öÌåx=s(nmax,:);xmax(gn,:)=x;drawTSP(Clist,x,ymax(gn),gn,0);gn=gn+1;end[min_ymax,index]=min(ymax);drawTSP(Clist,xmax(index,:),min_ymax,index,1);figure(2);plot(ymax,'r');holdon;plot(ymean,'b');grid;title('ËÑË÷¹ý³Ì');legend('×îÓŽâ','ƽ¾ù½â');fprintf('ÒÅ´«Ëã·¨µÃµ½µÄ×î¶Ì¾àÀë:%.2f\n',min_ymax);fprintf('ÒÅ´«Ëã·¨µÃµ½µÄ×î¶Ì·Ïß');disp(xmax(index,:));end%------------------------------------------------%¼ÆËãËùÓÐÖÖȺµÄÊÊÓ¦¶Èfunction[f,p]=objf(s,dislist)inn=size(s,1);%¶ÁÈ¡ÖÖȺ´óСf=zeros(inn,1);fori=1:innf(i)=CalDist(dislist,s(i,:));%¼ÆË㺯ÊýÖµ£¬¼´ÊÊÓ¦¶Èendf=1000./f';%È¡¾àÀëµ¹Êý%¸ù¾Ý¸öÌåµÄÊÊÓ¦¶È¼ÆËãÆ䱻ѡÔñµÄ¸ÅÂÊfsum=0;fori=1:innfsum=fsum+f(i)^15;%ÈÃÊÊÓ¦¶ÈÔ½ºÃµÄ¸öÌ屻ѡÔñ¸ÅÂÊÔ½¸ßendps=zeros(inn,1);fori=1:innps(i)=f(i)^15/fsum;end%¼ÆËãÀÛ»ý¸ÅÂÊp=zeros(inn,1);p(1)=ps(1);fori=2:innp(i)=p(i-1)+ps(i);endp=p';end%--------------------------------------------------%¸ù¾Ý±äÒì¸ÅÂÊÅжÏÊÇ·ñ±äÒìfunctionpcc=pro(pc)test(1:100)=0;l=round(100*pc);test(1:l)=1;n=round(rand*99)+1;pcc=test(n);end%--------------------------------------------------%¡°Ñ¡Ôñ¡±²Ù×÷functionseln=sel(p)seln=zeros(2,1);%´ÓÖÖȺÖÐÑ¡ÔñÁ½¸ö¸öÌ壬×îºÃ²»ÒªÁ½´ÎÑ¡Ôñͬһ¸ö¸öÌåfori=1:2r=rand;%²úÉúÒ»¸öËæ»úÊýprand=p-r;j=1;whileprand(j)0j=j+1;endseln(i)=j;%Ñ¡ÖиöÌåµÄÐòºÅifi==2&&j==seln(i-1)%%ÈôÏàͬ¾ÍÔÙÑ¡Ò»´Îr=rand;%²úÉúÒ»¸öËæ»úÊýprand=p-r;j=1;whileprand(j)0j=j+1;endendendend%------------------------------------------------%¡°½»²æ¡±²Ù×÷functionscro=cro(s,seln,pc)bn=size(s,2);pcc=pro(pc);%¸ù¾Ý½»²æ¸ÅÂʾö¶¨ÊÇ·ñ½øÐн»²æ²Ù×÷£¬1ÔòÊÇ£¬0Ôò·ñscro(1,:)=s(seln(1),:);scro(2,:)=s(seln(2),:);ifpcc==1c1=round(rand*(bn-2))+1;%ÔÚ[1,bn-1]·¶Î§ÄÚËæ»ú²úÉúÒ»¸ö½»²æλc2=round(rand*(bn-2))+1;chb1=min(c1,c2);chb2=max(c1,c2);middle=scro(1,chb1+1:chb2);scro(1,chb1+1:chb2)=scro(2,chb1+1:chb2);scro(2,chb1+1:chb2)=middle;fori=1:chb1%ËƺõÓÐÎÊÌâwhilefind(scro(1,chb1+1:chb2)==scro(1,i))zhi=find(scro(1,chb1+1:chb2)==scro(1,i));y=scro(2,chb1+zhi);scro(1,i)=y;endwhilefind(scro(2,chb1+1:chb2)==scro(2,i))zhi=find(scro(2,chb1+1:chb2)==scro(2,i));y=scro(1,chb1+zhi);scro(2,i)=y;endendfori=chb2+1:bnwhilefind(scro(1,1:chb2)==scro(1,i))zhi=logical(scro(1,1:chb2)==scro(1,i));y=scro(2,zhi);scro(1,i)=y;endwhilefind(scro(2,1:chb2)==scro(2,i))zhi=logical(scro(2,1:chb2)==scro(2,i));y=scro(1,zhi);scro(2,i)=y;endendendend%--------------------------------------------------%¡°±äÒ족²Ù×÷functionsnnew=mut(snew,pm)bn=size(snew,2);snnew=snew;pmm=pro(pm);%¸ù¾Ý±äÒì¸ÅÂʾö¶¨ÊÇ·ñ½øÐбäÒì²Ù×÷£¬1ÔòÊÇ£¬0Ôò·ñifpmm==1c1=round(rand*(bn-2))+1;%ÔÚ[1,bn-1]·¶Î§ÄÚËæ»ú²úÉúÒ»¸ö±äÒìλc2=round(rand*(bn-2))+1;chb1=min(c1,c2);chb2=max(c1,c2);x=snew(chb1+1:chb2);snnew(chb1+1:chb2)=fliplr(x);endend%------------------------------------------------%³ÇÊÐλÖÃ×ø±êfunction[DLn,cityn]=tsp(n)DLn=zeros(n,n);ifn==10city10=[0.40.4439;0.24390.1463;0.17070.2293;0.22930.761;0.51710.9414;0.87320.6536;0.68780.5219;0.84880.3609;0.66830.2536;0.61950.2634];%10citiesd'=2.691fori=1:10forj=1:10DLn(i,j)=((city10(i,1)-city10(j,1))^2+(city10(i,2)-city10(j,2))^2)^0.5;endendcityn=city10;endifn==30city30=[4194;3784;5467;2562;764;299;6858;7144;5462;8369;6460;1854;2260;8346;9138;2538;2442;5869;7171;7478;8776;1840;1340;827;6232;5835;4521;4126;4435;450];%30citiesd'=423.741byDBFogelfori=1:30forj=1:30DLn(i,j)=((city30(i,1)-city30(j,1))^2+(city30(i,2)-city30(j,2))^2)^0.5;endendcityn=city30;endifn==50city50=[3132;3239;4030;3769;2768;3752;3846;3162;3048;2147;2555;1657;1763;4241;1733;2532;564;852;1242;738;525;1077;4535;4257;3222;2723;5637;5241;4949;5848;5758;3910;4610;5915;5121;4828;5233;5827;6133;6263;2026;56;1313;2110;3015;3616;6242;6369;5264;4367];%50citiesd'=427.855byDBFogelfori=1:50forj=1:50DLn(i,j)=((city50(i,1)-city50(j,1))^2+(city50(i,2)-city50(j,2))^2)^0.5;endendcityn=city50;endifn==75city75=[4821;5226;5550;5050;4146;5142;5545;3833;3334;4535;4037;5030;5534;5438;2613;155;2148;2939;3344;1519;1619;1217;5040;2253;2136;2030;2629;4020;3626;6248;6741;6235;6527;6224;5520;3551;3050;4542;2145;366;625;1128;2659;3060;2222;2724;3020;3516;5410;5015;4413;3560;4060;4066;3176;4766;5070;5772;5565;238;743;956;1556;1070;1764;5557;6257;7064;644;595;504;6015;6614;668;4326];%75citiesd'=549.18byDBFogelfori=1:75forj=1:75DLn(i,j)=((city75(i,1)-city75(j,1))^2+(city75(i,2)-city75(j,2))^2)^0.5;endendcityn=city75;endend%------------------------------------------------%ÊÊÓ¦