蚁群算法及其应用综述

乔东平+裴杰+肖艳秋

摘要：

蚁群算法是一种新型仿生优化算法，其分布式计算机制及与其它算法的良好结合性，使其在短期内得到了快速发展和应用。首先在简述蚁群算法基本原理及特点的基础上，对算法的发展及研究状况作简要概述，然后结合几种具有代表性的算法改进模型，对算法在不同优化领域的应用进行介绍，最后结合蚁群算法的理论及应用研究成果，对算法的发展加以总结。

关键词：蚁群算法；信息素；组合优化

DOIDOI：10.11907/rjdk.172949

中图分类号：TP301

文献标识码：A 文章编号：1672-7800（2017）012-0217-05

Abstract：Ant colony algorithm， a new bionic optimization algorithm， has got rapid development and wide application in a short time for the good combination of its distributed computing mechanism with other algorithms. Based on a brief description of the basic principles and characteristics of ant colony algorithm， the paper provides a general overview of its development and research status， introduces its applications in different optimization fields according to several representative algorithms， and finally， gives a conclusion of its future prospect with an analysis of the research results of ant colony algorithm theory and applications.

Key Words：ant colony algorithm； pheromone； combinatorial optimization

0 引言

蚁群算法（Ant Colony Algorithm）是由意大利学者Dorigo M等[1]于20世纪90年代初期受到自然界中真实蚂蚁觅食行为启发而提出的一种仿生优化算法。算法采用分布式并行计算机制，具有较强的鲁棒性，且易与其它优化算法相结合。其具有的诸多优良特性，使蚁群算法迅速受到研究者们的广泛关注[2]。

蚁群算法最早应用于旅行商问题（Traveling Salesman Problem， TSP）中，并取得了较好的应用效果。随着算法的发展，学者们在基本蚁群算法基础上提出了诸多改进策略，有效提高了算法的求解性能，并逐渐将其扩展应用于诸如作业调度、路径规划、数据挖掘等多个领域，取得了丰硕的研究成果[3-5]。

1 蚁群算法基本原理及模型

蚁群算法的研究模型源于对真实蚂蚁觅食行为的模拟。蚂蚁在觅食过程中，会在所经路径上释放出一种具有挥发性的物质——信息素，不同蚂蚁个体通过感知信息素的存在及其强度指导自己的移动方向[6]。研究表明，蚂蚁更倾向于选择信息量较大的路径，由此形成一种正反馈机制：最优路径上的信息量越来越大，其它路径上的信息量则随时间逐渐衰减。蚂蚁个体间通过感知信息素交换路径信息，最终整个蚁群在这种自组织作用下搜索出巢穴与食物源之间的最优路径[7]。

蚁群算法借鉴和吸收了自然界中真实蚁群的觅食行为特点，是一个分布式多智能体系。以下借助n个城市的TSP问题对算法的数学模型作简要阐述[8]：

设将m只蚂蚁放置在n个随机城市上，其中n为TSP规模；m表示蚂蚁数量；C为TSP问题中城市的集合；τij（t）为t时刻在城市i和j路径上的信息量；ηij为启发式因子，表示t时刻蚂蚁从城市i转移到城市j的期望程度，通常取ηij为相邻两城市间距离的倒数。

式中，Lk为第k只蚂蚁在本次循环中所走路径的总长度，Q是蚂蚁完成一次完整路径搜索后释放的信息素总量。Ant-Cycle模型利用蚂蚁完成一次循环后的整体信息对路径上的信息素进行更新，其对TSP问题的求解性能较好[1]。

2 蚁群算法发展与改进

2.1 蚁群算法发展

蚁群算法在1991年刚被提出时并未受到研究者们的广泛关注，算法理论和应用在这一阶段也未取得突破性进展[9]。随着1996年Dorigo M等[8]《Ant System： Optimization by a Colony of Cooperating Agents》一文的发表，人们对蚁群算法的基本原理及数学模型有了更深入的理解。Dorigo M在文中通过对蚁群算法与遗传算法、模拟退火算法等其它算法的仿真实验对比，使研究者们逐渐认识到蚁群算法在求解优化问题方面的优越性。

