遺傳算法解決TSP問題

1、遺傳算法解決旅行商(TSP)問題旅行商問題(traveling saleman problem，簡稱 tsp):已知N個城市之間的相互距離，現(xiàn)有一個推銷員必須遍訪這n個城市，并且 每個城市只能訪問一次，最后又必須返回出發(fā)城市。如何安排他對這些城市的訪 問次序，可使其旅行路線的總長度最短？本程序使用MATLAB軟件，利用遺傳算法解決TSP問題。程序使用如下：gatsp 為主程序，cityNum為城市個數(shù)，在此程序中可以設(shè)置為30、50和70。Inn是種群 個數(shù)，gnmax是最大迭代次數(shù)，pc是交叉概率，pm是變異概率。算法程序運(yùn)行結(jié) 果如下：搜索過程算法程序如下（不同的function需放在不同

2、的.m文件中）: 注：紅色部分不屬于算法內(nèi)容，僅作間隔標(biāo)致。%主程序：%遺傳算法求解tspfunction gaTSPCityNum=30;dislist,Clist=tsp(CityNum);inn=100; %初始種群大小gnmax=1000;%最大代數(shù)pc=0.9; %交叉概率pm=0.08; %變異概率%產(chǎn)生初始種群for i=1:inns(i,:)=randperm(CityNum);endf,p=objf(s,dislist);gn=1;while gngnmax+1for j=1:2:innseln=sel(s,p); %選擇操作scro=cro(s,seln,pc); %交叉操

3、作 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; %產(chǎn)生了新的種群f,p=objf(s,dislist); %計(jì)算新種群的適應(yīng)度%記錄當(dāng)前代最好和平均的適應(yīng)度 fmax,nmax=max(f);ymean(gn)=1000/mean(f);ymax(gn)=1000/fmax;%記錄當(dāng)前代的最佳個體x=s(nmax,:);drawTSP(Clist,x,ymax(gn),gn,0);g

