ACO与变种(参考资料)

ACO算法

基本原理

​ 蚁群算法（Ant Colony Optimization，ACO）是一种基于种群寻优的启发式搜索算法，有意大利学者M.Dorigo等人[6]于1991年首先提出。该算法受到自然界真实蚁群集体在觅食过程中行为的启发，利用真实蚁群通过个体间的信息传递、搜索从蚁穴到食物间的最短路径等集体寻优特征，来解决一些离散系统优化中的困难问题。

​ 经过观察发现，蚂蚁在寻找食物的过程中，会在它所经过的路径上留下一种被称为信息素的化学物质，信息素能够沉积在路径上，并且随着时间逐步挥发。在蚂蚁的觅食过程中，同一蚁群中的其他蚂蚁能够感知到这种物质的存在及其强度，后续的蚂蚁会根据信息素浓度的高低来选择自己的行动方向，蚂蚁总会倾向于向信息素浓度高的方向行进，而蚂蚁在行进过程中留下的信息素又会对原有的信息素浓度予以加强，因此，经过蚂蚁越多的路径上的信息素浓度会越强，而后续的蚂蚁选择该路径的可能性就越大。通常在单位时间内，越短的路径会被越多的蚂蚁所访问，该路径上的信息素强度也越来越强，因此，后续的蚂蚁选择该短路径的概率也就越大。经过一段时间的搜索后，所有的蚂蚁都将选择这条最短的路径，也就是说，当蚁巢与食物之间存在多条路径时，整个蚁群能够通过搜索蚂蚁个体留下的信息素痕迹，寻找到蚁巢和食物之间的最短路径。

​ 蚁群算法中，蚂蚁个体作为每一个优化问题的可行解。首先随机生成初始种群，包括确定解的个数、信息素挥发系数、构造解的结构等。然后构造蚁群算法所特有的信息素矩阵每只妈蚁执行蚂蚊移动算子后，对整个群体的蚂蚁做一评价，记录最优的蚂蚁。之后算法根据信息素更新算子更新信息素矩阵，至此种群的一次选代过程完成。整个蚂蚁群体执行一定次数的选代后退出循环、输出最优解。

---

术语介绍

（1）蚂蚁个体。每只蚂蚁称为一个单独的个体，在算法中作为一个问题的解。

（2）蚂蚁群体。一定数量的蚂蚁个体组合在一起构成一个群体，蚂蚁是群体的基本单位。

（3）群体规模。群体中个体数目的总和称为群体规模，又叫种群大小。

（4）信息素。信息素是蚂蚁在所经过的路径上所释放的一种化学物质，后来的蚂蚁根据路径上的信息素的强度选择路径。

（5）蚂蚁移动算子。蚂蚁在寻优过程中通过蚂蚁移动算子来改善基因位，向最优解靠近。

（6）信息素更新算子。蚂蚁算法中，种群在每次迭代过程中，通过信息素更新算子来改变信息素矩阵，为蚂蚁移动算子提供基础。

---

算法细节

算法流程图

算法描述

​ ①初始化蚁群。初始化蚁群参数，包括设置蚂蚁数量、蚂蚁解的结构、信息素挥发系数等。

​ ②构造信息素矩阵。

​ ③每只蚂蚁执行蚂蚁移动算子。蚂蚁依据前面蚂蚁所留下的信息素，修改自己的解结构，完成一次循环。

​ ④依据适应度值对蚂蚁进行排序，对前n个解执行局部搜索算子。

​ ⑤评价蚁群。根据目标函数对每只蚂蚁的适应度值做一评价，并记录最优解。

​ ⑥根据信息素更新算子更新信息素矩阵。

​ ⑦若满足终止条件，即最短路径，输出最优解；否则，信息素挥发，算法继续进行步骤③。

算法特点

​ （1）自组织。组织力或组织指令是来自于系统的内部。 在抽象意义上讲，自组织就是在没有外界作用下使得系统熵减小的过程(即是系统从无序到有序的变化过程)。

