基于自适应调整哈里斯鹰优化算法求解机器人路径规划问题

黄霖，符强，童楠

基于自适应调整哈里斯鹰优化算法求解机器人路径规划问题

黄霖1，符强1，2*，童楠2

（1.宁波大学 信息科学与工程学院，浙江 宁波 315000； 2.宁波大学科学技术学院 信息工程学院，浙江 宁波 315300）（∗通信作者电子邮箱fuqiang@nbu.edu.cn）

针对启发式算法在机器人路径规划过程中存在路径长度不稳定和易陷入局部极小点的问题，提出一种基于自适应调整哈里斯鹰优化（AAHHO）算法。首先，利用收敛因子调整策略，调节全局搜索阶段和局部搜索阶段的平衡，同时利用自然常数为底数，提高搜索效率和收敛精度；其次，在全局搜索阶段，采用精英合作引导搜索策略，通过3个精英哈里斯鹰合作引导其他个体更新位置以提高搜索性能，通过3个最优位置加强种群间的信息交流；最后，通过模拟种内竞争策略增强哈里斯鹰跳出局部最优的能力。函数测试和机器人路径规划对比实验结果表明，所提算法无论是函数测试还是机器人路径规划都优于IHHO（Improve Harris Hawk Optimization）和CHHO（Chaotic Harris Hawk Optimization）等对比算法，对于求解机器人的路径规划具有较好的有效性、可行性和稳定性。

机器人；路径规划；哈里斯鹰优化算法；收敛因子调整；精英合作引导搜索；种内竞争

0 引言

随着机器人技术的快速发展，移动机器人广泛应用于工业、医疗和农业等领域［1］。移动机器人的路径规划是移动机器人研究中一项关键性技术，移动机器人路径规划的目标是从起点到目标点之间寻找到一条无碰撞且代价低的路线。规划有效且避障的路线一直是该技术的难题，国内外学者针对这一难题提出了许多路径规划方法［2］，例如A*（A star）［3］、人工势场［4］、启发式算法（群智能算法）［5］、神经网络［6］、深度学习［7］和强化学习［8］等不同机制特点的技术及方法，其中具有寻优机制简单、参数设置少、鲁棒性强和全局搜索能力强等特点的启发式算法通常被应用于机器人路径规划［9-10］。

Heidari等［11］提出一种新型启发式算法——哈里斯鹰优化（Harris Hawk Optimization， HHO）算法。HHO算法参数少、原理简单，且有较强的全局搜索能力，已经在车间调度［12］、图像处理［13-16］、神经网络训练［17］和特征选择［18-22］等方面有实际应用；但是与其他群智能算法［23］一样，HHO算法存在收敛精度低、收敛较慢和较易陷入局部最优的缺点。针对这些不足，本文提出了自适应调整哈里斯鹰优化（Adaptive Adjusted HHO， AAHHO）算法。首先通过采用收敛因子的调整策略，利用指数函数收敛性能提高后期的收敛精度，并通过调整倍数和指数函数提高前期的全局搜索概率，从而增强算法的寻优能力；其次针对哈里斯鹰缺乏种群间的信息交流和全局搜索的盲目性，引入精英合作引导搜索策略，根据适应度值排名前3的3只哈里斯鹰带领着种群更新位置，提高算法的搜索性能和效率；最后，因为引入了精英合作引导搜索策略，同时也增加了对精英哈里斯鹰以及算法自身种群对平均位置的依赖性，提高了陷入局部最优的概率，为了解决这一问题，加入了种内竞争策略，以增强跳出局部最优的能力。将AAHHO算法与对比算法分别进行函数测试比较并应用到机器人的路径规划，测试结果表明，AAHHO算法在寻优性能上和稳定性上都具有良好的优势。

1 HHO算法

HHO算法中每只哈里斯鹰个体代表区间内的一个可行解（候选解）。通过探索和开发阶段实现在区间内全局搜索和局部搜索猎物，而猎物的逃逸能量因子可以实现探索和开发的转换。

1.1　探索阶段

其中为种群数。

1.2　探索阶段与开发阶段的转换

在逃跑过程中，猎物的逃逸能量不断地减少，当逃逸能量减小为一定数值时，哈里斯鹰会采取策略的转换，从探索阶段的全局搜索转换为开发阶段的局部搜索。逃逸能量因子的公式为：

1.3　开发阶段

1.3.1软围攻

1.3.2硬围攻

1.3.3渐进式快速俯冲软围攻

1.3.4渐进式快速俯冲硬围攻

