basicantcolonyalgorithmfortsp.m

BasicAntColonyAlgorithmForTSP 也是算TSP问题的MATLAB算法程序

%  Basic Ant Colony Algorithm for TSP%
% ****** 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-coordinate
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=10000000000000;

% ******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_medium0.';
        psum(k,1)=sum(psum_medium(:,1));
        for j=1:n
            if tabu(k,j)==0
                p(1,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,:);
        sizel=[1,n];
        [r_index,c_index]=ind2sub(sizel,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)==0;
                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(k)=solution(k)+solution_medium(k,n);
        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_index1=find(bestsolution_NC(NC)==solution_NC(NC,:));
size3=[NC,m];
[r_index1(NC),c_index1(NC)]=ind2sub(size3,Linear_index1(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(1));
    detatao(g(NC,c_index1_t(NC,i)),route(c_index1_t(NC,i),1))=Q/solution(c_index1_t(NC,i));
    detatao(route(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,1),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,i)))=(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(route(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,1),n-1))+rou.*detatao(g(NC,c_index1_t(NC,i)),route(c_index1_t(NC,i),n-1));
    
    for s=2:n-1
        detatao(route(c_index1_t(NC,i),s),route(c_index1_t(NC,i),s-1))=Q/solution(c_index1_t(NC,i));
        detatao(route(c_index1_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,1),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,1),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)),'x');
hold on;
for i=1:n
    plot(x(i),y(i),'o');
    hold on;
end;
hold on;
for j=1:(n-1)
    line([x(bestroute(n)) x(bestroute(1))],[y(bestroute(n)) y(bestroute(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 coordinates in TSP ****** %

[fname,pname,filterindex]=uigetfile('*.*','All Files(*.*)');
set(handles.text_filename,'String',filename);
fid=fopen(filename,'r');
if fid==-1;
    warndlg('Can not open the file','WARN');
    fclose(fid);
end;
[A0,COUNT]=fscanf(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.