求一份基于matlab的TSP问题源代码

发布网友发布时间：2022-05-23 06:19

共1个回答

热心网友时间：2023-10-15 11:35

function [Shortest_Route,Shortest_Length]=anttsp(city,iter_max,m,Alpha,Beta,Rho,Q)
n=size(city,1);
d=zeros(n,n);
d=squareform(pdist(city));
Eta=1./d;
Tau=ones(n,n);
Tabu=zeros(m,n);
nC=1;
R_best=zeros(iter_max,n);
L_best=inf.*ones(iter_max,1);

    while nC<=iter_max
        route=[];
        for i=1:ceil(m/n)
            route=[route,randperm(n)];
        end
        Tabu(:,1)=(route(1,1:m))';
        for j=2:n
            for i=1:m
                visited=Tabu(i,1:(j-1));
                J=zeros(1,(n-j+1));
                P=J;
                Jc=1;
                for k=1:n
                    if isempty(find(visited==k, 1))
                        J(Jc)=k;
                        Jc=Jc+1;
                    end
                end
                for k=1:length(J)
                    P(k)=(Tau(visited(end),J(k))^Alpha)*(Eta(visited(end),J(k))^Beta);
                end
                P=P/(sum(P));

                Pcum=cumsum(P);
                Select=find(Pcum>=rand);
                if isempty(Select)%是不是一定能保证Select不为空
                    Tabu(i,j)=round(1+(n-1)*rand);
                else
                    next_visit=J(Select(1));
                    Tabu(i,j)=next_visit;
                end
            end
        end
        if nC>=2
            Tabu(1,:)=R_best(nC-1,:);
        end

        L=zeros(m,1);
        for i=1:m
            R=Tabu(i,:);
            for j=1:(n-1)
                L(i)=L(i)+d(R(j),R(j+1));
            end
            L(i)=L(i)+d(R(1),R(n));
        end
        L_best(nC)=min(L);
        pos=find(L==L_best(nC));
        R_best(nC,:)=Tabu(pos(1),:);
        nC=nC+1;


        Delta_Tau=zeros(n,n);
        for i=1:m
            for j=1:(n-1)
                Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,j+1))+Q/L(i);
            end
            Delta_Tau(Tabu(i,n),Tabu(i,1))=Delta_Tau(Tabu(i,n),Tabu(i,1))+Q/L(i);
        end
        Tau=(1-Rho).*Tau+Delta_Tau;
        Tabu=zeros(m,n);
    end
    Pos=find(L_best==min(L_best));
    Shortest_Route=R_best(Pos(1),:);
    Shortest_Length=L_best(Pos(1));
end