2 AAHHO算法

在HHO中，探索阶段和开发阶段转换始终存在矛盾，在迭代前期可能出现一定概率的局部搜索，导致HHO算法容易陷入局部最优。通过提出收敛因子调整策略，提高算法前期全局搜索的概率，降低算法前期进行局部搜索的概率，在一定程度上避免早熟收敛。在探索阶段，HHO算法采用随机哈里斯鹰个体更新位置，缺乏种群间的相互交流，而且在更新位置时，步长设置过长，导致位置更新“失效”。通过引入精英合作引导搜索策略，让精英哈里斯鹰引导其他个体更新位置；同时增加种群间的信息交流，利用精英合作引导式搜索控制过大的步长。HHO算法在更新时，比较依赖种群间的平均位置，在转换阶段时，因搜索不足容易导致陷入局部最优，通过引入种内竞争策略，在一定程度上能够帮助跳出局部最优。

2.1　收敛因子调整策略

HHO算法与AAHHO算法的逃逸能量对比如图1所示。从图1中可以看出：AAHHO算法前期逃逸能量的值比HHO算法大，降低了前期出现局部搜索的概率；AAHHO算法后期逃逸能量的值比HHO算法小，提高了后期的收敛精度。AAHHO算法打破了HHO算法以区间的范围，增大范围而不改变逃逸能量值以1和0.5为界限，以此增大前期全局搜索的概率。

2.2　精英合作引导搜索策略

哈里斯鹰之所以独特，就在于它可以跟其他家庭成员合作捕食从而进化出创新的团队追逐能力。在哈里斯鹰种群内之间存在阶层，利用种群内阶级，而选择适应度最好的三只精英哈里斯鹰进行引导式全局搜索：一方面，增加了种群间的信息交流；另一方面，通过精英引导以此提高哈里斯鹰全局搜索的性能。

2.3　种内竞争策略

从生态学的角度来看，种内竞争能够保留更加优秀和更加强壮的个体，使得衍生出更优秀的精英。通过模拟种内竞争策略来使得资源更有效的利用，为了更好模拟作如下假设：

1）在开发阶段每一轮迭代都能获取到食物。

2）食物量只够一只哈里斯鹰享用。

3）获得食物的为适应度值最高的哈里斯鹰，而未获得食物的哈里斯鹰则会遭到适应度值高的哈里斯鹰驱逐。

哈里斯鹰为了能够更好地享用食物，针对威胁度高的哈里斯鹰作出驱逐，而面对威胁度低的哈里斯鹰戒备心会有所降低，其数学模型为：

通过驱逐因子扩大搜索范围，同时一定程度上能够跳出局部最优。种内竞争策略是通过适应度值占比进行调节。适应度值越接近驱逐因子越大。

2.4　AAHHO算法流程

综上所述，本文改进HHO算法，利用3种相互联系的策略，提出了AAHHO算法。算法的流程如下。

步骤2 计算种群的适应度值。

步骤3 根据式（14），计算猎物的逃逸能量。

根据式（1）和式（15）更新位置

否则

通过式（19）模拟种内竞争，更新哈里斯鹰位置

步骤4 重复步骤2～3，直至达到最大迭代次数。

步骤5 输出最优解。

2.5　复杂度分析

表达式的3个部分分别代表计算适应度值、位置更新和种内竞争策略，因此AAHHO算法的时间复杂度为：

3 仿真实验与结果分析

本文仿真环境为Intel i7-8550U（1.8 GHz）处理器和8 GB运行内存，程序在Matlab 2018b仿真平台运行。为了测试改进算法的优化性能，将AAHHO算法与HSCA（Hybrid Sine Cosine Algorithm， HSCA）［9］、TGWO（Tent-initialized Grey Wolf Optimization， TGWO）［5］、HHO算法［11］、IHHO（Improved HHO）算法［12］和CHHO（Chaotic HHO）算法［25］进行对比测试。

3.1　测试函数

为了更好地体现改进算法的性能，引用15个CEC标准测试函数对本文改进算法进行分析比较，通过单峰函数测试算法的收敛精度和速度，通过多峰函数测试算法的跳出局部最优解的能力，两者结合检验算法的寻优性能。测试函数如表1所示。

表1　测试函数

为了测试的公平性，将各个算法的种群数都设置为30，迭代次数设置为500，分别单独进行30次实验，并统计30次实验得到的结果的平均值（AVG）和标准差（STD），实验测试结果如表2所示。

