下载掌阅APP，畅读海量书库
立即打开
1.算法基本思想
蚁群优化（Ant Colony Optimization，ACO）算法是由Dorigo等人于1991年提出的一种随机搜索算法，模拟了自然界蚂蚁的真实觅食过程。不同于之前介绍的各种进化计算方法，蚁群优化算法是一种构建式的元启发式算法，能更灵活地处理约束优化中的问题约束，使用合适的构建图，一步一步地构建有效解。
基于对自然界蚁群觅食过程的抽象建模，我们得到蚁群算法与自然界蚁群觅食过程一一对应的基本要素。
●蚁群：搜索空间内的一组有效解，表现为种群规模，即蚂蚁的数量 M 。
●蚂蚁：在搜索空间中构建有效解的基本单位。
●觅食空间：问题的搜索空间，表现为问题的规模，即解的维数 N 。
●蚁巢到食物的一条路径：一个有效解。
●信息素（pheromone）：信息素浓度，用于记忆路径信息和蚂蚁间的间接通信。
一只只视觉感知系统没有发育完全的蚂蚁构成的蚁群，在一个初始时刻全局路径信息未知的搜索空间中，要找到从蚁巢到食物源的最优路径，它们需要一种机制来交互、记忆路径。仿生学家的研究表明，这种机制依赖于一种由蚂蚁自身释放的化学物质，即信息素（pheromone），来实现蚁群的间接通信。蚂蚁在寻找食物的过程中能够感知路径上的信息素浓度，并倾向于向信息素浓度高的方向前进。在初始时，由于各路径上均没有分布信息素，蚂蚁纯随机选择路径，由于在较短的路径上，蚂蚁的往返时间比较短，单位时间内，通过该路径的蚂蚁多，所以信息素的积累速度比长路径快，因此，后续蚂蚁在路口上就能通过感知先前蚂蚁留下的信息，倾向于选择更短的路径前行。这种正反馈机制使得越来越多的蚂蚁在最优路径上行进，由于其他路径上的信息素会随着时间蒸发，最终所有的蚂蚁都在最优路径上行进。此外，蚁群这种自组织工作机制有较强的适应环境动态变化的能力。例如，当最优路径上突然出现障碍物时，蚁群也能绕行并很快重新探索出一条新的最优路径。
蚁群得到的当前最短的路径可能只是局部最优路径，而不是全局最优路径，因此蚁群不仅要有开发利用信息素信息的能力，使所有蚂蚁收敛到最优路径上，还要有充分的探索全局最优路径的能力，避免蚁群陷入局部最优路径上，所以蚁群不管在路径搜索的哪个阶段，在每个路口选路时都保留一定的随机性，而不是直接选择信息素积累最多的下一路段。
蚁群优化算法在发展中出现了不同变体。蚂蚁系统（Ant System，AS）是蚁群算法的雏形，它的出现为各种改进算法的提出带来了灵感。之后诞生了许多改进的蚁群优化算法。较为经典的蚁群优化算法的改进版本包括精华蚂蚁系统（Elitist Ant System，EAS）、基于排列的蚂蚁系统（Rank-Based Ant System，AS rank ）、最大最小蚂蚁系统（MAX-MIN AS，MMAS）等。它们大多在AS上直接进行改进，通过修正信息素的更新方式和增添信息素维护过程中的额外细节，使蚁群优化算法的性能得到提高。而到了1997年，ACO创始人Dorigo等人提出蚁群系统（Ant Colony System，ACS），实验结果表明ACS算法性能明显优于AS，因此ACS是蚁群优化算法发展史上的又一里程碑。之后蚁群算法继续发展，新拓展算法不断出现，例如采用下限技术的ANTS算法、超立方体AS算法等。传统的ACO算法是解决离散空间的优化问题的，到了21世纪，各种连续蚁群算法的出现，进一步拓展了蚁群算法的应用领域。本节选取AS和ACS作为代表，介绍蚁群优化算法的流程。
2.算法流程
旅行商问题（Traveling Salesman Problem，TSP）在蚁群优化算法的研究中起到重要作用，下面将依托TSP的求解介绍蚁群优化算法的流程。
直观上，TSP指的是在给定的城市集合中，一位商人从起点城市出发，希望能找到一条最短路径，使得每个城市都被访问且仅被访问一次，最后返回起点城市。
形式上，TSP可以用一个带权完全图
G
=（
N
，
A
）来描述，其中
N
是城市节点集合，
A
是所有边的集合，每条边
都被分配一个权值（即长度）
d
ij
，代表城市
i
和
j
之间的距离，其中
。TSP的目标就是寻找图中一条具有最小成本值的汉密尔顿回路，汉密尔顿回路指的是一条访问图
G
（
G
含有
个节点）中每个节点一次且仅一次的闭合路径，这样，TSP的一个最优解对应于节点标号为{1，2，…，
n
}的一个排列
π
，使得长度
f
（
π
）最小，
f
（
π
）定义为
蚁群优化算法的初级版本AS求解TSP的流程图和伪代码如图1-17所示。在AS的基础上，我们还将介绍蚁群优化算法的重要改进版本ACS。相比AS而言，ACS主要有以下3大改进，提高了算法的探索和开发能力。
图1-17 AS求解TSP的流程图和伪代码
●在构建解时，不像AS使用随机比例（random proportional）规则，而使用一种伪随机比例（pseudorandom proportional）规则，建立开发当前路径与探索新路径之间的平衡。
●新增了信息素局部更新的步骤，蚂蚁每经过空间内的某条边，都会除去该边上一定量的信息素，以增加后续蚂蚁探索其他路径的可能性。
●信息素全局更新仅在历史最优路径上进行，以充分开发历史最优路径，而不像AS在每次迭代中都对每条路径上的信息素进行蒸发和释放。
AS主要包括初始化信息素矩阵、解的构建与评估、信息素全局更新3大步骤，即下述步骤1、2、4。而ACS则在解的构建与评估过程中还包括信息素局部更新这一步骤，即下述步骤3。
AS和ACS的详细步骤介绍如下。
1）初始化信息素矩阵 ：对算法进行初始化时，对于一个 n 维问题空间中每条边上的信息素都初始化为 τ 0 ，若 τ 0 过小，则算法容易早熟，即蚂蚁很快集中到一条局部最优的路径上，若 τ 0 过大，则信息素对算法的指导作用有限，算法收敛速度过慢。对于蚁群优化算法的第一种变体——蚂蚁系统（Ant System，AS），我们使用 τ 0 = M/C nn ，其中 M 是种群中的蚂蚁数量， C nn 是使用贪心算法构建的路径的长度。
2）解的构建与评估 ：每只蚂蚁随机选择一个城市作为其出发城市，并维护一个路径记忆序列，用于存放该蚂蚁依次经过的城市。蚂蚁在构建路径的每一步中，AS算法按照一个随机比例规则选择下一个要到达的城市，而ACS算法则按照伪随机比例规则选择下一个城市。
●随机比例规则：每只蚂蚁 k 在节点 i 上，按照伪随机比例选择规则，依次在待访问节点集合 J k （ i ）中选择下一个节点 j ，逐步构建生成解。随机比例 p k （ i ， j ）由信息素 τ ij 和启发式信息 η ij 的加权乘积求得，即
其中， J k （ i ）表示从城市 i 可以直接到达又不在蚂蚁访问过的城市序列中的城市集合， η ij 是启发式信息，表示问题中引导下一步构建的信息，例如在TSP中，启发式信息可以选用 η ij =1 /d ij ，即城市 i 、 j 间的距离 d ij 越小，启发式 η ij 就越大，蚂蚁就更倾向于选择路径 j 作为下一个城市。 α 和 β 则为预先设置的参数，用于控制启发式信息和信息素浓度的权重关系，若 α =0，则蚁群算法退化为仅使用启发式信息的贪心算法，若 β =0，则蚂蚁仅根据信息素浓度确定路径，算法将快速收敛，但缺乏启发式信息的指导会使构建的路径与实际目标有较大差异，算法性能较差。文献[46]中的实验表明，在AS中设置 α =1、 β =2～5比较合适。
●伪随机比例规则：在上述随机比例规则的基础上，伪随机比例规则在构建解的每一步，以 q 0 的概率，选择最大的伪随机比例 p k （ i ， j ）对应的节点 j 作为下一个节点，以1 -q 0 的概率，按照伪随机选择比例 p k （ i ， j ）进行轮盘赌选择，确定下一个节点 j ，即
3）信息素局部更新 ：传统的AS算法只有全局信息素更新。ACS算法中引入了一种信息素更新方式，蚂蚁每经过一条路径，就减少那条路径上的信息素，避免同一条路径被重复选择，从而提高算法的探索能力。信息素局部更新如式（1-10）所示。
其中， ξ 是信息素局部挥发速率，满足0＜ ξ ＜1， τ 0 是信息素的初始值。通过文献[46]中的实验发现， ξ 为0.1， τ 0 取值为1 / （ nC nn ）时，算法对大多数实例有着非常好的性能，其中 n 为城市个数， C nn 是由贪婪算法构造的路径的长度。由于 τ 0 =1 / （ nC nn ）≤ τ （ i ， j ），局部更新计算出来后更新的信息素相比更新前减少了，也就是说，信息素局部更新规则作用于某条边上会使得这条边被其他蚂蚁选中的概率减小，这种机制增加了算法的探索能力，使蚂蚁更倾向于探索未被使用过的边，有效避免算法进入停滞状态。
4）信息素全局更新 ：当所有蚂蚁的路径被构建完成，即蚁群算法一次迭代，需要对路径上的信息素进行蒸发和释放。
在AS算法中，按照以下公式，对每条路径上的信息素都进行蒸发和释放。
其中，参数 ρ 代表信息素蒸发的速率，规定0＜ ρ ≤1， R k 是第 k 只蚂蚁构建的路径的边集合，Δ τ k （ i ， j ）是第 k 只蚂蚁在它经过的边上释放的信息素， C k 是蚂蚁构建的路径长度。
在ACS算法中，按照以下公式，仅对至今最优路径上的信息素进行蒸发和释放，以提高至今最优路径被选择的概率，提高算法的收敛能力。
其中，Δ τ b （ i ， j ）=1 /C b ， C b 为至今最优路径长度。值得注意的是，在ACS的全局更新中，只有至今最优路径 T b 上的边才有信息素蒸发和释放。
5）结束条件判断 ：当达到预先规定的最大进化代数，或最终结果达到了规定的误差要求时，算法结束；否则返回步骤2。