推荐|图说蚁群算法(ACO)附源码

图说蚁群算法(ACO)附源码

25-03-07 18:21

2831

13087

blog.csdn.net

id="article_content" class="article_content clearfix"> id="content_views" class="htmledit_views">

PS：再过几天就可以返校收拾东西了，想想还有点小激动呐hhh~回想疫情宅家的这半年，真是一段充满了焦虑、惊喜、忙碌、充实又时而无聊的时光。。。返校只能待三天又让人有点小遗憾呐。就想着趁还在家这几天，把毕设用到的一些算法整理一下吧！

废话不多说了，这次要讲的是蚁群算法(下称ACO)。

一、初识ACO：这是个啥玩意?

二、ACO的数学原理

三、MATLAB代码

一、初识ACO：这是个啥玩意?

ACO是一种用来规划最优路径的概率型算法，其原理参考了蚁群在寻找食物过程中发现最短路径的行为。

这里我们先不谈高大上的数学原理，我们先定性地理解下蚁群算法的基本原理。既然ACO参考了蚁群的觅食行为，那我们就不妨先了解下蚁群是如何在觅食过程中找到最优路径的吧，直接上图解释吧。

style="text-align:center;">

蚂蚁种群可以在行走过程中释放与感知一种叫做信息素的物质，并通过这种能力进行种群内的信息传递。每只蚂蚁都会在行走的路径上释放这种信息素，另外蚂蚁在选择出行路径时会一定程度上参考不同路径上其他蚂蚁留下的信息素浓度，并趋向于沿着信息素浓度较高的路径行走(如图1中的线路3所示)，越是短的路径上残留的信息素就会越多，久而久之，经过一段时间的摸索后，整个蚁群就会沿着信息素浓度最高的路径即最优路径行走了。

蚁群算法就是参照了上述蚁群觅食的过程而提出来的一种寻找最优路径的方法，最早用以解决旅行商(TSP)问题。蚁群算法的基本流程如下所示：

在以上算法描述中，需要遵循两个原则：一个是在同一世代中的蚂蚁之间互不干扰，即同一世代的蚂蚁在本次行走中释放的信息素对该世代中其他的蚂蚁无影响。另外一个就是每只蚂蚁在每条路径上只能走一次，为此可以设置禁忌表(Tabu)来控制。

二、ACO的数学原理

在一中，我们了解了自然界蚁群的觅食过程，而将这一过程进行数学化描述就是ACO算法了。在上面对蚁群觅食的描述中我们可以发现几个关键词：蚁群( ${\color{Red} m}$ )，信息素( ${\color{Red} \tau }$ )，信息素变化量( ${\color{Red} \Delta \tau }$ )，信息素挥发(挥发因子 ${\color{Red} \rho }$ )，路径选择(转移概率 ${\color{Red} p}$ )，久而久之(迭代次数 ${\color{Red} K}$ )，以及路径长度( ${\color{Red} L}$ )。如何对这些关键词数学化呐？且听我慢慢道来。

假设我们有图2这么一张栅格地图，起点终点图中已标出，假设蚂蚁只能从一个栅格中点到下一个相邻(八邻域)栅格中点这样一步一步运动，黑色块为假想的障碍物区域，很明显，这是一次静态的路径规划，我们的目的就是规划一条从起点到终点的最短无碰路径。

