新浪博客

一个用蚁群算法求最短路径的例子(matlab)

2013-10-14 03:59阅读：

http://blog.sina.cn/dpool/blog/u/1789848692

这个例子其实是当初数模比赛时用来完成碎片拼接的，但其所用到原理还是求解最短路径的原理。但这里的最短路径和数据结构中最短路径有一定的区别。在数据结构中，对于最短路径的求解常用的一般有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)));
br> 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;

我的更多文章

下载客户端阅读体验更佳

APP专享