智能计算之蚁群算法(ACO)介绍

蚁群算法(Ant Colony Optimization,ACO)由Dorigo 等人于1991年在第一届欧洲人工生命会议(European Conference on Artificial Intelligence,ECAL)上提出,是模拟自然界真实蚂蚁觅食过程的一种随机搜索算法。蚁群算法与遗传算法(GeneticAlgorithm,GA)、粒子群优化算法(Particle Swarm Optimization，PSO)、免疫算法(Immune Algorithm,IA)等同属于仿生优化算法,具有鲁棒性强、全局搜索、并行分布式计算、易与其他方法结合等优点,在典型组合优化问题如旅行商问题(Traveling SalesmanProblem，TSP)、车辆路径问题(Vehicle Routing Problem，VRP),车间作业调度问题(Job-shop Scheduling Problem,JSP)和动态组合规划问题如通信领域的路由问题中均得到了成功的应用。

2. 基本思想

在自然界中，蚂蚁群体在寻找食物的过程中，无论是蚂蚁与蚂蚁之间的协作还是蚂蚁与环境之间的交互均依赖于一种被称为信息素（Pheromone）的物质实现蚁群的间接通信，从而通过合作发现从蚁穴到食物源的最短路径。

蚂蚁在寻找食物的过程中往往是随机选择路径的，但它们能感知当前地面上的信息素浓度，并倾向于往信息素浓度高的方向行进。信息素由蚂蚁自身释放，是实现蚁群内间接通信的物质。由于较短路径上蚂蚁的往返时间比较短，单位时间内经过该路径的蚂蚁多，所以信息素的积累速度比较长路径快。因此，当后续蚂蚁在路口时，就能感知先前蚂蚁留下的信息，并倾向于选择一条较短的路径前行。这种正反馈机制使得越来越多的蚂蚁在巢穴与食物之间的最短路径上行进。由于其他路径上的信息素会随着时间蒸发，最终所有的蚂蚁都在最优路径上行进。

通过对自然界蚁群觅食过程进行抽象建模,我们可以对蚁群觅食现象和蚁群优化算法中的各个要素建立一一对应关系：

3. 研究进展

4. 基本流程

蚂蚁系统（Ant System，AS）是最基本的ACO算法，是以TSP作为应用实例提出的。

AS对于TSP的求解流程大致可分为两步：路径构建和信息素更新。

（1）路径构建

伪随机比例选择规则（random proportional）。

对于每只蚂蚁k，路径记忆向量 $R^k$ 按照访问顺序记录了所有k已经经过的城市序号。设蚂蚁k当前所在城市为i，则其选择城市j作为下一个访问对象的概率如上式。 $J_k\left ( i \right )$ 表示从城市i可以直接到达的、且又不在蚂蚁访问过的城市序列 $R^k$ 中的城市集合。η(i, j)是一个启发式信息，通常由 $\eta\left ( i,j \right )=1/d_{ij}$ 直接计算。 $\tau (i,j)$ 表示边(i, j)上的信息素量。

长度越短、信息素浓度越大的路径被蚂蚁选择的概率越大。a和b是两个预先设置的参数，用来控制启发式信息与信息素浓度作用的权重关系。当a=0时，算法演变成传统的随机贪心算法，最邻近城市被选中的概率最大。当b=0时，蚂蚁完全只根据信息素浓度确定路径，算法将快速收敛，这样构建出的最优路径往往与实际目标有着较大的差异，算法的性能比较糟糕。

（2）信息素更新

在算法初始化时，问题空间中所有的边上的信息素都被初始化为 $\tau _0$ 。
算法迭代每一轮，问题空间中的所有路径上的信息素都会发生蒸发，我们为所有边上的信息素乘上一个小于1的常数。信息素蒸发是自然界本身固有的特征，在算法中能够帮助避免信息素的无限积累，使得算法可以快速丢弃之前构建过的较差的路径。
蚂蚁根据自己构建的路径长度在它们本轮经过的边上释放信息素。蚂蚁构建的路径越短、释放的信息素就越多。一条边被蚂蚁爬过的次数越多、它所获得的信息素也越多。
迭代（2），直至算法终止。

可以结合下面公式来看哦：

m是蚂蚁个数；r是信息素的蒸发率，规定 $0<\rho\leqslant1$ 。 $\Delta\tau_k$ 是第k只蚂蚁在它经过的边上释放的信息素量，它等于蚂蚁k本轮构建路径长度的倒数。 $C_k$ 表示路径长度，它是 $R^k$ 中所有边的长度和。

5. 应用举例

接着，我们结合一个实例来做进一步介绍

步骤2.2中有提到轮盘赌法。是的，和我们遗传算法用的是一样的（当然后面新的方法会有不一样）。

轮盘赌法具体怎么操作，在这里稍微解释一下：
比方说，现在A占比为0.2，B占比为0.5，C占比为0.3。
则当你随机值大小位于为0-0.2时，选A，大小位于0.2-0.7时，选B，大小位于0.7-1.0时，选C。

6. 改进版

6.1 精华蚂蚁系统

精华蚂蚁系统（Elitist Ant System，EAS）是对基础AS的第一次改进，它在原AS信息素更新原则的基础上增加了一个对至今最优路径的强化手段。

引入这种额外的信息素强化手段有助于更好地引导蚂蚁搜索的偏向，使算法更快收敛。

6.2 基于排列的蚂蚁系

