-1-
蚁群优化综述
徐俊杰，忻展红
北京邮电大学经济管理学院( 100876)
摘要：蚁群优化（ACO）利用多个具有局部交互能力的简单代理在许多优化问题上取得了
不俗的表现。系统介绍了这种通用随机优化算法的演进历程。描述了蚂蚁系统（AS）对旅
行推销员问题的应用方法。最后总结了若干改进算法及蚁群优化的应用成果。
关键词：优化，蚁群优化，综述，蚂蚁算法，智能仿生算法，启发式算法
1.引言
蚁群优化（ACO）属于智能仿生算法——蚂蚁算法（AA）的范畴，后者是从蚂蚁觅
食时的路径选择机制中得到启发的：个体蚂蚁的能力有限，但是多个蚂蚁组成的群体却能
相互配合，在食物源和巢穴之间确定最小的路径。有关研究发现，蚂蚁之间是凭借信息素
轨迹（pheromone trails）进行信息交流并据以决定搜索方向的。当蚂蚁移动时，它会在经
过的路线上留下这种信息素，从而引导其他蚂蚁以更大的概率去选择相同的路线。当某条
路径上经过的蚂蚁越来越多时，其所积累的信息素就会越来越多（同时也有一定的挥发），
那么它被其他蚂蚁选择的机会就越大。
上述这种群体之间相互配合的机制被称为自催化行为[1-3]（autocatalytic behavior），该
过程具有正反馈的特性[4]（positive feedback），是一种增强型的学习系统。
2.研究历程
最先提出的蚂蚁算法被称为 AS[1-5]（Ant System），它是 Dorigo、Colorni、Maniezzo
在意大利的米兰理工学院合作研究组合优化问题计算机智能解决方法时的研究成果。
1995 年 Gambardella 和 Dorigo 提出了 Ant-Q 算法[6-7]。该算法建立了 AS 与 Q-learning[8]
的联系。模拟表明 Ant-Q 是一个非常有效的算法。
此后，Dorigo 和 Gambardella 提出了 ACS [9-10]（Ant Colony System）；Stützle 和 Hoos
提出了 MMAS [11] （MAX-MIN Ant System）。这两种扩展的蚂蚁算法都被用于解决对称旅
行推销员问题（TSP）以及非对称型的旅行推销员问题（ATSP），并取得了比较满意的结
果。
1999 年，Dorigo、Di Caro 和 Gambardella 把先前各种蚂蚁算法归结为 ACO 元启发式
-2-
算法 [12-13]（Ant Colony Optimization meta-heuristic）的概念，把此前各种基于 AS 演化而得
的算法归结到一个统一的框架中，并提供了抽象而规范的算法描述。作为一种新型的启发
式算法，ACO 元启发算法近年来受到了广泛关注。本文拟系统地介绍 ACO 元启发算法及
其研究现状，为描述简洁，下文将 ACO 元启发算法简称为 ACO 算法。
3. ACO 算法简介
首先定义若干描述变量：设 C为组件（components）的集合；L是组件元素间的连接
（或称为转移）的有限集合；J 为 L 中元素之间的连接成本函数；Ω是 C、L 之间的约束
集合；记 s 为组件 C中元素的某一排序（状态），S为所有这种可能排序的集合；设ψ是被
研究问题的一个解，那么它是 S的一个元素并且满足所有的约束；设 Jψ为解ψ的成本。
在搜索过程中，蚂蚁所收集的信息被存储在连接 lij（lij∈L）的信息素轨迹τij 中，其
中 )0(ijτ 被设置为一个很小的正值；另外每条弧还具有能见度（visibility）ηij。
ACO 算法就是在上述图表述下利用蚁群之间的协作来求解优化问题。若假设图 G=（C，
L）是从某离散优化问题中抽象而得，则该优化问题的解ψ就是在约束Ω.限制下的最小成
本排序。比如 TSP 问题中，C 是城市集合，L 是弧集合，J 为城市节点的距离矩阵，ηij
为 i、j 节点间欧式距离的倒数，解ψ就是一条哈密尔顿回路。
在 ACO 算法中主要包含有三个重要的过程：活动（activity）、轨迹挥发（evaporation）
与外部控制（daemon actions）。活动包括蚂蚁的创建、按照概率决策规则选择节点、轨迹
更新直至蚂蚁死亡并释放资源；轨迹挥发使得蚂蚁的解不会很快收敛，从而可以充分的搜
索更好的解；而外部控制措施则是一个可选的过程，它可以完成算法中单个蚂蚁无法完成
的工作，比如激活一个局部优化过程、执行轨迹的全局更新等。
1 Procedure ACO_meta-heuristic()
2 While (not terminate1)
3 Schedule_activities
4 ants_ activity();
5 pheromone_evaporation();
6 daemon_actions(); {optional}
7 End schedule_activities
1 一般通过限制循环次数(NC)或者环游长度达到某一预期值来结束算法的运行。
中国科技论文在线
-3-
8 End while
9 End procedure
图 1 ACO 算法主过程的伪代码描述(引自文献[13])
ACO 算法主过程的伪代码描述如下所示，三个子过程的具体描述代码可查看相关文
献。下面以 TSP 问题为例，具体介绍最先提出的 ACO 算法－AS 是如何应用于现实问题的。
4. AS 算法介绍
假设 m 个蚂蚁被平均分配到 n 个节点上，蚂蚁 k 的记忆变量 Mk记录其选择的节点序
列。各个蚂蚁都进入上述伪代码中的 while 循环，按照概率选择下一节点，直至形成最终
环游。
当处于节点 i 的蚂蚁准备选择下一节点时，需要计算 i 节点的蚂蚁路由表 Ai＝[aij(t)]，
aij(t)的计算公式为：
i
Nl
ililijijij Nj n;...1,2ittta
i
∈∀=⋅⋅= ∑
∈
,,][)]([/][)]([)( βαβα ητητ （1）
式中 Ni 为节点 i 的所有相邻节点集合；α、β分别为轨迹和能见度的权值。
路由表计算完毕之后，蚂蚁就可以按照概率决策规则选择合适的节点并更新记忆。令
)(tp kij 表示算法第 t 次循环中蚂蚁 k 从当前所处的节点 i 转移到节点j的概率，计算公式为：
k
i
Nl
ilij
k
ij Nj n;1,2,...,i tatatp
k
k
∈== ∑
∈
)(/)()( （2）
式中 kiN 是处于 i 节点的蚂蚁 k 仍未访问的节点集合。
当蚂蚁 k 完成一个环游后，算法利用该蚂蚁的记忆 Mk计算环游的长度并增强构成该环
游的弧 lij 的轨迹强度τij：
m21ktlttt kij
k
ijij ,...,,),(),()()( =∈∀∆+= ψτττ （3）
式中 )(/1)( tJt kk ψτ =∆ ， )(tJ kψ 是蚂蚁 k 在第 t 次循环中所得到的环游 )(tkψ 的长度，
可以看出短环游得到更多的轨迹增强。
需要说明的是，在 AS 算法最初提出时有三种轨迹更新方式，分别是 Ant-quantity、
中国科技论文在线
-4-
Ant-density 和 Ant-cycle2。在前两种方式3中，蚂蚁每移动一步就要进行轨迹更新，它们都
属于在线逐步（online step by step）的更新方式；而本文介绍的 Ant-cycle 轨迹更新方式则
是在一个环游完成之后才更新相关弧的轨迹，它是一种在线延迟（online delayed）的更新
方式。有关模拟表明其寻优性能优于前两种方式。
当所有蚂蚁都完成各自的环游后将触发轨迹挥发过程：
ji ; n1,2,...ji, tt ijij ≠=−= ,)()1()( τρτ （4）
式中ρ∈(0,1)称为挥发系数。随后蚂蚁“死亡”并释放占用的资源。
假设循环次数限制为 NC 次，则 AS 的时间复杂度为 )( 2nmNCO ⋅⋅ 。多若干 TSP 问题
的仿真显示,当蚂蚁数量 m=n、α=1、β=5、ρ= 左右时寻优结果最佳，此时时间复杂
度具有 )( 3nNCO ⋅ 的形式。
对 AS 的改进思路主要有[1][3][14]：
奖赏优秀个体的策略
当所有蚂蚁都完成各自的环游后，那些属于当前最好环游的弧得到额外的轨迹增强，
这是一种离线更新方式。
转移概率公式中考虑噪音
当考虑噪音时，转移概率公式中需添加随机噪音函数。对 4×4 表格问题的模拟表明：
低噪音对算法无显著影响；但是高噪音却使算法性能下降。
逐步增加节点的环游构筑方法
搜索过程总是从少数的几个节点开始，然后逐渐加入新的节点。这样人工蚂蚁就能为
原问题的每个子问题确定各自比较好的轨迹分布，而这又成为节点数增加时新问题的寻优
基础。
避免趋同选择行为4
当蚂蚁的搜索陷入停滞状态时，有可能意味着陷入局部极值点。此时若允许对当前的
轨迹水平进行修改（通过改变参数α，β的数值），就可以在某个可能解附近重新进行搜索。
2 国内有学者把这三种方式翻译为：蚂蚁数量、蚂蚁密度、蚂蚁圈。
3 在 Ant-quantity 中，当蚂蚁从节点 i 移转移到节点 j 时在该路径上留下的信息素轨迹为常量 Q1；
而在 Ant-density 中当蚂蚁从节点 i 移动到节点 j 时，在所经过的单位长度的路径上释放 Q2单位的信息素
轨迹。
4经过足够多次的循环后，所有的蚂蚁都会选择同样的路径。相关文献把这种现象称为趋同选择行为
(uni-path behavior[1][5] 、uniform behavior[2] 、stagnation behavior[3])。
中国科技论文在线
-5-
与遗传算法相结合
在这种改进算法中，每个蚂蚁都被设置了特定的α、β数值，并且按照遗传算法进化，
其中适应函数与该蚂蚁探索到的环游长度成反比。
AS 与其他启发式算法的比较 [1][3-5]表明它是一种很有竞争力的优化算法。其他 ACO
算法都是在 AS 基础上进行各种改进而得到的。
5. 其他 ACO 算法简介
Ant-Q
Ant-Q 在表述上与 AS 有了较大的差别，而且其状态转移规则比 AS 复杂。特别地在
Ant-Q 中，轨迹更新方式有了较大改进，它不仅考虑了下一步转移的期望收益，而且包含
了当前循环中最好环游（iteration-best）或者全局最好环游（global-best）的影响。
ACS
ACS 是在 AS 以及 Ant-Q 的基础上而提出的。ACS 的特点是在蚂蚁探索路径的过程中
应用局部更新，同时只对构成最好环游（当前循环中最好环游或者全局最好环游）的弧集
进行全局更新。
在应用 ACS 时，为了快速地求解大规模 TSP 问题，通常会为每个节点增加一个称为
候选集合（candidate list）的数据结构，用以记录那些相对更应该被选择的节点。在算法运
行时，当蚂蚁不能从候选集合中找到合适的节点时才从剩下的节点集合中寻找合适的转移
目标。
MMAS
MMAS 对 AS 的区别之处在于对各个弧的轨迹设置了极大值（ maxτ ）与极小值（ minτ ）
的限定，这样不会出现经过若干轮循环后，某些弧的轨迹趋于零的情况。
另外 MMAS 中引入了轨迹平滑机制（trail-smoothing mechanism），当算法经过长时间
模拟而进入停滞状态时，将根据线性比例来调整当前网络中的轨迹强度，即对于弧 lij，其
轨迹强度将按照 maxτ 与 )(tijτ 之间的差值按比例增大。
除了上面介绍的几种算法形式外，比较受关注的还包括 ASrank。在 ASrank 中把各个蚂
蚁所得的环游长度进行排序，然后根据此排序进行轨迹增强。另外还有许多与特定应用问
题相关的算法 [12][15]，比如针对 QAP（Quadratic Assign Problem）问题的 AS-QAP、
MMAS-QAP、HAS-QAP；针对 JSP（Job-shop Scheduling Problem）问题的 AS-JSP；针对
中国科技论文在线
-6-
VRP（Vehicle Routing Problem）的问题的 ASrank+2-opt、HAS-VRP；针对 SCS（Shortest
Common Supersequence）问题的 AS-SCS；针对 GC（Graph Coloring）问题的 ANTCOL；
针对 SOP（Sequential Ordering Problem）问题的 HAS-SOP；针对数据挖掘中规则分类问题
的 Ant-Miner；针对 CSPs（Constraint Satisfaction Problems）问题的 Ant-Solver 算法等。
上述这些算法都是解决一些静态问题，近年来 ACO 在通信网络路由优化5中也备受瞩
目。如 ABC (Ant-Based Control)、ASGA（Ant System Plus Genetic Algorithm）、AntNet-FS
等用于面向连接的网络路由优化算法；AntNet、AntNet-FA、Regular Ants 等用于面向无连
接的网络路由优化算法。限于篇幅，本文不再赘述。
6. 结论
ACO 的主要特征是正反馈、分布计算以及结构性的贪心启发。正反馈使得它能很快搜
索到比较好的解；分布计算避免了算法陷入局部收敛而不能继续优化；而贪心启发机制使
它能在寻优的早期阶段就搜索到可接受的解。目前国外 ACO 领域的研究热点集中在寻优
原理与数学基础的研究、收敛性研究、并行 ACO 算法研究以及利用 ACO 解决各类优化问
题等等。
从上个世纪九十年代后期起国内逐渐兴起了“蚂蚁热”，利用 ACO 解决组合优化问题
以及通信网络路由问题的论文很多，但对算法本身进行创新的则很少看见。
可以预见，作为一种新兴的智能仿生算法，ACO 具有非常重要的研究前景和应用价值。
参考文献
[1] Colorni A，Dorigo M，Maniezzo V. Ant system：an autocatalytic optimizing process[R].
Technical Report 91-016 Politecnico di Milano，1991.
[2] Colorni A ，Dorigo M ，Maniezzo V. Distributed optimization by ant colonies[A]. Proceedings
of the First European Conference on Artificial Life[C]，Paris，France：Elsevie Publishing，
1991，134-142.
[3] Dorigo M， Maniezzo V，Colorni A. The ant system：optimization by a colony of cooperating
agents[J]. IEEE Trans on Systems，Man， and Cybernetics-Part B，1996，26(1): 29-41.
[4] Dorigo M， Maniezzo V，Colorni A. Positive feedback as a search strategy. Technical Report
91-016，Dipartimento di Elettronica, Politecnico di Milano， IT， 1991.
[5] Colorni A，Dorigo M，Maniezzo V. An investigation of some properties of an ant algorithm[A].
Proceedings of the Parallel Problem Solving from Nature Conference(PPSN’92 )[C]. Brussels，
5文献[16]中把这类算法叫做 ACR(Ant Colony Routing)。
中国科技论文在线
-7-
Belgium：Elsevier Publishing，1992，509-520.
[6] Gambardella L M，Dorigo M. Ant-Q：a reinforcement learning approach to the traveling salesman
problem[A]. Proceedings of the 12th International Conference on Machine Learning[C]. Tahoe
City，CA：Morgan Kaufmann，1995，252-260.
[7] Dorigo M，Gambardella L M . A study of some properties of Ant-Q[A]. Proceedings of PPSN-IV，
Fourth International Conference on Parallel Problem Solving From Nature[C]，Berlin：Springer
-Verlag，1996，656-665.
[8] Watkins C. Learning with delayed rewards[D]. England：Psychology Department，University
of Cambridge，1989.
[9] Gambardella L M，Dorigo M. Solving symmetric and asymmetric TSPs by ant colonies[A].
Proceedings of the IEEE Conference on Evolutionary Computation，ICEC96[C]，IEEE Press，
1996，622-627.
[10] Dorigo M，Gambardella L M. Ant colony system：a cooperative learning approach to the traveling
salesman problem[J]. IEEE Transactions on Evolutionary Computation，1997，1(1)：53-66.
[11] Stützle T，Hoos H. The MAX-MIN ant system and local search for the traveling salesman
problem[A]. Baeck T，Michalewiez Z，Yao X. Proceedings of IEEE-ICEC-EPS’1997，IEEE
International Conference on Evolutionary Computation and Evolutionary Programming
Conference[C]. IEEE Press，1997，309-314.
[12] Dorigo M，Di Caro G，Gambardella L M. Ant algorithms for discrete optimization[R]. Technical
Report IRIDIA/98-10. Artif. Life， 1999，5(2)：137-172.
[13] Dorigo M，Di Caro G. Ant colony optimization a new meta-heuristic[A]. Proceedings of the
1999 Congress on Evolutionary Computation[C]，1999，2：1470-1477
[14] Colorni A，Dorigo M，Maffioli F，et al. Heuristics from nature for hard combinatorial
problems[J]. International Transactions In Operational Research，1996，3(1)：1-21.
[15] Dorigo M，Gambardella L M，Middendorf M，Guest editorial special section on ant colony
optimizationL[J]. IEEE Transactions on Evolutionary Computation，2002，6（4）：317-318.
[16] Bonabeau E，Dorigo M，Theraulaz G. Inspiration for optimization from social insect
behaviour[J]. Nature，2000，406（6）：39-42.
The Review of Ant Colony Optimization
XU Jun-jie XIN Zhan-hong
School of Economics and Management , Beijing University of Posts and Telecommunications ,
Beijing, PRC,100876
Abstract
Ant colony optimization（ACO）obtains satisfactory performance on many optimization questions
through locally interacting simple agents. Introduce systematically the evolvement of this new
中国科技论文在线
-8-
stochastic optimization method. The application on traveling salesman problem by Ant System（AS）
is described . Finally several improved algorithm forms and applications of ACO are summarized.
Key words：optimization, ant colony optimization ,review, ant algorithm simulating, biology
intelligent algorithm, heuristic algorithm
徐俊杰：男。1980 年出生。硕士研究生。主要研究方向是智能算法、运筹学、系统工程。
中国科技论文在线
