蚁群算法+LEACH 点滴（四） 蚁群算法（TSP问题）

蚁群算法弄了几天了，都是在网上找，然后在修改，有些有问题，改了下，发现运行效果还行，这里就给出来。

原文链接不知道了，只能说声对不起了。Sorry….

城市信息保存在city.txt中，运行时先加载进去,txt内容最后面给出。

clc;

clear all;

C = load(‘city.txt’)

在运行命令：

ACATSP(C,20,50,1,5,0.1,100)

%关于相关参数的设置，程序里已详细的说明。

下面是主程序：

function [R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q)
%%————————————————————————-
% % 主要参数符号说明
% % C n个城市的坐标，n×2的矩阵
% % NC_max 最大迭代次数
% % m 蚂蚁个数,一般取sqrt(n)~n/2
% % Alpha 表征信息素重要程度的参数
% % Beta 表征启发式因子重要程度的参数
% % Rho 信息素蒸发系数
% % Q 信息素增加强度系数
% % R_best 各代最佳路线
% % L_best 各代最佳路线的长度
% % 参考设置初始参数如下：
% % m=sqrt(n)~n/2;Alpha=1;Beta=5;Rho=0.1;NC_max=100;Q=100;

%%
%%第一步：变量初始化
n=size(C,1);%n表示问题的规模（城市个数），由于为坐标表示，所以两个城市之间均可达
D=zeros(n,n);%D表示完全图的赋权邻接矩阵
for i=1:n
    for j=1:n
        if i~=j
            D(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5;
        else
            D(i,j)=eps;      %i=j时不计算，应该为0，但后面的启发因子要取倒数，用eps（浮点相对精度）表示
        end
%        D(j,i)=D(i,j);   %对称矩阵
    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);   %各代最佳路线的长度
L_ave=zeros(NC_max,1);        %各代路线的平均长度

%%
while NC<=NC_max        %停止条件之一：达到最大迭代次数，停止
    
    %%
    %%第二步：将m只蚂蚁放到n个城市上
    Randpos=[];   %0行0列
    for i=1:(ceil(m/n))%ceil是向离它最近的大整数圆整
        Randpos=[Randpos,randperm(n)];%随机产生一个城市序列,长度超过蚂蚁个数m，数据对应为城市号
    end
    Tabu(:,1)=(Randpos(1,1:m))’;    %取前m个作为对应蚂蚁要放的城市号
    
    %%
    %%第三步：m只蚂蚁按概率函数选择下一座城市，完成各自的路径
    for j=2:n     %每只蚂蚁寻找自己的回路，计算m只蚂蚁各自的下一个城市，而不是一次算出第i只蚂蚁的全部路径
        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 length(find(visited==k))==0   %开始时置0,find返回矩阵X中所有非零元素所在位置
                 %find(visited==k)如果visited 中没有k,则返回Empty（0）
                    J(Jc)=k;%保存从1开始可以访问的城市号，将可以访问的城市选择出来
                    Jc=Jc+1; %能访问的城市个数自加1
                end
            end
            %下面计算待选城市的概率分布
            for k=1:length(J)
                P(k)=(Tau(visited(end),J(k))^Alpha)*(Eta(visited(end),J(k))^Beta);%end为矩阵末位索引
            end
            P=P/(sum(P));
            %按概率原则选取下一个城市
%             Pcum=cumsum(P);     %cumsum，元素累加即求和
%             Select=find(Pcum>=rand); %若计算的概率大于原来的就选择这条路线
%             to_visit=J(Select(1));
            [Select,to_visitP] = max(P);%求最大概率的路
            to_visit = J(to_visitP);
            Tabu(i,j)=to_visit;%更新第i只蚂蚁的第j个城市
        end
    end
%     if NC>=2
%         Tabu(1,:)=R_best(NC-1,:);
%     end
    
    %%
    %%第四步：记录本次迭代最佳路线
    L=zeros(m,1);     %开始距离为0，m*1的列向量
    for i=1:m%所有蚂蚁的路径长度对应于L中
        R=Tabu(i,:);
        for j=1:(n-1)
            L(i)=L(i)+D(R(j),R(j+1));    %原距离加上第j个城市到第j+1个城市的距离
        end
        L(i)=L(i)+D(R(1),R(n));      %路径上最后一个城市直接返回（这样合理？？）
    end
%     L_best(NC)=min(L);           %保存当前最佳距离
%     pos=find(L==L_best(NC));
    [L_best(NC),pos] = min(L);   %保存当前最佳距离值和在L中的位置，即哪只蚂蚁,用min函数保存一个即可
    R_best(NC,:)=Tabu(pos,:); %此轮迭代后的最佳路线
    L_ave(NC)=mean(L);           %此轮迭代后的平均距离
    NC=NC+1                      %迭代继续
    
    %%
    %%第五步：更新信息素
    Delta_Tau=zeros(n,n);        %开始时信息素为n*n的0矩阵
    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);
            %此次循环在路径（i，j）上的信息素增量
        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)); %找到最佳路径（非0为真）
Shortest_Route=R_best(Pos(1),:) %最大迭代次数后最佳路径
Shortest_Length=L_best(Pos(1)) %最大迭代次数后最短距离
subplot(1,2,1)                  %绘制第一个子图形
DrawRoute(C,Shortest_Route)     %画路线图的子函数
subplot(1,2,2)                  %绘制第二个子图形
plot(L_best)
hold on                         %保持图形
plot(L_ave,’r’)
title(‘平均距离和最短距离’)     %标题
%%
function DrawRoute(C,R)
%%====================================================================
%  DrawRoute.m
%  画路线图的子函数
%——————————————————————–
%  C    Coordinate        节点坐标，由一个N×2的矩阵存储
%  R    Route             路线
%%====================================================================

N=length(R);
scatter(C(:,1),C(:,2));
hold on
plot([C(R(1),1),C(R(N),1)],[C(R(1),2),C(R(N),2)])
hold on
for ii=2:N
    plot([C(R(ii-1),1),C(R(ii),1)],[C(R(ii-1),2),C(R(ii),2)])
    hold on
end

运行结果：

城市信息：

1304 2312
3639 1315
4177 2244
3712 1399
3488 1535
3326 1556
3238 1229
4196 1004
4312 790
4386 570
3007 1970
2562 1756
2788 1491
2381 1676
1332 695
3715 1678
3918 2179
4061 2370
3780 2212
3676 2578
4029 2838
4263 2931
3429 1908
3507 2367
3394 2643
3439 3201
2935 3240
3140 3550
2545 2357
2778 2826
2370 297

今天的文章蚁群算法+LEACH 点滴（四） 蚁群算法（TSP问题）分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。