1、 （）年 第 卷 第 期 收稿日期：基金项目：山西省科学技术发展项目（）作者简介：陈佳峻，男，硕士研究生，主要从事车辆路径规划方面的研究，-：；通信作者 范英，男，硕士，副教授，主要从事载运工具方面研究，-：。本文引用格式：陈佳峻，范英，代晓文，等 改进麻雀搜索算法的智能车路径规划研究 重庆理工大学学报（自然科学），（）：，（），（）：（）改进麻雀搜索算法的智能车路径规划研究陈佳峻，范英，代晓文，许晋军，赵敏（太原科技大学 交通与物流学院，太原 ）摘要：针对麻雀搜索算法存在的收敛速度慢和容易陷入局部最优等缺点，提出了一种改进的麻雀搜索算法。首先，使用 混沌映射函数初始化种群，提高种群多样性，以
2、此来增强麻雀种群在未知环境的探索能力。其次，对麻雀算法位置更新公式进行修改，对位置更新公式进行优化，提高算法的收敛速度。最后，设计 个不同的栅格地图，将改进后的麻雀搜索算法与原始算法在此地图中进行路径规划对比，验证改进麻雀搜索算法的性能。实验结果表明：改进后的麻雀搜索算法在智能车路径规划问题中有着更好的表现，具有更快的收敛速度和更好的寻优能力。关键词：车辆工程；路径规划；改进麻雀搜索算法；混沌映射中图分类号：文献标识码：文章编号：（）引言路径规划作为当前智能车领域的研究热点之一，其目的是在搜索空间内，找到一条连接起点到终点且安全无碰撞、能量损耗低的车辆行驶路径。目前，车辆路径规划的相关研究成果
3、大多都是基于对车辆路径规划算法进行调整和改进得来。常用的智能算法有粒子群算法 、人工蜂群算法 、人工萤火虫群优化算法 、遗传算法 、灰狼算法 等，其各有优势，所适用的范围也有所不同。采用麻雀搜索算法 进行路径规划。麻雀搜索算法模仿麻雀觅食行为进行路径规划，算法结构简单、易于实现，且控制参数较少，局部搜索能力较强等，但在算法迭代后期存在着收敛能力弱和跳出局部最优能力不足等问题。针对这些问题，国内外学者进行了大量深入研究。等 提出引入遗传算法的交叉和变异操作增强算法的收敛能力。等 引用正余弦算法（）提高算法的收敛能力，对麻雀种群的劳动协作关系进行了重新定义，来提高算法的寻优能力。等 提出了一种使用
4、 混沌映射初始化种群分布位置并融合自适应超参数和变异算子，使算法具有较高的种群多样性，加快了算法收敛速度和效率。张琳等 提出了一种多策略改进的麻雀搜索算法，通过混沌映射和反向学习机制进行种群初始化，提高算法种群的质量；其次通过借鉴粒子群算法的学习策略提升种群间的信息交流能力；融合了差分进化算法的变异较差操作，提高了算法跳出局部最优的能力。张卫波等 提出了一种改进 算法，并将其应用于路径规划中，在原算法的基础上引入同心圆采样策略选择下一路径点，使用邻近点选择方法考虑车辆的行驶特性，计算邻近系数以得到邻近点，并对路径进行平滑处理，改善了算法的寻优能力和所规划的路径质量。李爱莲等 通过在种群初始化阶
5、段使用折射反向学习机制提高种群多样性和算法的遍历性，对麻雀位置更新公式进行了修改，在麻雀种群位置更新策略中引入了正余弦策略和柯西变异，提高了麻雀搜索算法的寻优能力；付华等 引用精英混沌反向学习策略对种群进行初始化，提高算法的遍历性，结合鸡群算法，对麻雀搜索算法中跟随者的位置更新公式进行修改，提高算法的搜索能力，通过使用柯西 高斯变异策略提高算法的种群多样性和抗停滞能力，有效改善了算法的寻优能力；刘睿等 提出了一种增强型麻雀搜索算法，该算法使用 映射进行种群初始化，提高种群多样性，在算法的迭代阶段加入动态惯性权重和 分布扰动因子，最后采用随机回归的越界处理方法提高算法的搜索性能；陈功等 使用 混
6、沌映射初始化种群，提高了种群的多样性，其次，融入了一种螺旋探索策略，提高算法的遍历性，然后提出了一种自适应混合变异策略，改善算法的寻优能力；李兆凯等 基于 -技术完成智能车在未知环境下的地图构建，利用*实现了智能车的自主避障和未知环境下的局部路径规划。虽然上述研究针对麻雀搜索算法不足之处所提出的改进方法在一定程度上改善了算法的性能，但仍有很大的改进空间。基于以上研究，针对麻雀搜索算法收敛速度慢和容易陷入局部最优等缺点，提出了一种改进的麻雀搜索算法，从两方面对算法进行改进：为了解决麻雀搜索算法中初始化种群分布不够均匀的问题，引入了 混沌映射函数初始化种群，增强算法的遍历性，提高算法的寻优能力；提
7、出了一种麻雀种群位置更新策略，改善算法的寻优操作，使算法有更高的收敛速度。最后将该算法应用于路径规划中，仿真结果表明：改进的麻雀搜索算法寻优能力更强，收敛速度更快。麻雀搜索算法麻雀 搜 索 算 法（，）是 年提出的。该算法相对新颖，具有寻优能力强、收敛速度快的优点。根据麻雀个体的行为方式将其分为 种：负责搜寻食物的为发现者，种群中每个个体都能表现出此种行为方式，数量保持一定比例；跟随发现者进行觅食行为的称为跟随者；负责报警，发现危险时便会放弃觅食行为，当报警值超过一定范围时，种群中个体便会到其他的安全区域觅食。使用矩阵形式表示种群的初始位置，如式（）所示。，|（）其适应度值可用矩阵形式表示，如
8、式（）所示。（，）（，）（，|）（）麻雀种群通过在空间中不断搜索来改善自身的适应度值，发现者数量在种群中具有固定比例，为 ，发现者位置更新公式如式（）所示。()，（）式中：为种群中第 代中第 个个体的第 维位置，为（，中的均匀随机数，为一个服从标准正态分布随机数，为一个元素均为 的 陈佳峻，等：改进麻雀搜索算法的智能车路径规划研究矩阵。为警戒值，是 ，中的均匀随机数，为警戒阈值，取值范围为 ，。可以看出，当 时，表示侦察者发现了危险，发出报警信号，发现者将会向当前位置附近进行随机移动。跟随者为了得到更好的食物，会追随发现者进行位置移动。跟随者的位置更新公式如式（）所示。()，（）式中：为当第
9、次迭代种群中麻雀的最差位置，为第 次迭代种群中麻雀最优位置。若 ，跟随者的位置为一个标准正态分布随机数与一个以自然对数为底数的指数函数的积，当种群收敛时其取值符合标准正态分布随机数，表示第 只跟随者适应度较差、能量较低，需要飞往其他地方寻找食物。在麻雀进行觅食行为的同时，种群中的部分个体会进行警戒行为，发现危险时会放弃当前的觅食行为，寻找下一个觅食地点，警戒者数量在种群中具有固定比例，占到整个种群的 。警戒者的位置更新公式如式（）所示。（），（），（）式中：为一个符合标准正态分布的随机数，为一个 ，的均匀随机数，为一个较小的数，以防止分母唯一。式（）表示，为了减小被捕食的风险，通过靠近其他麻雀
10、个体来减小被捕食的风险；如果负责警戒的麻雀个体所处位置为当前最优时，它将会向自身附近的位置进行移动；如果负责警戒的麻雀个体所处的位置不是当前最优时，它将会向当前最优位置进行移动。改进麻雀搜索算法麻雀搜索算法在迭代过程中会存在收敛速度较慢和跳出局部最优能力较弱的问题。针对上述问题，采用 混沌映射 初始化种群的分布状态，从而使麻雀种群在空间中可以分布得更加均匀，增强种群的多样性，提高算法的遍历性，以改善算法在未知地图中的寻优能力；通过结合粒子群算法位置更新公式，将麻雀搜索算法中位置更新方式由向最优位置跳跃换为向最优位置移动，使其具有一定的跳出局部最优的能力。混沌映射混沌现象是指在一个确定的系统中，
11、存在着一些随机的、不规则的变量，这些变量具备不确定性、不可重复性和不可预测性。可以利用混沌变量的随机特性初始化种群的分布状态，使种群尽可能均匀地分布在空间中，保持较高的种群多样性，在一定程度上改善算法的寻优能力。映射函数 算子和 混沌映射函数 算子是当前比较常用的混沌算子。映射函数搜索最优解的速度受制于本身函数分布不均匀性的影响，其分布状态是两头大、中间小的情形；映射函数的映射范围小、参数空间小且存在有理数不动点等问题。使用 混沌映射初始化麻雀种群，该映射是一种映射折叠次数无限的混沌模型，相比上述 种映射函数，可以更加均匀地初始化种群的分布状态，获得更快的收敛速度等优点。其数学表达式如式（）所
12、示。()，（，），（）使用 混沌映射到空间中，初始种群分布状态如式（）所示，通过计算可得种群的初始化位置。（）（）式中：为搜索空间的上界，为搜索空间的下界。调整麻雀位置更新公式根据对不同行为方式的麻雀位置更新公式进行分析可知，麻雀的位置更新方式大概为 种：向处于当前最优位置的麻雀个体靠近；向原点位置靠近。当最优解与原点位置重合后，算法收敛速度很快，结果也很好，但是当最优解与原点位置不重合的情况下，麻雀种群会在原点与最优解之间徘徊，最终收敛于最优解。由此可知，麻雀搜索算法的收敛速度与当前所求问题的最优解位置和原点位置之间的距离成正比，即所求最优解靠近原点位置时，算法会有较好的表现，反之算法的性能
13、便会下降。同时，麻雀种群收敛到当前最优解附近往往是以跳跃的方式，这样的更新规则也导致了麻雀搜索算法较易陷入局部最优问题，而且全局搜寻性能较弱。针对上述缺点，对麻雀搜索算法进行改进以增强算法的寻优能力。为了避免麻雀种群在最优解与原点之间徘徊，删除了向原点位置靠近的操作，提高算法的寻优能力；通过结合粒子群算法 收敛于最优解的方式，将麻雀种群收敛于当前最优解附近的方式修改为向最优解位置移动，提高算法在未知空间的探索能力和跳出局部最优的能力。以上改进通过如下操作来实现。通过分析式（）可知：当报警值大于警戒阈值时，更新后的位置为当前位置乘以自然对数为底数的指数函数，随着 的增加，其取值范围将会减小，麻雀
14、的每一维都将变小。为了改善此现象，将发现者位置更新公式修改为乘以一个均值为 、方差为 的正态分布随机数。修改后的发现者位置更新公式如式（）所示。（），（）通过分析式（）可知：当 时，其值为一个正态分布随机数乘一个自然对数为底数的指数函数，其值收敛于 。删除了向原点靠近的操作，只保留向当前最优解靠近的步骤，即每只麻雀都会向所跟随的发现者靠近。修改后的跟随者位置更新公式如式（）所示。（）通过分析式（）可知：为了减小被捕食的风险，如果麻雀个体正处于当前最优觅食位置时，它将会向当前位置附近进行随机移动，移动的距离取决于自身位置距离最差位置的差值与自身适应度值与最差位置适应度值插值之比。将其修改为：如果
15、麻雀处于最优位置时，它将会向最优位置和最差位置之间的随机位置移动，简化其操作。警戒者位置更新公式修改如式（）所示。（），（），（）式中：为当前麻雀最差的位置，为当前麻雀最优的位置。改进 算法运行过程的流程如图 所示。图 改进麻雀搜索算法流程 仿真验证 试验设计为了验证改进麻雀搜索算法的性能，采用栅格法建模方式，在 种不同类型 的栅格地图上进行试验，个地图复杂程度依次递加；处理器为 ，操作系统为 位 、内存环境下使用 仿真软件，将改进的麻雀搜索算法与基本麻雀搜索算法进行对比，种算法初始化种群数量为 ，发现者比例均为 ，警戒者比例均为 ，最大迭代次数设置为 次。种算法寻优结果如陈佳峻，等：改进麻雀
16、搜索算法的智能车路径规划研究图 图 所示。图 地图 寻优结果图 地图 寻优结果图 地图 寻优结果种算法最优路径适应度、拐点个数和搜寻时间信息汇总如表 所示。仿真结果分析）从表可以看出，在个地图的基础上，改进麻雀搜索算法相较于原始算法，最优路径长度分别缩短了 、和 .，改进后的麻雀搜素算法随着地图复杂程度的增加其优势也越来越明显，说明改进后的麻雀搜索算法相较于原始算法有更好的全局搜索能力。车辆路径规划中，路径平滑率也是一个重要的影响因素。可以看出，在地图、地图和地图中，改进麻雀搜索算法所得最优路径的拐点个数较原始算法降低了 、和 ，未见地图复杂程度对路径拐点个数有明显影响。而且路径平滑度也有所降低，避免了冗余路径的产生。拐点数目的增加说明在局部区域内收敛速度较快，局部搜索的能力也随之降低。对比 种算法在 个地图中的最优路径搜寻时间可知，改进麻雀搜索算法相较于原始算法，最优路径的搜寻时间分别缩短了 、和 ，未见地图复杂程度对最优路径的搜寻时间有明显影响。可以看出，改进后的麻雀搜索算法收敛速度更快，寻优能力也更好。表 路径规划寻优信息地图类型寻优算法最优路径长度最优路径拐点个数个最优路径搜寻
