智能蚂蚁算法应用的最新进展

王培博

摘要：蚂蚁算法是一种新型的集群智能算法，它的主要特点有智能搜索、全局优化、鲁棒性强、正反馈机制、分布式计算，可以解决一些复杂问题，比如二次任务指派、组合优化、车辆路由、有序排列和车间任务调度等。本文介绍了蚂蚁算法在国内的工业生产、国防安全、交通运输、旅游、能源、农业科技、信息软件等各个领域的最新应用进展。

关键词：智能算法； 集群智能； 蚂蚁算法； 蚂蚁网络算法

中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2017）04-0183-03

Latest Progress of Smart Ant Colony Algorithm Application

WANG Pei-bo

（Yangcun High School of Wuqing District， Tianjin 301700， China）

Abstract： The ant colony algorithm as one of most promising swarm intelligence algorithms， has attracting characters， such as intelligent search， global optimization， strong robustness， positive feedback mechanism， and distributed computing. It provides a resolution to complicated problems， Quadratic Assignment Problem （QAP）， Combinatorial Optimization Problem （COP）， Vehicle Routing Problem （VRP）， Sequential Ordering Problem （SOP）， Job-shop Scheduling Problem （JSP）， etc. The latest progress of smart ant colony algorithm application is introduced， including industrial production， national security， traffic and transportation， tourism， energy， agriculture and information technology field.

Key words：intelligent algorithm； swarm Intelligence； ant colony algorithm； ant net algorithm；

1 概述

螞蚁算法是20世纪90年代初提出的模拟蚂蚁觅食行为的内在机制来求解复杂问题的方法。蚂蚁觅食行过程中，通过整体协作总能发现从蚁巢到食物源的最短路径。研究发现：蚂蚁能够通过一种称为挥发的“信息素”的机制来传递信息。蚂蚁在寻找食物源的路径上会释放一定量的信息素，后续其它蚂蚁可以感知信息素浓度，优先选择信息素浓度高的路径。蚂蚁到达终点以后会马上返回，蚂蚁来单程往返的时间越短，重复频率越高，洒下的信息素也会越多，在单位时间会则有更多的蚂蚁选择这条路径。蚂蚁以信息素作为媒介实现了群体内部的间接通信，依赖自身催化与正向反馈的机制可以最终发现觅食的最短路径。

2 蚂蚁算法的数学本质

如图1所示，蚂蚁算法运行机制的精髓有三点：1）信息素的更新机制，包括信息素的累积量、信息素的挥发量、信息素更新的时间切入点等；2）路径的选择机制，包括蚂蚁选路的前提、依据等；3）信息的传递机制，采用一种外激励方式类似“黑板系统”，可以保证蚂蚁间的沟通、协作。这些机制的共同作用使得蚂蚁算法有很强的求解能力。

图 1 蚂蚁觅食过程

蚂蚁算法本质上是一种仿生学的集群智能算法，若干低智能的个体通过相互之间的简单合作，能达到集体的、系统性的智能行为。它的典型技术特点有：1）分布式控制，没有中心控制，个体间通过非直接通信的方式进行信息传递，从而达到合作的目的；2）个体简单智能，遵循的行为规则也非常简单，不需要整体复杂运算，体现的系统集群智能；3）扩充性好，个体数目可以增加，通过增加小幅的通信开销实现搜索范围的加大；4）每个个体都能够改变环境，通过局部最优达到全局最优，最终呈现系统的自组织性；5）系统鲁棒性强，不会由于某个个体的故障而影响集群的最终整体表现。蚂蚁算法的这些特点，有助于解决一些复杂的问题，比如二次任务指派、组合优化、车辆路由、有序排列和车间任务调度问题等。

3 蚂蚁算法的最新应用

3.1在工业生产领域

有人将蚂蚁算法理论应用在在优化打孔机作业路径的应用中，为该工业的优化生产效能提供了参考与建议[1]；有人将蚂蚁算法应用在车身底板焊接路径规划中，找出了车身底板焊接路径的最优解，可以缩短焊枪的行走路程，提高了焊接的生产效率[2]。

有人利用模拟退火混合蚂蚁算法尝试解决OEM 协作生产环境生产管理问题，建立了一个带能力约束的、以总订单利润与准时交货为目标的多目标的OEM订单分配模型，可以让品牌制造商将不同生产任务合理分配给众多协作供应商[3]。有人将蚂蚁算法应用在选煤厂产品结构优化中，结合生产流程建立了产品结构优化数学模型，得到了满足各种约束条件下的各产品的最佳产量，提高了产品的生产率[4]。

