基于群智能的路径规划算法（二）------蚁群算法

   本系列文章主要记录学习基于群智能的路径规划算法过程中的一些关键知识点，并按照理解对其进行描述和进行相关思考。

   主要学习资料是来自 小黎的Ally 的 《第2期课程-基于群智能的三维路径规划算法》，视频链接如下（点击链接可跳转）：

   https://space.bilibili.com/477041559/channel/seriesdetail?sid=863038

   本篇文章是本系列的第二篇文章 ：蚁群算法

---

---

本系列文章链接 （点击可跳转）：

-----------------------------------------------------------------------------

   基于群智能的路径规划算法（一）------粒子群算法

   基于群智能的路径规划算法（二）------蚁群算法

   基于群智能的路径规划算法（三）------遗传算法

   基于群智能的路径规划算法（四）------人工蜂群算法

   基于群智能的路径规划算法（五）------狼群算法

   基于群智能的路径规划算法（六）------人工鱼群算法

-----------------------------------------------------------------------------

---

   一、蚁群算法简介

   蚁群算法(Ant Colony Algorithm,ACA)于1992年在首次提出，该算法模拟了自然界中蚂蚁的觅食行为。蚂蚁在寻找食物源时，会在其经过的路径上释放一种信息素，并能够感知其它蚂蚁释放的信息素。信息素浓度的大小表征路径的远近，信息素浓度越高，表示对应的路径距离越短。

   通常，蚂蚁会以较大的概率优先选择信息素浓度较高的路径，并释放一定量的信息素，以增强该条路径上的信息素浓度，这样，会形成一个正反馈。最终，蚂蚁能够找到一条从巢穴到食物源的最佳路径，即距离最短。

   二、蚁群模型详解

   以蚁群在城市间运动为例，设整个蚂蚁群体中蚂蚁的数里为m，城市的数里为n，城市i与城市j之间的相互距离为dij(i.,j=1,2… n)，t时刻城市i与城市j连接路径上的信息素浓度为τij（t）。初始时刻，各个城市间连接路径上的信息素浓度相同，不妨设为τij（0）=τ0

   蚂蚁k(k=1,2… m)根据各个城市间连接路径上的信息素浓度决定其下一个访问城市,设Pij(t)表示t时刻蚂蚁k从城市i转移到城市j的概率，其计算公式如下:

   以下描述均针对蚂蚁k而言：其中ηij(t)为启发函数，ηij(t)= 1/dij,表示蚂蚁k从城市i转移到城市j的期望程度。allowed为蚂蚁k待访问城市的集合（未访问过的节点的集合）。开始时，allowed中有(n-1)个元素，即包括除了蚂蚁k出发城市的其它所有城市。随着时间的推进，allowed中的元素不断减少，直至为空，即表示所有的城市均访问完毕。α为信息素重要程度因子，其值越大，表示信息素的浓度在转移中起的作用越大﹔β为启发函数重要程度因子﹐其值越大，表示启发函数在转移中的作用越大，即蚂蚁会以较大的概率转移到距离短的城市。

   在蚂蚁释放信息素的同时，各个城市间连接路径上的信息素也在逐渐消失，即信息素的挥发，设参数ρ(0<ρ<1)表示信息素的挥发程度。因此，当所有蚂蚁完成一次循环后，各个城市间连接路径上的信息素浓度需进行实时更新,具体公式如下:

   其中，△τijk表示第k只蚂蚁在城市i与城市j连接路径上释放的信息素浓度，△τij表示所有蚂蚁在城市i与城市j连接路径上释放的信息素浓度之和。

