蚁群算法.txt

来自「蚁群算法：用来进行路径设计、查找、规划等」· 文本 代码 · 共 258 行 · 第 1/2 页

0        0        0        0        0        0        156.87        0        0        0        0        0        0        0        0        0        0        80.368        0        0        0        0        0        0        0        0        0        0        0        0        0        0        0        76.916        0        0        0        0        0        0        0        0        0        0        0        0        0        0        0        0
0        76.913        0        0        0        0        0        0        0        0        0        0        0        0        0        0        0        0        76.89        0        0        0        0        0        0        0        0        0        0        0        0        0        76.914        0        0        0        0        0        0        0        0        0        0        0        0        0        0        0        0        0
0        0        0        0        0        0        0        0        0        0        0        0        0        0        0        0        0        0        0        0        0        0        0        0        79.409        0        0        0        0        0        76.918        0        0        0        0        0        0        0        0        0        0        0        0        0        0        76.912        0        0        0        0
0        0        0        0        0        0        0        0        0        0        0        0        0        0        0        0        0        0        0        0        0        0        0        0        0        0        0        0        0        0        0        0        0        76.923        76.926        0        0        0        0        0        0        0        0        76.921        0        0        0        0        0        0
];

%%第一步：变量初始化
n=size(C,1);%n表示问题的规模（城市个数）
gplot(D , C);%画无向图
hold on
XX=C';
plot(XX(1 ,  , XX(2 ,  , 'k+', 'markersize' , 5) %画十字架
for i=1:n
    text(C(i,1)+5,C(i,2),int2str(i)); %加标号
end

for i=1:n
    for j=1:n
        if D(i,j)==0       
            D(i,j)=inf;
        end
    end
end
Eta=1./D;%Eta为启发因子，这里设为距离的倒数
Tau=ones(n,n);%Tau为信息素矩阵
Tabu=zeros(m,n);%存储并记录路径的生成
NC=1;%迭代计数器
R_best=zeros(NC_max,n);%各代最佳路线
L_best=inf.*ones(NC_max,1);%各代最佳路线的长度
lastmin=inf;        %上代最小路径
thesameNum=0;       %终止算法条件之一
while NC<=NC_max%停止条件之一：达到最大迭代次数
    %%第二步：将m只蚂蚁放到n个城市上
    Randpos=ones(1,m)*s;
    Tabu(:,1)=(Randpos(1,1:m))';
    %%第三步：m只蚂蚁按概率函数选择相通的下一座城市，直到到达目的地
    for i=1:m    
        %按概率原则选取下一个城市
        %只有当达到最后的节点等于终点时候才结束
        j=2;
        to_visit=s;
        while to_visit~=e
            visited=Tabu(i,1j-1));%已访问的城市
            % 得到矩阵中最后一个不为0的数 ,即蚂蚁爬到的最后节点
            col=size(visited,2);
            lastvisited=visited(end);
            J=[];%待访问的城市，随机分布
            =J;%待访问城市的选择概率分布
            Jc=1;
            JJ=randperm(n);%随机分布
            for k=1:n
                flag=bHaveNum(visited,JJ(k));
                if  flag~=1
                    if        D(lastvisited,JJ(k))~=inf
                        J(Jc)=JJ(k);
                        Jc=Jc+1;
                    end
                end
            end
            if length(J) ==0
                break;
            end
            %下面计算待选城市的概率分布
            for k=1:length(J)    
                P(k)=(Tau(lastvisited,J(k))^Alpha)*(Eta(lastvisited,J(k))^Beta);
            end
            =P/(sum(P));   
            cum=cumsum(P);
            Select=find(Pcum>=rand);
            kk=randperm(length(Select));
            to_visit=J(Select(kk(1)));
            Tabu(i,j)=to_visit;
            j=j+1;
        end
    end
    %%第四步：记录本次迭代最佳路线
    L=zeros(m,1);
    for i=1:m
        R=Tabu(i,;
        F=thelastNum(R);
        if R(F)==e
            for j=1n-1)
                if  R(j+1)~=0
                    L(i)=L(i)+D(R(j),R(j+1));
                end
            end
        else
            L(i)=inf;
        end
    end
    if lastmin~=min(L)        
        thesameNum=0;
    else
        thesameNum=thesameNum+1;
    end
    if (thesameNum >0.2*NC_max)
        break;
    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=1n-1)
            if Tabu(i,j+1)~=0
                Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,j+1))+Q/L(i);
            end
        end
    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));
F=thelastNum(Shortest_Route);
Shortest_Route=Shortest_Route(1:F);



plot(XX(1 , Shortest_Route') , XX(2 , Shortest_Route') , 'g' ,  'linewidth' , 1) %画结果路径 
hold off