基于改进适应度函数的麻雀搜索算法路径规划研究.pdf

齐鲁工业大学学报第 卷 第 期 年 月出版 .:./.【机电与信息工程】基于改进适应度函数的麻雀搜索算法路径规划研究邓立霞张肖轶群陈奂宇齐鲁工业大学(山东省科学院)信息与自动化学院山东 济南 摘要:将一种智能优化算法 麻雀搜索算法应用于移动机器人二维路径规划并对其进行改进以提升寻路效率 基于该算法的实验环境在栅格地图中实现采用麻雀搜索算法进行路径规划为了解决该算法在路径规划应用中原本适应度值不佳种群易受局部最优个体误导的问题设计并改进了算法的适应度函数将本代的全局最优种群作为下一代迭代的评价标准并将适用于路径规划的思想加入到适应度函数中 在模拟场景中进行了寻路仿真实验实验结果验证了算法改进的合理性和提升程度关键词:移动机器人路径规划麻雀搜索算法适应度函数中图分类号:.文献标志码:文章编号:()():.:随着现代工业与计算机技术的发展机器人逐渐应用在各个领域例如在民用领域的机器人运送快递、自动耕种机工业领域的机械臂、水下无人勘探机军用领域的无人机侦察、无人轰炸机等 而每个移动机器人在实施目标前都有一个基础 路径规划移动机器人只有按照预期抵达目标地点方可进行下一步工作所以移动机器人路径规划是智能移动机器人发展技术的关键移动机器人的路径规划通常需要在整体环境中规划一条最短路径或最优路径 早期常用的路径规划算法有 算法、算法、快速扩展随机树等 此类传统路径规划算法结构简单、约束较收稿日期:网络出版时间:基金项目:山东省重点研发计划()山东省自然科学基金青年基金()作者简介:邓立霞博士、副教授研究方向:机器人控制.齐鲁工业大学学报 年第 期少、稳定性强适合早期的机器人进行简单场景的路径规划 但随着计算机的技术的飞速发展计算机的运算能力逐步增强对于智能仿生算法的运算能力也在逐步增强 此外相对于传统路径算法灵活性差、改进空间小、应用领域受限制的缺点智能仿生算法具有约束多、灵活性高、寻优能力强、模块化设计方便、不同智能仿生算法之间去劣存优的优点因此近年来许多智能仿生算法被应用于路径规划领域 在智能仿生算法中麻雀搜索算法有以下优点:()麻雀搜索算法于 年被设计出改进空间较大()麻雀搜索算法由 类种群相互配合进行寻优寻优能力较强()麻雀搜索算法中本代种群受上代种群影响较深前期收敛速度较高 因此本文利用麻雀搜索算法应用于地面二维移动机器人路径规划并针对麻雀搜索算法在路径规划过程中出现的陷入局部最优、寻路失败的问题对麻雀搜索算法的适应度函数进行改进使其加快收敛速度避免局部最优个体的误导导致的非最优路径或寻路失败情况增加寻路成功率地图环境模型本文的算法实现在栅格地图环境中栅格地图将环境信息划分为若干正方形栅格栅格信息由不同颜色表示 本文有关地图环境的信息用黑白方块表示 如图 所示黑色方块是表示不可通过区域的障碍物白色方块是表示可通过的区域的自由空间图 地图环境模型栅格地图将地图信息存储在矩阵()中其中 和 代表栅格地图中的位置信息 在矩阵中 代表自由路径区域 代表障碍物即不可通过的区域麻雀搜索算法.麻雀搜索算法基本原理麻雀搜索算法()由薛建凯等于 年提出其灵感源于对自然界中麻雀群体通过团队协作获取食物与躲避捕食者的行为 在麻雀搜索算法中适应度越优的麻雀越容易获得食物此类麻雀被称为发现者将带领团体进行觅食 发现者的位置更新方式为:()在式()中 代表某个麻雀 是维数 表示当前迭代的次数 为整体维度 为麻雀第 代的位置 ()为最大迭代次数 表示当前警戒值 表示安全阈值 是一个服从正态分布的随机数 是一个每个元素都为 的 维矩阵 当 ()在式()中 表示在第 代中适应度最差的麻雀的位置 表示第 代时全局最优个体的位置 为一个 维矩阵矩阵中的元素都随机预设为 或 并且 ()当 时此时 麻雀适应度值低此麻雀将随机前往其他位置 当 时此麻雀将向着最优个体 靠拢麻雀在觅食过程中部分麻雀需要保证整个团体的安全问题引导团体躲避捕食者此类麻雀被称为侦察者其位置更新公式为:()在式()中 表示迭代次数为 时的全局最优位置 负责控制步长其服从均值为、方差为 的正态分布 为不为 的常数避免分母为 为当前个体的适应度值 为全局最优个体适应度值 为全局最差个体适应度值 当 时表示该麻雀需要改变位置来使适应度趋于最优适应度当 时表示此麻雀将向着较优麻雀群体靠拢.适应度函数适应度函数是仿生智能算法迭代过程评价的关键算法根据当代的适应度值来进行下一代种群个体的选择适应度的灵感来源于自然界“优胜劣汰”的生物生存原则 在 中适应度函数用以淘汰种群中适应度不好的个体选择适应度好的发现者或加入者成为发现者作为局部最优进入下一代 在 应用于路径规划过程中路径的长短、路径是否经过障碍物、个体是否越过边界为适应度函数评价种群的标准路径规划适应度函数模型为:()()()在式()中 表示当前种群个体的适应度值 表示该个体的 节点在地图中的 轴位置 表示此个体的 节点的 轴位置 表示该个体的 节点在地图中的 轴位置 表示此个体的 节点的 轴位置、为地图环境的长与宽 表示本代中个体节点刷新在障碍物位置的数量 当 时表示此个体所含节点位置刷新在障碍物上此类节点存在越多 越高 当 时表示所有个体节点都刷新在自由空间此时个体中节点的距离越远 越高距离越近 越低 当节点的位置 或 大于维度 或 时取无限大 因此在麻雀搜索算法路径规划中 值越高表示麻雀个体 适应度越不好应当淘汰或尽快向最优靠拢 值越低表示麻雀个体 适应度越好应当加入下一代改进适应度函数在 路径规划中将个体与路径是否接触障碍物路径长短作为判断个体优劣的标准 当某个个体不接触障碍物且路径长度较短时将成为本代的最优个体但迭代初期全局可能存在许多此类个体此时若没有其他判断标准时极易陷入局部最优导致收敛速度降低或路径非最优 因此本文将算法迭代过程中当前代的临时全局路径加入到适应度函数中作为个体的判断标准对较优的麻雀种群个体进行二次淘汰平衡局部最优与全局最优的选择通过“优中选优”原则避免局部最优个体的误导导致的非最优路径或寻路失败情况提高寻路效率改进方法的原理为:假设个体 符合局部最优个体适应度值则在式()之前先对该局部最优个体进行全局路径判断即连接起点、终点与所有节点位置从起点开始依次选取相邻的 个节点位置、若 齐鲁工业大学学报 年第 期个节点两两之间路径存在障碍物则继续选取下一组节点位置即、若 个节点两两之间路径不存在障碍物或选取位置的过程中无法选取除终点外的下一个节点如图 中点 所示则直接淘汰 个节点中的中间节点 并由适应度函数重新评价本代个体适应度值挑选最优个体进入下一代迭代图 局部最优个体改进后的适应度函数判断流程如图 所示:图 改进适应度函数流程图 年第 期邓立霞等:基于改进适应度函数的麻雀搜索算法路径规划研究实验结果分析本文 预警值的安全阈值设置为.发现者比重设置为 侦察者比重设置为 种群数量设置为 最大迭代次数设置为 起点设置为()终点设置为()实验基于 实现 为确认实验合理性分别设置 种地图环境作为 组实验并与灰狼优化算法()路径规划进行对比第一组实验、第二组实验、第三组实验的路径与适应度值对比分别如图、图、图 所示图 第一组实验路径与适应度值对比图 第二组实验路径与适应度值对比图 第三组实验路径与适应度值对比齐鲁工业大学学报 年第 期 对于 组实验到达最佳适应度值所用迭代次数如表 所示路径长度对比如表 所示 表 与 算法改进前后达到最佳适应度所用迭代次数单位:次分组 算法 算法改进前 算法改进后第一组第二组第三组 表 与 算法改进前后路径长度单位:分组 算法 算法改进前 算法改进后第一组.第二组.第三组.实验结果表明麻雀搜索算法在路径规划领域寻优能力与灰狼优化器相差不大但收敛速度高于灰狼优化器 适应度函数改进后与改进前相比收敛速度有所提升且场景较复杂的情况下改进提升效果较好最佳适应度值降低表明改进后寻优能力更强此外改进后的路径长度缩短成功避免了个别局部最优个体的误导综合提高了麻雀搜索算法路径规划的寻路效率总结本文将麻雀搜索算法应用于路径规划领域并针对特用于路径规划的适应度函数原本的不足利用判断误导性局部最优个体的方法在本代中进行二次选择提高进入下一代的个体有效性为算法整体的稳定性设立良好的前提从而提高了算法收敛速度与寻路的成功率和稳定性 最后通过仿真实验验证了改进方法的有效性参考文献:.:?.:.王鹤静王丽娜.机器人路径规划算法综述.桂林理工大学学报:.:.():.():.张飞凯黄永忠李连茂等.基于 算法的货运索道路径规划方法.山东大学学报(工学版)():.王梓强胡晓光李晓筱等.移动机器人全局路径规划算法综述.计算机科学().音凌一向凤红.融合改进灰狼优化算法和人工势场法的路径规划.电子测量技术():.王玲玲孙磊丁光平等.基于改进麻雀搜索算法的无人机航路规划研究.弹箭与制导学报():.:.郝琨邓晁硕赵璐等.基于区域搜索粒子群算法的机器人路径规划.电子测量与仪器学报():.:.():.玄登影王福林高敏慧等.一种改进适应度函数的遗传算法.数学的实践与认识().:.(责任编辑:孙洪清校 对:赵立爱)