LiSheng
2008-11-09, 21:04
这是蚁群算法的程序哪个高手看看 能不能运行
%***********************************************************%
% Basic Ant Colony Algorithm for TSP %
% Matlab Version %
%***********************************************************%
%%******Initialization phase******%%
global A0;
global n;% city number
global g;
m=str2double(get(handles.edit_antsum,'String')); set ant number by using Matlab GUI
initao=str2double(get(handles.edit_tao,'String'));
alpha=str2double(get(handles.edit_alpha,'String'));
beta=str2double(get(handles.edit_beta,'String'));
Q=str2double(get(handles.edit_q,'String'));
rou=str2double(get(handles.edit_rou,'String'));
NCmax=str2double(get(handles.edit_ncmax,'String'));
A=reshape(A0,3,n);%get the city coordinates in TSP
x=A(2,:);% get X-coordinate
y=A(3,:);% get Y-corrdinate
for i=1:n
for j=1:n
distance(i,j)=sqrt((x(i)-x(j))^2+(y(i)-y(j))^2);
end
end
for i=1:n
for j=1:n
if j~=i
tao(i,j)=initao;
yita(i,j)=1/distance(i,j);
end;
end;
end;
initao=initao.*ones(n,n);
detatao=zeros(n,n);
bestsolution=100000000000;
%%********This is the phase in which ants build their tours******%%
for NC=1:NCmax
tabu=zeros(m,n);
for k=1:m
tabu(k,g(NC,k))=1;
maxp(1)=0;
for j=1:n
if tabu(k,j)==0
psum_medium0(1,j)=(tao(g(NC,k),j)^alpha).*(yita(g(NC,k),j)^beta);
else
psum_medium0(1,j)=0;
end
end
psum_medium=psum_medium.';
psum(k,1)=sum(psum_medium(:,1));
for j=1:n
if tabu(k,j)==0
p(i,j)=(tao(g(NC,k),j)^alpha).*(yita(g(NC,k),j)^beta)/psum(k,1);
else
p(:,j)=0;
end
if maxp(1)<p(1,j)
maxp(1)=p(1,j);
end
end
Linear_index=find(maxp(1)==p(1,:));
size1=[1,n];
[r_index,c_index]=ind2sub(size1,Linear_index(1));
solution_medium(k,1)=distance(g(NC,k),c_index(1));
route(k,1)=c_index(1);
tabu(k,c_index(1))=1;
tao(g(NC,k),c_index(1))=(1-rou)*tao(g(NC,k),c_index(1))+rou*initao(g(NC,k),c_index(1));%Local updating for the first iteration
tao(c_index(1),g(NC,k))=(1-rou)*tao(c_index(1),g(NC,k))+rou*initao(c_index(1),g(NC,k));
solution(k)=solution_medium(k,1);
for s=2:n-1
c_index(s)=0;
r_index(s)=0;
Linear_index(s)=0;
maxp(s)=0;
for j=1:n
if tabu(k,j)==0
psum_medium0(s,j)=(tao(route(k,s-1),j)^alpha).*(yita(route(k,s-1),j)^beta);
else
psum_medium0(s,j)=o;
end
end
psum_medium=psum_medium0.';
psum(k,s)=sum(psum_medium(:,s));
for j=1:n
if tabu(k,j)==0
p(s,j)=(tao(route(k,s-1),j)^alpha).*(yita(route(k,s-1),j)^beta)/psum(k,s);
else
p(s:(n-1),j)=0;
end
if maxp(s)<p(s,j)
maxp(s)=p(s,j);
end
end
Linear_index=find(maxp(s)==p);
size2=[n-1,n];
[r_index(s),c_index(s)]=ind2sub(size2,Linear_index(1));
solution_medium(k,s)=distance(c_index(s-1),c_index(s));
route(k,s)=c_index(s);
tabu(k,c_index(s))=1;
tao(c_index(s-1),c_index(s))=(1-rou)*tao(c_index(s-1),c_index(s))+rou*initao(c_index(s-1),c_index(s));
tao(c_index(s),c_index(s-1))=(1-rou)*tao(c_index(s),c_index(s-1))+rou*initao(c_index(s),c_index(s-1));
solution(k)=solution(k)+solution_medium(k,s);
end
tao(c_index(n-1),g(NC,k))=(1-rou)*tao(c_index(n-1),g(NC,k))+rou.*initao(c_index(n-1),g(NC,k));%Local updating for other iterations
tao(g(NC,k),c_index(n-1))=(1-rou)*tao(g(NC,k),c_index(n-1))+rou.*initao(g(NC,k),c_index(n-1));
solution_medium(k,n)=distance(c_index(n-1),g(NC,k));
solution_NC(NC,k)=solution(k);
bestsolution_NC(NC)=solution_NC(NC,1);
end;
for k=1:m
if bestsolution_NC(NC)>solution_NC(NC,k);
bestsolution_NC(NC)=solution_NC(NC,k);
end
end
%%*********In this phase global updating occurs******%%
Linear_indexl=find(bestsolution_NC(NC)==solution_NC(NC,:));
size3=[NC,m];
[r_index1(NC),c_index1(NC)]=ind2sub(size3,Linear_index(1));
bestroute_NC(NC,:)=route(c_index1(NC),:);
[aa,bb]=size(Linear_index1);
for i=1:bb
[r_index1_tao(NC,i),c_index1_t(NC,i)]=ind2sub(size3,Linear_index1(i));
detao(g(NC,c_index1_t(NC,i)),route(c_index1_t(NC,i),1))=Q/solution(c_index1_t(NC,i));
detao(rout(c_index1_t(NC,i),1),g(NC,c_index1_t(NC,i)))=Q/solution(c_index1_t(NC,i));
tao(g(NC,c_index1_t(NC,i)),route(c_index1_t(NC,i),1))=(1-rou).*tao(g(NC,c_index1_t(NC,i)),route(c_index1_t(NC,i),1))+rou.*detatao(g(NC,c_index1_t(NC,i)),route(c_index1_t(NC,i),1));
tao(route(c_index1_t(NC,i),1),g(NC,c_index1_t(NC,1)))=(1-rou).*tao(route(c_index1_t(NC,i),1),g(NC,c_index1_t(NC,i)))+rou.*detatao(route(c_index1_t(NC,i),1),g(NC,c_index1_t(NC,i)));
detatao(rout(c_index1_t(NC,i),n-1),g(NC,c_index1_t(NC,i)))=Q/solution(c_index1_t(NC,i));
detatao(g(NC,c_index1_t(NC,i)),route(c_index1_t(NC,i),n-1))=Q/solution(c_index1_t(NC,i));
tao(route(c_index1_t(NC,i),n-1),g(NC,c_index1_t(NC,i)))=(1-rou).*tao(route(c_index1_t(NC,i),n-1),g(NC,c_index1_t(NC,i)))+rou.*detatao(route(c_index1_t(NC,i),n-1),g(NC,c_index1_t(NC,i)));
tao(g(NC,c_index1_t(NC,i)),route(c_index1_t(NC,i),n-1))=(1-rou).*tao(g(NC,c_index1_t(NC,i),route(c_index1_t(NC,i),n-1))+rou.*detatao(g(NC,c_index1_t(NC,i)),route(c_index1_t(NC,i),n-1)));
for s=2:n-1
detao(route(c_index_t(NC,i),s),route(c_index1_t(NC,i),s-1))=Q/solution(c_index1_t(NC,i));
detao(route(c_index_t(NC,i),s-1),route(c_index1_t(NC,i),s))=Q/solution(c_index1_t(NC,i));
tao(route(c_index1_t(NC,i),s),route(c_index1_t(NC,i),s-1))=(1-rou).*tao(route(c_index1_t(NC,i),s),route(c_index1_t(NC,i),s-1))+rou.*detatao(route(c_index1_t(NC,i),s),route(c_index1_t(NC,i),s-1));
tao(route(c_index1_t(NC,i),s-1),route(c_index1_t(NC,i),s))=(1-rou).*tao(route(c_index1_t(NC,i),s-1),route(c_index1_t(NC,i),s))+rou.*detatao(route(c_index1_t(NC,i),s-1),route(c_index1_t(NC,i),s));
end
end
if bestsolution>bestsolution_NC(NC)
bestsolution=bestsolution_NC(NC);
end;
Linear_index2=find(bestsolution==bestsolution_NC);
size4=[1,NC];
[r_index2,c_index2]=ind2sub(size4,Linear_index2(1));
bestroute(1,:)=bestroute_NC(c_index2,:);
initao=tao;
end
%%***********Output the best result of TSP***********%%
for NC=1:NCmax
bestroute_NC(NC,n)=g(NC,c_index1(NC));
t(NC)=NC;
end;
bestroute(1,n)=bestroute_NC(c_index2,n);
plot(x(bestroute(n)),y(bestroute(n)),'*');
hold on;
for i=1:n
plot(x(i).y(i),'o');
hold on;
end;
hold on;
line([x(bestroute(n)),x(bestroute(1))],[y(bestroute(n)),y(bestroute(1))]);
hold on;
for j=1:(n-1)
line([x(bestroute(j)),x(bestroute(j+1))],[y(bestroute(j)),y(bestroute(j+1))]);
hold on;
end;
hold off;
xlabel('X coordinate');
ylabel('Y coordinate');
title('Best tour in NCmax iterations');
%************************************************************************%
% Function :Open and import file of city coordinate in TSP %
%************************************************************************%
[fname,pname,filterindex]=uigetfile('*.*','All Files(*.*)');
set(handles.text_filename,'String',filename);
fid=fopen(filename,'r');
if fid==-1;
warndlg('Can‘t open the file','WARN');
fclose(fid);
end
[A0,COUNT]=facanf(fid,'%g');
n=COUNT/3;
set(handles.edit_citysum,'String',n);
fclose(fid);
m=str2double(get(handles.edit_antsum,'String'));
NCmax=str2double(get(handles.edit_ncmax,'String'));
for NC=1:NCmax
for k=1:m
g(NC,k)=fix((n-1)*rand(1))+1;
end;
end;
%***********************************************************%
% Basic Ant Colony Algorithm for TSP %
% Matlab Version %
%***********************************************************%
%%******Initialization phase******%%
global A0;
global n;% city number
global g;
m=str2double(get(handles.edit_antsum,'String')); set ant number by using Matlab GUI
initao=str2double(get(handles.edit_tao,'String'));
alpha=str2double(get(handles.edit_alpha,'String'));
beta=str2double(get(handles.edit_beta,'String'));
Q=str2double(get(handles.edit_q,'String'));
rou=str2double(get(handles.edit_rou,'String'));
NCmax=str2double(get(handles.edit_ncmax,'String'));
A=reshape(A0,3,n);%get the city coordinates in TSP
x=A(2,:);% get X-coordinate
y=A(3,:);% get Y-corrdinate
for i=1:n
for j=1:n
distance(i,j)=sqrt((x(i)-x(j))^2+(y(i)-y(j))^2);
end
end
for i=1:n
for j=1:n
if j~=i
tao(i,j)=initao;
yita(i,j)=1/distance(i,j);
end;
end;
end;
initao=initao.*ones(n,n);
detatao=zeros(n,n);
bestsolution=100000000000;
%%********This is the phase in which ants build their tours******%%
for NC=1:NCmax
tabu=zeros(m,n);
for k=1:m
tabu(k,g(NC,k))=1;
maxp(1)=0;
for j=1:n
if tabu(k,j)==0
psum_medium0(1,j)=(tao(g(NC,k),j)^alpha).*(yita(g(NC,k),j)^beta);
else
psum_medium0(1,j)=0;
end
end
psum_medium=psum_medium.';
psum(k,1)=sum(psum_medium(:,1));
for j=1:n
if tabu(k,j)==0
p(i,j)=(tao(g(NC,k),j)^alpha).*(yita(g(NC,k),j)^beta)/psum(k,1);
else
p(:,j)=0;
end
if maxp(1)<p(1,j)
maxp(1)=p(1,j);
end
end
Linear_index=find(maxp(1)==p(1,:));
size1=[1,n];
[r_index,c_index]=ind2sub(size1,Linear_index(1));
solution_medium(k,1)=distance(g(NC,k),c_index(1));
route(k,1)=c_index(1);
tabu(k,c_index(1))=1;
tao(g(NC,k),c_index(1))=(1-rou)*tao(g(NC,k),c_index(1))+rou*initao(g(NC,k),c_index(1));%Local updating for the first iteration
tao(c_index(1),g(NC,k))=(1-rou)*tao(c_index(1),g(NC,k))+rou*initao(c_index(1),g(NC,k));
solution(k)=solution_medium(k,1);
for s=2:n-1
c_index(s)=0;
r_index(s)=0;
Linear_index(s)=0;
maxp(s)=0;
for j=1:n
if tabu(k,j)==0
psum_medium0(s,j)=(tao(route(k,s-1),j)^alpha).*(yita(route(k,s-1),j)^beta);
else
psum_medium0(s,j)=o;
end
end
psum_medium=psum_medium0.';
psum(k,s)=sum(psum_medium(:,s));
for j=1:n
if tabu(k,j)==0
p(s,j)=(tao(route(k,s-1),j)^alpha).*(yita(route(k,s-1),j)^beta)/psum(k,s);
else
p(s:(n-1),j)=0;
end
if maxp(s)<p(s,j)
maxp(s)=p(s,j);
end
end
Linear_index=find(maxp(s)==p);
size2=[n-1,n];
[r_index(s),c_index(s)]=ind2sub(size2,Linear_index(1));
solution_medium(k,s)=distance(c_index(s-1),c_index(s));
route(k,s)=c_index(s);
tabu(k,c_index(s))=1;
tao(c_index(s-1),c_index(s))=(1-rou)*tao(c_index(s-1),c_index(s))+rou*initao(c_index(s-1),c_index(s));
tao(c_index(s),c_index(s-1))=(1-rou)*tao(c_index(s),c_index(s-1))+rou*initao(c_index(s),c_index(s-1));
solution(k)=solution(k)+solution_medium(k,s);
end
tao(c_index(n-1),g(NC,k))=(1-rou)*tao(c_index(n-1),g(NC,k))+rou.*initao(c_index(n-1),g(NC,k));%Local updating for other iterations
tao(g(NC,k),c_index(n-1))=(1-rou)*tao(g(NC,k),c_index(n-1))+rou.*initao(g(NC,k),c_index(n-1));
solution_medium(k,n)=distance(c_index(n-1),g(NC,k));
solution_NC(NC,k)=solution(k);
bestsolution_NC(NC)=solution_NC(NC,1);
end;
for k=1:m
if bestsolution_NC(NC)>solution_NC(NC,k);
bestsolution_NC(NC)=solution_NC(NC,k);
end
end
%%*********In this phase global updating occurs******%%
Linear_indexl=find(bestsolution_NC(NC)==solution_NC(NC,:));
size3=[NC,m];
[r_index1(NC),c_index1(NC)]=ind2sub(size3,Linear_index(1));
bestroute_NC(NC,:)=route(c_index1(NC),:);
[aa,bb]=size(Linear_index1);
for i=1:bb
[r_index1_tao(NC,i),c_index1_t(NC,i)]=ind2sub(size3,Linear_index1(i));
detao(g(NC,c_index1_t(NC,i)),route(c_index1_t(NC,i),1))=Q/solution(c_index1_t(NC,i));
detao(rout(c_index1_t(NC,i),1),g(NC,c_index1_t(NC,i)))=Q/solution(c_index1_t(NC,i));
tao(g(NC,c_index1_t(NC,i)),route(c_index1_t(NC,i),1))=(1-rou).*tao(g(NC,c_index1_t(NC,i)),route(c_index1_t(NC,i),1))+rou.*detatao(g(NC,c_index1_t(NC,i)),route(c_index1_t(NC,i),1));
tao(route(c_index1_t(NC,i),1),g(NC,c_index1_t(NC,1)))=(1-rou).*tao(route(c_index1_t(NC,i),1),g(NC,c_index1_t(NC,i)))+rou.*detatao(route(c_index1_t(NC,i),1),g(NC,c_index1_t(NC,i)));
detatao(rout(c_index1_t(NC,i),n-1),g(NC,c_index1_t(NC,i)))=Q/solution(c_index1_t(NC,i));
detatao(g(NC,c_index1_t(NC,i)),route(c_index1_t(NC,i),n-1))=Q/solution(c_index1_t(NC,i));
tao(route(c_index1_t(NC,i),n-1),g(NC,c_index1_t(NC,i)))=(1-rou).*tao(route(c_index1_t(NC,i),n-1),g(NC,c_index1_t(NC,i)))+rou.*detatao(route(c_index1_t(NC,i),n-1),g(NC,c_index1_t(NC,i)));
tao(g(NC,c_index1_t(NC,i)),route(c_index1_t(NC,i),n-1))=(1-rou).*tao(g(NC,c_index1_t(NC,i),route(c_index1_t(NC,i),n-1))+rou.*detatao(g(NC,c_index1_t(NC,i)),route(c_index1_t(NC,i),n-1)));
for s=2:n-1
detao(route(c_index_t(NC,i),s),route(c_index1_t(NC,i),s-1))=Q/solution(c_index1_t(NC,i));
detao(route(c_index_t(NC,i),s-1),route(c_index1_t(NC,i),s))=Q/solution(c_index1_t(NC,i));
tao(route(c_index1_t(NC,i),s),route(c_index1_t(NC,i),s-1))=(1-rou).*tao(route(c_index1_t(NC,i),s),route(c_index1_t(NC,i),s-1))+rou.*detatao(route(c_index1_t(NC,i),s),route(c_index1_t(NC,i),s-1));
tao(route(c_index1_t(NC,i),s-1),route(c_index1_t(NC,i),s))=(1-rou).*tao(route(c_index1_t(NC,i),s-1),route(c_index1_t(NC,i),s))+rou.*detatao(route(c_index1_t(NC,i),s-1),route(c_index1_t(NC,i),s));
end
end
if bestsolution>bestsolution_NC(NC)
bestsolution=bestsolution_NC(NC);
end;
Linear_index2=find(bestsolution==bestsolution_NC);
size4=[1,NC];
[r_index2,c_index2]=ind2sub(size4,Linear_index2(1));
bestroute(1,:)=bestroute_NC(c_index2,:);
initao=tao;
end
%%***********Output the best result of TSP***********%%
for NC=1:NCmax
bestroute_NC(NC,n)=g(NC,c_index1(NC));
t(NC)=NC;
end;
bestroute(1,n)=bestroute_NC(c_index2,n);
plot(x(bestroute(n)),y(bestroute(n)),'*');
hold on;
for i=1:n
plot(x(i).y(i),'o');
hold on;
end;
hold on;
line([x(bestroute(n)),x(bestroute(1))],[y(bestroute(n)),y(bestroute(1))]);
hold on;
for j=1:(n-1)
line([x(bestroute(j)),x(bestroute(j+1))],[y(bestroute(j)),y(bestroute(j+1))]);
hold on;
end;
hold off;
xlabel('X coordinate');
ylabel('Y coordinate');
title('Best tour in NCmax iterations');
%************************************************************************%
% Function :Open and import file of city coordinate in TSP %
%************************************************************************%
[fname,pname,filterindex]=uigetfile('*.*','All Files(*.*)');
set(handles.text_filename,'String',filename);
fid=fopen(filename,'r');
if fid==-1;
warndlg('Can‘t open the file','WARN');
fclose(fid);
end
[A0,COUNT]=facanf(fid,'%g');
n=COUNT/3;
set(handles.edit_citysum,'String',n);
fclose(fid);
m=str2double(get(handles.edit_antsum,'String'));
NCmax=str2double(get(handles.edit_ncmax,'String'));
for NC=1:NCmax
for k=1:m
g(NC,k)=fix((n-1)*rand(1))+1;
end;
end;