有人采用改进蚂蚁算法对低速直线电机的结构进行了优化，提高了电机的电磁性能[5]。有人将蚂蚁算法应用在变风量空调控制系统中，提高了系统的稳定性以及自适应性，提升了动态响应速度，获得了更小的超调量[6]。有人提出了一种基于蚁群聚类算法神经网络温度补偿方法，解决了对压力传感器的温度漂移的补偿问题[7]。

3.2在国防系统领域

有人提出了基于“轮盘式选择策略、精英策略以及路径优化策略”的改进蚂蚁算法，并引入反舰导弹航路规划中，缩小了航路规划的最大搜索范围，缩短了最优航路长度，提高了航路搜索的收敛速度[8]。

有人将蚂蚁算法应用在战损装备抢修任务指派中，结合战时装备保障情况和战损装备抢修任务特点，建立了不同紧急度下的装备抢修任务指派模型，可以有效实施战损装备应急抢修任务的指派，提升了智能决策[9]。

3.3在交通运输领域

有人提出了混合粒子群的蚂蚁算法，可以诱导车辆在城市交通路网中规划较优出行路线，提高了出行质量，并建立出城市道路权值模型[10]；有人改进了现有蚂蚁算法的参数设置及信息更新机制，应用到飞行路径模型中，确保了飞机周期性返回检修机场，实现周期性检修[11]；有人在GIS 中应用蚂蚁算法，可以有效解决路径寻优和正射影像镶嵌线自动选择问题[12]。

3.4 在旅游與公共安全领域

有人采用蚂蚁算法较好地解决了旅游景区车辆路径问题，降低了运输成本[13]；有人将蚂蚁算法用于无人驾驶智能车的路径寻优，采用虚拟路径应用于动态路径规划，满足了车载系统的一些实时性和可行性要求[14]；有人将蚂蚁算法应用在道路应急疏散策略选择中，基于疏散车辆交通流和非疏散交通流的不确定性，建立带有区间参数的机会约束规划模型，可以有效缩短突发事件后车辆的应急疏散时间[15]。

3.5在能源领域

在超高压输电线路故障测距引入蚂蚁算法，可以来求解故障测距方程，算法测距精度高，不需要选择故障类型，有很强的实用价值[16]。有人将加权改进的蚂蚁算法应用在电网系统优化中，避免了提早陷入局部极优值，提高了收敛速度和计算准确度，并可以进一步降低网络损耗[17]。

基于蚂蚁算法正反馈性、并行性等优势，有人提出了混沌蚂蚁算法，优化了水库发电调度模型[18]。有人将蚂蚁算法应用在泵站优化调度运行问题，在保证运行可靠性的前提下，提高了能源的利用率[19]。

有人将改进蚂蚁算法应用在地下矿山运输路径优化中，提出以电机车总运输距离为目标函数，矿石接收点和溜井数目为变量的运输路径优化模型，得到最佳的运输路径[20]。有人提出了一种动态自适应的蚂蚁算法，并把算法应用于煤炭运输优化中，可以有效地节省运输费用，提高运输效率[21]。

3.6 在农业生产领域

有人将蚁群灰色神经网络模型预测水稻稻瘟病[22]；有人将蚂蚁算法应用在苹果糖度近红外光谱分析波长选择中，针对苹果近红外光谱数据的特点，建立了一种基于串联双通路构建图的波长变量选择模型，提高了苹果糖度定量分析模型的准确性和可靠性[23]。

3.7 在信息应用领域

有人提出了基于信息素扩散模型的蚂蚁算法，并用应用在虚拟现实系统中的碰撞检测中，通过手术中手术器械与人体的碰撞反映的仿真，验证了算法的效率和精确度[24]。有人将改良蚂蚁算法用于图像检测中，可以有效提取含一定噪声的低对比度图像边缘[25]。有人将蚂蚁算法应用在计算机病毒检测方面，可以降低漏警率和虚警率的发生，提高病毒检测软件对病毒检测的效能[26]。有人将蚁群聚类算法应用在教学评价系统中，从原始教学评价的数据中提取出有用信息，分析同类课程的特点，为这类课程评价、提高教学效果提供支持[27]。

4 总结

蚂蚁算法是一种新型的基于仿生学原理的集群智能算法，本质上也是一种模拟进化算法。蚂蚁间信息的传递没有采用直接方式，而是通过驻留在路径上的信息素得到指示，这种间接信息交流的方式称为外激励，外激励类似黑板指示系统。蚂蚁本身的智能较小，比较适合网络云化后的移动计算。蚂蚁算法的主要特点：智能搜索、全局优化、鲁棒性强、正反馈机制、分布式计算，而且易与其他算法相结合，可以采用模拟蚁群的协作行为解决一些复杂的问题，比如二次任务指派、组合优化、图着色、车辆路由、有序排列和车间任务调度问题等，仅在我国国内就广泛应用在工业生产、国防安全、交通运输、旅游、信息、能源、农业科技、信息软件等各个领域，结合未来的大数据分析，将有更为广阔的应用前景。

