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