张松灿，普杰信，司彦娜，孙力帆

1.河南科技大学 信息工程学院，河南 洛阳471023

2.河南科技大学 电气工程学院，河南 洛阳471023

1 引言

路径规划是移动机器人自主导航最关键的一个环节，也是机器人领域的研究热点[1]。其主要目的是在有障碍物的工作环境中，依据一定的性能指标（行走路径最短、规划时间最短及能耗最少等），在模型空间中找到一条从起始位置到目标位置的安全无碰撞的最优或次优路径[2]。

经过几十年的发展，国内外学者提出了许多富有成效的路径规划方法，如A*算法[3]、人工势场法[4]、神经网络[5]、遗传算法[6-7]、模糊逻辑[8]、粒子群优化算法[9]等。这些方法在移动机器人路径规划中取得较好的效果，但面对复杂环境时依然存在一定的缺陷。

蚁群算法是模拟自然界中蚂蚁群体觅食行为而提出的一种启发式搜索算法，具有正反馈、并行计算、鲁棒性好等特点，因此许多学者将蚁群算法用于机器人的路径规划并取得较好的效果[10-21]。蚁群算法具有较快的收敛速度，但也存在算法搜索停滞和易陷入局部最优等问题。针对这些问题，许多学者对蚁群算法的结构设计、运行机制、参数优化等进行深入研究并提出了许多改进策略。

本文主要讨论蚁群算法在移动机器人路径规划中的研究进展。首先介绍蚁群算法的工作原理及缺陷分析；然后根据算法的运行机理，从单蚁群、多蚁群及融合蚁群算法等方面分析各种改进策略，旨在为蚁群算法在移动机器人路径规划的进一步研究提供依据；最后对蚁群算法在移动机器人路径规划的未来研究与发展进行了展望。

2 蚁群算法的工作原理及缺陷分析

2.1 蚁群算法的工作原理

Ant System（蚂蚁系统）是意大利学者Dorigo M等受自然界中蚂蚁种群的觅食行为特征启发而设计的一种智能仿生优化算法[22]。Ant System是基本蚁群算法，为其他蚁群算法提供了基本框架，其基本结构如图1所示。

图1 蚂蚁系统的基本结构

蚁群算法用于机器人路径规划时主要由初始化、解构建和信息素更新三部分组成。

步骤1 初始化。包括信息素初始化，启发信息初始化，以及种群规模、信息素挥发率等参数初值的设置。

步骤2 解构建。解构建是蚁群算法迭代运行的基础，是算法最关键的环节，主要内容是在问题空间依据状态转移规则如何构建候选解。当用于路径规划时，解构建主要是根据状态转移规则选择下一路径点，最终形成完整路径。

步骤3 信息素更新。解构建完成后需要进行信息素更新，信息素更新包括两个环节。（1）信息素挥发，用于降低路径上的信息素，减小信息素对未来蚂蚁行为的影响，增加算法的探索能力；（2）信息素释放，蚂蚁在其所经过的路径上释放信息素，加强对蚂蚁未来选择该路径的影响，增强算法的开发能力。

步骤4 重复步骤2和步骤3，直到满足终止条件。

蚂蚁系统对所有的路径都进行信息素更新，既具有较好的优化能力，又能保持良好的种群多样性，但是由于缺乏对最优路径的开发，降低了算法的收敛速度。

2.2 蚁群算法的缺陷分析

蚁群算法在机器人路径规划领域得到了广泛的应用，但是存在收敛速度慢、易陷入局部最优、早熟收敛等问题，分析原因如下：

（1）收敛速度慢。蚁群算法中信息素初值相同，选择下一个节点时倾向于随机选择。虽然随机选择能探索更大的任务空间，有助于找到潜在的全局最优解，但是需要较长时间才能发挥正反馈的作用，导致算法初期收敛速度较慢。

