蚁群算法（ant colony algorithm）是由意大利学者 M. Dorigo 等 [1 , 2] 提出的一种基于种群的启发式仿生进化系统。蚁群算法最早用于解决著名的旅行商问题（TSP ，traveling salesman problem），采用了分布式正反馈并行计算机制，易于与其他方法结合，并具有较强的鲁棒性[3 ~ 8] 。

《1 基本蚁群算法的数学模型》

1 基本蚁群算法的数学模型

为了能够清楚地表达基本蚁群算法的数学模型，通常借助经典的对称 TSP 对其进行描述[4] 。蚂蚁 k（k ＝ 1，2 ，…，m）在运动过程中，根据各条路径上的信息量及路径的启发信息来计算状态转移概率。表示在 t 时刻蚂蚁 k 由元素（城市）i 转移到元素（城市）j 的状态转移概率

式中 α 为信息启发式因子，表示轨迹的相对重要性；β 为期望启发式因子，表示能见度的相对重要性；为启发函数，其表达式如下

式中 表示相邻 2 个城市之间的距离。该启发函数表示蚂蚁从元素 i 转移到元素 j 的期望程度。

为了避免残留信息素过多引起残留信息淹没启发信息，在每只蚂蚁走完一步或者完成对所有 n 个元素的遍历后，要对残留信息进行更新处理。由此，t＋ n 时刻在路径（i，j）上的信息量可按如下规则进行调整

式中 ρ 表示信息素挥发系数；表示本次循环中路径（i ，j）上的信息素增量，表示第 k 只蚂蚁在本次循环中留在路径（i，j）上的信息量。

根据信息素更新策略的不同， M. Dorigo 曾提出 3 种不同的基本蚁群算法模型，即 Ant-Cycle 模型、 Ant-Quantity 模型及 Ant-Density 模型，其差别在于求法的不同。其中 Ant-Quantity 模型和 Ant-Density 模型利用的是局部信息；而 Ant-Cycle 模型利用的是整体信息，在求解 TSP 时性能较好，因此通常采用 Ant-Cycle 模型作为蚁群算法的基本模型。

《2 蚁群算法的模型改进及其应用》

2 蚁群算法的模型改进及其应用

近年来，国内外学者在蚁群算法的模型改进和应用方面做了大量的工作，其共同目的是在合理时间复杂度的限制条件下，尽可能提高蚁群算法在一定空间复杂度下的寻优能力，从而改善蚁群算法的全局收敛性，并拓宽蚁群算法的应用领域[8] 。表 1 列举了部分的蚁群算法改进模型及其应用情况。

《表 1》

表 1 部分代表性蚁群算法的改进模型及其应用

Table 1 The list of typical ant colony algorithm models and their applications

《3 蚁群算法的发展方向》

3 蚁群算法的发展方向

《3.1 模型改进》

3.1 模型改进

人们针对不同的具体问题提出了许多不同类型的改进蚁群算法模型[8] ，但这些蚁群算法模型普适性不强，同时基本蚁群算法模型也不能直接应用于解决所有的优化问题。另外，自然界中的真实蚁群还有许多其他智能行为，用逆向思维和发散思维开发不同的蚁群算法模型是一条新的发展思路。基于此，可从以下几个方面对其模型进行改进。

1）设计一种通用的蚁群算法普适性模型首次提出蚁群算法时是用于解决 TSP 的，后来的一些改进蚁群算法基本上都是针对某一类问题的专用算法，而现实中的问题千差万别，并不是每一个问题都能够很容易化归到这样一个拥有高度社会性的蚁群智能模型中，而且系统高层次的行为是通过低层次昆虫之间简单行为的交互涌现而产生的[9] 。在算法的普适性研究方面，应进一步探索蚁群算法多种模型的高层次统一机制，并结合复杂性系统展开研究，提出更普适的蚁群算法模型。蚁群算法的正反馈机制就是一个很好的普适性模型。