​ （2）并行搜索。每只蚂蚁搜索的过程彼此独立，仅通过信息激素进行通信。 在问题空间的多点同时开始进行独立的解搜索，不仅增加了算法的可靠性，也使得算法具有较强的全局搜索能力。

​ （3）正反馈。蚂蚁能够最终找到最短路径，直接依赖于最短路径上信息激素的堆积，而信息激素的堆积却是一个正反馈的过程。

ACO在TSP问题中应用示例

​ 第一个ACO算法——蚂蚁系统(Ant System,$AS$)[6],[7],[8]是以$NP$难的TSP问题作为应用实例提出的。

问题描述

​ 已知$n$个城市的集合    C n = { c 1 , c 2 , . . . , c n }    \;C_n=\{c_1,c_2,...,c_n\}\; Cn​={c1​,c2​,...,cn​},任意两个城市之间均有路径连接，$d_{ij}(i,j=1,2,,...n)$表示城市$i$与$j$之间的距离，它是已知的（或者城市的坐标集合为已知。$d_{ij}$即为城市之间的欧几里得距离）。如上文所述，TSP的目的是找到从某个城市$c_i$出发，访问所有城市且只访问一次，最后回到$c_i$的最短封闭曲线。

基本流程

1.路径构建

​ 每只蚂蚁都随机选择一个城市作为其出发城市，并维护一个路径记忆向量，用来存放该蚂蚁依次经过的城市。蚂蚁在构建路径的每一步中，按照一个随机比例规则选择下一个要到达的城市。