（2）局部最优问题。蚁群算法具有正反馈的特点，初始时刻环境中的信息素完全相同，蚂蚁几乎按随机方式完成解的构建，这些解必然会存在优劣之分。在信息素更新时，蚁群算法在较优解经过的路径上留下更多的信息激素，而更多的信息激素又吸引了更多的蚂蚁，这个正反馈的过程迅速地扩大初始的差异，引导整个系统向最优解的方向进化。虽然正反馈使算法具有较好的收敛速度，但是如果算法开始得到的较优解为次优解，那么正反馈会使次优解很快占据优势，使算法陷入局部最优，且难以跳出局部最优。

（3）优化能力问题。蚁群算法中参数众多并且具有一定的关联性，虽然蚁群算法在很多领域都有广泛应用，但是参数选择更多是依赖经验和试错，不恰当的初始参数会减弱算法的寻优能力。当进行路径规划时，为避免形成环形路径或者重复访问某些节点在算法中设置禁忌表，但是禁忌表很容易造成“死锁”现象，减少种群中的有效蚂蚁数量，降低算法的优化效率。

（4）种群多样性与收敛速度的矛盾。种群多样性对应于候选解在问题空间的分布。个体分布越均匀，种群多样性就越好，得到全局最优解的概率就越大，但是寻优时间就越长；个体分布越集中，种群多样性就越差，不利于发挥算法的探索能力。正反馈加快了蚁群算法的收敛速度，却使算法较早地集中于部分候选解，因此正反馈降低了种群的多样性，也不利于提高算法的全局寻优能力。

3 单蚁群算法的改进研究

许多学者对上述问题进行了深入研究，寻求降低其复杂度及深度的改进优化算法。改进算法主要从结构改进、参数选取与优化、信息素初始化与更新规则等方面提高算法的优化能力，为后续算法的改进提供理论基础。

3.1 蚁群算法的结构改进

针对基本蚁群算法存在的问题，许多学者从算法框架和结构上提出了许多富有成效的改进措施，如Ant Colony System[23-24]（蚁群系统，ACS）、Max-Min Ant System（最大最小蚂蚁系统，MMAS）[25]、Ant System with elitist strategy（带精英策略的蚂蚁系统，ASelite）[26]、Ant system with elitist strategy and ranking（基于排序的蚂蚁系统，ASrank）[26]等经典改进算法，这些改进算法有效地提升了优化能力，但是采用一种固定模式去更新信息素和概率转移规则，缺乏灵活性，未能解决算法的早熟收敛问题。除此之外，针对具体应用场合，许多学者借鉴已有改进策略提出了许多新的改进方法。

陈雄等[27]在蚁群算法中引入信息素限定措施，并提出了自适应信息素挥发系数的方法来解决蚁群算法中的停滞现象，显著提高了算法的搜索能力。Dorigo等提出了元启发式蚁群优化算法（Ant Colony Optimization Meta Heuristic，ACO-MH），为求解复杂问题提供了通用算法框架[28]。为了解决ASelite算法易陷入局部最优解的缺陷，文献[29]将ASelite算法与插入、交换算子融合，提出混合精英蚂蚁系统HEAS（Hybrid Elite Ant System），在增强最优路径信息素的同时，还减少最差路径上的信息素，既实现了较好的寻优效果，又能有效地逃离局部最优。文献[30]在基本蚁群算法中引入精英蚂蚁策略和最大最小蚂蚁机制，更新精英蚂蚁的信息素，在寻优能力和收敛速度之间保持了较好的平衡。文献[31]在蚁群算法中加入回退和死亡策略，增加蚂蚁到达目标位置的概率，减小无效蚂蚁对信息素的影响，提高了算法的优化能力。文献[32]借鉴增强学习中的概念提出了Ant-Q 算法，采用伪随机比例状态转移规则构造候选解，在进行全局信息素更新中强化精英蚂蚁对信息素的影响，加快算法的收敛。文献[33]针对多无人机协调轨迹规划提出了一种新的最大-最小自适应蚁群优化方法，设置最小信息素和最大信息素路径，并成功地用于多无人机协调轨迹重规划。