参考文献：

[1] 李韵，李婧骞，林晨光，等.蚁群算法理论及其在优化打孔机作业路径的应用[J].科技创新导报2012，（36）： 221-222

[2] 林巨广，陈甦欣，戴淮初，黄文进.蚁群算法在白车身底板焊接路径规划中的应用[J].焊接学报，2015，35（01）： 5-9

[3] 韩锦东，李英俊，陈志祥.带能力约束的多目标OEM协作生产订单分配决策与混合蚁群算法应用研究[J].中国机械工程，2012，23（22）： 2714-2719.

[4] 孙伟，王宜雷，王慧，等.蚁群算法在选煤厂产品结构优化中的应用[J].工矿自动化，2012，（7）： 52-54.

[5] 魏华生，程志平，焦留成，等.改进的蚁群算法在低速永磁直线电机设计中的应用[J].微电机，2013，46（1）：9-12.

[6] 姚瑶，李曼珍.蚁群算法在变风量空调控制系统中的应用研究及仿真[J].工业控制计算机，2014，27（8）：70 -71.

[7] 孙艳梅，都文和，冯昌浩，等.基于蚁群聚类算法的RBF神经网络在压力传感器中的应用[J].传感技术学报，2013，26（6）： 806-809.

[8] 高曼，刘以安，张强.优化蚁群算法在反舰导弹航路规划中的应用[J].计算机应用，2012，32（9）：2530-2533.

[9] 蔡纪伟，贾云献，孙晓，等.蚁群算法在战损装备抢修任务指派中的应用研究[J].数学的实践与认识，2012，42（19）：160-165.

[10] 陈家琪，刘跃.混合蚁群算法在城市交通路径规划中的应用[J].计算机系统应用，2012，21（1）：122-126.

[11] 牟德一，刘金凤.改进的蚁群算法在飞行路径模型中的应用[J].计算机工程与科学，2012，34（6）：137-139.

[12] 欧春江.蚁群算法在GIS中的应用探讨[J].测绘与空间地理信息，2013，36（8）：187-193.

[13] 刘倩，卫文学，张鲁.改进蚁群算法在景区路径规划中的应用研究[J].信息技术与信息化，2012（6）：56-59.

[14] 谭宝成，宋洁.蚁群算法在无人驾驶智能车中的应用及改进[J].国外电子测量技术，2012，31（9）：15-17.

[15] 毛新华，王建伟，赵京，等.蚁群算法在道路应急疏散策略选择中的应用[J].中国安全科学学报，2014，24（10）：170-176.

[16] 刘迅，黄纯.蚁群算法在超高压输电线路故障测距的应用[J].电力系统及其自动化学报，2012，24（05）：132-137.

[17] 姚建红，张玲玉，孙大兴.改进多智能体蚁群算法在电力系统无功优化中的应用[J].化工自动化及仪表，2014，41（5）：520-523.

[18] 原文林，曲晓宁.混沌蚁群优化算法在梯级水库发电优化调度中的应用研究[J].水力发电学报，2013，32（3）：47–53.

[19] 袁尧，刘超.蚁群算法在泵站单机组优化运行中的应用[J].水力发电学报，2013，32（1）：263-268.

[20] 周科平，翟建波.改进蚁群算法在地下矿山运输路径优化的应用[J].中南大学学报：自然科学版，2014，45（1）：257-261.

[21] 魏星，李志远，李燕.改进型蚁群算法在煤炭运输中的应用研究[J].煤矿机械，2013，33（07）：208-209.

[22] 刘坤，钱永德，张福军.蚁群灰色神经网络模型在稻瘟病预测中的应用[J].自动化仪表，2013，34（2）： 30-33.

[23] 陈鑫，刘飞.蚁群算法在苹果糖度近红外光谱分析波长选择中的应用[J].分析试验室，2013，32（10）：50-53.

[24] 陈莉芝.基于优化的蚁群算法在碰撞检测中的应用研究[J].電脑知识与技术，2012，8（28）： 6758-6760.

[25] 殷小莉，黄晓彤，郑晓霞，等.蚁群算法在低对比度图像边缘检测中的应用[J].计算机技术与发展，2013，23（5）：180-183.

[26] 朱俚治.蚁群算法在检测病毒上的应用[J].计算机安全，2014（9）：17-20.

[27] 朱福珍，薛景.蚁群聚类算法在高职院校教学评价系统中的应用研究[J].江苏第二师范学院学报，2014，30（8）：93-96.