蚁群算法最优路径

1、蚁群算法最优路径机器人的路径规划-蚁群算法1. 蚁群算法众所周知，蚁群算法是优化领域中新出现并逐渐引起重视的一种仿 生进化算法它是群体智能的典型实现，是一种基于种群寻优的启发式搜索算法。自从M. Dorigo等意大利学者在1991年首先提出蚁群算法(Ant Colony System, ACS以来，这种新型的分布式智能模拟算法已逐渐引起人们的注意并得到广泛 的应用。蚁群算法的特点主要表现在以下五个方面：(1) 蚂蚁群体行为表现出正反馈过程。蚁群在寻优的过程中会释放一定量的 信息素，蚁群的规模越大，释放的信息素的量也就越大，而寻优路径上存在的 信息素浓度越高，就会吸引更多的蚂蚁，形成一种正反馈机

2、制，然后通过反馈 机制的调整，可对系统中的较优解起到一个自增强的作用，从而使问题的解向 着全局最优的方向演变，最终能有效地获得全局相对较优解。(2) 蚁群算法是一种本质并行的算法。个体之间不断进行信息交流和传递.有 利于最优解的发现，并在很大程度上减少了陷于局部最优的可能。(3) 蚁群算法易于与其他方法结合。蚁族算法通过与其他算法的结合，能够 扬长避短，提高算法的性能。(4) 蚁群算法提供的解具有全局性的特点。一群算法是一种群只能算法，每 只蚂蚁巡游的过程相对独立，他们会在自己的活动空间进行搜索，蚂蚁在寻优 过程中通过释放信息素，相互影响，互相通信，保证了解的全局性。(5) 蚁群算法具有鲁棒性

3、。蚁族算法的数学模型易于理解，可以广泛应用在 很多复杂的优化问题中，蚁族算法区别于传统优化算法的一个特点在于该算法 不依赖于初始点的选择，受初始点的影响相对较小，并且在整个算法过程中会 自适应的调整寻优路径。由此可见，在机器人寻找最优路径的过程中，采用蚁群算法实现路径的规 划问题，可以高效，准确的找到最优的路径。2. 移动机器人的路径规划2.1环境信息处理假设机器人运行环境为边长分别为x和丫的矩形区域，在矩形区域内分布有n 个异形障碍物，显然对于该获取的实际环境信息：首先，由于障碍物大小不一， 而且形状也各不相同，为了减少机器人处理地图信息的负担，需要对工作环境 行一些必要的预处理；其次，在后

4、续章节中，描述机器人的路径规划方法是基 于把障碍物近似成质点的基础上进行的，而要把障碍物近似成质点也同样需要 对工作环境的信息进行适当预处理。环境信息预处理遵循以下原则：1）移动机器人作二维平面运动，障碍物不考虑高度信息；2）小问距障碍物作合并处理，即如果两个障碍物相距太近，障碍物之间距离小 于机器人通过的最小安全距离。则将两个障碍物合并作为一个障碍物处理；3）作出障碍物的外接矩形，并对障碍物外接矩形进行径向扩张且对环境边界向 内作径向扩张，因此可把移动机器人退化成运动质点处理。2.2环境建模设机器人工作空间为二维结构化空间记为RS,并且障碍物位置、大小已知。用尺寸相同的栅格对RS4行划分，栅

5、格大小以机器人能在其内自由运动为 限，设机器人能自由运动的范围为0，R。若某一栅格尺寸范围内不含任何障 碍物，贝U称此栅格为自由栅格，反之称为障碍栅格。自由空间和障碍物均可表 示成栅格块的集合，我们将障碍物栅格集记为OS栅格标识可采用下述两种方法：（1）直角坐标法。以栅格阵左上角为坐标原点，水平向右为x轴正方向，竖直向下为丫轴正方向，每一栅格区间对应坐标轴上的一个单位长度。任一栅格 均可用直角坐标（x，y）唯一标识。（2）序号法。按从左到右，从上到下的顺序，从栅格阵左上角第一个栅格开 始，给每一个栅格一个序号n（从0开始计），则序号以与栅格块一一对应。2.3具体方法给定一个有弹个节点的城市道路

6、网的路径规划问题，我们可以把指定的 起始点s假设为人工蚁群（以下简称为蚁群）的巢穴，把目标点t假设为要寻找的 食物，则此路径规划问题就可以转化为蚁群寻找食物的路径寻优问题。假定人 工蚂蚁(以下简称为蚂蚁)的数量为m只，则每只蚂蚁的行为要符合以下的规则： (1)能够释放出两种类型的信息素：“食物”信息素和“巢穴”信息素； 根据与当前节点相连接的各个路径上的信息素浓度和路径长度，以相应的概 率来随机选择下一个节点；(3) 不再选择已经走过的节点为下一个节点，这可以通过一个结构数组来实现；(4) 在寻找食物时，通过“食物”信息素寻找下一个节点，同时释放“巢穴”信 息素；(5) 在寻找巢穴时，通过“巢

7、穴”信息素寻找下一个节点，同时释放“食物”信 息素；(6) 按一定的路径长度释放相应的信息素浓度，并且所释放的信息素浓度会随着 时间的推移而逐步减少；3. 程序设计流程在主程序流程中，地图数据库是从实际地图中抽象出来的城市道路网相关的数据信息，其中包括城市道路网的节点信息、道路信息和相应道路的信息素信 息，每部分信息都各自形成一个数据表。在节点表中，包括了各个节点的编号、 对应的地点名称和经纬度坐标等数据。在道路表中，包括了每条道路的起点和 终点对应的编号、道路的长度、级别和所经过的路线等数据。在信息素表中， 包括了对应道路上的“巢穴”信息素和“食物”信息素等数据。所需要输入的 参数包括：节点

8、的数量n、起始节点的编号OriNode、目标节点的编号DesNode 最大循环次数MaxCount、蚂蚁的数量m蒸发信息素的相对重要程度、每只蚂蚁所释放的信息素总量Q信息素浓度的相对重要程度口、启发式信息的相对重 要程。所需要初始化的参数包括：“巢穴”信息素和“食物”信息素等值，每条 道路对应的“巢穴”信息素和“食物”信息素的值分别仞始化为1，这是为了在计算下一个节点的选择概率时，分母不为 0。在程序开始时，首先连接地图数据库，然后输入、初始化各个参数并 开始进行循环。在每次循环中，每只蚂蚁依次进行寻食过程，如果有蚂蚁找到 了食物即找到了一条寻食路径，将此路径与本次循环中其它蚂蚁找到的寻食路

9、径进行比较，将最小的寻食路径更新为最优路径，并判断是否满足所给定的精 度，如果满足则退出循环，否则进行下一次循环。当循环次数达到最大次数时， 结束循环并判断是否找到了最优路径，如果找到了最优路径，则输出最优路径 的路线及其权值，否则显示没有找到最优路径。最后，关闭地图数据库并结束 程序。在每只蚂蚁进行寻食的过程中，首先判断蚂蚁是否正在寻找食物，如 果是则进行寻找食物的过程，否则进行寻找巢穴的过程。在进行寻找食物的过 程中，首先从地图数据库的道路表中读取与当前节点所连接的节点数，以及每 个节点的编号和权值。判断每个节点是否已经走过，如果此节点已经走过，贝U 读取下一个节点。从地图数据库的信息素表

10、中读取对应边的“食物”信息素值， 从当前点到下一可行点的转移是由基于信息量的状态转移概率和和距离启发式 信息概率综合决定的，而这里采用的综合决定方法是基于比例选择策略即“轮 盘赌”的方式。从地图数据库的道路表中读取对应边的权值，并计算所走过路 径的权值。从地图数据库的信息素表中读取对应边的“巢穴”信息素值，并重 新计算对应边的“巢穴”信息素值。当所得的值小于1时，将此值设置为1,这是为了保证下一回计算选择概率时分母不为 0。将重新计算的“巢穴”信息素值 更新到信息素表中。判断下一个目标节点是否为食物，如果是的话，贝M呆存各 个记录，如蚂蚁所走过的节点、此蚂蚁找到食物的次数以及整个路径的总权值

11、等数据，并为寻找巢穴做准备，如清空内存中的历史数据，将食物作为起始节 点等，否则设置下一个目标节点为当前节点。在进行寻找巢穴的过程中，大部分的操作都跟上面蚂蚁进行寻找食物的 过程一样，只不过将“食物”信息素和“巢穴”信息素进行对调，在判断下一 个目标节点是否为巢穴的时候，不需要保存各个记录，只需为寻找食物做准备， 如清空内存中的历史数据，将巢穴作为起始节点，并将此蚂蚁上次找到食物的 路径记录。程序流程图如下：4. Matlab 仿真4.1参数介绍地图数据库是从实际地图中抽象出来的城市道路网相关的数据信息, 其中包括城市道路网的节点信息、道路信息和相应道路的信息素信息，每部分信息都各自形成一个数

12、据表。在节点表中，包括了各个节点的编号、对应的地 点名称和经纬度坐标等数据。在道路表中，包括了每条道路的起点和终点对应 的编号、道路的长度、级别和所经过的路线等数据。在信息素表中，包括了对 应道路上的“巢 穴”信息素和“食物”信息素等数据。本仿真系统的静态地图数据假设在机器 人出发之前就已经得到，而动态地图数据假设按一定的频率可以得到。在机器人整个仿真系统中所需要输入的参数包括：节点的数量栉、起始节点的编号OriNode、目标节点的编号DesNode最大循环次数MaxCount、蚂蚁 的数量m蒸发信息素的相对重要程度、每只蚂蚁所释放的信息素总量 Q信息 素浓度的相对重要程度"、启发式

13、信息的相对重要程。所需要初始化的参数包括：“巢穴”信息素和“食物”信息素等值，每条道路对应的“巢穴”信息素和“食物”信 息素的值分别初始化为1，这是为了在计算下一个节点的选择概率时，分母不为0。4.2程序介绍4.2.1G2D.m用于把障碍物分布图转化为图的赋权邻接矩阵，地形图矩阵是一个01矩阵，里面的所有元素要么为0,要么为1。为0即表示机器人可以到达的节点， 为1即表示其对应的栅格是障碍物。源程序如下：fun ctio n D=G2D(G)a=1;N=size(G,1);D=i nf*o nes(NA2,NA2);for i=1:(NA2)x=ceil(i/N-0.00001);y=mod(

14、i,N);if y=0y=N;end x1=x-1;y1=y-1; if x1>=1 &&y1>=1 j=(x1-1)*N+y1;D(i,j)=1.414*a;D(j,i)=1.414*a; end x2=x-1;y2=y;if x2>=1j=(x2-1)*N+y2;D(i,j)=a;D(j,i)=a; end x3=x-1;y3=y+1; if x3>=1 && x3<=N j=(x3-1)*N+y3;D(i,j)=1.414*a;D(j,i)=1.414*a; end x4=x;y4=y-1;if y4>=1j=(x4-1

15、)*N+y4;D(i,j)=a;D(j,i)=a;end x5=x;y5=y+1;if y5<=N j=(x5-1)*N+y5; D(i,j)=a; D(j,i)=a;end x6=x+1;y6=y-1;if x6<=N&&y6>=1 j=(x6-1)*N+y6; D(i,j)=1.414*a; D(j,i)=1.414*a;end x7=x+1;y7=y;if x7<=N j=(x7-1)*N+y7; D(i,j)=a; D(j,i)=a;end x8=x+1;y8=y+1;if x8<=N&&y8<=Nj=(x8-1)*N

16、+y8;D(i,j)=1.414*a;D(j,i)=1.414*a;endendfor x=1:Nfor y=1:Nif G(x,y)=1J=(x-1)*N+y;D(:,J)=i nf*o nes(NA2,1);D(J,:)=i nf*on es(1,NA2); endendendfor i=1:(N-1)x=i*N+1;y=(i+1)*N;D(x,y)=i nf;D(y,x)=i nf;end4.2.2ACASP.m障碍物可以动的情况设计的蚁群算法，其主要功能就是通过派遣若干批蚂 蚁，来搜索动态环境下的最短路。程序内部设计准则完全按照前面的设计要求 进行，包括启发式信息规则、信息素更新规则，

17、等等。当然，此程序可以单独 运行，主要用于解决静态环境下的蚂蚁寻路问题。程序把各批次所有蚂蚁的行 走路线都记录下来，可以据此绘出蚂蚁寻路的动态图形。源程序如下：fun cti onROUTES,PL,Tau=Route(G,Tau,K,M,S,E,Alpha,Beta,Rho,Q)D=G2D(G);N=size(D,1);MM=size(G,1);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(1,N);for i=1:Nix=a*(mod(i,MM)-0.5);if ix=-

18、0.5ix=MM-0.5;endiy=a*(MM+0.5-ceil(i/MM);if i=EEta(1,i)=1/(ix-Exf2+(iy-EyF2)八0.5;elseEta(1,i)=100;endendROUTES=cell(K,M);PL=zeros(K,M);for k=1:Kdisp(k);for m=1:MW=S;Path=S;PLkm=0;TABUkm=o nes(1,N);TABUkm(S)=0;DD=D;DW=DD(W,:);DW仁fin d(DW<i nf);for j=1:le ngth(DW1)if TABUkm(DW1(j)=0DW(j)=i nf;endend

19、LJD=fi nd(DW<i nf); Len_LJD=le ngth(LJD);while W=E&&Len_LJD>=1PP=zeros(1,Len_LJD);for i=1:L en_LJDPP(i)=(Tau(W,LJD (i) )AAlpha)*(Eta(LJD(i)ABet a)；endPP=PP/(sum(PP);Pcum=cumsum(PP);Select=fi nd(Pcum>=ra nd); to_visit=LJD(Select(1);Path=Path,to_visit;PLkm=PLkm+DD(W,to_visit);theW=to_

20、visit;%move ton ext pointfor kk=1:N if TABUkm(kk)=O DD(W,kk)=i nf; DD(kk,W)=i nf;endendTABUkm(W)=0;DW=DD(W,:);DW仁fin d(DW<i nf);for j=1:le ngth(DW1)if TABUkm(DW1(j)=0 DW(j)=i nf;endendLJD=fi nd(DW<i nf);Len_LJD=le ngth(LJD); endROUTESk,m=Path;if Path(e nd)=EPL(k,m)=PLkm;elsePL(k,m)=i nf;endend

21、Delta_Tau=zeros(N,N);for m=1:Mif PL(k,m)<i nfROUT=ROUTESk,m;TS=le ngth(ROUT)-1;PL_km=PL(k,m);for 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;endendendTau=(1-Rho).*Tau+Delta_Tau;%pheromone evaporates some and accumulates someendplotif=1

22、;%controlparameter, determine ifplot or notif plotif=1%plot con verge nee curve mean PL=zeros(1,K);min PL=zeros(1,K);for i=1:KPLK=PL(i,:);Non zero=fi nd(PLK<i nf); PLKPLK=PLK(No nzero);mea nPL(i)=mea n( PLKPLK); mi nPL(i)=mi n(PLKPLK);endfigure(1) plot(mi nPL,'r'); hold onplot(mea nPL,

23、9;g');legend('最小路径长度平均路径长度 ');grid ontitle('收敛曲线(平均路径长度和最小 路径长度)');xlabel('迭代次数');ylabel('路径长度');%Plot Passi ng Graphfigure(2)axis(O,MM,O,MM)for i=1:MMfor j=1:MMif G(i,j)=1x1=j-1;y 1=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

24、.2,0.2,0.2); hold onelsex1=j-1;y 1=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 onendendendhold onROUT=ROUTESK,M;LENROUT=le ngth(ROUT);Rx=ROUT;Ry=ROUT;for ii=1:LENROUTRx(ii)=a*(mod(ROUT(ii),MM)-0.5);if Rx(ii)=-0.5 Rx(ii)=MM-0.5;endRy(ii)=a*(MM+0.5-ceil(

25、ROUT(ii)/MM);endplot(Rx,Ry,'Li neWidth',2)endtitle('Shortest Path');axis(0,MM,0,MM);plotif2=1;% Plot route forevery iterati onif plotif2=1figure(3)axis(0,MM,0,MM)for i=1:MMfor j=1:MMif G(i,j)=1x1=j-1;y 1=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,

26、0.2,0.2,0.2); hold onelsex1=j-1;y 1=MM-i;x2=j;y2=MM-i;x3=j;y3=MM-i+1; x4=j-1;y4=MM-i+1;endendendfor k=1:KPLK=PL(k,:);mi nPLK=mi n(PLK); pos=fi nd(PLK=mi nPLK); m=pos(1);ROUT=ROUTESk,m;LENROUT=le ngth(ROUT);Rx=ROUT;Ry=ROUT;for ii=1:LENROUTRx(ii)=a*(mod(ROUT(ii),MM)-0.5);if Rx(ii)=-0.5 Rx(ii)=MM-0.5;endRy(i