---

   三、将蚁群算法应用于路径规划

   用蚂蚁的行走路径表示待优化问题的可行解，整个蚂蚁群体的所有路径构成待优化问题的解空间。

   路径较短的蚂蚁释放的信息素量较多，随着时间的推进，较短的路径上累积的信息素浓度逐渐增高，选择该路径的蚂蚁个数也愈来愈多。

   最终，整个蚂蚁会在正反馈的作用下集中到最佳的路径上，此时对应的便是待优化问题的最优解。

   在二维环境中，拓扑地图由若干个节点按照某种连接关系组合而成，强调不同节点间的连通性，节点之间的联通代价通常用权值代表（长度、时间等)。蚁群算法在利用信息素选择路径时，可以考虑成在某个节点，按照该节点与其他节点的联通关系不同的权值比重（视为信息素比例)，选择路径。

   在三维环境中，三维空间不具有拓扑地图那样的连通性约束，而是不同经纬度对应的海拔高度(山峰高度）作为约束，其余空间皆为自由解空间。考虑在高度方向将三维空间切片分层，每一层的平面划分为若干个栅格，那么利用蚁群算法进行三维路径规划的本质是:在不同的切片平面确定不同的栅格，将这些栅格利用样条函数绘制成光滑的曲线。

---

   四、算法流程

   在三维空间中的规划流程：

   ① Step1:将三维空间按照高度进行切片，切片数量可以根据算法的精度要求和时间成本等综合考虑;

   ② Step2:针对每一个切片进行栅格化处理，如10×10个栅格;

   ③ Step3:某些栅格位于山峰高度以下，若选择了该栅格会导致规划的路径与山体相交，故需筛选可行栅格;

   ④ Step4:在Matlab定义切片信息结构体，该结构体应当包含每一个切片的可行栅格，本层切片与下一层切片的连接信息:包括信息素、启发因子等等

   ⑤ Step5:本层切片的栅格与下一侧切片的栅格的选择操作=蚂蚁在路口根据信息素浓度按照轮盘赌法选择路径的操作。

---

   五、轮盘选择法

   轮盘赌的核心思想就是对于每个待选择的点，其对应的概率越大，被选中的可能性就越大，通过将每个点对应的概率除以所有点对应概率之和的方式来对每个点对应的概率进行处理，处理后，每个点对应的概率相加即为1，然后将这些点依次摆放在0~1的一维数轴上，其概率值越大，所占用的数轴长度就越大（注意跟摆放位置无关，可任意摆放），摆放完成后每个点也就对应于0 ~ 1数轴上一个小区间，比如第1个点的概率是0.05，第2个点的概率是0.03，第3个点的概率是0.1 … …，则第1个点对应的区间为0 ~ 0.05，第2个点对应的区间为0.05 ~ 0.08 ，第3个点对应的区间率为0.08 ~ 0.18，以此类推，这样我们随机产生一个0 ~ 1之间的随机数，该随机数落在那个区间，那个点即为被选中的点。

---

   六、编程实现思路

   对 小黎的Ally 提供的程序 的实现思路总结如下：

   首先根据设定的切片层数，在Z轴方向上进行切片，并对每一层进行栅格化，在提供的程序中每十个点取一个栅格，进一步获得每一个切片层可访问的栅格，第一个切片层（即起点所在的切片层）可访问的节点即为起点，最后一个切片层（即终点所在的切片层）可访问的节点的终点，其他切片层可访问的栅格节点为不存在障碍物的节点。

   然后，初始化信息素和启发值，从第一层开始计算，当前层的每一个可访问节点与下一层的每一个可访问节点之间的距离，将距离的倒数再乘以一个系数（程序中的系数为100）作为这两点之间的启发值，并初始化当前层的所有可访问节点与下一层的所有可访问节点间路径的信息素为1。直至计算完最后一层，至此初始化部分完成。

   开始循环迭代，在每次迭代中（第一层循环），对于每只蚂蚁（第二层循环），要从每个切片层中选取一个节点，这些节点就组成了该蚂蚁代表的路径的关键点，再经过B样条曲线/贝塞尔曲线等方法就可以计算得该蚂蚁对应的路径。核心是如何从每个切片层中选取节点，第一个切片层选取的节点为起点，然后由上文介绍的蚂蚁从i点移动到j点的概率计算公式，计算该蚂蚁从当前层选择的节点到下一层所有可访问节点的概率，然后采用轮盘赌的方法从这些节点中选取一个节点作为该层选择的节点，然后用同样的方法获取其他层选择的节点，最后一个切片层选取的节点为终点。然后计算该条路径的对应的适用度，在本程序中，若该路径存在障碍物物，则赋一个很大的值，若不存在障碍物，则将路径长度作为适应度，容易看出在该程序中适应度越低越好。然后判断是否更新该蚂蚁的最优路径，以及是否更新整个蚁群的最优路径。然后计算该蚂蚁经过的路径的信息素增量，即本代中该只蚂蚁对应的关键点间的小路径的信息素增量增加（系数/路径适应度）。

   每个蚂蚁均完成以上操作后，也就是该代的第二层循环结束后，本代中，每条小路径对应的信息素增量的和也就计算完了，然后由上文介绍到的信息素更新公式对信息素进行更新，至此，本次迭代完成，按照第一层循环，进行下一代迭代，直到完成设定的迭代次数。

   程序实现上的缺陷：每层切片默认只能选择一个点，对于复杂的环境可能找不到合适的路径

---

   七、运行效果示例：

---

---

   上面的示例中100次迭代后的适应度为198.3144，而理论最优适应度为160.75，可知算法陷入了局部最优，且100次迭代耗时达到了6分钟，规划效率低下。

---