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

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

   主要学习资料是来自 小黎的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