通过收敛曲线，可以更直观地看出算法的寻优性能，6种算法测试函数的收敛曲线如图2所示。图2（a）～（f）为单峰测试函数的收敛曲线，通过与其他5种算法收敛曲线对比可以看出，图2（a）～（c）中AAHHO算法在精英合作引导策略和收敛因子调整策略的作用下，能快速找到最优解，收敛更快，收敛精度更高；图2（d）～（f）中，AAHHO算法在前期搜索时也曾陷入局部最优，但后期的种内竞争使之能够摆脱。图2（g）～（o）为多峰测试函数的收敛曲线，其中：对于图2（g）（j）（k）（m），AAHHO算法相较于HHO、IHHO和CHHO算法更接近最优解；对于图2（h）（i）（l），AAHHO算法的收敛和寻找最优解相较于其他5种算法更快；对于图2（n），TGWO一直困入局部最优，其他算法前期收敛都快；对图2（o），AAHHO算法能够逼近最优值，明显优于其他5种算法。

表2　6种算法在固定迭代次数下寻优结果比较

注：AVG表示均值，STD表示标准值。

由实验对比结果分析可知，AAHHO算法表现了较好的优化性能，寻优精度、寻优稳定性和收敛速度优于其他5种性能优越的代表性对比算法。

3.2　基于AAHHO算法的机器人路径规划

为了更好地展现AAHHO算法优势，将AAHHO算法应用于机器人的路径规划问题。很多学者将插值的方式应用于机器人的路径规划［10，26］，路径较短，但是机器人在移动过程中需要更多的判断和调整；而采用直线，只需设定几个节点直行，在节点旋转角度即可，不需要较多复杂的计算判断过程。

3.2.1环境建模与适应度函数

在建立模型前，先做如下假设：

1）将机器人看作一个无质量和无大小的质点。

2）移动的环境设置为二维。

3）障碍物为圆形，空间只有分布随意且若干个障碍物。

3.2.2基于AAHHO算法的机器人路径规划流程

基于AAHHO算法机器人路径规划的算法具体流程如下：

步骤1 根据具体环境设置节点数和最大迭代次数，确定机器人起点坐标和终点坐标。

步骤3 根据AAHHO算法和适应度函数更新每只哈里斯鹰的坐标位置。

步骤4 重复步骤3，直到达到最大迭代次数。

步骤5 输出最优路径。

图2　15个基准函数收敛曲线

3.2.3机器人的路径规划

不同场景的路径规划和收敛曲线对比如图3所示。

场景一障碍物较少，故设它的路径节点数为2，终点坐标为（4，4）和起点坐标为（0，0）。

场景二障碍物较多，故设它的路径节点数为3，终点坐标为（6，6）和起点坐标为（0，0）。

表3分别统计了6种算法在不同场景下的路径长度的最优值、最差值、平均值和方差，可以看出，AAHHO算法的搜索性能和稳定都较好。从图3（b）可以看出，对于HSCA算法，通过反向学习初始化种群、模因分组和种群进化等策略，在初始路径和寻优上具有部分优势，但在收敛性能上存在缺陷。

表36种算法在不同场景下的路径比较

Tab.3　Path comparison of six algorithms in different scenarios

对于TGWO算法，通过控制参数调整、动态权重因子和适应度比例系数等策略，在稳定性上和收敛性能上是有优势的。对于CHHO算法，采用高斯混沌映射，作用于探索、开发阶段和逃逸能量，对收敛精度有一定的改善。对于IHHO算法，通过两个精英个体引导其他个体，作用于全局搜索，使它的搜索性能有一定的改善。AAHHO算法在全局搜索上得益于精英合作引导搜索策略对节点坐标的把控较好，通过收敛因子的调节，在增大前期的全局搜索能力的同时，提高了后期的收敛精度，使路径规划的寻优和稳定性都较好。

图3　不同场景的路径规划和收敛曲线对比

4 结语

为了更好地求解机器人的路径规划问题和改进HHO算法的性能，本文针对HHO算法收敛精度不高、易陷入局部最优等存在的不足进行改进，提出AAHHO算法。首先，引入精英合作引导搜索策略，提高种群之间的相互交流和搜索性能，引入了收敛因子调整策略，提高前期全局搜索概率，利用指数函数特性提高后期的收敛精度；其次，加入了种内竞争策略，提高陷入局部极值的摆脱能力；再次，通过与5种其他对比算法进行测试函数实验对比分析，仿真结果验证了AAHHO算法具有较好的收敛精度和寻优性能；最后，通过将AAHHO算法与其他5种算法进行机器人路径规划的对比，验证了本文算法在求解机器人路径规划问题的优越性和稳定性。下一步将继续改进哈里斯鹰算法的寻优性能，研究新的改进算法并应用于机器人的路径规划和更多复杂的实际问题的优化。