​ 随机比例规则：对于每只蚂蚁$k$,路径记忆向量$R^k$按照访问顺序记录了所有$k$已经经过的城市序号。设蚂蚁$k$当前所在城市为$i$,则其选择城市$j$作为下一个访问对象的概率为：
$$p_k(i,j)=\{\begin{array}{cc}\frac{{[\tau (i,j)]}^{\alpha }{[\eta (i,j)]}^{\beta }}{{\sum }_{u\in J_{k(i)}}{[\tau (i,u)]}^{\alpha }{[\eta (i,u)]}^{\beta }},& j\in J_k(i)\\ 0,& 其他\end{array}$$
其中，$J_k(i)$表示从城市$i$可以直接到达的且又不在蚂蚁访问过的城市序列$R^k$中的城市集合。$\eta (i,j)$是一个启发式信息，通常由$\eta (i,j)=1/d_{ij}$直接计算。$\tau (i,j)$表示边$(i,j)$上的信息素量。由上述公式可知，长度越短、信息素浓度越大的路径被蚂蚁选择的概率越大。$\alpha$和$\beta$是两个预先设置的参数，用来控制启发式信息与信息素浓度作用的权重关系。当$\alpha =0$时，算法演变成传统的随机贪婪算法，最近邻城市被选中的概率最大。当$\beta =0$时，蚂蚁完全只根据信息素浓度确定路径，算法将快速收敛，这样构建出的最优路径往往与实际目标有着较大的差异，算法的性能比较糟糕。实验表明，在AS中设置$\alpha =1,\beta =2\sim 5$比较合适。

2.信息素更新

​ 在算法初始化时，问题空间中所有的边上的信息素都被初始化为${\tau }_0$。如果${\tau }_0$太小，算法容易早熟，即蚂蚁很快就集中在一条局部最优的路径上。反之，如果${\tau }_0$太大，信息素对搜索方向的指导作用就太低，也会影响算法性能。对$AS$来说，我们使用${\tau }_0=m/C^m$，$m$是蚂蚁的个数，$C^m$是由贪婪算法构造的路径的长度。

​ 当所有的蚂蚁构建完路径后，算法将会对所有的路径进行全局信息素的更新。注意，这里描述的是AS的ant-cycle版本，更新是在全部蚂蚁均完成了路径的构造后才进行的，信息素的浓度变化与蚂蚁在这一轮中构建的路径长度有关。信息素更新有两个步骤：首先，每一轮过后，问题空间中的所有信息素都会蒸发，我们为所有边的信息素乘上一个小于$1$的常数。信息素的蒸发是自然界本身固有的特征，在算法中能够避免信息素的无限积累，使得算法可以快速丢弃之前构建过的比较差的路径。随后所有的蚂蚁根据自己构建的路径长度在它们本轮经过的边上释放信息素。蚂蚁构建的路径越短，释放的信息素就越多；一条边上被蚂蚁爬过的次数越多，它所获得的信息素也越多。$AS$中城市$i$与城市$j$的相连边上的信息素量$\tau (i,j)$按如下公式进行更新：
$$\tau (i,j)=(1-\rho )\cdot \tau (i,j)+\sum _{k=1}^m△{\tau }_k(i,j)$$

$$△{\tau }_k(i,j)=\{\begin{array}{cc}(C^k{)}^{-1},& (i.j)\in R^k\\ 0,& 其他\end{array}$$

这里，$m$是蚂蚁个数；$\rho$是信息素的蒸发率，规定$0<\rho \le 1$，在$AS$中通常设置为$\rho =0.5$。$△{\tau }_k(i,j)$是第$k$只蚂蚁在它经过的边上释放的信息素量，它等于蚂蚁$k$本轮构建路径长度的倒数。$C_k$表示路径长度，它是$R^k$中所有边的长度和。

相关变种

精华蚂蚁系统(Elitist Ant System,$EAS$)

改进点

​ 精华蚁群系统[8]是对基础$AS$的第一次改进，它在原$AS$信息素更新原则的基础上增加了一个对至今最优路径的强化手段。在每轮信息素更新完毕后，搜索到至今最优路径（我们用$T_b$表示）的那只蚂蚁将会为这条路径添加额外的信息素。$EAS$中城市$i$与城市$j$的相连边上的信息素量$\tau (i,j)$按如下公式进行更新：
$$\tau (i,j)=(1-\rho )\cdot \tau (i,j)+\sum _{k=1}^m△{\tau }_k(i,j)+e△{\tau }_b(i,j)$$

$$△{\tau }_k(i,j)=\{\begin{array}{cc}(C^k{)}^{-1},& (i.j)\in R^k\\ 0,& 其他\end{array}$$

$$△{\tau }_b(i,j)=\{\begin{array}{cc}(C_b{)}^{-1},& (i.j)在路径T_b上\\ 0,& 其他\end{array}$$

在$EAS$中，新增了$△{\tau }_b(i,j)$，并定义参数$e$作为$△{\tau }_b(i,j)$的权值。$C_b$是算法开始至今最优路径的长度。可见，$EAS$在每轮迭代中为属于$T_b$的边增加了额外的$e/C_b$的信息素量。

---

基于排列的蚂蚁系统(rank-based Ant System,$A{S}_{rank}$)

改进点

​ 基于排列的蚂蚁系统[9]在$AS$的基础上给蚂蚁要释放的信息素大小$△{\tau }_k(i,j)$加上一个权值，进一步加大各边信息素量的差异，以指导搜索。在每一轮蚂蚁构建完路径后，它们将按照所得路径的长短进行排名，只有生成了至今最优路径的蚂蚁和排名在前$(\omega -1)$的蚂蚁才被允许释放信息素，蚂蚁在$(i,j)$上释放的信息素$△{\tau }_k(i,j)$的权值由蚂蚁的排名决定。$A{S}_{rank}$中的信息素更新规则如下：
$$\tau (i,j)=(1-\rho )\cdot \tau (i,j)+\sum _{k=1}^{\omega -1}(\omega -k)△{\tau }_k(i,j)+\omega △{\tau }_b(i,j)$$

$$△{\tau }_k(i,j)=\{\begin{array}{cc}(C^k{)}^{-1},& (i.j)\in R^k\\ 0,& 其他\end{array}$$

$$△{\tau }_b(i,j)=\{\begin{array}{cc}(C_b{)}^{-1},& (i.j)在路径T_b上\\ 0,& 其他\end{array}$$

​ 构建至今最优路径$T_b$的蚂蚁（该路径不一定出现在当前迭代的路径中，各种蚁群算法均假设蚂蚁有记忆功能，至今最优的路径总能被记住）产生的信息素的权值大小为$\omega$，它将在$T_b$的各边上增加$\omega /C_b$的信息素量，也就是说，路径$T_b$将获得最多的信息素量。其余的，在本次迭代中排名第$k(k=1,2,...,\omega -1)$的蚂蚁将释放$(\omega -k)/C_k$的信息素。排名越前的蚂蚁释放的信息素量越大，权值$(\omega -k)$对不同路径的信息素浓度差异起到了一个放大的作用，$A{S}_{rank}$能更有力度地指导蚂蚁搜索。一般设置$\omega =6$。

---

最大最小蚂蚁系统(MAX-MIN Ant System,$MMAS$)

改进点

最大最小蚂蚁系统（MAX-MIN Ant System,$MMAS$)[10]在基本$AS$算法的基础上进行了下列四项改进：

​ （1）只允许迭代最优蚂蚁（在本次迭代构建出最短路径的蚂蚁），或者至今最优蚂蚁释放信息素；

​ （2）信息素量大小的取值范围被限制在一个区间内；

​ （3）信息素初始值为信息素取值区间的上限，并伴随一个较小的信息素蒸发速率；

​ （4）每当系统进入停滞状态，问题空间内所有边上的信息素量都会被重新初始化。

下面我们介绍这四项改进带来的优势：

• 改进(1)借鉴于精华蚂蚁系统，但又有细微的不同。在$EAS$中，只允许至今最优的蚂蚁释放信息素，而在$MMAS$中，释放信息素的不仅有可能是至今最优蚂蚁，还有可能是迭代最优蚂蚁。实际上，迭代最优更新规则和至今最优更新规则在$MMAS$中会被交替使用。这两种规则使用的相对频率将会影响算法的搜索效果。如果只使用至今最优更新规则进行信息素的更新，搜索的导向性很强，算法会很快收敛到$T_b$附近；反之，如果只使用迭代更新最优规则，则算法的探索能力会得到增强，但收敛速度会下降。需要指出的是，计算智能领域的各个算法大多是不确定搜索，我们不能完全通过理论的分析就判断一种方法好还是不好，无论是对遗传算法、蚁群优化算法还是粒子群算法等的研究与改进，往往都是一个“理论猜想$\to$实验探索$\to$理论分析总结”的过程。
• 在$MMAS$中，为了避免某些边上的信息素浓度增长过快，算法出现早熟现象，即所有的蚂蚁都搜索一条较优而不是最优的路径，提出了改进(2)。信息素量的大小被限定在一个取值范围$[{\tau }_{min},{\tau }_{max}]$内。我们知道，蚂蚁是依据启发式信息和信息素浓度选择下一城市节点的，其中的启发式信息为蚂蚁当前所在城市$i$到下一可能城市$j$的距离的$d_{ij}$的倒数，由于各个$d_{ij}$的大小是事先给定的，取值范围已经确定，所以当信息素浓度也被限制在一个范围内以后，位于城市$i$的蚂蚁$k$选择城市$j$作为下一城市的概率$p_k(i,j)$也将被限制在一个区间内。我们假设这个区间为$[p_{min},p_{max}]$，关于$p_{min}$和$p_{max}$的值有兴趣的读者可以自行求解，我们在这里仅仅确定有$0<p_{min}\le p_k(i,j)\le p_{max}<1$，当且仅当蚂蚁只剩下一个可以选择的城市时才会有$p_{min}=p_{max}=1$。实际上，我们无需计算$p_{min}$和$p_{max}$的值的大小，只要知道$0<p_{min}\le p_k(i,j)\le p_{max}<1$就可以确定算法已经有效避免了陷入停滞状态的可能性。
• 由改进(3)我们知道，算发在初始化阶段，问题空间内所有边上的信息素均被初始化为${\tau }_{max}$的估计值，且信息素蒸发速率非常小(在$MMAS$中，一般将$\rho$置为$0.02$)，这样一来，不同边上的信息素浓度差异只会缓慢地增加，因此在算法的初始化阶段，$MMAS$有着较基本$AS$、$EAS$和$A{S}_{rank}$更强的探索能力。增强算法在初始阶段的探索能力有助于蚂蚁“视野开阔地”进行全局范围内的搜索，随后再逐渐缩小搜索范围，在后定格在一条全局最优路径上。
• 之前的蚁群算法，无论是$AS$、$EAS$还是$A{S}_{rank}$，均属于“一次性探索”，即随着算法的执行，某些边的信息素量变得越来越小，某些路径被选择的概率也会越来越小，系统的探索范围不断减小直至陷入停滞状态。在$MMAS$中，当算法接近或是进入停滞状态时，问题空间内所有边上的信息素浓度都将被重新初始化，从而有效地利用系统进入停滞状态后的迭代周期继续进行搜索，使算法具有更强的全局寻优能力。我们通常功过对各条边上信息素量大小的统计或观察算法在指定次数的迭代内至今最优路径有无被更新来判断算法是否停滞。

---

蚁群系统(Ant Colony System,$ACS$)

改进点

$ACS$[11]与蚂蚁系统的不同主要体现在三个方面：

1. 使用一种伪随机比例规则选择下一城市节点，建立开发当前路径与探索新路径之间的平衡
2. 信息素全局更新规则只在属于至今最优路径的边上进行蒸发和释放信息素
3. 新增信息素局部更新规则，蚂蚁每次经过空间内的某条边，它都会去除该边上一定量的信息素，以增加后续蚂蚁探索其余路径的可能性。

（1）伪随机比例规则

​ 对于每只蚂蚁$k$,路径记忆向量$R^k$按照访问顺序记录了所有$k$已经经过的城市序号。设蚂蚁$k$当前所在城市为$i$,则其选择城市$j$作为下一个访问对象的公式为：
j = { a r g    m a x j ∈ J k ( i ) { [ τ ( i , j ) ] , [ η ( i , j ) ] β } , q ≤ q 0 S , 其 他 \large j=\left\{\begin{array}{cc}{arg\;max_{j\in J_{k(i)}}\{\lbrack \tau(i,j) \rbrack,\lbrack \eta(i,j) \rbrack^\beta\},}&{q\leq q_0}\\S,&{其他}\end{array}\right. j={argmaxj∈Jk(i)​​{[τ(i,j)],[η(i,j)]β},S,​q≤q0​其他​
其中，$J_k(I)$表示从城市$i$可以直接到达的且又不在蚂蚁访问过的城市序列$R^k$中的城市集合。$\eta (i,j)$表示边$(i,j)$上的信息素量。$\beta$是描述信息素浓度和路径长度信息相对重要性的控制参数。$q_0$是一个$[0,1]$区间内的参数，当产生的随机数$q\le q_0$时，蚂蚁直接选择使启发式信息与信息素量的$\beta$指数乘积最大的下一城市节点，我们通常称之为开发；反之，当产生的随机数$q>q_0$时，$ACS$将和各种$AS$算法一样采用轮盘赌选择策略，此时选择下一城市$j$的概率公式如下：
$$p_k(i,j)=\{\begin{array}{cc}\frac{[\tau (i,j)]{[\eta (i,j)]}^{\beta }}{{\sum }_{u\in J_{k(i)}}[\tau (i,u)]{[\eta (i,u)]}^{\beta }},& j\in J_k(i)\\ 0,& 其他\end{array}$$
​ $q_0$是$ACS$引入的一个很重要的控制参数，在$ACS$的状态转移规则中，蚂蚁选择当前最优移动方向的概率为$q_0$，同时，蚂蚁以$(1-q_0)$的概率有偏向地搜索各条边。通过调整$q_0$，我们能有效调节“开发”与“探索”之间的平衡，以决定算法是集中开发最优路径附近的区域，还是探索其他的区域。

（2）信息素全局更新规则

​ 在$ACS$的信息素全局更新规则中，只有至今最优蚂蚁（构建出了从算法开始到当前迭代中最短路径的蚂蚁）被允许释放信息素，这个策略与伪随机比例状态转移规则一起作用，大大增强了算法搜索的导向性。在每轮的迭代中，所有蚂蚁均构建完路径后，信息素全局更新规则才被使用，由下面的公式给出：
$$\tau (i,j)=(1-\rho )\cdot \tau (i,j)+\rho \cdot △{\tau }_b(i,j),\forall (i,j)\in T_b$$
其中$△{\tau }_b(i,j)=1/C_b$。要强调的是，不论是信息素的蒸发还是释放，都只在属于至今最优路径的边上进行，这里与$AS$有很大的区别。因为$AS$算法将信息素的更新应用到了系统的所有边上，信息素更新的计算复杂度为$O(n^2)$，而$ACS$算法的信息素更新计算复杂度降低为$O(n)$。参数$\rho$代表信息素蒸发的速率，新增加的信息素$△{\tau }_b(i,j)$被乘上系数$\rho$后，更新后的信息素浓度被控制在旧信息素量与新释放的信息素量之间，用一种隐含的又更简单的方式实现了$MMAS$算法中对信息素量取值范围的限制。

（3）信息素局部更新规则

​ $ACS$在$AS$的基础上进行的另一项重大改进是信息素局部更新规则的引入。在路径构建过程中，对每一只蚂蚁，每当其经过一条边$(i,j)$时，它将立刻对这条边进行信息素的更新，更新所使用的公式如下：
$$\tau (i,j)=(1-\xi )\cdot \tau (i,j)+\xi \cdot {\tau }_0$$
其中，$\xi$是信息素局部挥发速率，满足$0<\xi <1$。${\tau }_0$是信息素的初始值。通过实验发现，$\xi$为$0.1$，${\tau }_0$取值为$1/(n{C}^m)$时，算法对大多数实例有着非常好的性能。其中$n$为城市个数，$C^m$是由贪婪算法构造的路径长度。

相关代码

​ 读者可根据相关描述自行编写ACS对应代码，也可网上可自行搜索。这里给出采用C++编写、测试集为TSPLIB95的$ACS$相关代码（相关链接）。此外，与演化计算相关的Python库中，这里推荐DEAP库（相关链接），该库中包含了很多我们常见的算法框架和测试实例，方便后续的科研学习。

---

其它改进版本

• 近似非确定性树搜索

• 多态蚁群算法

• 带聚类处理的蚁群算法

• 连续正交蚁群算法

---

蚁群优化算法相关应用

• 车间作业调度问题
• 车辆路径问题
• 其他应用
  • 分配问题
    • 二次分配问题
    • 广义分配问题
    • 概率分配问题
    • 冗余分配问题
  • 网络路由
    • 有向连接网络路由
    • 无连接网络路由
    • 光纤网络路由
  • 子集问题
    • 集合覆盖问题
    • 集合分离问题
    • 带权约束的图树分割
    • 边带权$l$-基数问题
    • 多重背包问题
    • 最大独立集问题
  • 最短公共超序列问题
  • 二维格模型蛋白质折叠问题
  • 数据挖掘
  • 图像处理
  • 系统辩识