(完整word版)基于蚁群算法的路径规划最新（精华版）

1、matlab实现基于蚁群算法的机器人路径规划1、 问题描述移动机器人路径规划是机器人学的一个重要研究领域。它要求机器人依据某个或某些优化原则 (如最小能量消耗，最短行走路线，最短行走时间等)，在其工作空间中找到一条从起始状态到目标状态的能避开障碍物的最优路径。机器人路径规划问题可以建模为一个有约束的优化问题，都要完成路径规划、定位和避障等任务。2 算法理论蚁群算法（ ant colony algorithm，aca ），最初是由意大利学者dorigo m.博士于 1991 年首次提出， 其本质是一个复杂的智能系统，且具有较强的鲁棒性，优良的分布式计算机制 等优点。 该算法经过十多年的发展，已被

2、广大的科学研究人员应用于各种问题的研究，如旅行商问题， 二次规划问题，生产调度问题等。但是算法本身性能的评价等算法理论研究方面进展较慢。dorigo提出了精英蚁群模型（eas ），在这一模型中信息素更新按照得到当前最优解的蚂蚁所构造的解来进行，但这样的策略往往使进化变得缓慢，并不能取得较好的效果。次年dorigo博士给出改进模型（acs ），文中改进了转移概率模型，并且应用了全局搜索与局部 搜 索 策 略 ， 来 得 进 行 深 度 搜 索 。st tzle与hoos给 出 了 最 大 - 最 小 蚂 蚁 系 统（max-minas），所谓最大 -最小即是为信息素设定上限与下限，设定上限避免搜

3、索陷入局部最优， 设定下限鼓励深度搜索。蚂蚁作为一个生物个体其自身的能力是十分有限的，比如蚂蚁个体是没有视觉的，蚂蚁自身体积又是那么渺小，但是由这些能力有限的蚂蚁组成的蚁 群却可以做出超越个体蚂蚁能力的超常行为。蚂蚁没有视觉却可以寻觅食物，蚂蚁体积渺小而蚁群却可以搬运比它们个体大十倍甚至百倍的昆虫。这些都说明蚂蚁群体内部的某种机制 使得它们具有了群体智能，可以做到蚂蚁个体无法实现的事情。经过生物学家的长时间观察 发现，蚂蚁是通过分泌于空间中的信息素进行信息交流，进而实现群体行为的。下面简要介绍蚁群通过信息素的交流找到最短路径的简化实例。如图2-1 所示，ae之间有两条路abcde与 abhde

4、 ，其中ab ， de ，hd ， hb的长度为1， bc ， cd 长度为0.5，并且， 假设路上信息素浓度为0，且各个蚂蚁行进速度相同，单位时间所走的长度为1， 每个单位时间内在走过路径上留下的信息素的量也相同。当t=0 时，从a点， e 点同时各有 30 只蚂蚁从该点出发。当 t=1 ，从 a 点出发的蚂蚁走到b 点时， 由于两条路bh与 bc 上的信息素浓度相同，所以蚂蚁以相同的概率选择bh 与 bc ，这样就有15 只蚂蚁选择走bh ，有 15 只蚂蚁选择走bc 。同样的从e 点出发的蚂蚁走到d 点，分别有15 只蚂蚁选择 dh和 dc 。当 t=2 时，选择 bc 与 dc 的蚂蚁

5、分别走过了bcd和 dcb ，而选择 bh与dh的蚂蚁都走到了h 点。所有的蚂蚁都在所走过的路上留下了相同浓度的信息素，那么路径 bcd上的信息素的浓度是路径bhd上信息素浓度的两倍，这样若再次有蚂蚁选择走bc 和 bh时，或选择走dc与 dh 时，都会以较大的概率选择信息素浓度高的一边。这样的过程反复进行下去，最短的路径上走过的蚂蚁较多，留下的信息素也越多，蚁群这样就可以找到一条较短的路。这就是它们群体智能的体现。蚁群算法就是模拟蚂蚁觅食过程中可以找到最短的路的行为过程设计的一种仿生算法。在用蚁群算法求解组合优化问题时，首先要将组合优化问题表达成与信息素相关的规范形式，然后各个蚂蚁独立地根据

