tsp_matlab.txt

Matlab的GA程序

   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