% ACO算法实现 function [Lnum_max, num] = p2p(Alpha, Beta) G=[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0; 0 1 1 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0; 0 1 1 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0; 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0; 0 1 1 1 0 0 1 1 1 0 0 0 0 0 0 0 1 1 0 0; 0 1 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0; 0 1 1 1 0 0 1 1 1 0 1 1 1 1 0 0 0 1 1 0; 0 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 1 1 0; 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0; 0 0 0 0 0 0 0 1 1 1 0 1 1 1 0 0 0 0 0 0; 0 0 0 0 0 0 0 1 1 1 0 1 1 1 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 1 1 0; 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0; 1 1 1 1 0 0 0 0 0 0 0 1 1 1 0 1 1 1 1 0; 1 1 1 1 0 0 1 1 0 1 1 1 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 1 1 0 1 1 1 0 0 0 0 0 1 1 0; 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0; 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0;]; MM=size(G,1); % 获取边长，G 地形图为01矩阵，如果为1表示障碍物 Tau=ones(MM*MM,MM*MM); % Tau 初始信息素矩阵 Tau=8.*Tau; K=100; %迭代次数（指蚂蚁出动多少波） M=50; %蚂蚁个数 % Alpha=1; % Alpha 表征信息素重要程度的参数 % Beta=7; % Beta 表征启发式因子重要程度的参数 Rho=0.3 ; % Rho 信息素蒸发系数 Q=1; % Q 信息素增加强度系数 minkl=inf; % 最小正数 mink=0; minl=0; D=G2D(G); N=size(D,1); %N表示问题的规模（像素个数） a=1; %小方格像素的边长 S=1 ; %最短路径的起始点 E=MM*MM; %最短路径的目的点 Ex=a*(mod(E,MM)-0.5); %终止点横坐标 if Ex==-0.5 Ex=MM-0.5; end Ey=a*(MM+0.5-ceil(E/MM)); %终止点纵坐标 ceil向上取整 Eta=zeros(N); %启发式信息，取为至目标点的直线距离的倒数 N=L^2 %以下启发式信息矩阵,每个点到终点距离的倒数 for i=1:N ix=a*(mod(i,MM)-0.5); if ix==-0.5 ix=MM-0.5; end iy=a*(MM+0.5-ceil(i/MM)); if i~=E Eta(i)=1/((ix-Ex)^2+(iy-Ey)^2)^0.5; else Eta(i)=100; end end ROUTES=cell(K,M); %用元胞结构存储每一代的每一只蚂蚁的爬行路线，K=100 迭代次数 M=50蚂蚁数量 cellplot:利用图形方式显示内容（奈斯！） PL=zeros(K,M); %用矩阵存储每一代的每一只蚂蚁的爬行路线长度 %启动K轮蚂蚁觅食活动，每轮派出M只蚂蚁 for k=1:K for m=1:M %状态初始化 W=S; %当前节点初始化为起始点 S为起始点 Path=S; %爬行路线初始化 PLkm=0; %爬行路线长度初始化 TABUkm=ones(N); %禁忌表初始化 TABUkm(S)=0; %已经在初始点了，因此要排除 DD=D; %邻接矩阵初始化 %下一步可以前往的节点 DW=DD(W,:); DW1=find(DW); % 当前点8邻域的索引，find：寻找非零元素的索引和值，返回线性索引 for j=1:length(DW1) if TABUkm(DW1(j))==0 DW(DW1(j))=0; end end LJD=find(DW); % 下一步的可选节点 Len_LJD=length(LJD);%可选节点的个数 %蚂蚁未遇到食物或者陷入死胡同或者觅食停止 while W~=E&&Len_LJD>=1 %轮盘赌法选择下一步怎么走 PP=zeros(Len_LJD); for i=1:Len_LJD PP(i)=(Tau(W,LJD(i))^Alpha)*((Eta(LJD(i)))^Beta); end sumpp=sum(PP); PP=PP/sumpp;%建立概率分布 Pcum(1)=PP(1); for i=2:Len_LJD Pcum(i)=Pcum(i-1)+PP(i); end Select=find(Pcum>=rand); to_visit=LJD(Select(1)); %状态更新和记录 Path=[Path,to_visit]; %路径增加 PLkm=PLkm+DD(W,to_visit); %路径长度增加 W=to_visit; %蚂蚁移到下一个节点 for kk=1:N % 更新禁忌表 if TABUkm(kk)==0 % 禁忌表 DD(W,kk)=0; % 双向关系 DD(kk,W)=0; end end TABUkm(W)=0; %已访问过的节点从禁忌表中删除 DW=DD(W,:); DW1=find(DW); for j=1:length(DW1) if TABUkm(DW1(j))==0 DW(j)=0; end end LJD=find(DW); Len_LJD=length(LJD);%可选节点的个数 end %记下每一代每一只蚂蚁的觅食路线和路线长度 ROUTES{k,m}=Path; if Path(end)==E PL(k,m)=PLkm; if PLkm

一、初识ACO：这是个啥玩意?

二、ACO的数学原理

三、MATLAB代码

评论记录：