上述措施主要是针对基本蚁群算法的结构改进，有效增强算法的寻优能力，加快收敛速度，避免早熟收敛。从本质上来说，加大迭代过程中最优解的利用[32]、弱化最差解的影响[29]能显著改善算法的收敛情况，但是也带来局部最优问题。为此，算法改进时还应考虑局部最优问题，常见解决方法包括限定信息素的范围[25]、改进信息素更新[27]、改变状态转移规则[23-24，32]及加入扰动项[29]等。算法结构的改进有助于深入理解蚁群算法的运行机制，为进一步的改进优化提供理论基础，但是已有模型的普适性并不强，需针对具体应用去改进算法结构。此外，蚁群算法仅仅是根据蚂蚁的觅食行为启发而来，然而蚂蚁群体还有其他复杂的行为可以借鉴，如：侦查、筑巢等[21]，将这类行为与觅食行为相结合，有望建立新的算法结构，进一步提升算法的优化效率。

3.2 蚁群算法的参数优化

算法参数对蚁群算法的寻优性能具有重要的影响，由于蚁群算法参数多且参数之间存在紧密的耦合作用，确定最优的算法参数成为一个极其复杂的问题。虽然有文献给出参数选取和优化方法，但是大多是依经验而定，缺乏理论依据。

Duan 等[34]分析了蚁群算法各个参数对优化性能的影响，通过实验得出各个参数的最优取值范围，给出了参数设置的三步优化方案。文献[27]分析了信息素挥发系数对蚁群算法优化能力的影响，提出自适应信息素挥发系数，提高了算法的全局搜索能力。为了避免陷入局部最优，Jiao 等[35]提出一种用于路径规划的多态蚁群优化算法，采用自适应状态转移策略和自适应信息素更新策略确保信息素强度与启发信息在算法迭代过程中的相对重要性。江明等[36]按照设定的参数变化规律自适应调整信息素挥发系数来提高算法的全局寻优能力，避免算法陷入局部最优。Sahu 等[14]提出一种自适应蚁群优化算法用于机器人的路径规划，在计算信息素增量时考虑每只蚂蚁走过的路径长度与所用时间，在最优路径与规划时间之间做到均衡。针对相邻栅格的启发权值差异不明显导致搜索效率较低的问题，文献[37]根据栅格到目标点的位置调整状态转移中的启发信息项，不仅提高了搜索速度，而且保持了选择的多样性，但是该调整方法与目标点位置有关，缺乏灵活性。Akka等[18]改进了状态转移公式，优先选择具有更多出口的邻节点作为下一节点，增强了种群的多样性，避免算法过早收敛。卜新苹等[38]以非均匀环境模型为基础，在状态转移规则中引入目标距离和障碍物距离等启发式信息，提出一种距离启发搜索和信息素混合更新的蚁群算法，使得算法具有较好的适应性和更快的收敛速度。文献[12]把A*算法概念引入到蚁群算法中，将节点处的估计值作为启发信息，提高了算法收敛速度。文献[39]改进了信息素初始化方法，动态调整信息素启发因子与期望启发因子，有效减少了蚂蚁前期到达最优路径的迭代次数，但是动态调整策略需要人为确定算法的运行情况，缺乏灵活性，而信息素初始化的改进能加快算法前期的搜索效率，但是却加大算法早熟的风险。刘振等[40]提出一种多粒度蚁群算法，对每个蚂蚁都设置不同的窗口宽度，并根据寻优情况自适应改变蚁群规模，所提算法应用于UAV的多机协同路径规划，能有效规避突发威胁，提高规划效率。

上述研究通常是根据蚁群算法的优化特征进行参数优化，如文献[27，36]采用的动态调整信息素挥发系数、文献[35]采用的自适应信息素更新等，这些改进策略将算法参数由固定不变模式改为动态调整模式，用较小的计算负担提高算法的优化性能，降低算法对参数的敏感性，但是这些动态调整通常是人为设定的参数变化规律或者引入新的参数来划分不同的运行过程，然而算法的迭代优化过程与设定的参数变化规律是否相吻合并没有得到保证，使得这类改进缺乏适应性。也有学者通过改进状态转移规则[18，37-38]，在保持种群多样性基础上加快算法的收敛速度。

