蚂蚁算法的应用与发展

叶 凡

(成都理工大学 管理科学学院，四川 成都 610059)

1 引言

蚂蚁算法是一种用于解决搜索问题的优化方法。1992年，Dorigo在他的博士毕业论文中首次提出了此算法并用于解决了经典的离散组合问题商旅问题、二次分配问题。十多年来，蚂蚁算法以及各种改进过的蚂蚁算法，被广泛的应用在实际生活的各个方面，应用范围不断扩大，在计算机技术应用、交通控制，图表制作等都有蚂蚁算法的影响。

2 蚂蚁算法简介

2.1 算法思想

蚂蚁在路径上前进时会根据前边走过的蚂蚁所留下的分泌物选择其要走的路径，我们把这种分泌物叫做信息素。其选择一条路径的概率与该路径上信息素的强度成正比。因此，由大量蚂蚁组成的群体的集体行为实际上构成一种学习信息的正反馈现象：某一条路径走过的蚂蚁越多，后面的蚂蚁选择该路径的可能性就越大。蚂蚁的个体间通过这种信息的交流寻求通向食物的最短路径。

2.2 算法原理

下面介绍蚂蚁算法的原理：第1步：初始化，NC=0，将m只蚂蚁置于n个顶点上;第2步：将各蚂蚁的初始出发点置于当前解集中;对每一个蚂蚁k，按概率P选择移至下一顶点j上;将顶点j置于当前解集;第3步：计算各蚂蚁的目标函数值;记录当前的最好解;第4步：按更新方程修改信息素轨迹强度;第5 步：对各边弧(i，j)，Δτij=0，NC=NC+1;第 6 步：若搜索次数NC＜预定迭代次数且无退化行为(即找到的都是相同解)，则转第二步;第7步：输出目前的最好解。

2.3 基本蚂蚁算法的优缺点

(1)优点：蚁群算法与其他启发式算法相比，在求解性能上，具有很强的鲁棒性和搜索较好解的能力，是一种基于种群的进化算法，具有本质并行性，易于并行实现，容易与多种启发式算法结合，以改善算法性能。

(2)缺点：如果参数设置不当，导致求解速度很慢且所得解的质量特别差。计算量大，求解所需时间较长实际操作中很难让所有蚂蚁都选择最优路线。

3 蚂蚁算法的研究进展

3.1 改进的蚁群优化算法

蚂蚁优化算法在提高蚂蚁的搜索性能方面有着显著的发展。但是在实际应用中，不同的搜索优化问题，基本蚂蚁算法受到了许多条件的局限，并且这些束缚都要根据具体问题进行相应的处理，因此产生了许多改进的蚂蚁算法以适应各领域的问题特点。

(1)基于优化排序的蚂蚁系统

在蚂蚁系统中加入遗传算法排序的概念，当每只蚂蚁都走完一条路径后，根据路径长度对蚂蚁排序，根据该蚂蚁的排名对激素轨迹量更新的贡献进行加权。只考虑其中最好的W只蚂蚁，并要避免很多蚂蚁过分重视某些局部极优路径的情况发生。

(2)最大-最小蚂蚁算法。

该算法在蚁群算法的基础上进行了改进，当在最佳路径上时，此路径的信息素的迹才会增加，通过信息素的迹被限定在一个范围内，从而使得在当前找出的最好路径的领域内蚂蚁的搜索更集中。蚂蚁算法的任务就是使问题不断地向着最优化的方向进行。该算法的本质是对最优的解进行强化，并且对最差的解进行弱化，使最优路径和最差路径之间的差异化信息量变大，使蚂蚁的搜索行为向最优路径集中。

(3)多群蚂蚁算法。

Middendorf和Martin提出多群蚂蚁算法，利用若干个蚁群并行操作，每次迭代完成后，蚁群之间交换一次信息。蚂蚁间进行交换信息的信息素有正信息素和负信息素两种类型，进而提高了寻优过程的速度。MCAS在TSP和QAP问题的求解上有比AS更好的表现。

蚂蚁算法的改进还可以与其他更多的智能算法进行结合，在许多问题上都能弱化自身单一的缺点，增强各自的优点来改进和完善算法的性能。

3.2 蚂蚁算法在优化问题中的应用

蚁群优化算法已应用于许多组合优化问题，包括蛋白质折叠或路由车辆的二次分配问题，很多派生的方法已经应用于实变量动力学问题，随机问题，多目标并行的实现。它也被用于产生货郎担问题的拟最优解。下面分别介绍了蚂蚁算法在不同领域中的基本应用：

3.2.1 离散组合中的应用

除TSP早期最为经典以外，蚂蚁算法早已应用到其他离散组合优化问题中：二次分配问题(QAP)指的是在n个地点分配n个设备使得分配代价最少，其实质也是TSP问题的一种。车间任务调度问题(job-shop)指的是一组M台机器和一组T个任务，任务有一组制定的将在这些机器上执行的操作序列组成。还有许多问题，如指派问题、车辆路线问题(VRP)、有序排列问题(SOP)、图着色问题(GCP)，电力系统故障检测等。

3.2.2 连续空间中的应用

连续空间优化问题中的特点是随着时间变化问题的解决方案也在变化。其中通信网络问题是蚂蚁算法解决连续空间优化问题中有代表性的一类问题。在国际上，Sehoonderwerd，White等人在路由有向和网络路由问题中较早使用蚂蚁算法.而Diearogy等人根据路由的自适应问题改进了蚂蚁算法并更适用于此类问题的解决。在国内，也有了基于解决的QoS路由调度问题的蚂蚁算法。

4 结束语

蚁群算法的本质是受自然界启发的一种随机优化算法，由于它具有很强的鲁棒性和搜索较好解的能力使得在许多方面显示出良好的计算性能。求解范围由初始离散空间优化的组合扩大到约束多目标和连续的空间区域，并在社会学宏观领域表现出强大的生命力。但是，不是所有的基本蚂蚁算法都能解决优化问题，改进后的算法模型往往不是普遍适用，并且蚂蚁在真实自然界中还有很多其他的智能行为可以研究。

［1]温文波，杜维.蚁群算法综述［J].石油化工自动化，2002(1).

［3]张贤达，保铮.通信信号处理［M].北京：国防工业出版社，2000.