[1] DENG X， LI R， ZHAO L， et al. Multi-obstacle path planning and optimization for mobile robot［J］. Expert Systems with Applications， 2021， 183： 115445.

[2] 徐小强，王明勇，冒燕.基于改进人工势场法的移动机器人路径规划［J］.计算机应用，2020，40（12）：3508-3512.（XU X Q， WANG M Y， MAO Y.Path planning of mobile robot based on improved artificial potential field method ［J］. Journal of Computer Applications， 2020，40 （12）： 3508-3512.）

[3] HUANG H， LI Y， BAI Q. An improved A star algorithm for wheeled robots path planning with jump points search and pruning method ［J］. Complex Engineering Systems， 2022， 2（3）： 11.

[4] 李伟，金世俊.基于人工势场法和启发式采样的最优路径收敛方法［J］.计算机应用，2021，41（10）：2912-2918.（LI W， JIN S J . Optimal path convergence method based on artificial potential field method and informed sampling ［J］. Journal of Computer Applications， 2021，41（10）： 2912-2918.）

[5] 刘志强，何丽，袁亮，等.采用改进灰狼算法的移动机器人路径规划［J］.西安交通大学学报，2022，56（10）：49-60.（LIU Z Q， HE L， YUAN L， et al. Path planning of mobile robot based on TGWO algorithm ［J］. Journal of Xi’an Jiaotong University， 2022，56（10）： 49-60.）

[6] WANG J， LIU J， CHEN W， et al. Robot path planning via neural-network-driven prediction［J］. IEEE Transactions on Artificial Intelligence， 2021， 3（3）： 451-460.

[7] WU P， CAO Y， HE Y， et al. Vision-based robot path planning with deep learning［C］// Proceedings of the 11th International Conference on Computer Vision Systems. Cham： Springer， 2017： 101-111.

[8] ABDI A， ADHIKARI D， PARK J H. A novel hybrid path planning method based on Q-learning and neural network for robot arm ［J］. Applied Sciences， 2021， 11（15）： 6770.

[9] 马莹莹，杜暖男.基于改进正余弦算法的机器人路径规划［J］.重庆交通大学学报（自然科学版），2021，40（9）：17-23.（MA Y Y， DU N N. Robot path planning based on the improved sine cosine algorithm ［J］. Journal of Chongqing Jiaotong University （Natural Sciences）， 2021，40 （9）： 17-23.）

[10] 刘景森，吉宏远，李煜.基于改进蝙蝠算法和三次样条插值的机器人路径规划［J］.自动化学报，2021，47（7）：1710-1719.（LIU J S， JI H Y， LI Y. Robotic path planning based on improved bat algorithm and cubic spline interpolation ［J］. Acta Automatica Sinica， 2021，47 （7）： 1710-1719.）

[11] HEIDARI A A， MIRJALILI S， FARIS H， et al. Harris hawks optimization： algorithm and applications ［J］. Future Generation Computer Systems， 2019， 97： 849-872.

[12] LIU C. An improved Harris hawks optimizer for job-shop scheduling problem［J］. The Journal of Supercomputing， 2021， 77： 14090-14129.

[13] JIA H， LANG C， OLIVA D， et al. Dynamic Harris hawks optimization with mutation mechanism for satellite image segmentation ［J］. Remote Sensing， 2019， 11（12）： 1421.

[14] GOLILARZ N A， MIRMOZAFFARI M， GASHTEROODKHANI T A， et al. Optimized wavelet-based satellite image de-noising with multi-population differential evolution-assisted Harris hawks optimization algorithm［J］. IEEE Access， 2020， 8： 133076-133085.

[15] JIA H， PENG X， KANG L， et al. Pulse coupled neural network based on Harris hawks optimization algorithm for image segmentation ［J］. Multimedia Tools and Applications， 2020， 79： 28369-28392.

[16] BANDYOPADHYAY R， KUNDU R， OLIVA D， et al. Segmentation of brain MRI using an altruistic Harris hawks’ optimization algorithm［J］. Knowledge-Based Systems， 2021， 232： 107468.

[17] CAMPBELL M O N. The Great Eagles： Their Evolution， Ecology and Conservation ［M］. Boca Raton： CRC Press， 2022：347-363.

