蚁群算法的改进策略

摘要：蚁群算法是模拟蚂蚁活动规律而提出的一种元启发式优化算法，研究表明其具有很多优点，在解决优化问题时表现出很好特性，但也存在一些缺陷。因此，许多学者提出了许多改进算法。该文对算法的改进策略进行研究，形成结论，为算法进一步发展提供参考。

关键词：蚁群算法；缺陷；改进算法；改进策略

中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2014）28-6674-03

蚁群算法（Ant Colony Optimization，ACO）是由意大利学者M Dorigo在1991年根据蚂蚁活动规律从而提出的一种仿生学的优化算法，并把其应用在求解TSP问题，表现出了很好的特性。[1] 算法得到了有很快的发展，应用领域也不断的拓广，因此对于该算法的研究就显得尤其重要，但是任何一种算法并不能完美，其存在着一些缺陷，如收敛速度慢，容易陷入局部最优等缺陷，所以很多学者提出了改进方法，对算法的改进方法总结，就成为必要的课题。

1 蚁群算法基本原理

在对蚂蚁觅食过程进行研究之后，发现蚂蚁可以在路径上留下一种叫做信息素的物质，并且蚂蚁能感知这种信息，并会向着信息素浓度高的方向移动。蚂蚁个体之间通过这种方式进行联系，于是群体的觅食行为就表现出一种正反馈性。在觅食过程中某一条路径越短，其信息素浓度会越高，经过的蚂蚁会越多，反之路径越长，经过的蚂蚁越少，信息素浓度会越低，这就是算法的基本原理。

为了叙述方便我们以[n]个城市[TSP]问题为例，其中[m]蚂蚁数量，[dij]为两城市之间距离，[bi（t）][i=（1]、2……[n）]是[t]时刻城市[i]蚂蚁的数量，那么[m=i=1nbi（t）]。

蚂蚁系统：我们将[m]只蚂蚁随机放到平面上[n]个城市，同时记录每一只蚂蚁所在的城市，设城市之间路径上信息素一样，即[τij（0）=c（c]是常数[）]。接下来蚂蚁按照觅食规则选择下一城市。在[t]时刻蚂蚁[k]从[i]城市转移到[j]城市的概率为[pkij（t）]，其中

2 蚁群算法的改进

蚁群算法得到很快发展，但是其本身是存在一些缺陷，于是很多学者提出很多改进方法，总结起来，我们从以下几个方面进行论述。

2.1 信息素的更新策略

蚁群算法中信息素起着重要作用，对算法的改进最先也是从信息素的更新开始的。

M Dorigo等在1997年针对蚁群算法的不足提出一种蚁群系统（Ant Colony System，ACS），这个系统的提出是以Ant Q算法[2]为基础的。其中ACS为了避免蚂蚁陷入局部最优在信息素的更新上实施新方法，其只对最优路径上的信息素进行更新，同时还引入了挥发机制，即蚂蚁走过的路径上除信息素要增加外还要挥发一部分，从而实现一种信息素局部调整以减小已选择过的路径再次被选择的概率。ACS对于AS算法的该进提高了其性能。在同年 T.Stützle， H.Hoos对AS算法进行了直接改进，该改进方法是在AS的基础上直接进行，对信息素进行限定，即MAX-MIN Ant System[3]。算法中信息素更新方式规定，每次迭代后只有一只蚂蚁进行信息素更新。为了避免陷入局部最优，信息素浓度被限制在[[τmin，τmax]]范围内，除此之外，信息素初始值为取值上限，这样初始阶段的搜索能力较强。MMAS算法得到了广泛应用，但还是存在一些缺点，如消耗时间较长。2007年薛莉等提出了一种双信息素更新的蚁群算法，该算法通过对全局信息素和接近最优路经上的信息素进行更新，改善蚁群算法的寻优能力。[4]2008年，李亚韫等提出信息素扩散蚁群算法用于求解TSP问题，该文引入了扩散模型，使得算法更逼真，更加接近蚂蚁真实行为，加大了蚂蚁之间的协作，加快了算法的收敛速度。[5]2013年赵伟等人提出了一种基于惩罚函数和新信息素更新方式的蚁群算法，该文引入了局部和全局信息素更新的新方式并且引入了惩罚函数，降低了算法的复杂度，并且减小了搜索范围，有利于发现较好的解。[6]孟祥萍等人提出了基于方向信息素协调的蚁群算法，该算法定义了一种新的信息素，该种信息素刻画全局信息，其使算法求得的解是最优解，并能加快算法的收敛速度。[7]

综上所述，以上的改进算法，都有效提高了算法性能，使得蚂蚁寻优能力更强，并有效避免算法的停滞，是行之有效的改进策略。

2.2 蚂蚁本身特性的改进

蚁群算法改进的另外一方面便是蚂蚁本身的特性。2008年汪采萍等提出具有变异特性的蚁群算法，并应用于求解TSP问题，该变异采用遗传算法中的变异对蚁群进行变异，该方法保存了蚁群的多样性，有效避免算法陷入停滞，使蚁群具有发现较好解的能力。[8]2008年郑松等提出了动态调整选择策略的蚁群算法，算法使得蚂蚁具有新特性，该种蚂蚁能够对信息素浓度较低的路径探索，有效加大搜索范围，避免陷入局部最优。[9]2009年薛晗等提出生存模糊自适应蚁群算法，其使得蚂蚁个体具有适应度，保证了蚂蚁种群多样性以及生存时间，改进算法更有效，更稳定。[10]2013年吴华锋等提出基于自然选择特性的蚁群算法，使蚂蚁具有自然选择特性即优胜劣汰的进化策略，其在解决TSP上表现出很好的特性。[11]

