2.3 基本蚁群算法及其典型改进算法

蚂蚁系统（AS）是最早的蚁群算法，也是基本蚁群算法。此后，人们提出了许多改进的蚁群算法，包括蚁群系统（ACS）[5]、基于排序的蚂蚁系统[6]、最大最小蚂蚁系统（MMAS）[7]等。它们与AS的主要区别在于状态转移规则和信息素更新规则的不同。其中，ACS和MMAS是两类应用广泛的蚁群算法。本节先介绍AS，然后介绍ACS和MMAS的工作原理。其他算法参见文献[8,9]。

为便于说明这些算法的基本原理，首先介绍旅行商问题（TSP）。TSP的图论描述如下：给定n个结点（每个结点代表一个城市）和连接结点的弧段（边）的集合E，对任意i∈N, j∈N,（i, j）∈E，用dij表示弧段的长度，即城市i和j 之间的距离，TSP问题就是在图G=（N, E）中找一条最短的Hamilton回路，即闭回路，经过每个结点一次且只一次，其长度为组成它的各弧段长度的和。在蚁群算法发展过程中，TSP常用作测试问题。

2.3.1 基本蚁群算法

在基本蚁群算法中，人工蚂蚁具有以下特征：

（1）蚂蚁在城市i根据信息素和启发信息选择下一个城市j。

（2）在从城市i到城市j 移动过程中或是在完成一次循环后，蚂蚁在边（i, j）上释放一定量的信息素τ（i, j）。

（3）为了满足问题的约束条件，在一次循环中，不允许蚂蚁选择已经访问过的城市。

下面给出基本蚁群算法的状态转移规则和信息素更新规则。

1）状态转移规则

在初始时刻，蚂蚁随机选取一个结点，然后蚂蚁从一个结点移动到另一个结点，直到经过所有的结点。设第k只蚂蚁当前所在的结点为i，则从该结点移到结点j的概率为

其中η（i, j）是弧（i, j）上的启发信息。在TSP问题中，η（i, j）一般选取为弧长的倒数。是由所有未经过的点组成的集合，α, β分别表示信息素和启发信息相对权重参数，它们控制τ（i, j）和η（i, j）在决策中所占的比重。由式（2-1）可知，那些具有较多的信息素且较短的弧段，被选择的概率较大。

2）信息素更新规则

经过n-1次选择，蚂蚁完成一个回路，也就是问题的一个可行解。当蚂蚁原路返回时，在它所经过的弧段上留下信息素，用Δ表示第k只蚂蚁在弧段（i, j）上的释放的量。它的取值与相应的可行解Tk质量有关。设Lk表示该回路的长度，显然，Lk 越小，解的质量越好，在所经过的弧段上留下的信息素Δ越大。任意弧段（i, j）上信息素的总改变量为

其中m是蚂蚁数。

根据具体算法的不同，Δ的表达形式可以不同。Dorigo[2]曾给出3种不同的模型，分别为Ant Cycle System、Ant Quantity System和Ant Density System。

在Ant Cycle System中，Δ为

其中Q为常数；Lk表示第k只蚂蚁在本次循环中所走路径的长度。

在Ant Quantity System中，Δ为

在Ant Density System中，Δ为

后两种算法与Ant Cycle System的区别在于，蚂蚁每走一步都要更新信息素的强度，而不是等到所有蚂蚁完成一个解的构造以后。在Ant Quantity System中，信息素强度的增量为Q/dij，此时增量会随着城市之间距离的减小而增大。在Ant Density System中，从城市i到城市j 的蚂蚁在路径上释放的信息素强度是一个与弧长无关的常数Q。Ant Cycle System利用全局信息更新信息素，它在求解TSP问题时性能较好。

此外，基本蚁群算法引入信息素挥发机制。设信息素的保持系数为ρ，则信息素挥发系数为1-ρ。信息素按式（2-6）调整

至此一次迭代结束，进入下一次迭代。重复进行上述过程，直到满足某个停止条件则算法停止。

研究表明，基本蚁群算法具有以下优点：

