群智能优化算法在路径规划中的应用

张文辉，王晨宇

(1.2.桂林电子科技大学 计算机与信息安全学院，广西 桂林 541004)

0引言

在移动机器人相关技术研究中，导航技术是其核心，而路径规划是导航技术研究的一个重要环节和组成部分。传统的路径规划方法主要有人工势场法，栅格法，自由空间法等，这些传统的路径规划方法或是为局部极小值问题无法求出最优路径，或是在复杂环境下求解速度过慢。此外，某些传统算法在多障碍或动态的环境下可能无法获得可行路径。群智能算法因为具有较强的全局搜索能力和并行处理能力，能够较好的适应复杂的环境，可以用来解决传统的路径规划算法存在的问题。本文主要介绍了三种群智能算法以及它们在路径规划中最近的相关研究，并对算法的实验结果进行了对比。最后，总结了群智能算法应用在路径规划中存在的问题，提出了今后主要的研究方向。

1路径规划中的群智能算法

群智能(Swarm Intelligence)这一表述最早在1989年由Gerardo Beni在分子自动机系统中提出。群智能算法是模仿自然界的生物群体的自治行为来构造和优化算法[1]。在SI系统中，每个成员个体根据其他成员及其环境的信息调整自己的行为，不断地进行简单自组织的局部行为，再通过不同个体之间的信息交流，进而实现群体智能。群智能算法由于其分布性、自组织性、较强的鲁棒性等优点，已经成功应用在函数优化等领域。因为群智能算法具有较好的鲁棒性，以及并行搜索等特点，近年来许多学者将其应用到优化路径规划的算法之中。许多研究者借助群智能算法的这些特点和优势，对传统的路径规划方法进行优化，取得了显著的效果。许多研究人员的相关实验表明，将群智能算法与传统路径规划方法结合，能够有效提高算法的性能和效率。

1.1人工鱼群算法

1.1.1 人工鱼群算法简介

人工鱼群算法(Artificial Fish Swarm Algorithm, AFSA)是模拟鱼群在自然环境中寻找食物的群智能算法，是由我国学者李晓磊[2]提出的。在人工鱼系统中，每条人工鱼个体根据周围环境的食物浓度以及周围同伴数量来决定将要进行的行为，主要有觅食行为、追尾行为、聚群行为。其中，觅食行为是个体向更优解的方向前进的个体寻优过程，追尾行为和聚群行为是个体与周围环境相互交互的过程。经过多次迭代操作之后，大部分人工鱼将会聚集在食物浓度最好的区域，即寻找到最优解。借助人工鱼群算法的较强的并行搜索能力和快速的全局寻优能力，能较好地提高路径规划的结果。人工鱼群算法的流程图如图1所示。

图1 人工鱼群算法流程图

使用人工鱼群算法进行路径规划的实验中，将要进行路径规划的区域通过建模方法(栅格法，自由空间法，链路图法)转化为解空间。其中，目标点代表着食物浓度最高的点，距离目标点越远的点食物浓度越低，多条人工鱼在解空间中进行并行搜索，通过同伴之间的相互影响，不断向着食物浓度更高的方向前进，从到达目标点的人工鱼所经过的路径中选择最优的路径作为路径寻优结果。但是传统的人工鱼群算法存在着后期收敛速度慢，寻优精度不高的问题，许多研究者提出了相关的改进方法。

1.1.2 人工鱼群算法改进路径规划方法

黄宜庆等[3]提出基于多策略混合人工鱼群算法。处于局部极值周围的人工鱼个体由于视野原因无法寻找到全局极值，引入加权平均距离策略为人工鱼选择合适的视野，保证收敛速度并且防止陷入局部最优。采用对数递增函数作为移动因子，能更好的定位前进方向，保证全局收敛速度和收敛精度。在算法中增加高斯变异策略，增加了种群多样性，能够提高全局搜索能力。

在原始人工鱼群算法中，人工鱼的视野，步长等参数都是固定的，固定参数会导致算法的适应能力较弱。比如，步长不变可能会导致在算法前期因为步长过小而收敛速度慢，或是在算法后期因为步长过大而产生振荡现象。与采用固定参数的原始人工鱼群算法相比，加入了自适应策略的人工鱼群算法能够根据当前搜索环境的差异，自适应地选取适合的参数，进而能够提高算法的搜索性能。

