Matlab的GA程序 遺傳算法求TSP 

  
  
   for i=1:ngpool, 
      cost(i)=sum(diag(distance(gpool(i,:)',rshift(gpool(i,:))'))); 
   end 
   % record current best solution 
   [costmin,idx]=min(cost); 
   tourmin=gpool(idx,:); 
   %============== 
   % copy gens in th gpool according to the probility ratio 
   % >1.1 copy twice 
   % >=0.9 copy once 
   % <0.9 remove 
   [csort,ridx]=sort(cost); % sort from small to big. 
   csum=sum(csort); 
   caverage=csum/ngpool; 
   cprobilities=caverage./csort; 
   copynumbers=0;removenumbers=0; 
   for i=1:ngpool, 
       if cprobilities(i)>1.1 
           copynumbers=copynumbers+1; 
       end 
       if cprobilities(i)<0.9 
           removenumbers=removenumbers+1; 
       end 
   end 
   copygpool=min(copynumbers,removenumbers); 
   for i=1:copygpool 
       for j=ngpool:-1:2*i+2 
           gpool(j,:)=gpool(j-1,:); 
       end 
  
       gpool(2*i+1,:)=gpool(i,:); 
   end 
   if copygpool==0 
       gpool(ngpool,:)=gpool(1,:); 
   end 
   %========= 
   %when genaration is more than 50,or the patterns in a couple are too close,do 
mutation 
   for i=1:ngpool/2 
       % 
       sameidx=[gpool(2*i-1,:)==gpool(2*i,:)]; 
       diffidx=find(sameidx==0); 
       if length(diffidx)<=2 
           gpool(2*i,:)=[1 randomize([2:12]')' 1]; 
       end 
   end 
   %=========== 
   %cross gens in couples 
   for i=1:ngpool/2 
       [gpool(2*i-1,:),gpool(2*i,:)]=crossgens(gpool(2*i-1,:),gpool(2*i,:)); 
   end 
  
  
  
   for i=1:ngpool, 
      cost(i)=sum(diag(distance(gpool(i,:)',rshift(gpool(i,:))'))); 
   end 
   % record current best solution 
   [costmin,idx]=min(cost); 
   tourmin=gpool(idx,:); 
   disp([num2str(increase) 'minmum trip length = ' num2str(costmin)]) 
end 
  
  
  
  
disp(['cost function evaluation: ' int2str(increase) ' times!']) 
disp(['n:' int2str(resultincrease)]) 
disp(['minmum trip length = ' num2str(resultcost)]) 
disp('optimum tour = ') 
disp(num2str(resulttour)) 
  
%==================================================== 
function B=randomize(A,rowcol) 
% Usage: B=randomize(A,rowcol) 
% randomize row orders or column orders of A matrix 
% rowcol: if =0 or omitted, row order (default) 
%         if = 1, column order 
  
rand('state',sum(100*clock)) 
if nargin == 1, 
   rowcol=0; 
end 
if rowcol==0, 
   [m,n]=size(A); 
   p=rand(m,1); 
   [p1,I]=sort(p); 
   B=A(I,:); 
elseif rowcol==1, 
   Ap=A'; 
   [m,n]=size(Ap); 
   p=rand(m,1); 
   [p1,I]=sort(p); 
   B=Ap(I,:)'; 
end 
%===================================================== 
function y=rshift(x,dir) 
% Usage: y=rshift(x,dir) 
% rotate x vector to right (down) by 1 if dir = 0 (default) 
% or rotate x to left (up) by 1 if dir = 1 
  
if nargin<2, dir=0; end 
  
[m,n]=size(x); 
  
if m > 1, 
   if n == 1, 
      col=1; 
   elseif n > 1, 
      error('x must be a vector! break'); 
   end % x is a column vector 
elseif m == 1, 
   if n == 1, 
      y=x; return 
   elseif n > 1, 
      col=0; % x is a row vector 
   end 
end 
  
if dir==1,  % rotate left or up 
   if col==0, % row vector, rotate left 
      y = [x(2:n) x(1)]; 
   elseif col==1, 
      y = [x(2:n); x(1)]; % rotate up 
   end 
elseif dir==0, % default rotate right or down 
   if col==0, 
      y = [x(n) x(1:n-1)]; 
   elseif col==1 % column vector 
      y = [x(n); x(1:n-1)]; 
   end 
end 
%================================================== 
function [L1,L2]=crossgens(X1,X2) 
% Usage:[L1,L2]=crossgens(X1,X2) 
s=randomize([2:12]')'; 
n1=min(s(1),s(11));n2=max(s(1),s(11)); 
X3=X1;X4=X2; 
for i=n1:n2, 
    for j=1:13, 
        if X2(i)==X3(j), 
            X3(j)=0; 
        end 
        if X1(i)==X4(j), 
            X4(j)=0; 
        end 
    end 
end 
j=13;k=13; 
for i=12:-1:2, 
    if X3(i)~=0, 
        j=j-1; 
        t=X3(j);X3(j)=X3(i);X3(i)=t; 
    end 
    if X4(i)~=0, 
        k=k-1; 
        t=X4(k);X4(k)=X4(i);X4(i)=t; 
    end 
end 
for i=n1:n2 
    X3(2+i-n1)=X2(i); 
    X4(2+i-n1)=X1(i); 
end 
L1=X3;L2=X4; 
%======================= 
  
  
  
其中distTSP.txt為10個城市距離矩陣。 
  
0       622     1042    776     2236    2496    1821    636     825     1130 
2005    1953 
622     0       1608    1342    2802    3063    2387    972     1161    1166 
2623    2519 
1042    1608    0       1336    2544    2805    2129    1622    1811    2116 
2313    2261 
776     1342    1336    0       1451    1721    1045    1356    1545    1229 
1229    1177 
2236    2802    2544    1451    0       1172    842     2542    2353    2048 
2048    1439 
2496    3063    2805    1721    1172    0       676     2376    2187    1882 
1813    1327 
1821    2387    2129    1045    842     676     0       1700    1511    1206 
1165    651 
636     972     1622    1356    2542    2376    1700    0       189     494 
1651    1686 
825     1161    1811    1545    2353    2187    1511    189     0       305 
1462    1497 
1130    1166    2116    1229    2048    1882    1206    494     305     0 
1157    1192 
2005    2623    2313    1229    2048    1813    1165    1651    1462    1157 
0       514 
1953    2519    2261    1177    1439    1327    651     1686    1497    1192 

514     0 
  
-- 
 
 2004-4-7 13:41