蚂蚁特性的改进是算法改进新方向，改進时加入新特性，使蚂蚁在寻求最优解上表现出很好的特性，在跳出局部最优方面也表现出了有效性。

2.3 算法的融合方面

算法的改进层出不穷，科技发展到今天各种智能算法不断出现，每种算法都有自己的优缺点，所以我们把具有不同优点的算法进行综合、融合就成为算法改进另外一个重要方向。

2008年黄立君、许永花，提出了遗传算法与蚁群算法融合新算法，分别利用了两种算法的优点进行结合，并将其应用于求解TSP问题，表现出很好的特性。[12]2010年，刘好斌等人将蚁群算法和免疫算法的优点进行有机结合形成了带免疫变异的蚁群算法，其表现出很好的稳定性和寻优能力。[13]2013年李擎等将粒子群算法与蚁群算法进行结合，利用粒子群算法的优点对蚁群算法参数进行优化，从而改进了蚁群算法耗时大的缺陷，是对蚁群算法的很好补充，该算法应用于求解优化问题，表现出很好的特性。[14]

随着计算机技术的发展，新算法不断的出现，算法融合的改进方法将成为算法改进的重要方面，有着很广的前景。

2.4 应用领域

算法始终都是为了解决实际问题，对于算法改进的另一个方面即使对算法应用领域的不断拓展。

蚁群算法从一开始出现便应用于求解TSP问题，随着算法的发展应用领域不断扩大，已经渗透到组合优化、指派问题、图像处理、城市路径规划、网络路由、单机调度、电路分布线等各个方面，表现出很强生命力。2008年张景虎等将蚁群算法进行改进应用于图像处理，对CT图像的边缘进行检测，表现出很好的性质。[15]2011年张潇等将蚁群算法进行适当改进并应用于求解车辆路径问题，表现出很好的稳定性以及寻求最优解的能力。[16]

算法终究要应用于实际，虽然现在对于蚁群算法应用的文章不在少数，但是都是简化之后的简单应用，对于应用的研究还有很长的路要走，这也是对算法进行改进的一个重要方面。

3 结论、展望

蚁群算法的发展告诉我们，蚁群算法是一种具有研究价值的算法，随着科技发展，仿生算法会成为智能计算的重要部分，蚁群算法的研究也将是一个长期研究的课题，现在对于蚁群算法的改进策略虽然很多，但还有很多方面做的还不够，有待于进一步深入。

1） 对于蚁群算法的理论研究还不够深入，其收敛性的证明还没有完整的理论依据；对于算法的参数设置还处于实验阶段，没有选择的理论依据。

2） 算法应用领域还不够宽广，虽然现在算法应用文章比较多，但是大多数只是在理论方面的应用还没有真正应用到实际中去，这方面还需要不断推广。

3） 现在新仿生算法不断出现，与这些算法的结合，还需要进一步加强，不断完善算法的特性，解决更多实际问题。

参考文献：

[1] Dorigo M， Maniezzo V， Colorni A. Positive feedback as a search strategy[R]. TechnicalReport 91-016， Dipartimento di Elettronica， Politecnico di Milano， IT 1991.

[2] Dorigo M， Gambardella L M. A study of some properties of Ant-Q[C]//Proceedings of PPSN-IV，Fourth International Conference on Parallel Problem Solving From Nature.Berlin：SpringerVerlag，1996，656-665.

[3] Stutzle T， Hoos H. The MAX-MIN ant system and local search for the traveling salesman problem[C]//Baeck T， Michalewiez Z， Yao X. Proceedings of IEEE-ICEC-EPS1997，IEEE International Conference on Evolutionary Computation and Evolutionary Programming Conference.IEEE Press，1997，309-314.

[4] 薛莉，戴居豐，魏志成.双信息素蚁群算法法及其在TSP中的应用研究[J].计算机仿真，2007，24（8）：167-170.

[5] 李亚韫，杜永贵.用于求解TSP 的信息素扩散蚁群算法[J].机械工程与自动化，2008，3：39-41

[6] 赵伟，蔡兴盛，曲慧雁.一种基于惩罚函数和新信息素更新方式的蚁群算法[J].计算机工程与科学，2013，35（3）：103-107.

[7] 孟祥萍，片兆宇，沈中玉，等.基于方向信息素协调的蚁群算法[J]. 控制与决策，2013，28（5）：782-786.

[8] 汪采萍，胡学钢.具有分段和变异特性的蚁群算法求解TSP 问题[J].计算机技术与发展，2008，18（6）：90-93.

[9] 郑松，侯迪波，周泽魁.动态调整选择策略的改进蚁群算法[J].控制与决策，2008，23（2）：225-228.

[10] 薛晗，李迅，马宏绪.生存模糊自适应的蚁群算法及收敛性[J].控制与决策，2009，24（9）：1288-1293.

[11] 吴华锋，陈信强，毛奇凰，等.基于自然选择策略的蚁群算法求解TSP 问题[J].通信学报，2013，34（4）：165-170.

[12] 黄立君，许永花.遗传算法和蚁群算法融合求解TSP[J].东北农业大学学报，2008，39（4）：109-113.

[13] 刘好斌，胡小兵，赵吉东.带免疫变异的蚁群优化算法[J].计算机仿真.2010，27（12）：221-224.

[14] 李擎，张超，陈鹏，等.一种基于粒子群参数优化的改进蚁群算法[J].控制与决策，2013，28（6）：873-878.

[15] 张景虎，郭敏，王亚文.基于改进蚁群算法的CT图像边缘检测方法研究[J].计算机应用，2008，28（5）：1236-1239.

[16] 张潇，王江晴.混合蚁群算法在车辆路径问题中的应用[J].计算机工程，2011，37（24）：190-192.