1998年，Dorigo發起了第一次蚁群算法的专题会议（ANTS98），进一步激发了研究者们对蚁群算法的研究热情，吸引了更多研究者参与到蚁群算法的研究工作中。

2000 年，Bonabeau等[10]首次发表了蚁群算法的研究综述；Gutjahr W J等[11]首次从有向图论的角度对ACO的收敛性进行探讨，并取得了初步的研究成果；同年，《Future Generation Computer Systems》上出版了蚁群算法特刊，有力推动了蚁群算法的发展，将蚁群算法的研究推向学术新高度。endprint

与此同时，在蚁群算法被提出至今的二十几年发展历程中，国内外研究者针对基本蚁群算法存在的收敛速度慢、易停滞等不足，从改进信息素调整机制、搜索策略，以及与其它仿生优化算法融合等方面出发，提出了许多行之有效的改进算法。

2.2 蚁群算法改进

2.2.1 信息素调整策略改进

蚁群算法收敛到最优解的过程是信息素正反馈的动态实现过程，信息素的调整策略对算法的收敛性和求解效率具有很大影响。基于此，学者们在蚁群算法的信息素调整策略方面开展了大量研究工作。

Stutzle T和Hoos H等[12]提出了最大-最小蚁群系统（MAX-MIN Ant System， MMAS）。MMAS强化了对最优路径信息的反馈，只允许最优路径上的信息素更新。为避免某些路径被过分强调而陷入早熟，各路径信息素的取值被限制在区间[τmin，τmax]内，并将信息素初始值设定为τmax，以增加算法在初始阶段的寻优能力。MMAS将蚂蚁的搜索行为集中到最优解附近，提高了算法的收敛速度和求解质量。

Bullnheimer等[13]针对蚁群算法收敛速度慢的问题，将排序思想扩展到蚁群算法中，提出了基于排序的蚂蚁系统（Rank Based Ant System， RAS）。RAS按蚂蚁搜索的路径长度以递增顺序排列，并根据蚂蚁在排列中的次序对其赋予不同的信息素更新权值。蚂蚁构建的路径越短，信息素加权系数越大，以此增大最优解被选择的概率。

易正俊等[14]為进一步提高蚁群算法的全局搜索能力，在信息素更新规则中引入双曲正切函数作为动态因子。通过动态调整信息素更新权重，更好地反映了路径信息，在提高解的全局性和保证算法收敛速度间取得了较好平衡。

李新超等[15]针对基本蚁群算法中蚂蚁间协作的不足，提出一种基于互信息扩散的改进蚁群算法应用于短波网络频率指配问题。通过建立信息素扩散模型，加强近距离蚂蚁个体间的协作行为，提高了算法收敛速度。

此外，还有众多针对信息素调整策略的改进算法被不断提出。如采用双信息素更新策略[16]，引入惩罚函数降低较差路径的选择概率[17]，定义方向信息素以强化最优路径[18]等改进思想都在一定程度上提高了算法的求解性能。

2.2.2 搜索策略改进

对算法搜索策略的改进有利于增加路径选择的多样性，提高算法的全局搜索能力。研究者们从改进搜索策略出发，提出了一系列改进算法。

王丽美等[19]提出一种具有随机扰动特性的蚁群算法，通过改进状态转移概率，引入具有倒指数曲线特性的扰动因子，对算法解的产生赋予一定随机特性，使蚂蚁以一定概率随机选择一条信息素不是最多的潜在“最优”路径，提高路径选择的多样性。

张飞君等[20]从改进蚂蚁路径形成机制出发，基于蚂蚁正反向搜索相遇形成完整路径的原理，提出一种相遇蚁群算法。由两只蚂蚁相遇组合成一次周游路径，共同完成对一条路径的搜索，以扩大解的搜索空间，提高蚂蚁周游质量。

鲍文杰等[21]通过定义不同蚂蚁类别并采取不同的信息素调控机制，同时引入信息素更新权值和概率选择权值，提出一种更符合真实蚁群行为的多态蚁群算法。

其它的搜索策略改进思想包括：通过引入灾变算子使算法更好地跳出局部最优[22]、定义动态搜索诱导算子动态调节算法在不同寻优阶段的搜索方向[23]、采取非相交选择策略对相交路径的信息素进行差异化更新[24]等。这些对算法搜索策略的改进，提高了算法在搜索时的全局性，避免了算法的过早停滞。