3.3 信息素初始化方法的改进

传统蚁群算法均匀初始化信息素值，该方法简单易行，但在算法初期存在搜索的盲目性，用于路径规划时容易出现死锁现象，影响算法的收敛速度与优化能力。为解决这一问题，许多学者采用不均匀分配初始信息素的方式，加强先验路径信息指导全局寻找最优路径能力。不均匀分配初始信息素的方法可以分为两类：

（1）根据任务和最优路径的特征进行信息素初始化。文献[41]根据下一节点中邻接的障碍栅格个数提出了一种非均匀信息素初始化方法，即下一节点离障碍物越近，那么该路线的初始信息素越小，反之就越大，指导蚂蚁快速行进和安全避障，加快算法收敛速度。王晓燕等[42]根据零点定理提出不均衡分配初始信息素的方法，不同位置的栅格赋予不同的初始信息素，降低蚁群搜索的盲目性，提高算法的搜索效率，然而该方法将起点与终点组成的矩形区域作为有利区域，区域内的信息素依然相同，改进效果有限，也不适用于复杂地图。李龙澍等[43]在已经明确起点和终点相对位置的情况下，依据起点与终点之间的方向，对每条路径上的初始信息素进行区分优化，越朝向终点位置的地方初始信息素浓度越高，引导蚂蚁朝着正确的大方向行进，缩减搜索初期的时间消耗。文献[44]采用当前节点、下一个节点以及起点与终点之间的距离等因素计算信息素初值，得到了不均匀分布的初始信息素。

（2）其他优化算法得到的初始路径作为信息素初值的参考。文献[45]利用粒子群算法得到的初始结果去初始化蚁群算法的信息素分布，采用分布式技术实现蚂蚁之间的并行搜索。文献[46]将遗传算法得到的路径信息作为一部分初始信息素，与原信息素叠加共同构成信息素初值，取得较好的寻优效果。人工势场法模型简单，实时性强，有学者将其用于信息素的初始化。王芳等[47]将人工势场法的规划结果作为先验知识，对蚁群初始到达的栅格进行邻域信息素的初始化，并通过构建势场导向权改变蚂蚁概率转移函数，提高了路径搜索效率。罗德林等[48]利用机器人受到的虚拟人工势场力及机器人与目标之间的距离构造机器人避障和移动的综合启发信息，将蚁群算法和人工势场法进行有效的结合，提高了常规蚁群算法对最优路径的搜索效率。

上述两类信息素初始化改进方法有效地减少算法初期由于盲目搜索导致的路径交叉、效率低下等问题。基于任务和最优路径特征的改进方法，计算量小，缩减搜索初期的时间消耗，但是其适应性依赖于环境的特征及任务要求，当环境比较复杂时，其效果并不明显。第二种改进措施能有效改善信息素的初始分布，但是需要消耗一定的预处理时间进行初始路径规划，并不适用于实时应用场合。此外，上述两类改进策略能改变信息素初值的分布，尤其是倾向于最优路径的不均匀分布，虽然加快了算法的收敛速度，但是在正反馈的作用下会使蚁群算法更容易陷入局部最优，同时降低了种群的多样性，不利于得到全局最优解。

3.4 信息素更新规则的改进

信息素更新是蚁群算法最重要的一个环节，包括全局信息素更新和局部信息素更新。这两种更新都包括信息素挥发和信息素增强。信息素挥发有助于探索问题空间的未知区域，降低陷入局部最优的概率。信息素增强主要是强化蚂蚁所经过路径上的信息素值，增大对后续蚂蚁的吸引力。信息素增强需要考虑对哪些路径进行信息素增强，是全部路径，还是最优路径或次优路径等。