基于排列的蚂蚁系统（rank-based Ant System， $AS_{rank}$ ）在AS的基础上给蚂蚁要释放的信息素大小加上一个权值，进一步加大各边信息素量的差异，以指导搜索。在每一轮所有蚂蚁构建完路径后，它们将按照所得路径的长短进行排名，只有生成了至今最优路径的蚂蚁和排名在前(ω-1)的蚂蚁才被允许释放信息素，蚂蚁在边(i, j)上释放的信息素的权值由蚂蚁的排名决定。

权值(ω−k)对不同路径的信息素浓度差异起到了一个放大的作用， $AS_{rank}$ 能更有力度地指导蚂蚁搜索。

6.3 最大最小蚂蚁系

最大最小蚂蚁系统（MAX-MIN Ant System，MMAS）在基本AS算法的基础上进行了四项改进：

只允许迭代最优蚂蚁（在本次迭代构建出最短路径的蚂蚁），或者至今最优蚂蚁释放信息素。（迭代最优更新规则和至今最优更新规则在MMAS中会被交替使用。）如果只使用至今最优更新规则进行信息素的更新，搜索的导向性很强，算法会很快收敛到T b T_bTb附近；反之，如果只使用迭代最优更新规则，则算法的探索能力会得到增强，但收敛速度会下降。实验结果表明，对于小规模的TSP问题，仅仅使用迭代最优信息素更新方式即可。随着问题规模的增大，至今最优信息素规则的使用变得越来越重要。
信息素量大小的取值范围被限制在一个区间 $\left [\tau _{min},\tau _{max} \right ]$ 内。当信息素浓度也被限制在一个范围内以后，位于城市i的蚂蚁k选择城市j作为下一城市的概率也将被限制在一个区间内。算法有效避免了陷入停滞状态（所有蚂蚁不断重复搜索同一条路径）的可能性。
(3)信息素初始值为信息素取值区间的上限，并伴随一个较小的信息素蒸发速率。利好：增强算法在初始阶段的探索能力，有助于蚂蚁“视野开阔地”进行全局范围内的搜索。随后蚂蚁逐渐缩小搜索范围。
(4)每当系统进入停滞状态，问题空间内所有边上的信息素量都会被重新初始化。（我们通常通过对各条边上信息素量大小的统计或是观察算法在指定次数的迭代内至今最优路径有无被更新来判断算法是否停滞。）有效地利用系统进入停滞状态后的迭代周期继续进行搜索，使算法具有更强的全局寻优能力。

6.4 蚁群系统

1997年，蚁群算法的创始人Dorigo在“Ant colony system: a cooperative learning approach to the traveling salesman problem”一文中提出了一种具有全新机制的ACO算法——蚁群系统（Ant Colony System，ACS），进一步提高了ACO算法的性能。

（1）使用一种伪随机比例规则（pseudorandom proportional）选择下城市节点，建立开发当前路径与探索新路径之间的平衡。

在这里插入图片描述

$q_0$ 是一个[0, 1]区间内的参数，当产生的随机数q≤ $q_0$ 时，蚂蚁直接选择使启发式信息与信息素量的指数乘积最大的下城市节点，我们通常称之为开发（exploitation）；反之，当产生的随机数q> $q_0$ 时ACS将和各种AS算法一样使用轮盘赌选择策略，我们称之为偏向探索（bias exploration）。

通过调整 $q_0$ ，我们能有效调节“开发”与“探索”之间的平衡，以决定算法是集中开发最优路径附近的区域，还是探索其它的区域。

（2）使用信息素全局更新规则，每轮迭代中所有蚂蚁都已构建完路径后，在属于至今最优路径的边上蒸发和释放信息素。

在这里插入图片描述

其中 $\Delta \tau _{b}(i,j)= 1 / C_b$ ，不论是信息素的蒸发还是释放，都只在属于至今最优路径的边上进行，这里与AS有很大的区别。因为AS算法将信息素的更新应用到了系统的所有边上，信息素更新的计算复杂度为 $O(n^2)$ ，而ACS算法的信息素更新计算复杂度降低为O(n)。参数ρ代表信息素蒸发的速率，新增加的信息素被乘上系数ρ后，更新后的信息素浓度被控制在旧信息素量与新释放的信息素量之间，用一种隐含的又更简单的方式实现了MMAS算法中对信息素量取值范围的限制。

（3）引入信息素局部更新规则，在路径构建过程中，对每一只蚂蚁，每当其经过一条边(i, j)时，它将立刻对这条边进行信息素的更新。

在这里插入图片描述

在这里插入图片描述
信息素局部更新规则作用于某条边上会使得这条边被其他蚂蚁选中的概率减少。这种机制大大增加了算法的探索能力，后续蚂蚁倾向于探索未被使用过的边，有效地避免了算法进入停滞状态。

顺序构建和并行构建。顺序构建是指当一只蚂蚁完成一轮完整的构建并返回到初始城市之后，下一只蚂蚁才开始构建；并行构建是指所有蚂蚁同时开始构建，每次所有蚂蚁各走一步（从当前城市移动到下一个城市）。对于ACS，要注意到两种路径构建方式会造成算法行为的区别。
在ACS中通常我们选择让所有蚂蚁并行地工作。

6.5 连续正交蚁群系统

连续正交蚁群算法（Continuous Orthogonal Ant Colony, COAC）：近年来，将应用领域扩展到连续空间的蚁群算法也在发展，连续正交蚁群就是其中比较优秀的一种。COAC通过在问题空间内自适应地选择和调整一定数量的区域，并利用蚂蚁在这些区域内进行正交搜索、在区域间进行状态转移、并更新各个区域的信息素来搜索问题空间中的最优解。
COAC的基本思想是利用正交试验的方法将连续空间离散化。