2.2.3 与其它算法融合

蚁群算法具有较强的正反馈能力，通过信息素的积累更新快速收敛到最优解，但初始信息素不足，求解速度慢。利用蚁群算法与其它优化算法的良好结合性，学者们提出了诸多求解性能更好的融合算法。

张岩岩等[25]结合蚁群算法的并行搜索特点和人工免疫算法（Artificial Immune Algorithm， AIA）的快速收敛性，提出一种改进的人工免疫-蚁群混合算法应用于机器人路径规划问题。算法前期利用AIA快速随机的全局搜索能力，找出蚁群算法在不同路径环境下的最优参数组合，后期采用蚁群算法的正反馈性，通过信息素的积累和更新收敛于最优路径上，有效提高了算法的求解效率。

吴冬敏等[26]将蚁群算法与人工神经网络融合，利用蚁群算法优化训练BP神经网络权值，提出了具有神经网络广泛映射能力和蚁群算法快速收敛性能的混合优化算法。

柏建普等[27]提出一种遗传蚁群混合算法。算法前期利用遗传算法较好的全局搜索能力生成问题的初始可行解，使算法产生丰富的解空间，后期利用蚁群算法的分布式并行计算机制快速寻求问题的最优解，有效提高了算法的求解性能。

李擎等[28]提出了一种基于粒子群参数优化的改进蚁群算法，以粒子群算法中的粒子表征蚁群算法的一组参数，通过搜寻较优粒子实现对蚁群算法参数优化的目的。

蚁群算法融合改进的另一途径是结合局部搜索算法，实现对蚁群算法初始解的二次优化[29-31]。通过不同算法的融合，综合利用各种算法的优点，弥补单一算法的不足，以获得求解性能更好的混合算法，将更有利于算法在实际中的应用。

3 蚁群算法应用

蚁群算法最初应用于求解TSP问题，随着对蚁群算法研究的不断深入，其理论越来越丰富和完善。各种改进策略的不断提出，使蚁群算法更易于求解组合优化问题，算法的应用领域也由此得到了极大扩展，展现出这一新兴仿生优化算法的强大生命力及广阔的应用前景。以下简要介绍蚁群算法在几种典型问题中的应用。

3.1 蚁群算法在车间作业调度问题中的应用

车间作业调度问题 （Job-shop Scheduling Problem， JSP） 是实际生产中的一个多约束组合优化问题，蚁群算法应用于求解JSP问题时，通常将其转化为在解构造图中寻找最佳路径问题[32]。endprint

王丽红等[33]提出一种求解JSP的多态蚂蚁策略。通过定义不同蚂蚁类别并采取不同的信息素更新策略，同时结合改进的启发式信息计算转移概率，实现了对JSP问题的有效解决。

王硕等[34]提出一种改进的蚁群算法求解JSP问题。其采用基于机器的编码方式，在解码过程中采用替换式的转换方法，使搜索解进一步向可行解转化，并在状态转移规则中对目标工序采取限制策略，减少了不可行解的产生。

王艳红等[35]针对算法在求解阶段的不同收敛状况，采用两种不同的自适应信息素更新策略，使螞蚁迅速向全局最优解方向进行搜索，并引入“集中度”和“选择度”概念对解的分布作动态调整，在加速算法收敛和防止算法早熟停滞之间取得平衡。

蚁群算法在柔性作业车间调度、动态车间作业调度、混流装配线作业调度等更符合生产实际的复杂车间作业调度问题中也有着广泛应用[36-38]。

3.2 蚁群算法在车辆路径问题中的应用

车辆路径问题（Vehicle Routing Problem， VRP）是现代物流领域的核心问题，近年来，国内外学者利用蚁群算法对VRP问题开展了大量研究，提出了多种类型的蚁群算法求解方法[39]。

何文玲等[40]结合最大—最小蚁群算法和自适应策略，引入全局路径因素实现了对启发式因子的改进，并设定多种路径选择规则，建立了基于混合行为的蚁群算法求解车辆路径问题。