由于在人工鱼群算法中，最优解会保留在公告牌中，个体间不会分享最优解信息，这意味着它缺乏自上而下的信息交互，这会降低算法的搜索效率。Li等[4]采用混合策略，将差分进化引入到人工鱼群算法中。通过变异，交叉和选择操作，使人工鱼个体摆脱局部最优，提高收敛速度。李君等[5]利用最速下降法替代部分觅食行为，保证后期的人工鱼每次行为之后都是向适应度较优的方向前进，减少了人工鱼行为的随机性，提高了算法的收敛速度。邓涛等[6]提出了一种免疫人工鱼群网络算法，引入精英鱼策略，简化聚群行为和追尾行为，构造免疫人工鱼群网络。在减少了计算时间的同时，能有效加快跳出局部极值的速度。姚凌波等[7]借鉴反向学习中反向解的原理，将反向解作为新的引导点，调整人工鱼的状态，提高了发掘潜在较优解的机率，避免其陷入局部最优。

在算法后期，人工鱼个体大部分集中在环境中的极值点附近，同伴之间的相互影响会越来越弱，所以算法的后期收敛速度变慢。以上改进算法通过减少算法的随机性，增加较优个体的影响力，从而提高算法的收敛速度。

针对人工鱼群算法收敛精度不高以及不容易跳出局部极值的问题，许多学者采用将传统人工鱼群算法与其他智能算法相结合得到新的混合算法。周金治等[8]提出了基于差分进化与模拟退火的人工鱼群算法，采用模拟退火算法对适应度最高的状态进行细化搜索，解决陷入局部最优解的情况，引入差分策略提高搜索后期的寻优精度，逼近最优解。张淦[9]向传统人工鱼群算法中引入了萤火虫算法中的吸引度概念，在每次迭代过程中，最低浓度的个体会在行动时会受到最高浓度个体的吸引，处在局部最优解附近的人工鱼个体会向着全局最优个体所在方向前进，能够加快收敛速度。实验表明，算法的收敛速度得到了较大提升，并且具备一定的跳出局部极值的能力。

人工鱼群算法的优点是具有较好的并行搜索能力，并且对初始值要求不高，鲁棒性较强，在应用于路径该规划问题中时可以在较短的时间内寻找到接近最优路径的可行解。缺点是算后期收敛速度慢，收敛精度低的。现有的研究主要对算法的参数调整，个体更新提出了改进策略，或是将人工鱼群算法与其他算法融合，弥补算法的不足。改进后算法与原始人工鱼群算法相比，算法性能在各方面都有较大提升。

1.2蚁群算法

1.2.1 蚁群算法简介

蚁群算法(Ant Colony Algorithm,ACA)是20世纪90年代由意大利学者Marco Dorigo等人[10]首先提出来的一种基于种群的模拟进化算法，是受自然界中蚂蚁寻找食物过程中发现路径的行为启发而来的最早是用于解决旅行商(TSP)问题。在蚁群系统中，每一个蚂蚁个体在寻找食物的过程中，都会在走过的路径留下一定浓度的信息素，而蚂蚁在选择路径时候会更倾向于选择信息素强度更大的路径，因此人工蚁群是一种基于正反馈的分布式协作系统。算法流程如图2所示。

图2 人工蚁群算法流程图

1.2.2 蚁群算法改进路径规划方法

蚁群算法目前主要有两种改进方向，一种是改进信息素的更新方式、路径寻优状态选择策略、参数调整，另一种是将蚁群算法与其他算法进行融合。

尚晓磊[11]对信息素更新公式行改进，结合最大—最小值蚂蚁算法，将信息素的浓度划分在一定范围之间，当一个种群的所有蚂蚁都到达目标栅格后，在更新信息素时，派出反向蚂蚁对路径进行全局信息素更新，避免局部最优，从而改善算法的执行效率。为了提高算法的全局搜索能力，使其尽快找到最优路径，Yu等[12]采用信息素自适应衰减规则，在选择下一步时考虑信息素和距离，而不仅仅考虑信息素浓度。在蚁群算法中，信息素的更新规则影响着算法的全局搜索能力和局部搜索能力。

以上改进算法对信息素的更新公式进行了改进，避免了信息素平均分配导致蚁群算法收敛速度下降的问题。同时解决了蚂蚁容易陷入局部最优和滞后搜索的问题，使得蚁群可以根据实际情况在原有路径和新路径之间得到更好的选择。