2）进一步研究自然蚁群行为，提出更加智能化的蚁群混合行为模型从深度上说，虽然蚁群算法是基于蚂蚁觅食行为而发展起来的，但是自然界中的真实蚂蚁觅食机理并不那么简单，仍有许多借鉴之处，今后应继续挖掘蚂蚁觅食中一些未知的行为，得到新的蚁群算法模型；从广度上说，蚂蚁等昆虫除了寻找食物之外，还有着任务分配、构造墓地、建造巢穴、繁衍后代、清除垃圾、保卫领地等多种复杂的社会行为[10] ，将蚁群的这些行为与其觅食行为进行融合、统一，提出更加智能化的蚁群算法混合行为模型，还有待于从昆虫学、社会学、仿生学、信息学等综合角度对其进行深入研究。

3）摆脱传统模拟框架，开发新的蚁群算法模型蚁群算法是建立在对自然界中真实蚂蚁觅食行为进行模拟的基础上。模拟把蚁群算法与自然界中可能发生的过程紧密地联系在一起。模拟具有解释能力的同时，也有不利的方面，沿着模拟的道路走下去会阻碍那些不符合模拟所认可的模式发展。因此，在可供选择的框架下，有必要采用逆向思维和发散思维，重新表示各种通用方法的原理和过程，开发出更加优良的蚁群算法模型，摆脱给蚁群算法以启示的模拟参照的最初限制，开辟一条新的通向比较和应用的综合之路。

《3.2 理论分析》

3.2 理论分析

蚁群算法是一种概率搜索算法，从数学上对其正确性与可靠性进行证明比确定性算法困难。自 W. J.Gutjahr 最先从有向图论的角度对一种改进蚁群算法的收敛性进行理论证明至今，人们在其收敛性研究方面已经取得了相当丰富的理论研究成果，但是这些理论成果基本上都是针对一些改进蚁群算法的理论分析，例如 W. J. Gutjahr[11 , 12] 对一类 GBAS ， GBAS/tdev 及 GBAS/tdlb 算法的收敛性进行了证明， T. Stüezle 和 M. Dorigo 对 算法 [13] 的收敛性进行了理论证明， J. H.Yoo 等 [14 , 15] 对一类分布式蚂蚁路由算法的收敛性进行了深入的理论分析，孙焘等[16] 对一类简单蚁群算法的收敛性作了初步研究，丁建立等[17] 对一种遗传（蚁群算法的收敛性进行了 Markov 理论分析， Y. H. Hou 等 [18] 基于不动点理论对一类 GACA 的收敛性进行了初步研究，等等，这些证明并没有把对蚁群算法的理论分析统一到一个共同的框架内。

此外，在蚁群算法的理论研究方面还存在许多问题需要进一步解决，比如初始化参数选择问题、信息素分配问题、收敛速度问题等，这些均带有经验性和直觉性，至今没有经过严格的数学论证；同时，连续域蚁群算法的收敛性证明仍存在许多研究空白。蚁群算法的收敛性证明和理论分析仍然是一个非常具有挑战性的研究方向。

《3.3 并行实现》

3.3 并行实现

蚁群算法本身隐含着一定的并行性，单只蚂蚁在一次循环中独立于其他蚂蚁。因此，本质上蚁群算法应以分布式的协同优化计算方式为特征，而在串行计算机上对蚁群算法的进行模拟并不能真正体现蚁群算法的本质特征，进一步的研究工作还应开展蚁群算法的并行机实现。

并行机实现中往往需要在计算与通信之间寻求一种平衡，蚁群算法的并行机实现主要集中在最优的并行化[19 ~ 22] 。所谓最优的并行化是指使用适量的处理机以最小的代价使得并行化蚁群算法性能达到当前情况下的最好，或者说当并行化蚁群算法性能不变时，应竭力减少计算和通信的成本。

在研究蚁群算法并行机实现问题时，需要解决对蚁群算法并行化过程中并行计算模型的选择以及对蚁群算法的分解、映射方法的改进等问题，还需要解决在对蚁群算法并行化过程中粒度处理标准的问题，使并行处理过程具有较好的可扩展性，并具有良好的负载均衡性。主要存在如下几个问题：

1）在不考虑处理机间差异、选择同步更新方法的情况下，如何确定问题规模与加速比之间的关系；在处理机增多的情况下，如何选择处理机的最佳数目以使计算时间减少；

