蚁群算法--------解决TSP问题

1.蚂蚁觅食行为

　　（1）路径上释放信息素，信息素浓度的大小代表了蚂蚁所走路径的长短

　　（2）信息素的浓度随着时间的推进而逐渐减少

2.蚁群算法求解优化问题的基本思路

　　（1）蚂蚁的行走路径表示待优化问题的可行解

　　（2）所有蚂蚁构成的蚂蚁群体所走的路径就构成了待优化问题的解空间

　　路径较短的蚂蚁释放的信息素量较多，随着时间的推进，较短的路径上累积的信息素浓度逐渐增高， 选择该路径的蚂蚁个数也愈来愈多。 最终， 整个蚂蚁会在正反馈的作用下集中到最佳的路径上， 此时对应的便是待优化问题的最优解。

　　步骤：初始化----路径构造----自动更新----得出结果

　　流程如图：

3.求解TSP问题

　　（1）符号说明以及计算公式

　　　　　　蚂蚁数量：m

　　　　　　城市数量：n

　　　　　　城市i与城市j之间的距离：d_ij （i,j<1,2,...,n）　　

 具体代码如下（代码巨详细，小白都看得懂）：

%% 清空环境变量
clear;
clc;
tic
%% 导入数据
load citys_data.mat
%% 计算各城市间距离d
n=size(citys,1);%总的城市个数
D=zeros(n,n);
for i=1:n
    for j=1:n
        if i~=j
            D(i,j)=sqrt(sum((citys(i,:)-citys(j,:)).^2));
        else
            D(i,j)=1e-4;
        end
    end
end
%% 初始化参数
m=100;%蚂蚁数量
alpha=2;%信息素启发因子（若减少到0，则变成随机贪婪算法，一般情况下取值[1,2]）
rho=0.5;%信息素挥发系数
beta=5;%自启发因子（取值过大，易于陷入局部最优；取值国小，将导致蚁群陷入随机搜索，收敛慢，不易于寻优）
Eta=1./D;%启发函数（也称为先验知识能见度，该函数不固定）
Q=1;%循环一次释放信息素的总和
Table=zeros(m,n);%路径记录表（也就是禁忌表）
Tau=ones(n,n);%信息素矩阵
iter=1;%迭代次数初始值
iter_max=260;%最大迭代次数
Route_best=zeros(iter_max,n);%每一代最佳路径
Length_best=zeros(iter_max,1);%每一代最佳路径长度
%% 用while循环 经迭代寻找最佳路径
while iter <=iter_max
    iter
    %随机产生蚂蚁所在城市
    start=zeros(m,1);
    for i=1:m
        temp=randperm(n);%1-n里面的随机整数序列
        start(i)=temp(1);
    end
    Table(:,1)=start;
    citys_index=1:n;%城市索引
    %逐个蚂蚁路劲选择
    for i=1:m
        %逐个城市路径选择
        for j=2:n
            tabu=Table(i,1:(j-1));%已经访问的城市（一共n-1个城市，禁忌表）
            allow_index=~ismember(citys_index,tabu);
            %ismember(A,B)表示B中元素在A中是否出现，出现则返回值1，否则为0
            %~表示取反
            allow=citys_index(allow_index);%未访问城市集合
            P=allow;
            %城市间转移概率计算
            for k=1:length(allow)
                P(k)=Tau(tabu(end),allow(k))^alpha*Eta(tabu(end),allow(k))^beta;
            end
            P=P/sum(P);
            %运用轮盘赌选择下一个访问城市
               Pc=cumsum(P);%cumsum累加函数，cumsum(A,2)表示返回每行的累加和
               target_index=find(Pc>=rand);
               target=allow(target_index(1));
%                 target_index=max(Pc);
%                 target=allow(target_index(1));
               Table(i,j)=target;
        end
    end
    %计算各个蚂蚁路径距离
    Length=zeros(m,1);
    for i=1:m
        Route=Table(i,:);
        for j=1:(n-1)
            Length(i)=Length(i)+D(Route(j),Route(j+1));
        end
        Length(i)=Length(i)+D(Route(n),Route(1));
    end
    %计算最短路径距离以及平均距离
    if iter==1
        [min_length,min_index]=min(Length);
        Length_best(iter)=min_length;
        Route_best(iter,:)=Table(min_index,:);
    else
        [min_length,min_index]=min(Length);
        Length_best(iter)=min(Length_best(iter-1),min_length);
        if Length_best(iter)==min_length
            Route_best(iter,:)=Table(min_index,:);
        else
            Route_best(iter,:)=Table(min_index,:);
        end
    end
    Delta_Tau=zeros(n,n);
    %信息素更新模型有三种
    for i=1:m
        for j=1:(n-1)
            Delta_Tau(Table(i,j),Table(i,j+1))=Delta_Tau(Table(i,j),Table(i,j+1))+Q/Length(i);
        end
        Delta_Tau(Table(i,n),Table(i,1))=Delta_Tau(Table(i,n),Table(i,1))+Q/Length(i);
    end
    Tau=(1-rho)*Tau+Delta_Tau;%信息浓度更新方程
    iter=iter+1;
    Table=zeros(m,n);
end
  %% 结果显示
  [Short_length,index]=min(Length_best);
  Short_route=Route_best(index,:);
  disp(['最短距离：' num2str(Short_length)]);
  disp(['最短路径' num2str([Short_route Short_route(1)])]);
  %% 绘图
  figure(1)
  plot([citys(Short_route,1);citys(Short_route(1),1)],...
      [citys(Short_route,2);citys(Short_route(1),2)],'*-');
  grid on
  for i=1:size(citys,1)
      text(citys(i,1),citys(i,2),[' ' num2str(i)]);
  end
   text(citys(Short_route(1),1),citys(Short_route(1),2) ,'起点');   
   text(citys(Short_route(end),1),citys(Short_route(end),2),'    终点');
   xlabel('城市位置横坐标')
   ylabel('城市位置纵坐标')
  title(['蚁群算法优化路径(最短距离:' num2str(Short_length) ')'])
  toc

　　求解如图：

TSP数据集下载地址：

　　http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/index.html