改进麻雀搜索算法的无人车路径规划
时间：2023-06-10 10:10:17 来源：雅意学习网 本文已影响 人 
葛 唱，钱素琴
改进麻雀搜索算法的无人车路径规划
葛 唱，钱素琴
（东华大学 信息科学与技术学院，上海 201620）
针对麻雀搜索算法后期容易早熟，易陷入局部最优后搜索能力下降的不足，提出了一种结合伯努利（Bernoulli）映射和禁忌搜索算法的改进麻雀搜索算法。改进麻雀搜索算法在初始化阶段，使用Bernoulli映射初始化种群位置，取代传统算法初始化阶段采用随机数的方式，优化了种群分布不均，搜索范围不足的问题，同时当超过一定迭代次数全局最优值仍没有更新时再次使用Bernoulli映射对种群进行扰动增强全局搜索能力，在算法进入后期寻优阶段时使用禁忌搜索算法，应用其禁忌准则和特赦准则的结构实现良好的全局搜索能力。然后将该算法应用到无人车全局路径规划问题中，并进行了实验验证其有效性。实验结果表明改进后的麻雀搜索算法拥有更好的全局搜索能力和更高的精度。
无人车；
路径规划；
改进麻雀搜索算法；
混沌映射；
禁忌算法
随着当今社会科技水平的迅猛发展，自动驾驶车辆已渐渐成为热点话题。如今的自动驾驶技术不仅只存在于实验室中，同时在近几年随着各个厂商的新车发布，成为各个厂商新车的卖点。自动驾驶车辆可分为6个级别：无自动化、驾驶员辅助、部分自动化、条件自动化、高度自动化、全自动化。如今实现部分自动化级别的新车已成功上市，还有些厂商声明已经可以实现高度自动化级别，而路径规划作为自动驾驶车辆中极为重要的一环，如何更快更好地获得最优路径也已成为当前的研究热点。路径规划问题[1-2]主要是让目标对象在有多个障碍物的复杂环境中找到一条从起始点到目标点的安全无碰撞路径。现在处理路径规划问题的常用算法主要分为2大类：传统路径规划算法，如迪克斯特拉算法（Dijkstra）[3]、A*算法[4]、人工势场法[5]等；
部分群智能优化算法，如蚁群算法[6-7]、粒子群算法[8-9]、遗传算法[10]、麻雀算法等。
为了进一步增强算法的性能，学者们已经提出各种策略结合现有的方法来更好地解决路径规划问题。付兴武等人将粒子群算法和天牛须算法结合，降低了收敛值，有效地缩短了路径长度[11]。王辉等人引入新的距离启发函数因子、调整状态转移概率等对传统蚁群进行优化改进，并将其应用到存取车的路径规划问题中，得到了更强的全局搜索性能和更快的收敛速度[12]。麻雀搜索算法是2020年提出的一种新型群智能优化算法，主要受到麻雀的觅食行为和觅食过程中的警戒行为的启发，具有收敛速度快、局部搜索能力强、参数少等特点，在图像处理、机器人控制、路径规划等领域均有一定的研究。汤安迪等人对传统麻雀搜索算法进行改进，采用了立方映射初始化种群，并使用反向学习策略引入精英粒子，增强了种群的多样性，扩大搜索区域范围，并应用到无人机的航迹规划问题中[13]。综合现有的研究成果，本文提出了一种结合伯努利（Bernoulli）映射与禁忌搜索算法的改进麻雀搜索算法：使用Bernoulli映射初始化种群位置，取代传统算法初始化阶段采用随机数的方式，并且与汤安迪等人采用的立方映射相比，Bernoulli映射遍历性更强，在整个环境建模中分布更均匀，优化了种群分布不均、搜索范围不足的问题；
同时当超过一定迭代次数全局最优值仍没有更新时，再次使用Bernoulli映射对种群进行扰动，增强算法的全局搜索能力和收敛速度，降低算法陷入局部最优而无法跳出的可能性，并在后期寻优阶段引入禁忌算法进一步提高算法的精度；
最后将该算法引入无人车路径规划中。
传统的麻雀算法在麻雀种群初始化阶段采用的是生成随机数的方式进行初始化种群位置，导致种群中麻雀的位置良莠不齐，同时不能遍历环境中的所有位置，导致其收敛速度较低。所以本文提出在种群初始化阶段引入Bernoulli映射。Bernoulli映射属于混沌映射的一种，常被用来产生混沌序列，其具有非线性、遍历性、随机性等特征，在优化领域替代随机数初始化种群，会影响算法的整个过程，同时能获得比随机数更好的寻优效果。Bernoulli映射的数学表达式可表示为
不仅在种群的初始化阶段引入混沌映射，在麻雀搜索算法进行迭代更新的过程中，当全局最优值超过10次未进行更新时，便会认为该种群在某一位置停留过久有陷入局部最优的嫌疑，便会再次采用Bernoulli映射对整个种群进行扰动，减小其落入局部最优而无法跳出的概率，即提高了全局搜索能力。
在算法的后期寻优阶段引入禁忌算法，应用其禁忌准则和特设准则的结构，在迭代的过程中不断求解给定初始解的领域解，并从中挑选出质量较好的作为候选解，最后根据候选解更改禁忌表。
通过引入禁忌算法可以进一步提高整体的全局搜索能力和寻优能力，能更好地提高最优路径的精度。
图1 环境模型
对于该算法中的评价函数，本文采用该路径的长度作为标准，即
图2 3种算法进行50次实验结果对比
从图中可以看出：传统麻雀搜索算法和粒子群算法在进行50次最优路径的搜索中，结果有很大的波动，表明传统麻雀搜索算法和粒子群算法在求解路径规划问题中容易陷入局部最优，导致最终的结果偏离全局最优而使最终结果产生较大的偏差；
而改进的麻雀搜索算法每一次的搜索结果相差不大，可以看出改进后的算法具有更好的全局搜索能力和更好的精度。3种算法进行50次实验的数据对比结果如表1所示。
表1 3种算法50次实验数据对比
从表1的数据可以看出，不论是最优值、均值还是方差，改进麻雀搜索算法都是最好的。尤其在方差的数据对比中可以看出，改进的麻雀搜索算法特别稳定，说明改进后的算法在寻优过程中能找到更好的结果，同时体现了改进后的算法在全局搜索能力上的优越性。同时在均时一栏可以看出改进麻雀搜索算法在加入混沌映射和禁忌算法后增加了大量的计算量，但实际效率并没有与其他2种算法相差太多。图3、图4及图5分别为传统麻雀搜索算法、改进麻雀搜索算法和粒子群算法的一次寻优结果，图6为3种算法迭代次数与适应度值对比图。
图3 传统麻雀搜索算法结果
图4 改进麻雀搜索算法结果
图5 粒子群算法结果
图6 适应度值对比
图中粒子群算法、传统麻雀搜索算法和改进麻雀搜索算法的适应度值分别为155.3165、163.3408150.7585m，可以看出，改进后的麻雀算法拥有更快的收敛速度和更好的适应度值。因为改进的麻雀算法在种群初始化阶段引入了Bernoulli映射，使得初始化的种群拥有更好的位置，可以尽快地趋向全局最优值；
而且在迭代的过程中能够减小陷入局部最优的可能，从而获得更好的全局最优结果。
针对无人车的路径规划问题，本文提出了一种结合Bernoulli映射和禁忌算法的改进麻雀搜索算法：在传统算法的初始化种群阶段采用Bernoulli映射，使种群位置不仅保留了随机数初始化种群的随机性，同时使得种群具有更丰富的多样性，能更好地遍历二维环境；
在算法迭代过程中找到的全局最优值超过10次迭代过程都没有发生变化时，怀疑算法会陷入局部最优，此时再次采用Bernoulli映射对种群进行扰动，使算法避免陷入局部最优而影响最终的结果；
同时在后期的寻优阶段，采用禁忌算法能够使结果进一步优化。实验结果表明，改进后的麻雀搜索算法拥有更快的收敛速度、更好的全局搜索能力和更高的精度，相较于粒子群算法和传统麻雀搜索算法，不仅效率更高，同时避免了陷入局部最优的可能，可以获得更短的路径。
[1] HOSSAIN M A, FERDOUS I. Autonomous robot path planning in dynamic environment using a new optimization technique inspired by bacterial foraging technique[J]. Robotics and Autonomous Systems, 2015, 64: 137-141.
[2] ZHU D, YAN M. Survey on technology of mobile robot path planning[J]. Control and Decision, 2010, 25(7): 961-967.
[3] 陈亚琳, 庄丽阳, 朱龙彪. 基于改进 Dijkstra 算法的泊车系统路径规划研究[J]. 现代制造工程, 2017(8): 63-67.
[4] BING F, LIN C, ZHOU Y, et al. An improved algorithm for the industrial robot path planning with high success rate and short length[J]. Robotics and Autonomous Systems,2018,106:26-37.
[5] SONG J H, DAI T, LIU Y J. Path planning of mobile robots based on improved artificial potential field method[J]. Computer Engineering & Science,2017,39(7):1328-1332.
[6] HOSSEIN Y, MARKID, ZAKEROLHOSSEINI, et al. Unsupervised probabilistic feature selection using ant colony optimization[J]. Expert Systems with Applications,2016,53:27-42.
[7] LEE J. Heterogeneous-ants-based path planner for global path planning of mobile robot applications[J]. International Journal of Control, Automation and Systems, 2017,15(4):1754-1769.
[8] LIN Q Z, LIU S B, ZHU Q L, et al. Particle swarm optimization with a balanceable fitness estimation for many objective optimization problems[J]. IEEE Transactions on Evolutionary Computation,2018,22(1):32-46.
[9] MO H, XU L. Research of biogeography particle swarm optimization for robot path planning[J]. Neurocomputing, 2015, 148: 91-99.
[10] ELHOSENY M, THARWAT A, HASSANIEN A E, et al. Bezier curve based path planning in a dynamic field using modified genetic algorithm[J]. Journal of Computational Science, 2018,25: 339-350.
[11] 付兴武, 胡洋. 基于改进粒子群算法的三维路径规划[J].电光与控制,2021,28(3):86-89.
[12] 王辉, 王景良, 朱龙彪, 等. 基于改进蚁群算法的泊车系统路径规划[J]. 控制工程, 2018, 25(2):254-258.
[13] 汤安迪, 韩统, 徐登武, 等. 基于混沌麻雀搜索算法的无人机航迹规划方法[J]. 计算机应用, 2021, 41(7): 2128-2136.
Path planning of unmanned vehicle based on improved sparrow search algorithm
GE Chang, QIAN Suqin
（College of Information Science and Technology, Donghua University, Shanghai 201620, China）
An improved sparrow search algorithm based on Bernoulli mapping and tabu search algorithm is proposed to solve the problem that sparrow search algorithm is easy to be premature and fall into local optimization. In the initialization phase of the improved sparrow search algorithm, Bernoulli map is used to initialize the population position, instead of the random number method used in the initialization phase of the traditional algorithm, which optimizes the problems of uneven population distribution and insufficient search range. At the same time, when the global optimal value is not updated after a certain number of iterations, Bernoulli map is used again to disturb the population to enhance the global search ability. The tabu search algorithm is used when the algorithm enters the later optimization stage, and its structure of tabu criteria and Amnesty criteria is applied to achieve good global search ability. Then the algorithm is applied to the global path planning problem of unmanned vehicles, and experiments are carried out to verify its effectiveness. The experimental results show that the improved sparrow search algorithm has better global search ability and higher accuracy.
unmanned vehicle; path planning; improved sparrow search algorithm; chaotic mapping; tabu search
TP273
A
2095-4999(2022)06-0107-05
葛唱，钱素琴.改进麻雀搜索算法的无人车路径规划[J].导航定位学报, 2022, 10(6): 107-111.（GE Chang, QIAN Suqin.Path planning of unmanned vehicle based on improved sparrow search algorithm[J]. Journal of Navigation and Positioning, 2022, 10(6): 107-111.）
10.16547/j.cnki.10-1096.20220614.
2022-06-14
葛唱（1998—），男，辽宁大连人，硕士研究生，研究方向为无人车轨迹跟踪与路径规划。
钱素琴（1971—），女，上海人，硕士，副教授，研究方向为嵌入式系统和人工智能。
猜你喜欢 搜索算法全局麻雀 一种基于分层前探回溯搜索算法的合环回路拓扑分析方法现代电力(2022年2期)2022-05-23改进的非结构化对等网络动态搜索算法军民两用技术与产品(2021年2期)2021-04-13改进的和声搜索算法求解凸二次规划及线性规划烟台大学学报（自然科学与工程版）(2021年1期)2021-03-19拯救受伤的小麻雀作文小学中年级(2019年10期)2019-11-04落子山东，意在全局金桥(2018年4期)2018-09-26基于莱维飞行的乌鸦搜索算法智能计算机与应用(2018年3期)2018-09-05记忆型非经典扩散方程在中的全局吸引子Acta Mathematica Scientia(English Series)(2018年6期)2018-03-01燕子和麻雀文理导航·科普童话(2016年7期)2017-02-04紧盯着窗外的麻雀山东青年(2016年1期)2016-02-28着眼全局，积极负责，机动灵活——记平津战役第一阶段西线的一次阻击战军事历史(1986年4期)1986-08-21
