电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛

标题: 一个用蚁群算法求最短路径的例子(matlab) [打印本页]

作者: yuyang911220 时间: 2016-9-11 20:21 标题: 一个用蚁群算法求最短路径的例子(matlab)

这个例子其实是当初数模比赛时用来完成碎片拼接的，但其所用到原理还是求解最短路径的原理。但这里的最短路径和数据结构中最短路径有一定的区别。在数据结构中，对于最短路径的求解常用的一般有Dijkstra算法与Floyd算法，但对于要求出一条经过所有的点的并且要求路径最短，这些算法还是有一定的局限性的。而蚁群算法则很好地满足了这些条件。
话说回来，很想吐槽一下网络流传的一些蚁群算法的例子，当初学习这个时候，身边也没有相关的书籍，只好到网上找例子。网上关于这个算法源代码的常见的有2个版本，都是出自博客，但是在例子都代码是不完整的，缺失了一部分，但就是这样的例子，居然流传甚广，我很好奇那些转载这些源码的人是否真的有去学习过这些，去调试过。
当然，我下面的例子也是无法直接编译通过的，因为涉及到图像读取处理等方面的东西，所以就只贴算法代码部分。但是对于这个问题蚁群算法有一个比较大的缺点，就是收敛很慢，不过对于数量小的路径，效果还是很好的。
function bestqueue =aco1(nt,nc_max,m ,st, sd ,Alpha ,Beta ,Rho ,Q,gethead,getend)
%参数解释：
%nt 路径所经过的点的个数；
%nc_max 迭代的次数；
%m 蚂蚁的个数；
%st 起点序号；
%sd 终点序号；
%Alpha 信息素系数；
�ta 启发因子系数；
%Rho 蒸发系数；
% Q 信息量；
%gethead getend 是用来求距离矩阵的，可根据实际情况修改

% nt = 209;%碎片个数
full = zeros(nt,nt);
tic;
%初始化距离矩阵
for i =1:nt
for t  = 1:nt
      if i ~= t
         full(i,t) = sum(abs(getend(:,i)  - gethead(:,t)));
      else
         full(i,t) = inf;
      end
end
end
% a =full(156,187)
eta  = 1./full;%启发因子，取距离的倒数
% eta
% e = eta(4,2)
tau = ones(nt,nt);%信息素矩阵
% tabu = zeros(nt,nt);%禁忌矩阵，取蚂蚁数量和碎片数量一致，以减少迭代次数
nc =1;%初始化迭代次数;
rbest=zeros(nc_max,nt);%各代最佳路线
rbest(:,1) = (linspace(st,st,nc_max))';
rbest(:,nt) =(linspace(sd,sd,nc_max))';
lbest=zeros(nc_max,1);%各代最佳路线的长度
pathlen = 0;%临时记录每代最佳路线长度
stime = 1;%记录代数进度
for i = 1:nc_max % 代数循环
delta_tau=zeros(nt,nt);%初始化改变量
stime
for t = 1:m % 对蚂蚁群体的循环，

      tabu=zeros(1,nt);%禁忌向量，标记已访问的碎片，初试值设为0，访问之后则变为1;
      viseted = zeros(1,nt);%记录已访问的元素的位置
      tabu(st) = 1;%st为起点，在此表示为碎片矩阵的编号，因为已经将蚁群放在起点，故也应将禁忌向量和位置向量的状态进行修改
      tabu(sd) =1;%同上
      visited(nt) = sd ;%同上；
      visited(1) = st;%同上；

      ht  = 0;
      for r  = 2:nt-1  %记录了还没访问的图片编号
            vp = 1;%visited指示量
            pp  = [];%置空的概率向量
            jc = 0;
            %获取尚未访问的位置的向量。
            wv = zeros( nt -2 - ht );
            for  k  =1 : nt
               if tabu(k) ==  0
                  jc = jc +1;
                  wv(jc)  = k;

               end
            end
%          a =(tau(visited(end),ju(3))^Alpha)*(eta(visited(end),ju(3))^Beta)
%          visited(end)
         %计算选择的概率
         for k=1:length(wv)
            pp(k)=(tau(visited(vp),wv(k))^Alpha)*(eta(visited(vp),wv(k))^Beta);%下一张碎片的选择概率计算，p =（信息素^信息素系数）*（启发因子^启发因子系数）
         end
         pp=pp./(sum(pp));%归一化
         pcum  =cumsum(pp);
         psl = find(pcum >= rand);%轮盘赌法
         to_visit= wv(psl(1)) ;%完成选点
         tabu(to_visit) =1;
         visited(r) = to_visit;
         ht =ht +1;%已访问碎片个数变化
         vp  =vp+1;
      end
      %路径变化信息
      %对单个蚂蚁的路径进行统计
      sum1 =0;
      for pr = 1:nt -1
         x = visited(pr);
         y = visited(pr+1) ;
         sum1 =sum1 + full(x,y);
      end
%       vcell{t} =visited;%元胞记录每个蚂蚁的路径，即碎片顺序;
%       msum(t) = sum1;
      %信息素变化；

      for ww=1

nt-1)
         delta_tau(visited(ww),visited(ww+1))=delta_tau(visited(ww),visited(ww+1)) + Q/sum1;
      end
%          delta_tau(visited(end),visited(1))=delta_tau(visited(end),visited(1))+Q/(sum1/100);
%          if t == m & i == nc_max
%                bestqueue = visited
%          end
      if t == m
         bestqueue  = visited
      end
end
tau=(1-Rho).*tau+delta_tau;
%完成信息素的更新，找出现有的最新的最佳路径,即信息素最多的路径；
stime  =stime +1;
end
toc;

欢迎光临电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛 (http://bbs.eccn.com/)