基本蚁群算法蚂蚁觅食路径的演变

1、基本蚁群算法-蚂蚁觅食路径的演变UNITY3D中进行模拟演算经过60代之后蚂蚁在觅食过程中能够在其经过的路径上留下一种称之为信息素的物质，并在觅食过程中能够感知这种物质的强度，并指导自己的行动方向,它们总是朝着信息素强度高的方向移动，因此大量的蚂蚁组成的集体觅食就表现为一种对信息素的正反馈现象。某一条路径越短，路径上经过的蚂蚁就越多，其信息素遗留的也就越多，信息素的浓度也就越高，蚂蚁选择这条路的几率也就越高，由此构成正反馈的过程，从而逐渐地逼近最优路径，并找到最优路径。算法简要流程：初始化。选择从初始节点下一步可以到达的所有节点，根据公式JV竹如科3GN-tabuk(0其他计算出前往每个节点的

2、概率。并利用赌徒轮盘选取下一步的初始点。需要注意的是蚂蚁只能向四周八个节点前进。第k只蚂蚁从节点i到节点j的概率。因(圳在t时刻，表示节点i至节点j边上的信息激素量，各条边的初始值为同一常数砌1表示i，j两节点间的启发值，与两节点间距离成反比。a一一怡a、8为信息素和启发值得权重参数N网格数量，例如地图(a)中N=16tabuj.保存第k只蚂蚁已行的节点。若蚂蚁陷入U型障碍，使得蚂蚁无后续节点选择，则默认该蚂蚁已经死亡，算法删除该蚂蚁及其所寻路径更新路径以及路径长度。重复(2),(3)两步，直到找到食物或者无路可走之后退出。重复(2),(3),(4)直到m只蚂蚁全部完成旅途，一代算是结束。信息

3、素更新。每次所有蚂蚁旅行完成后对信息素进行全局更新，过去的信息素逐渐消逝，并加入新的信息素。其中没有找到食物的蚂蚁不予以计算。根据公式Tij(t+1)=(1-p)*Tijt)+丁舒蚂蚁矗经过了蚂蚁怡不经过2jP挥发系数，一般取01之间常数近強+1)在t+1时刻，节点i,j间信息素的量旬本次循环中节点i，j间信息素的增量在t时刻，第k只蚂蚁所寻路径的长度(7)重复(2)(6)，直到n代蚂蚁全部完成旅行。地图信息1214567910111213141516网格环境(黑色为障碍物)和行动逻辑图PI1234567891()1i1213141516/hIfl网格与序号关系图网格规模N;网格数量蚂蚁种群数

4、量numberOfAnts;迭代次数numberOfIterations;信息素挥发系数p；/般取01之间常数信息素Tij；留在i,j节点间信息素的量，各条边的初始值为同一常数信息素权重参数a;信息素增量tij;/本次循环中节点i,j间信息素的增量启发值n；计算各个网格节点到目标网格的直线距离的倒数。启发值权重参数B；禁忌表tabu;保存蚂蚁已行节点。若蚂蚁陷入U型障碍，使得蚂蚁无后续节点选择,则默认该蚂蚁已经死亡，算法删除该蚂蚁及其所寻路径概率p;前往各个节点的概率值路径path;/记录这一代这一只蚂蚁的行动路线路径表PATH;/记录每一代每一只蚂蚁的行动路线路径长度pathLeagth;/

5、记录这一代这一只蚂蚁的行动路线的距离路径长度表PATH_LEAGTH;/记录每一代每一只蚂蚁的行动路线的距离起点start;/蚁巢终点target;/食物算法开始前的初始化工作和要用到的公式函数:直线和斜线网格之间的移动成本BET-DISTANCE(_start,_target)dstX=|_startX-_targetX|的绝对值dstY=|_startY-_targetY|的绝对值ifdstXdstYreturn1.4*dstY+1*(dstX-dstY)return1.4*dstX+1*(dstY-dstX)/欧几里得距离平方。EUCLID-DISTANCE(_startX,_start

6、Y,_targetX,_targetY)dstX=|_startX-_targetX|的绝对值dstY=|_startY-_targetY|的绝对值return(dstXA2+dstYA2)A0.5/初始化启发式信息，计算各个网格到目标网格的直线距离的倒数。启发值和直线距离成倒数，直线距离越远启发值越小，反之亦然。s=当前网格序号fori=0to网格坐标xforj=0to网格坐标yifsk目标网格序号ns-1=1/EUCLID-DISTANCE(i,j,target.i,target.j)elsens-1=999s+=1;/初始化每条路径上信息素的量fori=0toN-1forj=0toN-1

7、T=1；算法开始foriteration=1tonumberOflterations-1forant=1tonumberOfAnts-1currentNode=starta=1B=8pathLength=0/禁忌表初始化，用来记录这一代这一只蚂蚁走过的路，已经走过的路用false表示fori=0to网格坐标xforj=0tc网格坐标ytabuij=truetabucurrentNode.xcurrentNode.y=false/起点不让走了下一步可以前往的节点GetNeighbours()见之前发表的A*网格寻路这篇文章neighbours=GetNeighbours(currentNode)

8、;fori=0toneighbours.Count-1neighbour=neighbours;ifneighbour不是障碍物&tabuneighbour.xneighbour.ymovableRange.Add(neighbour);/可以前往的节点/蚂蚁未遇到食物并且未陷入死胡同whilecurrentNode工target&movableRange.Count=1/计算走每条路的概率fori=0tomovableRange.Count-1tcurrentNode.网格序号-1movableRangei.网格序号-1八ae=nmovableRangei.网格序号-1八Bpi=t*epsu

9、m=0fori=0top.length-1psum=pi+psumfori=0top.length-1pi=pi/psum用赌徒轮盘选择下一步怎么走pcum0=P0pcumO=P0fori=1tomovableRange.Count-1pcumi=pcumi-1+pipindex=0;random=(O.Of,1.0f)之间的随机小数fori=0tomovableRange.Count-1ifpcumi=randompindex=ibreaknextNode=movableRangepindex;/状态更新和记录path.Add(nextNode)pathLength=pathLength+B

10、etDistance(currentNode,nextNode)currentNode=nextNode已访问过的节点从禁忌表中删除tabucurrentNode.xcurrentNode.y=false/下一步可以前往的节点neighbours=GetNeighbours(currentNode);fori=0toneighbours.Count-1neighbour=neighbours;ifneighbour不是障碍物&tabuneighbour.xneighbour.ymovableRange.Add(neighbour);/可以前往的节点这里结束while循环记下每一代每一只蚂蚁的觅

11、食路线和路线长度PATHiterationnumberOfAnts=pathifpathpath.Count-1=targetPATH_LEAGTHiterationnumberOfAnts=pathLeagthelsePATH_LEAGTHiterationnumberOfAnts=0这里结束forant=1tonumberOfAnts遍历更新信息素fori=0toN-1forj=0toN-1&ij=0;fori=0tonumberOfAnts-1ifPATH_LEAGTHiterationi工0pia=PATHiterationiplia=PATH_LEAGTHiterationifors=0topia.Count-2x=piasy=pias+1txy=Atxy+1/pliatyx=A