4、n=gn+1;%pause;endgn=gn-1;figure(2);plot(ymax,r); hold on;plot(ymean,b);grid;title(搜索過程);legend(最優(yōu)解，平均解);string1=最終度,num2str(ymax(gn);gtext(string1);End %交叉程序：function scro=cro(s,seln,pc);bn=size(s,2);pcc=pro(pc); %根據(jù)交叉概率決定是否進(jìn)行交叉操作，1則是，0則否 scro(1,:)=s(seln(1),:);scro(2,:)=s(seln(2),:);if pcc=1c1=roun

5、d(rand*(bn-2)+1; %在1,bn-1范圍內(nèi)隨機(jī)產(chǎn)生一個交叉位 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;for i=1:chb1while find(scro(1,chb1+1:chb2)=scro(1,i)zhi=find(scro(1,chb1+1:chb2)=scro(1,i);y=scro(2,chb1+zhi);scr

6、o(1,i)=y;endwhile find(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;endendfor i=chb2+1:bnwhile find(scro(1,1:chb2)=scro(1,i)zhi=find(scro(1,1:chb2)=scro(1,i);y=scro(2,zhi);scro(1,i)=y;endwhile find(scro(2,1:chb2)=scro(2,i)zhi=find(scro(2,1:chb2)=

7、scro(2,i);y=scro(1,zhi);scro(2,i)=y;endendendEnd %變異程序：function snnew=mut(snew,pm);bn=size(snew,2);snnew=snew;pmm=pro(pm); %根據(jù)變異概率決定是否進(jìn)行變異操作，1則是，0則否 if pmm=1c1=round(rand*(bn-2)+1; %在1,bn-1范圍內(nèi)隨機(jī)產(chǎn)生一個變異位 c2=round(rand*(bn-2)+1;chb1=min(c1,c2);chb2=max(c1,c2);x=snew(chb1+1:chb2);snnew(chb1+1:chb2)=flip

8、lr(x);endend %適應(yīng)度計(jì)算：function f,p=objf(s,dislist);inn=size(s,1); %讀取種群大小for i=1:innf(i)=caldist(dislist,s(i,:); %計(jì)算函數(shù)值，即適應(yīng)度endf=1000./f;%計(jì)算選擇概率fsum=0;for i=1:innfsum=fsum+f(i)T5;endfor i=1:innps(i)=f(i)八15/fsum;end%計(jì)算累積概率p(1)=ps(1);for i=2:innp(i)=p(i-1)+ps(i);endp=p;end %選著個體程序：function seln=sel(s,p

9、);inn=size(p,1);%從種群中選擇兩個個體for i=1:2r=rand; %產(chǎn)生一個隨機(jī)數(shù)prand=p-r;j=1;while prand(j)0j=j+1;endseln(i)=j; %選中個體的序號 end end%城市坐標(biāo)： function DLn,cityn=tsp(n)if n=10 city10=0.40.4439;0.24390.1463;0.17070.2293;0.22930.761;0.5171 0.9414; 0.87320.6536;0.68780.5219;0.84880.3609;0.66830.2536;0.6195 0.2634;%10 cit

10、ies d=2.691 for i=1:10 for j=1:10DL10(i,j) = (city10(i,1)-city10(j,1)八2+(city10(i,2)-city10(j,2)八 2)八0.5; end endDLn=DL10;cityn=city10;end if n=30city30=4194;37 84; 54 67;25 62; 7 64;2 99; 68 58;71 44; 54 62; 83 69;64 60;18 54;22 60; 8316;91 38;25 38;24 42;58 69;71 71;74 78; 87 76; 18 40; 13 40;82 7

11、;62 32;58 35;45 21;41 26;44 35;4 50;%30 cities d=423.741 by D B Fogel for i=1:30 for j=1:30DL30(i,j)=(city30(i,1)-city30(j,1)八2+(city30(i,2)-city30(j,2)八 2)八0.5; end end DLn=DL30; cityn=city30; end if n=50city50=31 32;32 39;40 30;37 69;27 68;37 52;38 46;31 62;30 48;21 47;25 55;16 57;163;42 41;17 33;

12、25 32;5 64; 8 52; 12 42; 7 38; 5 25; 10 77; 45 35;42 57;32 22;2Z3;56 37;52 41;49 49;58 48;57 58;39 10;46 10;59 15;51 21;48 28;52 33;58 27;61 33;62 63;20 26;5 6;13 13;21 10;30 15;36 16;62 42;6369;52 64;43 67;%50 cities d=427.855 by D B Fogel for i=1:50 for j=1:50DL50(i,j) = (city5 0(i,1)-city5 0(j,1)

13、八2+(city5 0(i,2)-city5 0(j,2)八 2)八0.5;endendDLn=DL50;cityn=city50;endif n=75city75=48 21;52 26;55 50;50 50;41 46;51 42;55 45;38 33;33 34;45 35;40 37;50 30;55 34;54 38;26 13;15 5;21 48;29 39;33 44;15 19;16 19;12 17;50 40;22 53;21 36;2CB0;26 29; 40 20;36 26; 62 48; 67 41; 62 35; 65 27; 62 24; 55 20;35

14、 51;30 50;45 42;21 45;36 6;6 25;11 28;26 59;30 60;22 22;27 24;30 20;35 16;54 10;50 15;44 13;35 60;40 60;40 66;31 76;47 66;50 70;57 72;55 65;2 38;7 43;9 56;15 56;170;17 64;55 57;62 57;70 64;64 4;59 5;50 4;60 15;66 14;66 8;43 26;%75 cities d=549.18 by D B Fogel for i=1:75 for j=1:75DL75(i,j) = (city7

15、5(i,1)-city7 5(j,1)八2+(city7 5(i,2)-city7 5(j,2)八 2)八0.5;endendDLn=DL75;cityn=city75;end end %根據(jù)交叉概率決定是否進(jìn)行交叉操作: function pcc=pro(pc);test(1:100)=0;l=round(100*pc);test(1:l)=1;n=round(rand*99)+1;pcc=test(n);end %計(jì)算城市距離矩陣：function F=caldist(dislist,s) distan=0;n=size(s,2);for i=1:n-1distan=distan+disl

16、ist(s(i),s(i+1);enddistan=distan+dislist(s(n),s(1);F=distan;%作圖：function m=drawTSP(Clist,BSF,bsf,p,f)CityNum=size(Clist,1);for i=1:CityNum-1plot(Clist(BSF(i),1),Clist(BSF(i+1),1),Clist(BSF(i),2),Clist(BSF(i+1),2),ms-,LineWidth,2,MarkerEdgeColor,k,MarkerFace Color,g);hold on;endplot(Clist(BSF(CityNum),1),Clist(B