[18] TURABIEH H， AZWARI S A， ROKAYA M， et al. Enhanced Harris hawks optimization as a feature selection for the prediction of student performance ［J］. Computing， 2021， 103： 1417-1438.

[19] ABDEL-BASSET M， DING W， EL-SHAHAT D. A hybrid Harris hawks optimization algorithm with simulated annealing for feature selection ［J］. Artificial Intelligence Review， 2021， 54： 593-637.

[20] SIHWAIL R， OMAR K， ARIFFIN K A Z， et al. Improved Harris hawks optimization using elite opposition-based learning and novel search mechanism for feature selection ［J］. IEEE Access， 2020， 8： 121127-121145.

[21] AL-SAFI H， MUNILLA J， RAHEBI J. Patient privacy in smart cities by blockchain technology and feature selection with Harris Hawks Optimization （HHO） algorithm and machine learning ［J］. Multimedia Tools and Applications， 2022， 81： 8719-8743.

[22] ZHANG Y， LIU R， WANG X， et al. Boosted binary Harris hawks optimizer and feature selection ［J］. Engineering with Computers， 2021， 37： 3741-3770.

[23] CHAKRABORTY A， KAR A K. Swarm intelligence： a review of algorithms ［M］// Nature-Inspired Computing and Optimization 10. Cham： Springer， 2017： 475-494.

[24] BARTHELEMY P， BERTOLOTTI J， WIERSMA D S. A Lévy flight for light ［J］. Nature， 2008， 453： 495-498.

[25] GEZICI H， LIVATYALI H. Chaotic Harris hawks optimization algorithm ［J］. Journal of Computational Design and Engineering， 2022， 9（1）： 216-245.

[26] 刘景森，袁蒙蒙，李煜.基于改进的樽海鞘群算法求解机器人路径规划问题［J］.计算机研究与发展，2022，59（6）：1297-1314.（LIU J S， YUAN M M， LI Y. Robot path planning based on improved salp swarm algorithm ［J］. Journal of Computer Research and Development， 2022，59（6）： 1297-1314.）

Solving robot path planning problem by adaptively adjusted Harris hawk optimization algorithm

HUANG Lin1， FU Qiang1，2*， TONG Nan2

（1，，315000，；2，，315300，）

Aiming at the problem that the heuristic algorithms have unstable path lengths and are easy to fall into local minimum in the process of robot path planning， an Adaptively Adjusted Harris Hawk Optimization （AAHHO） algorithm was proposed. Firstly， the convergence factor adjustment strategy was used to adjust the balance between the global search stage and the local search stage， and the natural constant was used as the base to improve the search efficiency and convergence accuracy. Then， in the global search phase， the elite cooperation guided search strategy was adopted， by three elite Harris hawks cooperatively guiding other individuals to update the positions， so that the search performance was enhanced， and the information exchange among the populations was enhanced through the three optimal positions. Finally， by simulating the intraspecific competition strategy， the ability of the Harris hawks to jump out of the local optimum was improved. The comparative experimental results of function testing and robot path planning show that the proposed algorithm is superior to comparison algorithms such as IHHO（Improve Harris Hawk Optimization） and CHHO（Chaotic Harris Hawk Optimization）， in both function testing and path planning， and it has better effectiveness， feasibility and stability in robot path planning.

robot; path planning; Harris Hawk Optimization (HHO) algorithm; convergence factor adjustment; elite cooperation guided search; intraspecific competition

This work is partially supported by Ningbo Natural Science Foundation （2021J135）.

HUANG Lin， born in 1997， M.S. candidate. His research interests include swarm intelligence algorithm， machine learning.

FU Qiang， born in 1975， Ph. D.， associate professor. His research interests include swarm intelligence algorithm， machine learning.

TONG Nan， born in 1981， M.S.， lecturer. Her research interests include path planning， swarm intelligence algorithm.

TP242； TP301.6

A

1001-9081（2023）12-3840-08

10.11772/j.issn.1001-9081.2022121847

2022⁃12⁃13；

2023⁃03⁃03；

2023⁃03⁃06。

宁波市自然科学基金资助项目（2021J135）。

黄霖（1997—），男，江西赣州人，硕士研究生，主要研究方向：群智能算法、机器学习；符强（1975—），男，江西赣州人，副教授，博士，CCF会员，主要研究方向：群智能算法、机器学习；童楠（1981—），女，浙江绍兴人，讲师，硕士，主要研究方向：路径规划、群智能算法。