M Huang等[41]提出一种求解VRP问题的改进蚁群算法。通过设置路径信息素权重，并引入惩罚函数改进了信息素更新规则，提高了路径搜索的准确性。同时对蚂蚁搜索到的初始路线引入3-opt交换策略，实现了对初始规划路径的进一步优化。

刘霞等[42]针对车辆路径问题提出一种参数自适应的最大最小蚁群算法求解方法。针对客户点的不同分布特征，设定了顺序法和并行法两种路线构建策略，并对算法采取伪随机比例选取规则和自适应调整策略，在提高解空间多样性的同时，提高了算法收敛速度。

刘志硕等[43]在蚁群算法求解VRP问题基础上，通过定义蚂蚁吸引力，动态调整局部更新时释放的信息量，避免了因弧段间信息量差距过大对算法全局性搜索的限制；针对VRP中可行解结构不同于TSP问题的特点，提出一种近似解可行化策略实现了对车辆路径问题的有效求解。

车辆路径问题按照约束条件和研究重点不同，有着多种分类方式和扩展模型，如具有时间窗约束的车辆路径问题、带容量约束的车辆路径问题等。蚁群算法在VRP的扩展问题中也取得了较多研究成果[44-46]。

3.3 蚁群算法在机器人路径规划中的应用

机器人路径规划是指在未知环境中，机器人按照一定性能指标搜索一条从初始位置到目标位置的较优无碰路径[47]。近年来，国内外研究者们针对机器人路径规划问题，提出了多种路径规划策略，蚁群算法是一种常用的求解方法。

樊晓平等[48]基于距离信息构造了新的距离启发式信息概率函数，产生多条初始可行移动路径，并使用路径修正策略对弯曲路径作直线修正处理。同时，对算法中的状态转移规则采取比例选择策略，以更好地决定蚂蚁在下一时刻的移动路径。

潘杰等[49]针对路径规划中存在的路径尖峰问题，在基本蚁群算法中引入交叉变异算子，以丰富解的多样性，并利用简化和平滑算子对求得的初始规划路径作进一步优化，解决了路径中存在的尖峰问题。

张银玲等[50]基于栅格法建立了移动机器人工作环境模型，通过在算法中引入凸化处理策略和蚂蚁回退策略，对环境中的障碍物进行初始化处理，有效消除了凹形“陷阱”，一定程度上避免了路径规划中死锁现象的产生。

赵娟平等[51]结合差分演化算法，并引入混沌扰动因子实现了对信息素更新方式的改进，避免了搜索陷入局部极值；综合考虑路径长度、平滑度和危险度等指标，提出一种新的评价函数，克服了以路径长度为单一评价指标时会牺牲问题真实性的缺陷。

采用蚁群算法求解机器人路径规划问题，能够克服传统规划方法存在的诸多不足[52]。为了更好地解决机器人路径规划问题，研究者们不断提出一系列新的改进蚁群算法求解策略[53-54]。

此外，蚁群算法在图像处理[55]、网络路由[56]、控制参数优化[57]等领域也有着广泛应用，并取得了很大进展。

4 结语

本文在介绍蚁群算法原理的基础上，结合几种代表性的算法改进模型，对算法目前几个常见应用领域的研究现状进行了综述。理论和应用研究表明，经过不断地发展与完善，蚁群算法在理论和多个应用领域的研究都取得了突破性进展，显示出其在求解优化问题方面的优越性。

蚁群算法作为一种新兴的仿生优化算法，相比于其它优化算法，其研究时间并不长，各种改进策略虽在一定程度上改善了蚁群算法的求解性能，也仍存在一些不足有待进一步发展和完善。算法中对关键参数的选取及初始值的设定带有一定的经验性，缺乏科学的理论论证，在不同优化领域的应用也多是基于对问题的仿真实验。在现有研究成果的基础上，进一步认识算法各参数间的关联性及其对算法求解性能的影响，继续挖掘蚁群的其它行为，发展与其它新兴仿生算法（如萤火虫算法、混合蛙跳算法等）的智能融合等，将使蚁群算法的理论与应用更加完善和丰富。

参考文献：

[1] COLORNI A， DORIGO M， MANIEZZO V. Distributed optimization by ant colonies[C]. European Conference on Artificial Life，1991.

[2] 王永.多目标路由问题中的蚁群优化算法研究[D].长沙：湖南大学，2009.