文献[44]除正常的信息素更新外，引入最好与最差解概念，强化最好解所在路径上的信息素，减小最差解路径上的信息素，加快算法的收敛速度。柳长安等[37]参考狼群分配原则对信息素进行更新，增大局部最优路径的信息素量，同时去除局部最差路径上蚂蚁释放的信息素，避免算法陷入局部最优，但是该方法缩小了算法的搜索空间，影响了算法的探索能力。针对蚁群算法中蚂蚁之间协作不足的问题，黄国锐等[49]通过建立信息素扩散模型，提出一种基于信息素扩散的蚁群算法，使相距较近的蚂蚁个体之间能更好地进行协作，有效提高算法的收敛速度和寻优能力。文献[50]将粒子群算法的局域搜索和全局搜索机制与蚁群算法的信息素更新策略相结合，有效解决了蚁群算法的搜索停滞与早熟收敛问题。赵娟平等[51]用差分演化算法进行信息素的更新，同时在信息素更新环节加入了混沌扰动因子以增强算法的随机性能，使其有效跳出局部最优点和避免算法停滞。曾明如等[52]提出一种自动调整步长参数的多步长蚁群算法，根据多步长蚁群算法的特点，设计了局部信息素更新策略对路径节点之间的栅格节点进行信息素更新，使得改进算法更高效，提高了机器人的路径规划性能。顾军华等[53]提出了一种多步长改进蚁群算法，在状态转移概率规则中加入拐点参数，改善了路径的平滑度，设计了新的信息素奖惩机制，有效地避免局部最优，提高算法的收敛速度。文献[10]提出了一种自由步长的蚁群算法，并设计了相应的局部信息素更新规则，仿真表明该算法寻得的路径更短，收敛性更好。文献[54]改进了蚁群算法的全局信息素更新策略和信息素增量计算方法，提高算法的运行效率，减小了陷入局部最优的可能性。陈超等[55]改进蚁群算法的启发函数和信息素更新方式来提高三维场景下移动机器人路径规划的实时性。

文献[37，44]采用强化最优解的引导作用、减小最差解路径上的信息素来加快算法的收敛速度，但是降低了算法的探索能力，不利于最优解的获取。文献[50-51]借鉴其他智能算法的运行机制改进蚁群算法的更新规则，有效解决了蚁群算法早熟收敛问题，但是算法结构复杂，耗时更多。前述改进措施通常将蚂蚁的移动步长局限于单个栅格，规划的路径较长、平滑性较差等。文献[52，56]采用多步长或者可视范围内自由步长[10]的蚁群算法，这类方法能提高路径的平滑度，进一步减小路径长度，但是信息素更新规则需要进一步展开研究，同时还引入了新的碰撞判断问题。

4 多蚁群优化算法的研究与发展

蚁群算法由初始化、解构建和信息素更新三部分组成，每一部分对算法都有重要的影响。目前大多数单蚁群算法的改进都是从这几方面展开，以解决收敛速度和多样性的矛盾，但是这种改进是一种折中方案，未能充分发挥蚁群算法的优化效率。与此同时，一些学者对蚁群算法的架构组成、信息交换模式等展开研究，提出多蚁群优化算法。采用多个蚁群的合作既能保持种群的多样性，又能提高蚁群算法的优化能力。

在多蚁群优化算法中，蚁群个数大多采用两个，采用更多的蚁群个数并不能显著提升优化性能反而增加了运行时间。根据多蚁群算法中各个蚁群的特征，可分为同构多蚁群算法和异构多蚁群算法。为了充分发挥蚁群算法的优化性能，大多采用异构多蚁群算法，即各个蚁群算法结构不同。同时多蚁群算法中各个蚁群的运行机制也有所不同。根据各个蚁群的运行机制，可将多蚁群优化算法分为以下两种。

4.1 基于顺序运行的多蚁群算法

