tsp1.m

基本蚁群算法解TSP问题[matlab程序

% %   **** Initialization phase *****   % %

global A0;
global n; % city number
global g;


m=str2double(get(handles.edit_antsum,'String')); 
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);
x=A(2,:);
y=A(3,:);
for i=1:n
    for j=1:n
        distance(i,j)=sqrt((x(i)-x(j))*(x(i)-x(j))+(y(i)-y(j))*(y(i)-y(j)));
    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=1000000000000;

% % ****路线构造**** % %

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,:));
        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));
        tao(c_index(1),g(NC,k))=(1-rou)*tao(c_index(1),g(NC,k))+rou*initao(c_index(1),g(NC,k));
        soulution(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));
        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);
        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
    
    
    % % ****全局更新**** % %
    Linear_index1=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));
        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,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,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,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
            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,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


% %****输出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;
xlable('X coordinate');
ylable('Y coordiante');
title('Best tour in NCmax iterations');