（1）具有较强的全局搜索能力。在算法中，一群蚂蚁通过相互协作来更好地适应环境，以获得更好的性能；利用蚂蚁群体而不是单只蚂蚁，使得算法找到全局最优解的概率增加；另外，使用概率规则而不是确定性规则指导搜索，使得算法有可能逃离局部最优。而传统优化算法对初值、迭代步长较敏感，一旦陷入局部最优就很难逃离。

（2）具有潜在的并行性。所有蚂蚁同时独立地在解空间中搜索，非常适合于并行实现，因此它本质上是一种高效的并行搜索算法。一方面蚂蚁的搜索行为是独立自主的，不需要集中控制；另一方面，即使一只或者几只蚂蚁做出不好的选择，整个蚁群系统仍然能够保持正常功能。这种分布式并行模式大大提高整个算法的运行效率和鲁棒性。

（3）在优化过程中不依赖于优化问题本身的数学性质，如连续性、可导性以及目标函数和约束条件的精确数学描述等。

（4）具有学习能力，在复杂的、不确定的、时变的环境中，通过自我学习不断提高蚂蚁的适应性。

但是，基本蚁群算法存在以下缺点：

（1）与遗传算法等相比，该算法一般需要较长的搜索时间。这是因为蚁群中个体的移动是随机的，虽然通过信息的交流能够向着最优路径进化，但是当问题规模较大时，很难在较短时间内从杂乱无章的路径中找出一条较好的路径，而解的构造过程也会占用大量的计算时间。这一缺点是蚁群算法本身决定的，很难有本质上的改进，但可通过采用局部搜索等方法提高算法收敛性，减少算法搜索到满意解的时间。

（2）容易出现停滞现象。停滞现象是指当算法搜索到一定程度后，所有蚂蚁不能构造新的解，以致不能对搜索空间做进一步探索的现象。蚂蚁总是倾向沿着信息素强度高的弧段移动，由信息素更新规则可见，未被选取的弧段与包含在优解中的弧段相比，信息素强度的差异越来越大，它们被选择的概率也就越来越小，从而导致算法有时只能在信息素更新中的优解附近进行搜索。这种信息素更新规则实现了正反馈机制，但是停滞现象是这种方式要避免的一个不足之处。所以在算法的求解过程中，需要折中考虑算法的探索（exploration）和开发（exploitation）能力。

（3）有些优化问题难以用构造图描述。虽然构造图在一定程度上扩展了蚁群算法的应用范围，但许多较复杂的实际问题仍然难以用构造图描述。

2.3.2 蚁群系统

蚁群系统是Dorigo和Gambardella于1997年提出的，蚁群系统与蚂蚁系统主要有以下不同之处。

1）状态转移规则

在ACS中，状态转移规则如下：一只位于结点i的蚂蚁按照式（2-7）给出的规则选取下一个将要到达的城市j，

其中，q是一个[0,1]之间的服从均匀分布的随机数，q0是一个参数（q0∈[0,1]）, S是按照式（2-1）给出的概率分布选出的一个随机变量，J（i）是可选城市集合。

式（2-7）给出的状态转移规则称为伪随机比例状态转移规则（pseudo random-proportional state transition rule）。这个状态转移规则，与式（2-1）给出的随机状态转移规则（random-proportional state transition rule）一样，都倾向于选择较短的且有较多信息素的边作为移动方向。参数q0决定了探索和开发的相对重要性：当一只位于结点i的蚂蚁按照式（2-7）给出的规则选取下一个将要到达的城市j 时，它先产生一个随机数0≤q≤1；如果q≤q0，依据式（2-7）选取最好边，否则按照式（2-1）选取一条边。

2）全局信息素更新规则

在ACS中，只有全局最优的蚂蚁才被允许释放信息素。这种策略以及伪随机比例规则的使用，使得蚂蚁具有更强的开发能力：蚂蚁的搜索主要集中到当前迭代为止时所找出的最优路径的邻域内。在每只蚂蚁都构造完一个解之后，全局信息素更新规则按照下式执行：

