function gaTSP

CityNum=30;
[dislist,Clist]=tsp(CityNum);

inn=100; %初始種群大小
gnmax=1000;  %最大代數
pc=0.8; %交叉概率
pm=0.8; %變異概率

%產生初始種群
for i=1:inn
    s(i,:)=randperm(CityNum);
end
[f,p]=objf(s,dislist);

gn=1;
while gn<gnmax+1
   for j=1:2:inn
      seln=sel(s,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);
   end
   s=smnew;  %產生了新的種群
   [f,p]=objf(s,dislist);  %計算新種群的適應度
   %記錄當前代最好和平均的適應度
   [fmax,nmax]=max(f);
   ymean(gn)=1000/mean(f);
   ymax(gn)=1000/fmax;
   %記錄當前代的最佳個體
   x=s(nmax,:);
   drawTSP(Clist,x,ymax(gn),gn,0);
   gn=gn+1;
   %pause;
end
gn=gn-1;

figure(2);
plot(ymax,'r'); hold on;
plot(ymean,'b');grid;
title('搜索過程');
legend('最優解','平均解');
end

%------------------------------------------------
%計算適應度函數
function [f,p]=objf(s,dislist);

inn=size(s,1);  %讀取種群大小
for i=1:inn
   f(i)=CalDist(dislist,s(i,:));  %計算函數值，即適應度
end
f=1000./f';
%計算選擇概率
fsum=0;
for i=1:inn
   fsum=fsum+f(i)^15;
end
for i=1:inn
   ps(i)=f(i)^15/fsum;
end
%計算累積概率
p(1)=ps(1);
for i=2:inn
   p(i)=p(i-1)+ps(i);
end
p=p';
end

%--------------------------------------------------
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

%--------------------------------------------------
%“選擇”操作
function seln=sel(s,p);

inn=size(p,1);
%從種群中選擇兩個個體
for i=1:2
   r=rand;  %產生一個隨機數
   prand=p-r;
   j=1;
   while prand(j)<0
       j=j+1;
   end
   seln(i)=j; %選中個體的序號
end
end

%------------------------------------------------
%“交叉”操作
function scro=cro(s,seln,pc);

bn=size(s,2);
pcc=pro(pc);  %根據交叉概率決定是否進行交叉操作，1則是，0則否
scro(1,:)=s(seln(1),:);
scro(2,:)=s(seln(2),:);
if pcc==1
   c1=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;
   for i=1:chb1
       while find(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;
       end
       while 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;
       end
   end
   for i=chb2+1:bn
       while 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;
       end
       while find(scro(2,1:chb2)==scro(2,i))
           zhi=find(scro(2,1:chb2)==scro(2,i));
           y=scro(1,zhi);
           scro(2,i)=y;
       end
   end
end
end

%--------------------------------------------------
%“變異”操作
function snnew=mut(snew,pm);

bn=size(snew,2);
snnew=snew;

pmm=pro(pm);  %根據變異概率決定是否進行變異操作，1則是，0則否
if pmm==1
   c1=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);
end
end