[3] CAO Y， LEI L， FANG Y D. Application of ant colony algorithm to job-shop scheduling problem [J].Advanced Materials Research， 2012， 411：407-410.endprint

[4] 周之平，华路.复杂环境路径规划的改进蚁群算法[J].计算机工程与设计， 2011，32（5）：1773-1776.

[5] 陈宝钢，唐飞，蔡铁，等.改进蚁群算法MMAS在分类规则挖掘中的研究[J].计算机技术与发展，2014（6）：179-183.

[6] BONABEAU E， DORIGO M， THERAULAZ G. Inspiration for optimization from social insect behavior [J]. Nature， 2000，406（6791）：39.

[7] 弓晋丽.基于蚁群算法的城市物流配送路径优化问题的研究[D].西安：长安大学，2007.

[8] DORIGO M， MANIEZZO V， COLORNI A. The ant system： optimization by a colony of cooperating agents[C]. IEEE Transactions on Systems， Man， and Cybernetics. 1996：29-41.

[9] 刘瑞杰.蚁群算法及其应用研究[D].重庆：重庆大学，2012.

[10] BONABEAU E， DORIGO M， THERAULAZ G. Inspiration for optimization from social insect behavior [J]. Nature， 2000，406（6791）：39-42.

[11] GUTJAHR W J. A graph-based ant system and its convergence [J]. Future Generation Computer Systems， 2000，16（8）：873-888.

[12] STUTZLE T， HOOS H. MAX-MIN Ant system and local search for the traveling salesman problem[C]. IEEE International Conference on Evolutionary Computation. IEEE， 1997：309-314.

[13] BULLNHEIMER B， HARTL R F， STRAUSS C. A new rank based version of the ant system—a computational study[J]. Central European Journal of Operations Research， 1999，7（1）：25-38.

[14] 易正俊，李勇霞，易校石.自適应蚁群算法求解最短路径和TSP问题[J].计算机技术与发展，2016，26（12）：1-5.

[15] 李新超，贺前华，李艳雄.基于互信息扩散蚁群算法的短波频率优化指配[J].华中科技大学学报：自然科学版，2016，44（4）：6-11.

[16] MOU L M. A novel ant colony system with double pheromones for the generalized TSP[C]. Seventh International Conference on Natural Computation， 2011：1923-1928.

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

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

[19] 王丽美，王龙香，郑程友.利用随机扰动特性的集合覆盖蚁群算法识别tag SNPs[J].宜宾学院学报，2015，15（6）：81-85.

[20] 张飞君.新型蚁群算法及其在边坡工程中的应用研究[D].武汉：武汉工业学院，2009.

[21] 鲍文杰，朱信忠，赵建民，等.加权值多态蚁群算法[J].软件工程，2016，19（4）：1-4.

[22] 熊伟清，周扬，魏平.具有灾变的动态蚁群算法[J].电路与系统学报，2005，10（6）：98-101.

[23] 游晓明，刘升，吕金秋.一种动态搜索策略的蚁群算法及其在机器人路径规划中的应用[J].控制与决策，2017，32（3）：552-556.

[24] 王越，黄丽丰.一种基于无相交搜索策略的蚁群算法[J].重庆理工大学学报，2011，25（4）：65-69.

[25] 张岩岩，侯媛彬，李晨.基于人工免疫改进的搬运机器人蚁群路径规划[J].计算机测量与控制，2015，23（12）：4124-4127.

[26] 吴冬敏，邵剑平，芮延年.基于蚁群算法和神经网络的数控机床故障诊断技术研究[J].机械设计与制造，2013（1）：165-167.

[27] 柏建普，吴强.蚁群混合遗传算法的研究及应用[J].电子科技，2011（4）：20-23.

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

[29] 霍艳丽.面向路径规划的多策略和变异算子蚁群算法研究[D].南昌：南昌大学，2015.

[30] WEI Z L， LI Y G. An ant colony algorithm with Tabu search and its application[C]. Fourth International Conference on Intelligent Computation Technology and Automation. IEEE Computer Society， 2011：412-416.endprint

[31] 贾瑞玉，马文华.基于邻域搜索的改进最大最小蚁群算法[J].计算机仿真，2014，31（12）：261-264.

