摘要：在介绍蚁群算法的原理和特点后，着重分析了当前一些有代表性的蚁群算法的改进机制和应用成果，并采用比较的方式指出了这些方法的特点和主要应用范围等，最后总结了好的蚁群算法应具有的特点以及将来的研究策略与发展趋势。
关键词：蚁群算法； 组合优化
1蚁群算法
1.1蚁群算法的原理
蚁群算法是通过蚂蚁个体在候选解的空间中独立地搜索解，并在搜寻的解上留下一定的信息素；蚂蚁间以信息素为介质进行间接、异步的信息传递。随着算法的推进，较优解（较优的路径）的信息素浓度会越来越浓，同时其他路径上信息素浓度却会随着时间的消逝而削减变弱。当算法渐渐趋于收敛时，在最优解（最优路径）上的信息素浓度应该是最大的。整个蚁群算法的最优解即最优路径将在蚂蚁个体的共同协作下求出。意大利学者Dorigo M.等人[1～3]通过模拟蚂蚁寻路的群体行为最先提出了蚁群算法，并用于求解复杂的组合优化等问题，获得了较好的效果。
1.2蚁群算法挑战
（1）在蚁群算法中，所固有的加速收敛与防止早熟、停滞是一对矛盾。因此有研究者为了加速蚁群算法收敛的过程，提出充分利用学习机制强化最优信息的反馈；但由于强化了最优信息反馈，带来了早熟、停滞的发生。别的研究者又考虑让各个路径上信息素的变化固定在一个范围内，这样可以有效防止早熟、停滞现象的出现；但是却由于解的分布较分散，使蚁群算法收敛的过程变慢。
（2）算法初期的各个路径上具有相同初始信息素的问题。面对初始路径上相同浓度的信息素，路径选择一般采用贪心算法，而这次路径选择可能是不准确或错误的，因此会误导别的蚂蚁，使该路径上的信息素得到不应该的增加。最后，收敛的结果是信息素浓度最强的路径不是正确的最优路径。
（3）由于利用了正反馈原理，在蚁群算法进行过程中，任何一次路径选择和信息素更新发生的错误都会误导整个算法最优路径的选择，最终得到的最优解是错误的。
2蚁群算法的研究成果
研究者对蚁群算法进行了多方面优化。Dorigo M.等人提出称为AntQ System的蚁群算法[4]。Stutzle T.等人为了防止在AntQ System中的早熟和停滞现象，提出了MaxMin蚁群算法[5]。Gambardella等人[6]提出了蚁群系统(Ant Colony System)；同时，他们还提出了一种混合型蚁群算法HAS[7]，目标是加大蚂蚁个体自主选择的自适应能力，提高解的多样性。Botee H.M.等人结合遗传算法求得参数m、α、β、ρ的最佳组合[8]。吴斌等人提出了基于蚁群算法的分段求解算法[9]。Zhang等人[10]提出了采用确定性选择和随机选择相结合的策略及自适应调整选择概率的办法、优化算法的收敛速度和性能。同时，研究者也使用了蚁群算法来解决实际问题，并取得了较好的效果。Bilchev G.等人在解决工程设计中连续空间的优化问题时，用蚁群算法精确化其利用遗传算法求解时所得到的初步结果[11]。Gutjahr W.J.等人提出一种以图为基础的蚁群系统框架，以此解决组合优化问题[12]。
3蚁群算法的改进机制分析
3.1自适应调整信息素的蚁群算法
针对蚁群算法加速收敛与早熟停滞现象的矛盾，文献[13]提出一种基于分布均匀度的自适应蚁群算法，算法自适应地调整路径选择概率的确定策略和信息素更新策略。该算法引入了聚度的概念来衡量解的均匀程度，并且还引入了信息权重来限制信息素和期望程度对蚂蚁选择概率的影响程度。
以求解TSP为例：设从城市i共有r条路径到达另外r个城市i1，i2，…，ir。首先通过聚度的公式求得城市i的聚度为sta(i)，并根据城市i的聚度sta(i)确定蚂蚁在该城市时，下一步可供选择的路径条数为w；然后将以城市i为起点的r条路径按其信息素由高到低地排序，序号依次存于数组rank中，并可以引用上面求出的w和数组rank，根据公式求得路径(i, j)的信息权重ξij。蚂蚁由城市i按下式的概率选择城市j：
