2.4 蚁群算法研究现状
自1991年Dorigo等提出蚁群算法以来[10]，特别是1996年Dorigo[2]等系统阐述了蚁群算法的基本原理和数学模型之后，蚁群算法倍受关注，取得了大量的应用与理论研究成果。
2.4.1 蚁群算法的应用
在蚁群算法最初发展阶段，它主要应用于解决旅行商问题（TSP）、二次指派问题（QAP）以及作业调度问题（JSP）等为数不多的几类问题。现在已经在图着色问题[11]、车辆路径问题[12]、项目调度[13]、约束满足问题[14]、点覆盖问题[15]、网格划分问题[16]、背包问题[17]等许多复杂静态组合优化上取得了令人瞩目的成果。
蚁群算法在动态组合优化问题中一个最成功的应用是网络路由问题[18～20]。这主要是由于这类问题的内部信息和分布计算、随机动态以及异步网络状态更新等特征与蚁群算法的特征匹配得很好。
蚁群算法还用来解决连续优化问题。Bilchev和Parmee[21]提出了第一个求解连续优化问题的蚁群算法。它由全局搜索与局部搜索两部分组成，利用蚁群算法进行局部搜索，而全局搜索由遗传算法完成。其中，全局搜索确定整个搜索空间的区域，并给这些区域做出简单的评价。新区域的创建通过类似于遗传算法的交叉和变异操作完成。蚂蚁在经过的区域上根据该区域的目标函数值留下信息素，这些信息素可以指导其他蚂蚁进行局部搜索。Dreo和Siarry[22]在该算法的基础上引入了密度等级结构（Dense heterarchy），将信息素间接通信和直接通信两种方式结合起来。陈崚等[23]提出，将解空间划分成若干子域，根据信息量求出解所在的子域，然后在该子域内已有的解中确定解的具体值。杨勇等[24]提出一种求解连续空间优化问题的蚁群算法，该算法主要包括全局搜索、局部搜索和信息素强度更新规则。在全局搜索过程中，蚂蚁的移动方向由信息素强度和启发式函数确定。在局部搜索过程中，采用确定性搜索改善算法寻优性能，加快收敛速率。李艳君和吴铁军[25]用二进制对每个连续变量编码，然后让蚂蚁在离散域搜索。汪镭等[26]将蚁群算法引入连续空间的函数寻优问题，通过将传统蚁群算法中的“信息量留存”过程拓展为连续空间中的“信息量分布函数”，导出了相应的求解算法。程志刚等[27]保留了连续问题可行解的原有形式，并融合演化算法的种群与操作功能。他们将蚁群分为全局和局部蚂蚁，个体分别执行全局探索式和局部挖掘式搜索，并释放信息素，实现信息共享，利用正反馈机制以加速寻优进程。寇晓丽和刘三阳[28]将解空间按一定原则分解成离散子空间，蚂蚁在离散子空间搜索；并且用改进的Alopex算法对蚂蚁搜索得到的解进行修正。Socha和Dorigo[29]提出了离散域中蚁群算法的一个直接推广，其基本思想是利用概率密度函数（probability density function）替代离散域中的离散概率分布，蚂蚁依据概率密度函数进行抽样。段海滨等[30]提出了一种用于求解连续空间优化问题的改进蚁群算法，将连续空间优化问题的解向量分解成有限个网格，同时构造了一个与蚁群转移概率相关的评价函数，并借助相遇搜索策略对蚁群算法进行了改进，将信息素数量限制在一个有界区间，以提高改进蚁群算法的全局收敛性能。
蚁群算法还广泛用于求解多目标优化问题。张勇德和黄莎白[31]提出了基于蚁群算法的连续多目标算法。他们定义了连续空间中信息量的留存方式和蚂蚁的行走策略，并将信息素交流和基于全局最优经验指导两种寻优方式结合，以加速算法收敛和维持多样性。Doerner等[32]提出一类基于pareto占优的多目标蚁群算法，并用于项目证券投资组合（proj ect portfolio selection）。蚁群算法已经在许多工程中的多目标优化问题得到应用，如多QoS约束海量数据网格任务调度[33]、热轧带钢轧制批量计划优化[34]、柔性约束电网规划[35]等。此外，蚁群算法还用来解决复杂混合变量等优化问题[36]。
2.4.2 蚁群算法的改进
针对基本蚁群算法的不足，国内外学者深入研究了信息素释放方式、信息素更新规则、路径选择策略、参数的选取以及并行实现和计算效率等，并且融合其他算法改进基本蚁群算法。
1）信息素释放方式
当AS应用到TSP问题中，蚂蚁采用边（edge）模式释放信息素，即将信息素释放到边上。随后研究者提出的信息素释放方式还有点（vertex）模式和团（clique）模式[37]等。与这几种方式相对应，信息素分别表征边、点和团的偏好。实验表明，针对不同问题，合理地选取信息素释放方式对于算法性能有着重要影响。
2）信息素更新规则
信息素更新规则是蚁群算法的核心。在AS中更新规则对所有蚂蚁经过的路径上的信息素都进行更新，这就降低了选择最优路径的概率，使得蚂蚁不能很快集中在最优路径的邻域内搜索。为克服这一缺陷，Dorigo和Gambardella[5]提出了全局更新规则和局部更新规则。一方面，由于全局更新规则只对全局最优路径进行信息素的增强，其他路径的信息素由于挥发机制会逐渐减少，这就增大了最优路径与其他路径在信息素上的差异，使得蚂蚁更倾向于选择最优路径中的边，并且很快集中在最优路径的邻域内搜索，从而提高算法的搜索效率。另一方面，局部更新规则使得蚂蚁具有更好的探索新解的能力。在此基础上，Stützle和Hoos[7]提出仅允许最优蚂蚁更新信息素，从而强化算法开发能力，达到提高算法获得更好解的效率的目的。但是这种精英策略（elitistst strategy）往往会导致算法在搜索早期收敛于局部最优解而过早停滞。为此，他们提出限制信息素上下界的方法，并通过把信息素初始化为信息素的上界使算法在初始阶段具有较好的探索能力。
此外，Bullnheimer等[6]将排序的概念扩展到蚂蚁系统，提出了基于排序的蚂蚁系统。该算法在每一次迭代后，将蚂蚁所经路径的长度按从小到大的顺序排列，并根据路径长度赋予不同的权重，路径较短的权重较大。鉴于蚂蚁系统搜索效率低和质量差的缺点，李士勇[8]提出了利用最优最差蚂蚁更新信息素。覃刚力和杨家本[38]采用锦标赛竞争策略更新信息素。陈崚等[39]提出了一种分布均匀度的自适应蚁群算法，根据优化过程中解的分布均匀度，自适应地调整路径选择概率的制定策略和信息素更新策略，以求在加速收敛和防止早熟、停滞现象之间取得很好的平衡。他们[40]还提出了一种具有感觉和知觉特征的蚁群算法，使蚂蚁受显意识和潜意识的相互作用选择路径，同时自适应地修改路径上的信息量。黄国锐等[41]提出了一种基于信息素扩散的蚁群算法，通过建立信息素扩散模型，使相距较近的蚂蚁之间能更好地进行协作。曹先彬和尹宝勇[42]采用异步更新规则调整各个蚂蚁的信息素强度，从而间接改变蚂蚁间合作方式。
3）路径选择策略
路径选择策略直接影响到解的质量。Dorigo和Gambardella[5]在随机比例状态转移规则的基础上，提出了伪随机比例状态转移规则（Pseudo-random-proportional state transition rule）。它提供了一种直接的方法平衡新路径的探索和先验知识以及问题积累知识的开发。郝晋等[43]提出了一种随机扰动蚁群算法，该算法具有一定的自适应性以及很强的随机扰动特性。李万庆和李彦苍[44]提出了基于信息熵的路径选择策略。王一清等[45]利用Bayes决策的后验分析技术，改进了基本蚁群算法中的随机搜索策略。
4）参数的选取
蚁群算法的参数是影响其解的质量和计算效率的关键因素。目前尚没有完善的理论指导，一般采用试凑法（trial and error）选定，该方法显然会影响算法的应用和性能。Botee等[46]用遗传算法求得参数的最优组合，但是该方法比较烦琐。Zecchin等[47]针对给排水系统优化问题用敏感度分析法给出了参数选取原则。冯远静[48]指出随着运行代数的增加逐渐减小信息素的挥发率，能改进算法性能。段海滨和王道波[49]在分析蚁群算法的全局收敛性的基础上，提出信息素强度变参数控制、挥发系数动态自适应调节策略。邢桂华和于盛林[50]对参数和选择策略进行了分阶段设计，而且参数的分阶段是根据寻优状态动态划分的。段海滨[9]提出用三步走的方法确定参数。Birattari等[51]采用机器学习的方法设置参数。Pellegrini等[52]分析了蚂蚁数、挥发率、信息素和启发信息的指数对于MMAS收敛速度的影响，提出了选取参数的方法。
5）与其他算法的融合
局部搜索常用来改善蚁群算法的性能[53]。蚁群算法执行一种粗搜索，它为局部搜索提供好的初始解；反过来，局部搜索这种精搜索又有助于避免蚁群算法陷于局部最优解。
利用蚁群算法良好的耦合能力，将蚁群算法和遗传算法相结合是蚁群算法改进的另一途径[54]。蚁群算法具有很强的正反馈能力，在算法后期能够加快算法的进化速度，促使算法迅速收敛，但在算法初期信息素匮乏，进化速度较慢；遗传算法具有快速随机的全局搜索能力，但不能利用系统的反馈信息。采用遗传算法生成信息素初始分布，利用蚁群算法求精确解，能够实现两种算法的优势互补。为了克服蚁群算法求解时间较长的缺陷，吴庆洪等[55]提出了一种具有变异特征的蚁群算法。陈烨[56]引入遗传算法中的杂交算子。孙焘等[57]提出了一种简单蚁群算法，利用变异算子改善蚁群初始解。段海滨等[58]采用云模型定性关联规则和自然界的小生境思想改善蚁群算法性能。文献[59,60]将蚁群算法和神经网络相结合，利用神经网络广泛映射能力和蚁群算法快速全局收敛能力，可在一定程度上避免神经网络易陷入局部极小点的缺陷。侯云鹤等[61]将粒子群算法应用到蚁群算法的局部搜索中，提高了优化效率和计算精度。文献[62,63]融合免疫系统的适应能力和蚁群算法的全局搜索能力，提出免疫蚁群融合算法，取得了较好的实验效果。
6）并行实现和计算效率
并行实现是改善蚁群算法计算效率的有效途径。Randall和Lewis[64]研究了5种并行实现方法：①并行独立蚁群法：一组蚁群算法在处理机上串行实现，每个蚁群的参数可能不同，它的优点是蚁群不需要通信；②并行交互蚁群法：它与并行独立蚁群法的区别在于蚁群间有交互信息；③并行蚂蚁法，它给每个蚂蚁分配一个从处理机，主处理机负责接受用户的输入，确定蚂蚁的初始位置、全局信息素更新、完成输出等任务；④解元素的并行评价法：它在从处理机上评价解元素；⑤混合法：它结合了并行蚂蚁法和解元素的并行评价法。
陈崚和章春芳[65]提出了并行蚁群算法中处理机间信息交流的两种策略，使得各处理机能够自适应地选择其他处理机以进行信息交换和相应信息素的全局更新。他们还提出了一种确定处理机之间进行信息交流的时间的策略，可以根据解的分布情况自适应地确定信息交流的时间，以平衡全局收敛速度和解的多样性。在算法每一次信息交换后，采用自适应的更新策略，根据信息素的均匀度进行信息素的更新，以达到避免早熟和局部收敛的目的。
最近，熊伟清和魏平[66]提出了一种二进制蚁群算法。这种算法采用二进制编码。由于这种算法对单个蚂蚁的智能行为要求比较低，对应的存储空间相对较少，从而提高了算法的计算效率。
2.4.3 蚁群算法的理论研究
虽然蚁群算法在应用上取得了丰硕成果，但蚁群算法的理论研究还主要集中于算法的收敛性和随机模型等方面。
Gutjahr[67]用Markov过程描述了一类蚁群算法GBAS，并且证明了其收敛性。Stützle和Dorigo[68]证明了一类蚁群算法
的收敛性。在此基础上，证明了两类具有代表性的蚁群算法即蚁群系统和最大最小蚂蚁系统，在给定信息素最小值（信息素下界）τmin和最大值（信息素上界）τmax的条件下以概率1收敛到最优解。Gutjahr[69]还在GBAS的基础上提出了两类新的算法GBAS/tdev和GBAS/tdlb，并证明可以通过选取合适的参数保证算法的收敛性。
Hou等[70]用不动点理论分析了一类广义蚁群算法的收敛性。Yoo等[71],[72]分析了一类分布式蚂蚁路由算法的收敛性。Badr和Fahmy[73]用分支随机过程描述蚁群算法，从分支随机路径和分支WIENER过程的角度研究了蚂蚁路径存亡的比率，并证明了该过程为稳态分布。孙焘等[74]提出了一种简单蚁群算法，利用变异算子改善蚁群初始解，并给出了收敛性证明。丁建立等[75]依据Markov理论对一种遗传蚁群融合算法的收敛性进行了分析，证明了其优化解满足值序列单调非增且收敛。
段海滨等[76]以Markov链和离散鞅作为研究工具，对基本蚁群算法收敛性问题进行了理论证明，把最优解集序列转变为下鞅序列考查残留信息素轨迹向量的收敛性，并且给出了基本蚁群算法首达时间的定义，从理论上分析了基本蚁群算法首次到达时间的期望值。
最近，黄翰等[77]基于吸收态Markov过程模型，以期望收敛时间作为研究指标对蚁群算法收敛速度进行了理论分析；根据吸收态的性质给出了期望收敛时间的估算方法，理论上衡量了蚁群算法收敛速度，并且提出了ACO-易和ACO-难问题的判定方法。他们还给出了蚁群算法参数的优化设计理论方法，以确保算法能在多项式时间内求解ACO-易问题。并且针对蚁群系统，分析了算法参数与迭代时间的关系，提出了蚁群系统易求解问题的具体判别规则。
值得指出的是，Blum和Dorigo[78]研究了蚁群算法的搜索偏向（search bias）。针对简化的蚂蚁系统，研究了第一、第二类欺骗问题，分析了竞争平衡系统（competition balance system）与第二类欺骗的关系。他们发现对于竞争平衡系统，可能不会出现第二类欺骗；而对于非竞争平衡系统，可能会发生第二类欺骗。