蚁群算法概述

蚁群算法（ant colony optimization algorithm—ACO）是20世纪90年代由意大利学者Dorigo、Maniezzo、Colorini等提出的一种进化算法^{［131,132,133,134］}。他们首先将其运用于经典的优化问题——旅行商问题（traveling salesman problem, TSP），并取得了良好的效果。之后该算法被其他领域的许多学者所接受并陆续应用到其他许多问题，且在很多方面表现出相当好的性能。

蚁群算法的基本原理是模仿自然界中真实蚁群的觅食行为。自然界中蚁群能通过相互协作找到从蚁巢到食物的最短路径，并且能随着环境变化（如突然出现障碍物）而变化，很快地重新找到最短路径。仿生学家们经过大量细致的观察研究发现，蚂蚁个体之间是通过一种称之为信息素（pheromone）的化学物质进行信息的传递。蚂蚁在运动过程中，会在它们所经过的路径上留下信息素，而且同一蚁群的蚂蚁能够感知到这种物质及其强度，并以此来指导自己的运动方向。一条路径上留下的信息素浓度大小与这条路径上通过的蚂蚁数成正比，当通过的蚂蚁越多，则留下的信息素就越多，后来的蚂蚁选择这条路径的概率也将越大。整个蚁群就是通过这种信息素进行相互协作，形成正反馈，使多个路径上的蚂蚁逐渐聚集到最短的那条路径上来。

下面通过一个实例来说明蚁群算法的原理。如图3.6（a）所示，设A为蚁巢，E为食物源，CD为一障碍物，一群蚂蚁在A和E之间来回运送食物。假设蚂蚁单位时间移动的距离为1，且每经过一个单位时间各有30只蚂蚁由A到达E，或由E到达A，且每个蚂蚁可在路径上留下浓度为1的信息素。各点之间的距离，如图3.6所示（AB、EF的长度忽略不计）。为简单起见，设信息素保留时间为1。在t＝0时刻，由于路径上均无信息素，位于B和F的蚂蚁可以随机选择路径。从统计的角度可以认为它们以相同的概率选择BC、BD、FC、FD，因此各有15只蚂蚁选往C，15只选往D，如图3.6（b）所示。经过一个时间单位，路径BDF上经过的蚂蚁数为15，路径BCF上经过的蚂蚁数为30，则路径BCF上的信息素是路径BDF上信息素的两倍。因此，在t＝1时刻，分别从A、E出发的30只蚂蚁将会以1/3的概率选择前往D，2/3的概率选择前往C，即有10只蚂蚁从A和E出发前往D，有20只蚂蚁从A和E出发前往C，如图3.6（c）所示。随着时间的推移，后续的蚂蚁将会以越来越大的概率选择路径BCF，最终完全选择这条路径，从而找到了由蚁巢到食物源的最短路径。

图3.6　蚁群算法基本原理

蚁群算法正是在上述真实蚂蚁的觅食行为的激发下提出的一种进化算法。它采用了一个称之为“人工蚁群”的代理集合，其中每一只人工蚂蚁通过遗留在路径上的信息素信息进行交流，通过“群体智能”的模式，共同合作找到问题的最优解或近似最优解^［135］。蚁群算法是一种基于种群的拟生态系统算法，它的主要特点包括以下几方面：

（1）正反馈机制。经过蚂蚁越多的路径，留下的信息素就越多，后续蚂蚁选择该路径的概率也就越大，通过信息素的不断更新最终收敛于最优路径上，正反馈的特点使得该方法能够很快地发现较好的解。

（2）较强的鲁棒性。反映在算法模型的适应性上，它可以普遍地应用于各种组合优化问题的求解之中。

（3）分布式并行计算能力。算法在全局的多点同时进行解的搜索，具有本质并行性，易于并行实现，也易于和其他启发式方法的结合^［136］。

目前蚁群算法已经在若干个领域获得了成功的应用，其中最成功的应用是在组合优化问题中的应用。其中，在静态组合优化问题中的应用包括旅行商问题（TSP）^{［131-133,136］}、二次分配问题（quadratic assignment problem, QAP）^{［137,138］}、Job-Shop调度问题^{［131,134］}等。在动态组合优化问题中的应用则包括集成电路布线设计、电信路由控制、交通建模及规划、电力系统优化及故障分析等^［139］。

近几年，也有一些学者开始将蚁群算法用于项目进度安排问题，这是因为项目进度安排问题从本质上也是一类组合优化问题，它是将各工序安排进度的顺序或开始时间进行组合优化，以寻求最佳的目标函数。如Merkle等^［140］将蚁群算法用于单模式RCPSP问题中，Luo等^［141］将蚁群算法用于带一般逻辑关系约束的RCPSP问题中，以及笔者将蚁群算法用于工期—成本均衡的RCPSP问题的优化和资源均衡的RCPSP问题的优化^{［142,143,30］}中，和Shou^［90］将蚁群算法用于一次性支付模式下的支付进度安排问题中等。