6、局部的信息素进行决策构造解，并根据解的优劣更新周围的信息素，这样的过程反复的进行即可求出组合优化问题的优化解。归结蚁群算法有如下特点：（ 1）分布式计算：各个蚂蚁独立地构造解，当有蚂蚁个体构造的解较差时，并不会影响整体的求解结果。这使得算法具有较强的适应性；（ 2）自组织性：系统学中自组织性就是系统的组织指令是来自系统的内部。同样的蚁群算法中的各个蚂蚁的决策是根据系统内部信息素的分布进行的。这使得算法具有较强的鲁棒性；（ 3）正反馈机制与负反馈机制结合：若某部分空间上分布的信息素越多，那么在这个空间上走过的蚂蚁也就越多；走过的蚂蚁越多，在那个空间上留下的信息素也就越多，这就是存在的正反馈机制。

7、但蚁群算法中解的构造是通过计算转移概率实现的，也就是说构造解的时候可以接受退化解，这限制了正反馈机制，可以使得搜索范围扩大，这是蚁群算法中隐含的负反馈机制。3 求解步骤应用蚁群算法求解机器人路径优化问题的主要步骤如下：（ 1）输入由0 和 1 组成的矩阵表示机器人需要寻找最优路径的地图的地图，其中0 表示此处可以通过的，1 表示此处为障碍物。2018161412108642002468101214161820上图的表示矩阵为：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 0 0 0 0 0 0 0 0 0 0 0 0 0 0;0 1 1

8、 0 0 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 0 0 0 0 0 0 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 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 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 0 0 0;0 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0;0 0 0 0 0 0 0 0 0 0 1 1 1

9、 1 0 0 0 0 0 0;0 0 0 0 0 0 0 1 1 0 1 1 1 1 0 0 0 0 0 0;0 0 0 0 0 0 0 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 1 1 0 1 1 1 1 0;0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 1 1 0;0 0 1 1 0 0 0 0 0 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 0 0 0 0 0;0 0 0 0 0 0 1 1 1 0 1 1 0 0 0 0 0 1 1 0;0 0 0

10、 0 0 0 0 0 0 0 1 1 0 0 1 0 0 1 1 0;0 0 0 0 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 0 0 0 0 0 0 0 0 0 0;(2) 输入初始的信息素矩阵，选择初始点和终止点并且设置各种参数。在此次计算中， 我们设置所有位置的初始信息素相等。(3) 选择从初始点下一步可以到达的节点，根据每个节点的信息素求出前往每个节点的概率，并利用轮盘算法选取下一步的初始点。ijtijpkijijtijifjntabukkn tabuk0otherwise其中ijt 为析取图中弧i, j上的信息素的浓度。i

11、j 为与弧i, j相关联的启发式信息。，分别为ijt，ij 的权重参数。（4）更新路径，以及路程长度。(5)重复（ 3）（ 4）过程，直到蚂蚁到达终点或者无路可走。（6） 重复（ 3）（ 4）（ 5），直到某一代m 只蚂蚁迭代结束。（7） 更新信息素矩阵，其中没有到达的蚂蚁不计算在内。ij t11ijtijijtqlk t，如果蚂蚁k经过 i， j0，如果蚂蚁k不经过i ， j其中为信息素挥发系数。q 为信息量增加强度。lk t为路径长度。（8） 重复（ 3） -（ 7），直至 n 代蚂蚁迭代结束。4 运行结果（图、表等）将上述矩阵输入到程序中，画出最短路径的路线，并且输入每一轮迭代的最短路径

12、，查看程序的收敛效果，在程序中设置plotif=1则输出收敛和最短路径图，在程序中设置plotif2=1 则输出每一代蚂蚁的路径图。最终输出的结果如图2018161412108642002468101214161820收 敛 曲 线 （ 最 小 路 径 长 度 ）45403530路度25 长 径201510500102030405060708090100迭 代 次 数5 ma tlab程序function m_main()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 0 0 0 0 0 0 0 0 0 0 0 0 0 0;0 1 1

13、 0 0 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 0 0 0 0 0 0 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 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 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 0 0 0;0 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0;0 0 0 0 0 0 0 0 0 0 1 1 1

14、 1 0 0 0 0 0 0;0 0 0 0 0 0 0 1 1 0 1 1 1 1 0 0 0 0 0 0;0 0 0 0 0 0 0 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 1 1 0 1 1 1 1 0;0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 1 1 0;0 0 1 1 0 0 0 0 0 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 0 0 0 0 0;0 0 0 0 0 0 1 1 1 0 1 1 0 0 0 0 0 1 1 0;0 0 0

15、 0 0 0 0 0 0 0 1 1 0 0 1 0 0 1 1 0;0 0 0 0 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 0 0 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;% k迭代次数（指蚂蚁出动多少波）m=50;% m蚂蚁个数（每一波蚂蚁有多少个）s=1 ;% s 起始点（最短路径的起始点） e=mm*mm;% e终止点（最