针对在复杂环境中，蚁群搜索路径效率慢，劣质解影响算法的运行速度的问题，王钦钊[13]等结合人工势场法对蚁群算法改进，通过人工势场计算路径点的适应值，初始化信息素矩阵来获得高质量的初始解，并在算法寻优阶段引入势场力导向算子，改算法能有效降低路径搜索时候的盲目性和随机性，保证蚁群搜索的全局性。赵峰等[14]设计了一种实时性的，能够动态调整的自适应搜索半径蚁群算法。该算法将路径规划的区域划分为若干个子区域，根据环境的复杂程度自适应地调整搜索半径，寻找到所有最优局部目标点，之后再寻找全局最优目标点。传统的蚁群算法中，蚂蚁搜索路径只与信息素有关，目标方向与路径选择没有直接影响，算法的搜索效率比较低。柳长安[15]等提出根据目标点吸引机制，自适应调整启发函数，提高算法的收敛速度，机器人可以快速地避开障碍物安全到达目标点。

蚁群算法的路径选择是基于信息素的浓度的，在复杂环境中，蚁群算法在初始搜索时由于缺少信息素的参与会产生许多劣质解，影响算法的运行效率，加入初始化信息能够提高初始解的质量。在算法搜索时，增加目标点对路径的影响使路径的选择更具方向性，降低算法搜索时的随机性和盲目性，能够有效减少劣质解的产生。实验表明改进后的算法的收敛速度比传统蚁群算法有了较大提升，能够较好地适应复杂的动态环境。

于树科等[16]提出了融合了蚁群算法和遗传算法的方法，蚁群算法的反馈机制使其能够利用系统中的反馈信息，进行全局寻优能力。而遗传算法搜搜速度快，适合大范围搜索。算法前期，用遗传算法产生的最优解来初始化蚁群算法的信息素。算法后期利用蚁群算法的收敛速度快来寻找最优路径。

个人认为蚁群算法具有较强的自适应能力和鲁棒性，是一种全局搜索算法，利用信息素正反馈和信息共享机制来寻找最优路径是蚁群算法最大的特点，能够很好地应用于路径规划的问题中。但是蚁群算法的计算量大，易陷入局部最优解。现有的改进算法主要是对蚁群算法的信息素更新方式，路径选择方式改进，或是融合蚁群算法与其它群智能算法。

2.3粒子群算法

2.3.1 粒子群算法简介

算法(Particle Swarm Optimization, PSO)是Kennedy和Eberhart于1995年提出的群智能优化算法[17]，已经被广泛应用于训练神经网络、功能优化和各类基于过程的分析应用。其基本思想是所有粒子通过适应度函数确定飞行速度，并由速度决定粒子在解空间中的搜索行为。每个粒子都有一个由目标函数决定的适应值，并知道给粒子本身发现的适应值最好的位置以及整个群体的粒子发现的最好位置。粒子通过自身经验和群体经验来决定下一步的行为。

在路径寻优算法中，每个粒子的位置代表一个可行解即有效路径，通过不断更新迭代最终找到评价最优的函数值即最优解。与其他算法相比，粒子群算法具有简单易实现、收敛速度快、控制参数少等优点，并适用于复杂非线性问题及离散优化问题。但PSO算法也是一种随机启发式算法，其自身存在一些不足，初始化粒子的随机性较强，影响粒子群的寻优效率和可靠性，依赖历史最优导致算法后期的局部搜索能力较差。粒子群算法的流程图如图3所示。

图3 粒子群的速度和位置更新

1.3.2 粒子群算法改进路径规划方法

粒子群算法由于粒子搜索的随机性，存在着收敛速度差、局部寻优能力弱的缺点，方昕[18]结合A星搜索算法的思想，初始化种群生成含有启发信息的粒子群，引入平滑度调整粒子搜索方向，使用惯性权重来控制算法的局部搜索能力和全局搜索能力，提高了算法的收敛精度。杨景明等[19]提出一种多目标自适应混沌粒子群优化算法，该算法对全局最优粒子采用了一种新型动态加权方法，并引入了自适应变异策略，算法在不同时期能够自适应地调整参数，不仅提高了最优解的质量，而且提高了最优解的均匀性。

粒子群算法依赖全局历史最优解和个体历史最优解，可以很好地利用群体信息，收敛性强。但是依赖历史信息容易导致算法在搜索后期的种群多样性较差，局部搜索能力不足。针对多目标问题要求得到的非劣解能够尽可能分布均匀且覆盖广泛，张超[20]提出了混合粒子群算法与人工蜂群算法的混合算法，兼顾了收敛性能和多样性。为了减弱个体对历史最优解的依赖，自适应的调整每个个体历史最优解的加速因子，使个体历史最优解的影响逐渐降低，让更加优秀的全局历史最优解发挥更大的作用。

