改进鲸鱼优化算法在机器人路径规划中的应用.pdf

收稿日期:基金项目:国家重点研发计划项目()辽宁省“兴辽英才计划”项目().作者简介:赵俊涛()男河北沧州人东北大学博士研究生 罗小川()男四川西充人东北大学教授博士生导师.第卷第期 年 月东北 大 学 学 报(自 然 科 学 版)().:./.改进鲸鱼优化算法在机器人路径规划中的应用赵俊涛 罗小川 刘俊秘(.东北大学 信息科学与工程学院 辽宁 沈阳 .河南城建学院 电气与控制工程学院 河南 平顶山)摘 要:针对使用标准鲸鱼优化算法求解机器人路径规划问题时存在收敛速度慢且容易陷入局部最优值的问题提出混合粒子群优化算法与自适应权重策略的改进鲸鱼优化算法().通过在标准 和 算法中引入非线性惯性权重因子使种群进化过程中自适应更新权重提高了算法的全局探索能力和收敛速度同时通过将寻优能力较强的 算法引入 算法的开发阶段保证迭代的新解优于原始解增强了算法跳出局部最优的能力.最后将 算法应用到的栅格地图仿真环境中进行机器人最佳路径求解.通过对比给定算法的耗时、规划路径长度以及拐点数结果表明提出的 算法在优化精度和收敛速度上优于文中给定的其他算法验证了改进算法的有效性.关 键 词:混合优化算法粒子群优化鲸鱼优化算法自适应权重路径规划中图分类号:文献标志码:文章编号:()(.:.):()().:()()目前随着移动机器人的智能化和自主化程度越来越高移动机器人已经被广泛应用于家庭、医院、酒店、工业以及军事领域.路径规划是移动机器人应用过程中需要解决的基本问题其目的是为机器人在复杂场景中寻求从起始点到目标点的最优无碰撞可行路径.评判路径最优的标准 包括规划路径的长度、耗时、转弯角度以及拐点数等.目前使用的路径规划方法可以分为两类:传统算法和启发式算法.传统的路径规划算法包括单元分解法()、人工势场法()以及快速扩展随机树()等该类方法可以规划出近最优路径但是随着网络节点的增加存在规划效率低和耗时长的不足.启发式算法由于具有良好的空间搜索能力被广泛应用于机器人路径规划中.启发式算法包括神经网络法()、模糊推理法()以 及 自 然 启 发 式 算 法().其中自然启发式算法是研究者受自然界生物行为方式的启发而提出的如蚁群优化()、粒子群优化()、萤火虫算法()、布 谷 鸟 搜 索()和鲸鱼优化算法()等这些算法为解决机器人在复杂环境中的路径规划问题提供了新思路.鲸鱼优化算法是由澳大利亚学者 等受座头鲸气泡网捕食行为启发提出的群体智能优化算法.该算法具有实现原理简单、调整参数少和寻优性能强等优点因此众多研究者将其应用于神经网络、自动控制以及机器人路径规划中.标准 寻优后期由于种群多样性减少造成算法存在收敛速度慢、寻优精度低和容易陷入局部最优等缺点.针对以上不足许多学者在原有算法基础上进行改进:文献提出一种基于遗传算法和改进鲸鱼优化算法相结合的路径规划方法解决了机器人在复杂动态环境中的路径规划和智能避障问题文献提出一种基于鲸鱼优化算法和模糊逻辑控制器的混合算法可以用于工业场景下机器人规划平滑路径和实现避障功能提高了机器人的自主性降低了算法的计算复杂度文献提出一种基于和声二次优化和动态平衡策略的鲸鱼优化算法通过将和声搜索策略、动态平衡策略与鲸鱼优化算法相融合提高了算法的寻优能力并将其用于解决地面无人车的全局路径规划问题文献提出一种时变独立搜索 概 率 和 免 疫 记 忆 改 进 的 鲸 鱼 优 化 算 法()通过采用非线性收敛因子、时变独立搜索概率以及免疫记忆机制提高了算法的计算精度和收敛速度将该算法应用在机器人路径规划中验证了算法的有效性和稳定性.为了克服 解决复杂优化问题时早熟收敛、搜索能力差以及求解精度低等不足进一步提高算法性能本文提出了一种混合粒子群优化算法和自适应权重策略的改进鲸鱼优化算法()首先通过在 算法和 中引入非线性权重因子平衡算法的局部寻优能力和全局寻优能力算法开始初期由于种群个体较为分散权重值较大可以加快算法的全局探索能力随着算法迭代次数的增加权重值逐渐减小加快算法的收敛速度对局部进行精细化搜索.同时通过将 算法引入 算法的开发阶段保证迭代后新解优于原始解增强了算法的寻优能力.最后将改进的 应用于模拟环境下机器人路径规划问题的求解.机器人路径规划问题数学模型 环境建模机器人路径规划的目的是在包含障碍物和自由运行空间的未知环境中求得最优无碰撞路径因此可以将机器人的运行环境使用栅格地图进行表示其中白色栅格代表机器人的可运行区域黑色栅格代表环境中的静态障碍物如图 所示.图 机器人运行环境栅格地图 机器人可以在中心坐标的八邻域白色栅格方向运动从图中圆圈表示的起始位置移动至五角星表示的目标点位置.环境地图的数学表示为 的二值矩阵地图中的栅格按从左至右从上至下依次编号为()其中任意栅格 的坐标()可通过公式()计算求得东北大学学报(自然科学版)第 卷 .()式中:表示取余运算表示取整运算.适应度函数机器人路径规划过程中需要满足如下约束条件:运动路径必须局限于地图的栅格空间内且不能超出地图边界规划路径长度最短以保证获取路径为最优路径机器人运动路径不能穿越障碍物栅格区域避免发生碰撞.根据以上约束可以将机器人路径规划问题抽象为求解适应度最小的单目标优化问题定义路径规划问题的适应度函数:()().()式中:为算法的迭代次数()为第 次迭代时机器人的路径规划长度其具体定义为()()().()式中:()为第 次迭代时机器人位置坐标()为第 次迭代时机器人位置坐标求得的()为两点之间的欧氏距离.()用于判断第 次迭代时路径点 是否发生越界或与上一路径点连线是否穿越障碍物当路径点可行时返回值为 反之返回较大的常数 具体定义如下:()不可行可行.()混合粒子群和自适应权重鲸鱼优化算法 鲸鱼优化算法()鲸鱼优化算法是根据座头鲸群体捕食小型鱼虾的行为提出的仿生元启发式算法种群中每条鲸鱼相当于问题的一个解通过收缩包围、气泡网攻击和随机搜索完成捕食猎物过程最终猎物的位置相当于问题的全局最优解.假设初始鲸鱼种群规模为 搜索空间的维度为 则第 条鲸鱼位置可以通过 ()表示其中.)收缩包围.座头鲸在发现猎物后会逐步对其进行包围算法假设猎物位置或最接近猎物的位置为问题的最优解定义最优位置以后其他鲸鱼将通过不断更新自身位置来靠近最优位置位置更新公式为 ()()()()().()式中:为当前的迭代次数 为当前的鲸鱼位置为当前为止最优的鲸鱼位置的值会随着迭代次数的增加而不断更新 和 为系数计算公式为 ().()式中:其值将随着迭代次数的增加从 减小至 不断减小的过程即鲸鱼收缩包围猎物的过程 为最大迭代次数 为取值范围在之间的随机数.)气泡网攻击.座头鲸捕食包括收缩包围和螺旋位置更新两个过程在收缩包围阶段由公式()可以看出 的取值范围为 随着 的改变 的值也随之改变.当 的取值为 时算法处于开发阶段鲸鱼通过螺旋游动的方式不断向最优位置靠近该过程中螺旋位置更新通过公式()计算求得()()().()式中:()()表示当前鲸鱼位置与最优位置之间的距离 为对数螺旋形状常数为取值 的随机值.鲸鱼在螺旋游向猎物的同时伴随着收缩包围的过程鲸鱼以收缩包围机制进行位置更新和以螺旋游动进行位置更新的概率均为 具体可以表示为()().()().()式中:为取值范围在之间的随机数.)随机搜索.为了增强算法的全局搜索能力当 的取值在 之外时算法处于探索阶段将在鲸鱼种群中随机选择鲸鱼个体进行位置更新计算公式:()()().()式中:为种群中随机选择的鲸鱼个体 表示当前鲸鱼位置与随机选择的鲸鱼个体之间的距离系数 和 与式()和式()的取值相同.粒子群优化算法()粒子群优化算法是由 等受鸟群觅食行为启发而提出的一种群体智能优化算法算法模型中将群体中的每只鸟看作优化问题的一第 期 赵俊涛等:改进鲸鱼优化算法在机器人路径规划中的应用 个解并称之为“粒子”这些粒子将以一定的速度在搜索空间飞行飞行过程中该速度会根据自身与其他粒子的经验进行动态更新.假设初始种群中有 个粒子这些粒子在 维搜索空间进行搜索则第 个粒子的位置可以表示为 ()飞行速度为 ().在飞行过程中粒子 的个体最优位置为()目前为止种群中所有粒子的全局最优位置为 ().粒子 的飞行速度和位置更新可以通过如下公式求得()()()()()()()().()式中:为算法当前的迭代次数为加速因子为介于之间的随机数.混合粒子群和自适应权重鲸鱼优化算法()通常使用群体智能算法解决()问题时算法的性能主要受收敛早熟和收敛速度的影响平衡算法在搜索空间中的探索和开发能力颇为重要.算法收敛速度快但全局探索的能力较弱 具有良好的探索能力但开发能力主要受公式()和公式()中当前位置与最优位置之间的距离制约.在 算法中如果种群的全局最优解陷入局部最优时其他粒子也将停止继续搜索而跟随全局最优解陷入局部最优.总结来说 算法寻优能力强但搜索空间能力较弱 探索空间能力强但寻优能力受收敛速度制约.因此可以将 算法应用于 的开发阶段以提高算法得到全局最优解的能力.混合 是粒子群算法和鲸鱼优化算法的结合体通过在 算法和 中同时引入非线性权重因子克服了 算法由于受恒定惯性权重的限制造成搜索空间范围小的缺点同时在 中通过引入非线性惯性权重进行收缩包围和螺旋游走位置更新可以加快算法的收敛速度提升算法的寻优能力.混合 吸收了二者各自的优点因此寻优性能更为突出.惯性权重因子是平衡算法全局探索和局部开发能力的主要因素本文使用了自适应惯性权重策略引入非线性权重 随着迭代次数的增加 的值将随之动态改变.在迭代初期较大的权重可以提高算法的全局探索能力迭代后期较小的权重 有 利 于 算 法 进 行 精 细 化 的 局 部 寻 优.的更新公式为 ().()式中:为调节系数当 取不同值时权重 随之改变如图 所示.图 不同 值下的权重曲线 从图中可以看出 取不同值时权重 的变化速率不同 期望迭代前期权重取值较大算法具有较强的全局搜索能力和收敛速度随着迭代次数的增加迭代中期权重大幅减小直至后期缓慢趋近于 提高算法的收敛速度和求解精度经过多次实验本文选取 .混合算法中引入非线性权重以后 算法的位置更新公式为()()()()()()()().()算法粒子移动速度和位置更新公式为()()()()()()()().()混合 实现步骤及流程混合 的具体实现步骤描述如下:步骤 种群及算法参数初始化.随机初始化鲸鱼种群和粒子群的位置为 ()初始化移动速度为 ().同时需要对种群规模 最大迭代次数 搜索空间维度 迭代次数初始值 等参数进行初始化步骤 计算种群中每个个体适应度值通过比较找出最优个体位置 步骤 根据公式()与公式()更新系数 东北大学学报(自然科学版)第 卷 和 的值更新 以及 的值生成取值为区间的随机数 步骤 根据 和的取值进行位置更新.如果 .且则在种群中随机选择鲸鱼个体并根据公式()和公式()进行位置更新如果 且 则根据公式()和公式()进行位置更新如果 则根据公式()进行位置更新步骤 根据公式()更新粒子群个体的移动速度根据公式()更新粒子群位置 步骤 返回步骤 进行迭代更新判断是否达到最大迭代次数如果算法迭代完成则终止算法执行步骤 算法迭代完成返回最终计算得到的最优位置 以及求解最优值时的种群个体位置求解完成.的流程图如图 所示.图 流程图 在机器人路径规划中的应用 为了验证混合 在求解机器人路径规划问题上的有效性本文分别在简单少障碍物场景和复杂多障碍物场景两种仿真实验环境中选择文献中的灰狼优化算法、文献中的蚁群优化算法、标准鲸鱼优化算法、以及本文的混合 种算法进行对比仿真实验.硬件环境及参数配置实验运行硬件平台主机操作系统为 处理器为 ()()主频 内存 软件平台使用的是 .各对比算法相关参数设置如表 所示.表 各算法参数设置 算法参数 /.().路径规划仿真实验实验环境选择为 的栅格地图机器人从起始点移动至目标点地图中黑色区域为障碍物.仿真实验中 种算法采用相同的参数如初始种群规模均为 最大迭代次数为 次搜索空间范围为 适应度函数如公式()所示.为了保证生成路径的最优性在路径生成阶段对路径的生成方向做了进一步限定即路径不会出现“折返”或“回环”的现象生成路径点无障碍区选择使用插值或直连方式进行简单优化处理保证了路径的最优性.最后通过对算法生成的规划路径长度、耗时及拐点数量进行统计分析进而对算法的性能进行评估.仿真实验得到的规划路径以及适应度曲线分别如图 图 所示各算法规划路径的耗时、路径长度及拐点数对比数据如表 表 所示.图 简单场景路径规划仿真结果 第 期 赵俊涛等:改进鲸鱼优化算法在机器人路径规划中的应用 图 简单场景适应度函数变化曲线 图 复杂场景路径规划仿真结果 图 复杂场景适应度函数变化曲线 表 简单场景仿真实验结果 算法耗时/路径长度/拐点数 表 复杂场景仿真实验结果 算法耗时/路径长度/拐点数 实验结果与分析由图 和图 可以看出在障碍物较少的简单环境中 和改进的 均可以规划出较优的路径:算法在迭代 次后获得最优路径长度为 算法在迭代 次后获得最优路径长度为 在迭代 次以后获得最优路径长度为 而改进的 在迭代 次后获得最优路径长度为 .可以看出 算法耗时最长 算法迭代次数最多改进的混合 迭代次数最少与 相比提高了 路径长度与 算法相比缩短了 在收敛精度和收敛速度上都得到了提升 通过表 对比 种算法的耗时和路径拐点数来看改进后的算法耗时最短为 相对于对比算法中规划耗时最短的 提高 路径拐点数为 路径优于其他 种算法.由图 和图 可以看出在障碍物较多的复杂环境中 算法在迭代 次后获得最优路径长度为 算法在迭代 次后获得最优路径长度为 在迭代 次后获得最优路径长度为 改进后的 在迭代 次后获得了最优路径长度为 .虽然 算法的路径长度优于 但三者在收敛精度和收敛速度方面都不及改进后的 改进后的算法在迭代次数方面与对比算法中迭代次数最少的 相比效率提高了 路径长度方面与 算法相比缩短了 在耗时和路径拐点数上来看改进后的算法耗时最短为 相对于对比算法中耗时最短的 提高了 路径拐点数为 算法的性能在 种算法中为最优.综合以上数据和分析说明改进后的 能够成功应用于机器人的路径规划问题无论在简单场景还是复杂场景中算法的收敛精度和收敛速度等性能均得到了提升.东北大学学报(自然科学版)第 卷 结 语本文针对机器人路径规划问题提出一种基于混合粒子群和自适应惯性权重的改进鲸鱼优化算法.将寻优能力较强的粒子群算法引入鲸鱼优化算法的开发阶段平衡算法的探索和开发能力.同时通过引入自适应权重因子使改进的算法在迭代初期具有较大的权重充分探索未知空间算法迭代后期权重呈非线性减小算法可以在局部范围进行精细化搜索.最后将改进后的算法应用于求解栅格地图环境机器人路径规划的问题验证了算法可以更快地求解机器人的最佳无碰撞运动路径.后续的研究工作将在真实环境和动态障碍物环境中进一步探索算法性能的提升空间.参考文献:.:.():.:.:.():.():.蔡雨岑杜鹏桢.基于平衡鲸鱼优化算法的无人车路径规划.控制与决策():.(.():.)杨博李昌华李智杰等.改进鲸鱼算法及其在路径规划的应用.计算机测量与控制():.(.():.).:./.:.:.():.:./().:.孔芝杨青峰赵杰等.基于自适应调整权重和搜索策略的鲸鱼优化算法.东北大学学报(自然科学版)():.(.()():.)./.:.():.:.赵志刚林玉娇尹兆远.基于自适应惯性权重的均值粒子群优化算法.计算机工程与科学():.(.():.).():.第 期 赵俊涛等:改进鲸鱼优化算法在机器人路径规划中的应用