| 蚁群算法及其matlab代码详解 | 您所在的位置：网站首页 › 蚁群算法路径规划代码 › 蚁群算法及其matlab代码详解 |
蚁群算法及其matlab代码详解
|
蚁群算法是模拟蚁群觅食行为的一种优化算法。在整个觅食过程中蚂蚁散播信息素，蚂蚁通过感知到的信息素多少，来决定所要选择的下一个栅格。 在初始阶段，由于地面上没有信息素，因此蚁群的行走路径是随机的，蚂蚁在行走的过程中会不断释放信息素，标识自己行走的路径。随着时间的推移，有若干只蚂蚁找到了食物，此时便存在若干条从洞穴到食物的路径。由于蚂蚁的行为轨迹是随机分布的，因此在单位时间内，短路径上的蚂蚁数量比长路径上的蚂蚁密度要大，短路径留下的信息素浓度也越高。这为后面的蚂蚁们提供了有力的方向指引，越来越多的蚂蚁聚集到最短的路径上去。对于单个蚂蚁来说，它并没有要寻找最短路径，只是根据概率选择；对于整个蚁群系统来说，它们却达到了寻找到最优路径的客观上的效果。 假设蚁群中蚂蚁的总数为M，各蚂蚁在栅格环境下移动，并且根据状态转移规则选择下一个栅格，假设在时刻t时，蚂蚁k位于栅格i，那么蚂蚁k选择下一个栅格j的概率为： (1)式中：V表示蚂蚁K可以选择下一个栅格的集合；Alpha为信息素浓度启发因子,Alpha越大，表明蚂蚁K越趋向于选择多数蚂蚁走过的路径；Beta表示期望启发因子，反映了能见度信息对蚂蚁选择下一步位置所起作用的大小，Beta值越大，表明蚂蚁K越趋向于选择距离目标点近的栅格，越倾向于往能见度程。表示t时刻路径(i,j)上的信息素浓度；表示t时刻路径(i,j)上的启发信息，其定义为： 蚁群算法的核心部分在于模拟了蚁群的转移概率选择行为，通过使用信息素和启发式函数值进行转移概率计算。其中蚂蚁状态转移过程中以节点到目标点之间的距离的倒数作为启发信息，不利于障碍物的预先规避。并且在复杂的路径规划环境下，蚁群算法在一个庞大的空间中搜索，在优化初期路径上的信息素浓度较小，正向反馈信息不明显尤其是随机解产生的过程中的“盲目搜索”产生大量的局部交叉路径，降低蚁群算法的运行效率，且容易陷入局部最优，搜索进行到一定程度后，容易出现停滞现象，所有个体发现的解完全一致，不能进行进一步搜索，不利于发现更好的解。 matlab仿真 绘制方格图举例： G=[ 0 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 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ] MM = size(G,1); figure(3) axis([0,MM,0,MM]) for i=1:MM for j=1:MM if G(i,j)==1 x1=j-1;y1=MM-i; x2=j;y2=MM-i; x3=j;y3=MM-i+1; x4=j-1;y4=MM-i+1; fill([x1,x2,x3,x4],[y1,y2,y3,y4],[0.3,0.3,0.3]); hold on else x1=j-1;y1=MM-i; x2=j;y2=MM-i; x3=j;y3=MM-i+1; x4=j-1;y4=MM-i+1; fill([x1,x2,x3,x4],[y1,y2,y3,y4],[1,1,1]); hold on end end end
完整代码以及注释如下： D=G2D(G); %把栅格地图转为邻接矩阵 N=size(D,1);%N表示问题的规模（象素个数）返回矩阵D行数 MM=size(G,1);%返回G的行数 a=1;%小方格象素的边长 Ex=a*(mod(E,MM)-0.5);%终止点横坐标 a乘以变量E对MM（行）取余(得到列)后减0.5 即所处列 if Ex==-0.5 Ex=MM-0.5; end Ey=a*(MM+0.5-ceil(E/MM));%E/MM结果取整 终止点纵坐标 Eta=zeros(1,N);%启发式信息，取为至目标点的直线距离的倒数 初始信息素矩阵 %下面构造启发式信息矩阵 for i=1:N ix=a*(mod(i,MM)-0.5);%a乘以变量i对MM取余后减0.5 列 if ix==-0.5 ix=MM-0.5; end iy=a*(MM+0.5-ceil(i/MM));%ceil将结果朝正无穷方向取整 if i~=E %i是否等于E Eta(1,i)=((ix-Ex)^2+(iy-Ey)^2)^(0.5); %与终点的直线距离的倒数，启发信息 else Eta(1,i)=0.01; end end ROUTES=cell(K,M);%用细胞结构存储每一代的每一只蚂蚁的爬行路线 蚂蚁个数*迭代次数矩阵，每个元素是一个结构 PL=zeros(K,M);%用矩阵存储每一代的每一只蚂蚁的爬行路线长度 %% -----------启动K轮蚂蚁觅食活动，每轮派出M只蚂蚁-------------------- tic for k=1:K %disp(k); for m=1:M %% 第一步：状态初始化 W=S;%当前节点初始化为起始点 Path=S;%爬行路线初始化 PLkm=0;%爬行路线长度初始化 TABUkm=ones(1,N); %生成禁忌列表,所有节点均未走过，所以都置为1 TABUkm(S)=0;%已经在初始点了，因此要排除 DD=D;%邻接矩阵初始化 %% 第二步：下一步可以前往的节点 DW=DD(W,:); %把矩阵DD的第W行所有列赋值给DW % DW1=find(DW=rand);%产生任意0~1之间的随机数，轮盘赌算法，尽量避免陷入局部最优解 to_visit=LJD(Select(1));%下一步将要前往的节点 %% 第四步：状态更新和记录 Path=[Path,to_visit];%路线节点增加 PLkm=PLkm+DD(W,to_visit);%路径长度增加，记录本次迭代最佳路线长度，每只蚂蚁都有自己走过的长度记录在向量中。 W=to_visit;%蚂蚁移到下一个节点 %N：所有点 for kk=1:N if TABUkm(kk)==0 %禁忌列表 DD(W,kk)=inf; %在此次循环中设置为不可达 DD(kk,W)=inf; end end TABUkm(W)=0;%已访问过的节点从禁忌表中删除 DW=DD(W,:); LJD=find(DW |
【本文地址】