顺序运行的多蚁群算法通常是将一个蚁群分为两个部分，分别置于起点与终点，顺序执行各个蚁群算法；或者是按照分层设计的思想将多个蚁群置于不同的规划层，每一层执行不同的功能。这两种设计方法一般是通过信息素矩阵进行种群间的信息交换。

王沛栋等[57-58]通过蚂蚁的折返搜索策略完成了最优路径搜索，增强蚂蚁搜索的多样性，避免算法停滞；通过优化禁忌表提高蚂蚁的搜索能力，利用双向蚂蚁群体的不同搜索策略提高算法收敛速度。文献[17]提出一种用于机器人路径规划的双层蚁群算法，利用精英蚁群算法获得初始无碰路径，然后采用基于蚁群算法的转折点优化方法对初始路径从路径长度、平滑性以及安全性等方面进一步优化，实验表明该算法能有效地得到无碰最优路径。许凯波等[59]设计了基于双层蚁群算法的机器人路径规划方法，每次迭代时将基本蚁群算法找到的最优路径向外扩展一定的距离构造一个小环境，采用蚁群算法在此空间内进行寻优，如果找到更优的路径，则更新路径并执行信息素二次更新策略，虽然提升了寻优性能，但是限制了算法的探索能力，不利于获取最优解。朱庆保等[60]将蚁群分为两个部分，分别置于起点与终点，蚁群对向移动，利用蚂蚁相遇判断准则快速构建可行路径，加快寻路时间。文献[61]设计了新的蚂蚁相遇判断准则，通过控制方向相反的两组蚂蚁同时进行路径搜索，充分发挥蚁群的合作性，提高了算法寻优速度。文献[62]提出基于改进蚁群算法的多批次协同三维航迹规划算法，引入蚂蚁子群间多约束条件下的协同进化策略，有效解决了多无人机多批次协同三维航迹规划。

4.2 基于并行运行的多蚁群算法

在并行运行的多蚁群算法中，各个蚁群同时运行，蚁群间的信息交换策略是并行多蚁群优化算法的关键，包括信息交换的内容、方式、频率以及交换时机等。

Ellabib 等[63]提出了多蚁群算法的信息交换策略并按照搜索多样性对各种交换策略进行了评估。文献[64]提出了并行蚁群算法的信息交流策略，各种群自适应地选择信息交换对象，根据解的分布情况自适应地确定信息交流的时间，以取得收敛速度和多样性之间的平衡；信息交换后，根据信息素均匀度采用自适应更新策略进行信息素更新，避免了蚁群算法的早熟和局部收敛。张鹏等[65]利用蚁群间的相似度自适应选择最互补的蚁群进行信息交换，以加强蚁群间的协作，增强算法逃离局部最优的能力。Lee[66]设计了一个异构蚁群组成的路径规划器（HAB-PP），不同种类的蚁群有不同的可视范围与运动速度，并修改了状态转移规则和信息素更新方法，仿真结果验证了算法的有效性。

在多蚁群算法中，每个种群可采用不同的类型，具有不同的状态转移规则和信息素更新机制，经过种群间的信息交换，既能保持蚁群的多样性，又可改善算法的优化效率。文献[17，59]所设计的双层蚁群算法虽然提升了算法的寻优能力，但是却需要一定的时间进行二次优化，导致优化效率不高。文献[60-61]将蚂蚁分组同时进行相向搜索路径，蚂蚁相遇则构成一条路径，但是需要设计合适的相遇判断准则，否则无法找到完整路径，复杂环境下的规划效果并不理想。并行运行的多蚁群算法[64-65]能有效平衡收敛速度和种群多样性之间的矛盾，有利于跳出局部最优，但信息交换策略需要正确设计与优化，不合适的信息交换策略反而会恶化蚁群算法的性能。

5 融合蚁群算法的研究与发展

融合蚁群算法主要是蚁群算法与其他优化算法相混合，弥补蚁群算法的不足，提高算法的优化性能。大量文献表明，融合蚁群算法更易于获得全局最优解，避免局部最优，有效平衡算法收敛速度和种群多样性的矛盾。根据优化方法的功能可将融合蚁群算法分为三类。