其中，ω是信息素挥发参数（0＜ω＜1）, Lgb是全局最优路径长度。

由式（2-8）和式（2-9）可知，只有那些属于全局最优路径的弧段上的信息素才得到增强。全局更新规则的另一个类型是用当前迭代的最优解更新信息素。在这种策略中，式（2-9）中用当前迭代的最优路径长度Lib代替Lgb，并且只有属于当前迭代的最优路径中的弧段才会得到增强。实验表明，这两种类型对蚁群系统性能影响的差别很小，全局最优的性能稍好一些。

3）局部信息素更新规则

在构造解时，蚂蚁应用式（2-10）给出的局部更新规则对它们所经过的边更新信息素：

其中，r（0＜r＜1）是一个参数。

实验表明，当Δτ（i, j）=τ0时（其中τ0为一常数），算法能在较短的时间内获得较好的解。特别地，在TSP问题中，τ0=（nLnn）-1，其中Lnn是由最近邻域启发算法求得路径的长度，n是城市的数目。

4）蚁群系统采用候选表策略

蚁群系统是一种构造式随机算法，在每一步，如果蚂蚁在选择下一个城市时考虑所有可选的城市，状态转移规则的计算量会很大。为了提高蚁群系统的搜索效率，特别是对于较大规模的问题，蚁群系统采用候选表策略。候选表是一个表，它记录从当前城市出发偏好程度较高的城市（preferred cities）。只要候选表中还有未访问过的城市，蚂蚁就会按照状态转移规则从候选表中选取一个城市。当候选表中的所有城市都被访问过时，蚂蚁才会考虑不在候选表中的城市。

2.3.3 最大最小蚂蚁系统

Stützle和Hoos在2000年提出MMAS。它与AS的差异主要体现在信息素更新规则上。

1）MMAS采用精英策略来更新信息素

具体而言，在每个蚂蚁构造完一个解之后，只增加最优解对应弧段的信息素。这个解可能是当前最优解（best-so-far solution），也可能是当前迭代的最优解（iteration-best solution）。当只使用当前最优解时，搜索可能会过快地集中到这个解的周围，从而限制了对新解的搜索，甚至可能会陷于局部最优解。而利用当前迭代的最优解来更新信息素可以减少这样的风险。这是因为当前迭代的最优解在每次迭代时都可能不同。一般地，利用当前最优解来更新信息素，可使蚁群获得较强的开发能力，而利用当前迭代的最优解来更新信息素，可使蚁群获得较强的探索能力。实验表明，采用混合策略且在迭代过程中增加使用当前最优解进行信息素更新的频率，能有效平衡探索和开发能力，从而提高算法性能。

2）信息素取值限制在区间[τmin, τmax]，其中τmin、τmax分别是信息素下界和上界

MMAS通过将超出这个范围的值强制设置为τmin或τmax，避免不同弧段的信息强度差异过大，从而达到避免停滞的目的。

3）MMAS将信息素初始化为τmax

在MMAS中，信息素的值在第一次迭代之后都被设置为τmax（1）。这一点可以通过将信息素的初始值设置为某个非常大的数值来实现。这种策略使得蚂蚁在算法的初始阶段能够具有更好的探索能力。实验表明，它能改善算法的性能。

4）MMAS还利用信息素的平滑机制提高其性能

当MMAS已经收敛或接近收敛时，这种机制将信息素作如下调整：

其中，0＜δ＜1; τ（i, j）与τ（i, j）*是信息素调整前后的信息素值。信息素平滑机制的基本思想是通过增加选择信息素值较小的解元素的概率提高搜索新解的能力。由于δ＜1，它能避免完全丢失在算法运行过程中所积累的信息。当δ=1时，它相当于信息素的重新初始化。而当δ=0时，该机制不发挥作用。平滑机制有助于改善算法的探索能力。同时，这个机制可以降低MMAS对信息素下限的敏感程度，有利于在全局范围内搜索新的解，同时避免过早收敛于局部优解。