2）在不考虑处理机间差异、选择同步更新方法的情况下，当处理机一定时，如何选择最优的蚁群规模 m 以使效用函数的值最大；

3）在不考虑处理机间差异、选择异步更新方法的情况下，当问题规模一定时，如何分配处理机数目和各处理机上的蚁群规模使效用函数值最大；

4）当并行机实现时，局部迭代若干次后需要交换信息。局部迭代次数的增大也会使得蚁群算法早熟的概率增大，而局部迭代次数减小则会增加通信时间，因此还要努力解决如何有效避免蚁群算法的过早停滞和减少通信开销之间的平衡问题。

《3.4 应用领域》

3.4 应用领域

从目前公开发表的蚁群算法相关学术论文来看，大约五分之三的论文是蚁群算法在不同优化领域中的应用研究成果。虽然蚁群算法的应用范围已经几乎涉及到各个优化领域，但还存在很多不足，在应用上着重从如下两方面对其进行研究：

1）纵向而言，蚁群算法的应用深度还不够。从公开发表的研究成果来看，大部分应用还仅仅停留在仿真阶段，而且所做的研究大都是在对实际问题实验条件或约束条件进行简化的前提下进行的。尤其在动态优化问题、随机优化问题、多目标优化问题等方面的研究还需要进一步深化；

2）横向而言，蚁群算法的应用领域还需要进一步拓宽。不同的应用领域都有许多不同的实际问题，尝试蚁群算法在不同具体问题中的实际应用是今后的一项重要研究内容。如何抽象实际问题，使蚁群算法的求解更接近工程实际是广大蚁群算法研究者所共同关注的一个关键性问题。

《3.5 硬件实现》

3.5 硬件实现

蚁群算法的硬件实现是仿生硬件研究领域中一个新的子分支，在理论与实验研究方面均取得了较为明显的进展[23 , 24] ，但是还存在如下问题[25] ：

1）所开发的蚁群算法仿生硬件实现所能处理电路的规模、复杂程度远远比不上常规电路综合方法。对于规模较大、功能较复杂的电路，已开发的蚁群算法仿生硬件的进化时间太长或者在要求的时间内很难找到解，是制约其工程应用的主要问题；

2）对于蚁群算法仿生硬件产品的可靠性、可测试性、普适性以及鲁棒性问题需要进一步研究。虽然蚁群算法硬件只需要根据其外部特性就可用蚁群算法进行自动寻优，但是还需要进一步对蚁群算法仿生硬件进行理论分析与建模，有些问题（如模式识别问题）仅对系统外部特性的不完备测试是很难保证蚁群算法仿生硬件系统的可靠性；

3）今后应该研制开发可批量工程应用的蚁群算法仿生硬件芯片，以进一步推进的商业化进程；

4）研制蚁群算法的仿生硬件开发平台、建立蚁群算法仿生硬件产品的技术规范等是不可忽视的研究内容。

《3.6 智能融合》

3.6 智能融合

近几年，国内外学者陆续提出了蚁群算法与遗传算法、人工神经网络、微粒群算法、人工免疫算法等其他仿生优化算法的融合策略，但是从现有的成果来看，这些智能融合大部分是一些初步尝试，多数是针对具体问题进行的。所解决的问题不同，其融合策略也就存在着很多差异，应该在现有成果的基础上继续进行深入研究，努力探索蚁群算法与一种或几种仿生优化算法相融合的统一机制。

另一方面，蚁群算法与一些新兴的、目前影响不是很大的仿生优化算法（如人工鱼群算法[26] 、混合蛙跳算法[27] 、蜂群算法[28] 、情感计算[29] 等）之间的融合至今还是存在着研究空白，将其进行智能融合并应用于解决实际问题，容易诞生许多创新性研究成果，也是一个很有意义的研究方向。

《4 结语》

4 结语

蚁群算法的理论研究和实际应用表明，它是一种很有前途的仿生优化算法。随着人类认识的进步和社会发展的加速，仿生智能及最优化系统理论将越来越成为科学认识和工程实践的有力工具，蚁群算法理论及其应用的研究必将是一个长期的研究课题。蚁群算法这一新兴的仿生优化算法必将展现出更加广阔、更加引人注目的发展前景。