[32] 姬耀锋，党培，郭小波.基于蚁群算法的车间作业调度问题研究[J].计算机与数字工程，2011，39（1）：4-6.

[33] 王丽红.蚁群算法及其在车间调度中的应用研究[D].合肥：合肥工业大学，2009.

[34] 王硕. 基于改进蚁群算法的作业车间调度研究[D].上海：华东理工大学，2013.

[35] 王艳红，王文霞，于洪霞，等.一类求解作业车间调度问题的动态平衡自适应蚁群算法[J].计算机集成制造系统，2013（10）：2521-2527.

[36] RUI Z， SHILONG W， ZHEQI Z， et al. An ant colony algorithm for job shop scheduling problem with tool flow [J]. Proceedings of the Institution of Mechanical Engineers Part B Journal of Engineering Manufacture， 2014，228（8）：959-968.

[37] 范华丽，熊禾根，蒋国璋，等.动态车间作业调度问题中调度规则算法研究综述[J].计算机应用研究，2016，33（3）：648-653.

[38] 薛琴微，兰秀菊，陈呈频.基于蚁群算法的混流装配线排序研究[J].轻工机械， 2010， 28（5）：107-112.

[39] 卞晨，趙建东.车辆路径问题的发展及其应用[J].电脑知识与技术，2016，12（26）：79-80.

[40] 何文玲，倪郁东，汪婷婷.基于混合行为蚁群算法的车辆路径问题[J].合肥工业大学学报：自然科学版，2014（7）：883-887.

[41] HUANG M， DING P. An improved ant colony algorithm and its application in vehicle routing problem [J]. Mathematical Problems in Engineering， 2013，2013（6）：1-9.

[42] 刘霞，杨超.最小-最大车辆路径问题的蚁群算法[J].解放军理工大学学报：自然科学版，2012（3）：336-341.

[43] 刘志硕，申金升，柴跃廷.基于自适应蚁群算法的车辆路径问题研究[J].控制与决策，2005（5）：562-566.

[44] 马建华，房勇，袁杰.多车场多车型最快完成车辆路径问题的变异蚁群算法[J].系统工程理论与实践，2011，31（8）：1508-1516.

[45] 李琳，刘士新，唐加福.改进的蚁群算法求解带时间窗的车辆路径问题[J].控制与决策，2010，25（9）：1379-1383.

[46] YU S P， LI Y P. An improved ant colony optimization for VRP with time windows [J]. Applied Mechanics & Materials， 2013，266：1609-1613.

[47] 余勇.基于改进蚁群算法的移动机器人路径规划研究[J].机械传动，2016（7）：58-61.

[48] 樊晓平，罗熊，易晟，等.复杂环境下基于蚁群优化算法的机器人路径规划[J].控制与决策，2004（2）：166-170.

[49] PAN J， WANG X S， CHENG Y H. Improved ant colony algorithm for mobile robot path planning [J]. Journal of China University of Mining & Technology， 2012，41（1）：108-113.

[50] 张银玲，牛小梅.蚁群算法在移动机器人路径规划中的仿真研究[J].计算机仿真，2011（6）：231-234.

[51] 赵娟平，高宪文，符秀辉，等.移动机器人路径规划的改进蚁群优化算法[J].控制理论与应用，2011（4）：457-461.

[52] 朱大奇，颜明重.移动机器人路径规划技术综述[J].控制与决策，2010，25（7）：961-967.

[53] 刘建华，杨建国，刘华平，等.基于势场蚁群算法的移动机器人全局路径规划方法[J].农业机械学报，2015，46（9）：18-27.

[54] WANG H， JUN X U， ZHAO H， et al. Mobile robot path planning based on smoothing ant colony algorithm[J]. Journal of Yanshan University， 2017.

[55] ZHANG C， PENG H. Image edge detection based on hybrid ant colony algorithm [J]. Scientific Bulletin of National Mining University， 2016.

[56] 戴天虹，李昊.基于改进蚁群算法的无线传感器网络路由的优化[J].计算机测量与控制，2016，24（2）：321-324.

[57] 陈书谦，张丽虹.蚁群算法在PID控制器参数优化中的应用研究[J].计算机仿真，2011，28（1）：238-241.

（责任编辑：黄 健）endprint