16、短路径的目的点） 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;% 小方格象素的边长ex=a*(mod(e,mm)-0.5);%终止点横坐标if ex=-0.5ex=mm-0.5;endey=a*(mm+0.5-ceil(e/mm);%终止点纵坐标eta=zeros(n);% 启发式信息，取为至目标点的直线距离的倒数%

17、下面构造启发式信息矩阵for i=1:n ix=a*(mod(i,mm)-0.5);if ix=-0.5 ix=mm-0.5;endiy=a*(mm+0.5-ceil(i/mm); if i=eeta(i)=1/(ix-ex)2+(iy-ey)2)0.5;else eta(i)=100;endendroutes=cell(k,m);%用细胞结构存储每一代的每一只蚂蚁的爬行路线pl=zeros(k,m);% 用矩阵存储每一代的每一只蚂蚁的爬行路线长度% - 启动 k 轮蚂蚁觅食活动，每轮派出m 只蚂蚁 -for k=1:k for m=1:m% 第一步：状态初始化w=s;% 当前节点初始化为起始

18、点path=s;%爬行路线初始化 plkm=0;% 爬行路线长度初始化tabukm=ones(n);% 禁忌表初始化tabukm(s)=0;% 已经在初始点了，因此要排除dd=d;% 邻接矩阵初始化% 第二步：下一步可以前往的节点dw=dd(w,:);dw1=find(dw);for j=1:length(dw1)if tabukm(dw1(j)=0 dw(dw1(j)=0;endend ljd=find(dw);len_ljd=length(ljd);% 可选节点的个数% 觅食停止条件：蚂蚁未遇到食物或者陷入死胡同while w=e&len_ljd=1% 第三步：转轮赌法选择下一步怎么走pp

19、=zeros(len_ljd); for i=1:len_ljdpp(i)=(tau(w,ljd(i)alpha)*(eta(ljd(i)beta); endsumpp=sum(pp); pp=pp/sumpp;%建立概率分布pcum(1)=pp(1);for i=2:len_ljd pcum(i)=pcum(i-1)+pp(i); endselect=find(pcum=rand); to_visit=ljd(select(1);% 第四步：状态更新和记录path=path,to_visit;% 路径增加plkm=plkm+dd(w,to_visit);%路径长度增加w=to_visit;%

20、 蚂蚁移到下一个节点for kk=1:nif tabukm(kk)=0 dd(w,kk)=0;dd(kk,w)=0;endendtabukm(w)=0;%已访问过的节点从禁忌表中删除dw=dd(w,:);dw1=find(dw);for j=1:length(dw1)if tabukm(dw1(j)=0 dw(j)=0;end endljd=find(dw);len_ljd=length(ljd);% 可选节点的个数end% 第五步：记下每一代每一只蚂蚁的觅食路线和路线长度routesk,m=path;if path(end)=e pl(k,m)=plkm; if plkmminklmink=

21、k;minl=m;minkl=plkm;end elsepl(k,m)=0;end end% 第六步：更新信息素delta_tau=zeros(n,n);% 更新量初始化for m=1:mif pl(k,m)rout=routesk,m;ts=length(rout)-1;% 跳数pl_km=pl(k,m);endendfor s=1:ts x=rout(s); y=rout(s+1);delta_tau(x,y)=delta_tau(x,y)+q/pl_km; delta_tau(y,x)=delta_tau(y,x)+q/pl_km;endtau=(1-rho).*tau+delta_ta

22、u;% 信息素挥发一部分，新增加一部分end%绘图plotif=1;% 是否绘图的控制参数if plotif=1 % 绘收敛曲线minpl=zeros(k); for i=1:kplk=pl(i,:);nonzero=find(plk); plkplk=plk(nonzero); minpl(i)=min(plkplk);end figure(1) plot(minpl); hold ongrid ontitle( 收敛曲线（最小路径长度）); xlabel( 迭代次数 );ylabel( 路径长度 ); % 绘爬行图figure(2)axis(0,mm,0,mm)for i=1:mm for

23、 j=1:mm if g(i,j)=1x1=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.2,0.2,0.2);hold on elsex1=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 hold onrout=routesmink,minl; lenrout=length(rout); rx=rout;ry=rout;for ii=1:lenrout rx(ii)=a*(mod(rout(ii),mm)-0.5); if rx(ii)=-0.5rx(ii)=mm-0.5;endry(ii)=a*(mm+0.5-ceil(rout(ii)/mm); endplot(rx,ry) endplotif2=0;% 绘各代蚂