针对粒子群算法过早收敛问题文献，刘洁[21]提出了自适应权重策略。在粒子群算法中，惯性权重较大时会提高算法的全局搜索能力，惯性权重较小的时候算法偏向于局部搜索。将利用个体粒子的速度和群体粒子的离散度来动态地调整惯性权重，能够避免陷入局部最优解。为了提高算法的准确性和稳定性，在位置更新中引入了自然选择方法，保持种群多样性。实验证明，改进后的算法有效地提升了收敛速度、加强了算法的全局搜索能力。

Guo等[22]根据移动机器人路径规划问题的总体设计，提出了模糊神经网络的控制方法，该方法结合了模糊控制和神经网络。改进的粒子群算法用于调整模糊神经网络的参数，以更好地实现移动机器人的路径规划。神经网络具有较强的容错性和自适应学习的能力，能够有效地分析和融合环境中的信息。模糊控制具有逻辑推理的能力，在处理结构化知识方面更为有效。该算法结合了神经网络与模糊控制的优点，融合神经网络的自学习能力和模糊控制的模糊推理能力，并利用粒子群算法对模糊神经网络的参数进行优化，增加了算法的搜索精度。

粒子群算法具有简单易实现，收敛速度快，适应性强等优点。但是粒子群算法同其他群智能算法一样，存在着易陷入局部最优的问题。目前的改进放方法对粒子群的更新策略、参数调整进行了改进，或者是利用粒子群算法的优势将粒子群算法与神经网络或者其他智能算法相融合。

2群智能算法性能比较

每种群智能算法在应用到路径规划的时候都有其优点，但也会存在不足。存在的比较大问题是结果易陷入局部最优，收敛速度慢，收敛精度低等问题。总结结果如表1所示。

表1 各群智能算法优化路径规划存在的优缺点比较

人工鱼群算法在应用到路径规划时，具有收敛速度快，对初始参数不敏感，鲁棒性高，较强的全局搜索能力等优点。但是算法后期的搜索速度慢，而且人工鱼容易在局部最优解附近徘徊，导致收敛精度下降。目前已应用于组合优化、神经网络训练、约束优化、电力系统负荷预测、参数估计、多目标优化等题，并且取得了良好的效果。

人工蚁群算法本身就是模仿蚂蚁寻找路径而来，在进行路径的时候具有正反馈，分布式协作和信息共享的特点。但是蚁群算法的计算时间比较长，而且依赖于信息素的影响，可能当出现较优路径的时候由于信息素含量的影响出现停滞现象。蚁群算法最初用于解决旅行商问题。已经陆续渗透到其他领域中，如二次分配问题、大规模集成电路设计、通讯网络中的路由问题以及负载平衡问题、车辆调度问题、数据聚类问题、区域性无线电频率自动分配问题等。

粒子群算法的参数较少，易于实现，收敛精度高，算法早期的收敛速度快，但是局部搜索能力差，后期搜索速度慢。粒子群算法最早应用于训练人工神经网络，随后，粒子群算法被广泛地应用于函数优化、 约束优化、 模式分类、机器人路径规划、 信号处理、模式识别等工程领域。

3结束语

本文主要从群智能算法对路径规划研究成果进行了论述。传统的路规划方法由于计算时间长，处理复杂环境能力弱等问题并不能很好的得到一条最优路径。群智能优化算法因为普遍具有分布性，自组织性，较强的鲁棒性的优点，被广泛地应用在路径规划领域，并取得了一定的成果，但是仍有一些问题需要解决。比如，改进后算法虽然在一定条件下避免了陷入局部最优，或是增强了跳出局部极值的能力，但是依然存在着陷入局部最优的可能性。有的算法收敛速度较快，但是会发生早熟现象，影响收敛精度。

对参数的调整能够改变算法的性能，如何设置最优参数适应不同的环境也是一种优化问题。路径规划算法应用场景不断拓展，为了满足多约束条件的目标优化，将多种算法进行融合是一种主要的方法。目前的路径规划研究多是在已知静态的二维环境下进行实验，随着技术领域的不断拓展，复杂三维环境下的动态路径规划是未来研究的趋势。