5.1 优化方法用于信息素初始化、更新或状态转移规则的优化

刘建华等[67]在蚁群算法搜索过程中加入人工势场局部搜索寻优算法，使蚁群倾向于具有高适应值的子空间搜索，减少盲目搜索引起的局部交叉路径及“迷失”蚂蚁的数量，提高了对障碍物的预避障能力。文献[68]将路径规划分为两步，首先采用遗传算法生成初始路径，将较优路径作为蚁群算法信息素初始化的参考信息，减少蚁群算法搜索初期的盲目性，然后利用蚁群算法对初始路径进一步优化，仿真结果表明改进算法能避免局部最优，加快算法的收敛速度。文献[69]利用粒子群算法和遗传算法的随机、快速和全局性，通过粗略搜索获得一系列次优解用于蚁群算法的初始信息素分布，然后利用蚁群算法获取最优解。赵娟平等[51]采用带有信息素下限的蚁群优化算法，结合差分演化算法实现信息素更新的概率型交替，提高算法的协作交流，既保证了算法的收敛速度又确保了算法的多样性，在一定程度上防止陷入局部最优。

5.2 优化方法用于蚁群算法的参数优化

Mahi 等[70]设计了一种基于粒子群和蚁群的混合算法，用粒子群算法去优化蚁群算法的主要参数。王雪松等[71]提出一种基于图知识迁移的蚁群算法参数选择方法，能够快速得到优化参数，提高了蚁群算法的适应能力。文献[72]用节点间的采样信息替代欧氏距离表示的启发函数，并结合Voronoi 分割方法以增加多个海洋自主航行器（multiple Autonomous Marine Vehicles，AMV）自适应海洋采集任务的覆盖面，减小了算法的优化时间。针对无人战斗机的三维路径规划，Duan等[20]提出了一种混合蚁群优化和差分进化模型，将蚂蚁种群分为几个子种群，利用DE 的突变操作使得种群间的信息素分布更合理，在保持蚁群算法强鲁棒性的同时，加快了全局收敛速度。

5.3 优化方法产生初始路径

潘杰等[73]在蚁群算法中融入遗传算子，利用交叉与变异操作来扩大解的搜索空间，提升解的全局性。文献[74]将路径规划分为两个阶段，先由Dijkstra 算法规划出次优路径，再用蚁群算法优化这些次优路径以获得最优路径。文献[75]将问题求解分为两个阶段：第1 阶段利用快速反向梯度法获取可能的优化解；第2阶段采用ACO算法进一步提高解的质量。杜振鑫等[76]提出一种基于蚁群算法和模拟退火算法的融合算法，每轮迭代后的路径用模拟退火进行优化，使信息素释放更好地反映路径的质量；同时退火思想还用于信息素更新，有效避免算法早熟。针对自主水下机器人在全局路径规划时存在搜索效率低、时间较长等问题，潘昕等[77]提出了一种遗传和蚁群算法的混合算法，提高了两种基本算法的融合效率，在保持搜索精度的同时，有效提高算法的收敛速度。

蚁群算法与其他方法相融合，具有强鲁棒性、寻优速度快、收敛性强等特点。虽然这些融合策略可以取长补短、优势互补，有效提升蚁群算法的寻优能力，但是在一定程度上增加算法的复杂程度，同时也需要更多优化时间。

6 蚁群算法的改进总结与展望

6.1 蚁群算法的改进总结

蚁群算法在移动机器人路径规划中得到广泛应用，为了进一步提升蚁群算法的全局寻优能力，许多学者提出了许多富有成效的改进措施，将上述的内容进行总结，如表1所示。

对蚁群算法改进时，除了提升全局优化能力外，还需要处理正反馈带来的局部最优问题。避免陷入局部最优的常用方法是在算法中保持一定的随机性或者添加扰动信息，这些措施在一定程度上能避免算法陷入局部最优，但是却改变蚁群算法正常的迭代优化过程，降低了算法的收敛速度。为了便于对比分析，将常见的逃离局部极值方法总结，如表2所示。

