基于改进的樽海鞘群算法求解机器人路径规划问题  

Robot Path Planning Based on Improved Salp Swarm Algorithm

作　　者：刘景森[1,2] 袁蒙蒙 李煜[4] Liu Jingsen;Yuan Mengmeng;Li Yu(Institute of Intelligent Networks System,Henan University,Kaifeng,Henan 475004;College of Software,Henan University,Kaifeng,Henan 475004;School of Information Engineering,Zhengzhou Institute of Science and Technology,Zhengzhou 450052;Institute of Management Science and Engineering,Henan University,Kaifeng,Henan 475004)

机构地区：[1]河南大学智能网络系统研究所,河南开封475004 [2]河南大学软件学院,河南开封475004 [3]郑州科技学院信息工程学院,郑州450052 [4]河南大学管理科学与工程研究所,河南开封475004

出　　处：《计算机研究与发展》2022年第6期1297-1314,共18页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(71601071);河南省重点研发与推广专项(222102210065)。

摘　　要：为了探索出更好解决机器人路径规划问题的方法,提出一种差异演化的寄生樽海鞘群算法.首先在领导者位置更新公式中加入对应的上一代领导者位置信息,加强全局搜索的充分性,同时引入自适应惯性权重,更好平衡领导者在不同进化阶段对于广度和深度搜索的不同需求,提高寻优精度.然后在算法结构中引入具有不同演化策略和寄生行为机制的寄生-宿主双种群及宿主群劣汰思想,增加种群的多样性,提高算法跳出局部极值的能力.理论分析证明了改进算法的时间复杂度与基本算法相同,6种对比算法在10个不同特征的标准测试函数上进行仿真对比测试,实验结果表明:该算法的寻优精度、收敛性能均有显著提高和改善.最后将改进算法与三次埃尔米特插值相结合,以路径上的节点组合为基础定义算法中个体位置的编码方式,以绕开障碍、最短路径为目标构造了适应度函数和约束条件,求解机器人路径规划问题.在不同复杂程度的障碍物场景和不同插值方法下进行的算例求解结果显示,该算法寻优结果的最佳值、平均值和方差整体上明显优于其他5种性能优越的代表性对比算法,也验证了融合埃尔米特插值方法对于求解机器人路径规划问题的优越性和有效性.To find an improved method to solve the robot path planning problem,a parasitic salp swarm algorithm based on differential evolution strategy is proposed.The position of salp of the previous generation is added into the leader position update formula to enhance the adequacy of global search.At the same time,the inertia weight of nonlinear decreasing trend is introduced to reasonably adjust the balance between the breadth search and the depth mining of salp leaders in different iteration periods,to improve solution accuracy.The following are introduced into the evolutionary structure:1)The parasitic and host double populations with different evolutionary mechanisms,2)their parasitic behaviors,and 3)the idea of survival of the fittest,to increase the diversity of the population and improve the ability of the algorithm to jump out of the local extreme value.The theoretical analysis proves that the time complexity of the improved algorithm is the same as that of the basic algorithm,and the simulation experiment is conducted on 10 standard test functions with different characteristics through six representative comparison algorithms.The results show that the optimization accuracy and stability of the algorithm are significantly improved.Finally,the algorithm is combined with the hermite interpolation method to define the algorithm encoding mode based on the path node.The fitness function and constraint conditions are constructed to bypass obstacles and the shortest paths,to solve the robot path planning problem.Experimental results in different complex obstacle scenes and different interpolation methods for robot path planning show that the improved algorithm is superior to the other five comparison algorithms in terms of the best value,the average value and the variance of the solution results,which also proves the superiority and effectiveness of the fusion Hermite interpolation method in solving the robot path planning problem.

关 键 词：樽海鞘群算法 惯性权重 双种群 埃尔米特插值 机器人路径规划 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]