6.2 蚁群算法未来的研究与展望

蚁群算法具有隐含并行性、正反馈、强鲁棒性及易与其他智能方法相结合等优点，自提出以来在众多领域得到了广泛应用。但是与遗传算法、粒子群算法等方法相比，蚁群算法的研究还远不成熟，实际应用方面也尚未挖掘出其真正潜力，还有很多富有挑战性的课题亟待解决，主要体现在以下几个方面：

（1）蚁群算法的理论研究

蚁群算法作为一种概率搜索算法，从数学上对其正确性和可靠性进行证明比确定性算法更困难。已有方法过于复杂且要求严格，寻找新的理论分析方法是一个亟待解决的问题。此外，蚁群算法的参数设置与优化、信息素分配策略等大多凭借经验或依靠实验人为确定，缺少数学证明和普适性，这些问题有待深入研究。

表1 蚁群算法提升全局寻优能力的方法及优缺点

表2 蚁群算法逃离局部极值的方法及优缺点

（2）蚁群算法的多样性与收敛速度研究

多样性与收敛速度本质上对应于蚁群算法中的探索与利用。已有许多学者尝试解决种群的多样性和算法收敛速度的矛盾，但是收敛速度受诸多因素影响且与问题密切相关，种群多样性的准确描述也有待进一步研究，因此如何解决种群多样性与收敛速度的矛盾值得深入研究与讨论。

（3）蚁群算法的集成研究

利用算法的互补性，将蚁群算法与其他优化方法相融合，解决蚁群算法的缺陷。由于优化算法类型多，特点不一，新智能算法也不断涌现，如何选择合适的融合算法，设计相应的融合策略及运行机制，充分发挥各自优势，需要深入的研究与分析。此外融合算法虽然能取得较好的优化效果，但是融合策略及运行机制缺乏必要的理论基础，对此进行研究有助于融合算法的发展。

（4）多蚁群算法的进一步研究

多蚁群算法已在移动机器人路径规划中得到了应用，但是依然有许多需要进一步研究的内容。采用多蚁群算法，既能获得比单蚁群更好的多样性，又可以提高蚁群的优化能力。单蚁群算法改进时侧重于算法的结构设计、参数优化等，而多蚁群算法的研究侧重于算法的整体架构设计与群间的协调优化。因此在进行多蚁群算法的研究时，除已有的单蚁群优化策略外，还需要深入研究多蚁群的整体框架与运行机制、蚁群特征、蚁群间的信息交换策略等对优化性能的影响，这也是蚁群算法未来的一个重要研究内容。

（5）扩展蚁群算法的应用范围

在高维空间、多机器人协同等领域应用移动机器人时也需要进行路径规划，而这些场合具有不同的特点与需求，如何将蚁群算法有效运用在这些场合需要深入研究。此外，机器人的工作环境复杂多变，如何提高蚁群算法在动态环境甚至极端环境时的路径规划实时性和规划效率也是今后的重要研究内容。

7 结束语

本文介绍了蚁群算法的工作机制，分析了蚁群算法缺陷的原因。针对蚁群算法在移动机器人路径规划中存在的局部最优、收敛速度慢等问题，从蚁群算法结构、参数选取及优化、信息素优化等方面对已有改进方法进行总结分析。为了充分发挥蚁群算法的优化能力，对多蚁群优化算法在移动机器人路径规划的应用进行了分类比较与分析。由于单一算法难以解决复杂的优化问题，融合蚁群算法可以取长补短、优势互补，有效平衡算法收敛速度和种群多样性的矛盾，提升其寻优能力，按照优化方法在融合算法中的作用对其进行分类分析与总结。最后从蚁群算法的理论研究、算法智能融合、多蚁群算法研究以及应用范围等方面对蚁群算法在移动机器人路径规划未来的研究内容和研究热点进行了展望。