一种改进的爬行动物搜索算法

杜兴丽 刘玲 袁平

摘要：针对爬行动物搜索算法存在早熟收敛、易陷入局部最优等问题，提出一种改进的爬行动物搜索算法（LERSA）。通过精英反向学习策略提高初始种群的质量，在种群位置更新求解适应度值的过程中加入Levy飞行策略对种群中个体位置进行更新，结合非线性加权策略改良控制参数平衡RSA算法的全局搜索与局部搜索能力。使用公开的性能验证函数、秩和检验及三杆桁架问题进行算法性能测试，结果表明改进后的算法具有良好的寻优性能，能有效解决工程优化问题。

关键词：爬行动物搜索算法 精英反向学习 Levy飞行 非线性加权策略

中图分类号：T391文献标志码：A文章编号：1671-8755（2023）03-0082-07

An Improved Reptile Search Algorithm

DU Xingli1， LIU Ling2， YUAN Ping1

（1. School of Computer Science and Technology， Southwest University of Science and Technology，

Mianyang 621010， Sichuan， China; 2. Educational Informationization Office， Southwest University

of Science and Technology， Mianyang 621010， Sichuan， China）

Abstract：  An improved reptile search algorithm （LERSA） was proposed to address the problems of premature convergence and easy falling into local optimum in reptile search algorithm. The elite oppositionbased learning strategy was used to improve the quality of the initial population， the Levy flight strategy was added to update the individual positions in the population during the process of fitness value solution for population position update， and the nonlinear weighting strategy was combined to improve the control parameters to balance the global search and local search ability of RSA algorithm. The algorithm performance test was carried out by using the public performance verification function， rank sum test， and threebar truss problem. The results show that the improved algorithm has good optimization performance and can effectively solve engineering optimization problems.

Keywords：  Reptile search algorithm; Elite oppositionbased learning; Levy flight; Nonlinear weighting strategy

元启发式算法结合了随机算法和局部搜索算法的优势，具有较出色的搜索性能。爬行动物搜索算法（Reptile search algorithm，RSA）是Abualigah等受鳄鱼狩猎行为启发提出的一种新的元启发式算法［1］。RSA相较于蝗虫优化算法（Grasshopper optimization algorithm， GOA）［2］、灰狼优化算法（Grey wolf optimizer， GWO）［3］、海洋捕食者算法（Marine predators algorithm， MPA）［4］和樽海鞘优化算法（Salp swarm algorithm， SSA）［5］具有更好的全局搜索性能。

Almotairi等［6］将RSA算法与鮣鱼优化算法（Remora optimization algorithm， ROA）［7］相结合，使用均值转移策略来调控算法的搜索性能，解决RSA算法全局搜索与局部搜索不平衡的问题。Shinawi等［8］将RSA算法与自适应神经模糊推理系统（Adaptive neurofuzzy inference system， ANFIS）相結合，用于岩土的膨胀潜力预测。付华等［9］针对该算法的缺陷，使用水波进化和动态莱维飞行进行改进。李新华等［10］构建WPD-RSA-ELM模型进行水文时间序列多步预测。Ekinci等［11］提出基于莱维飞行的爬行动物搜索算法解决电力系统工程设计问题。Huang等［12］提出基于Levy飞行和交互式交叉策略的爬行动物搜索算法。

从已有的研究中发现，RSA算法所需调节参数少，易于实现，拓展了优化问题的解决方案。但RSA算法仍存在早熟收敛、寻优精度低和易陷入局部最优的问题［9］，算法局部搜索能力和全局搜索能力需要更好平衡［7］。针对前述问题，本文提出了一种改进的爬行动物搜索算法（Reptile search algorithm combining Levy flight and elite oppositionbased learning，LERSA），以期为工程优化问题提供更好的解决方案。

1爬行动物搜索算法

RSA算法核心包含2个阶段：围捕阶段和狩猎阶段。围捕阶段的策略是高空行走和腹部行走，负责全局搜索；狩猎阶段的策略是协调狩猎和合作狩猎，负责局部勘探。

当tT2时，进行全局搜索，数学表达式如下：

xt+1i，j=Besttj-ηti，j×β-Rti，j×rand，tT4（1）

xt+1i，j=Besttj×xr1，j×ES×rand，T4

当t>T2时，进行局部勘探，数学表达式如下：

xt+1i，j=Besttj×Pti，j×rand，T2

xt+1i，j=Besttj-ηti，j×ε-Rti，j×rand，t>3T4（4）

式中：Besttj是当前迭代的最优位置；rand∈［0，1］；r1∈［1，N］，N是候选解总数；ES=2×r3×（1-tT），r3∈［-1，1］，t是当前迭代次数，T是最大迭代次数；ηi，j=Besttj×Pi，j是第 i 个种群个体第 j 维的狩猎算子；Pi，j是最佳解与当前解在第j维位置的百分比，β是敏感系数；Ri，j是缩减函数，数学表达式如下：

Pi，j=α+xi，j-MxiBesttj×（Bj，u-Bj，l）+ε（5）

Mxi=1nnj=1xi，j（6）

Ri，j=Besttj-xr2，jBesttj+ε（7）

式中：ε是很小的正数；Mxi是候选解的平均位置；Bj，u与Bj，l是j维的上下界；α是敏感参数；r2∈［1，N］。

ES参数通过调节围捕阶段全局搜索的步长跳跃程度在一定程度上平衡算法的全局搜索和局部搜索。

2LERSA算法

LERSA算法的基本思路为：利用精英反向学习策略构建初始种群，提升初始种群的质量；利用Levy飞行策略改良种群个体的位置变更策略，增强RSA算法的局部搜索能力，让算法更好跳出局部最优；结合非线性加权策略，改良控制参数，平衡RSA算法的全局搜索与局部搜索能力。

2.1基于精英反向种群的初始化策略

精英反向种群初始化策略同时搜索当前解和动态反向学习的解，并选择保存更优的解［13］。本文使用精英反向学习构造反向种群［14］，并从候选解和反向候选解中选取最优解，使生成的候选解包含更多有效信息。该策略代替原算法的随机生成初始种群的方法，有助于提升算法初始种群质量，避免初始盲目搜索。

D维空间中精英xi的数学表达式如下：

xi=［xi，1，xi，2，…xi，D］（8）

种群精英反向解x—i，j的数学表达式如下：

x—i，j=r（bj，l+bj，u）-xi，j（9）

式中：xi，j是种群的个体信息；bj，l是种群的下边界；bj，u是种群的上边界。

2.2基于Levy飞行的个体更新策略

Levy飞行策略能提升种群个体位置更新的稳定性［15］。该策略有助于提升算法在后期跳出局部最优，避免陷入局部停滞。利用Levy飞行的步长和方向保证个体位置更新的稳定性，步长服从Levy分布，数学公式如下：

L（s）=γ2πexp［-γ2（s-μ）］1（s-μ）3/2（10）

式中：L（s）代表移动步长的概率；μ代表最小移动步长，0<μ

使用Levy飞行策略优化后，个体位置更新策略的数学表达式如下：

xti=xt-1i⊙L（λ）（11）

式中：L（λ）为Levy飞行策略的位置更新信息；xti为种群个体的位置信息。

2.3基于自适应的参数更新策略

ES参数用于控制算法全局搜索时的腹部行走策略，该参数影响算法跳出局部极值的能力。当RSA算法迭代次数设置为500次时，ES参数随迭代产生的信息变化过程如图1所示。

可以发现，参数值在后期仍然保持较大的跳跃范围，震荡较大，在一定程度上影响算法全局和局部搜索的性能平衡。针对前述问题，本文利用非线性加权的自适应参数优化RSA算法。在迭代初期，赋予算法较大的扰动性，保证算法能有效进行全局搜索，探索解的位置信息。但随着迭代次数增加，算法的扰动性不断降低，保证迭代后期算法能有效开展局部搜索，完成解的收敛。自适应参数更新策略的数学表达式如下：

ES=kπ6×r3×（arccos（tT））（12）

式中：k是扰动控制系数，本文实验中取值为2.5；t是当前迭代次数；T是最大迭代次数；r3∈［-1，1］。

改进后的ES参数随迭代次数的信息变化过程如图2所示。可以发现，改进后该参数随迭代时间呈现出非线性变化，后期震荡范围减小。

2.4LERSA算法实现流程

LERSA算法流程图如图3所示。

步骤1：初始化鳄鱼种群数目N，迭代次数T，求解问题的维数D以及参数β，α；

步骤2：使用精英反向学习策略初始化种群；

步驟3：计算种群个体的适应度信息；

步骤4：计算自适应参数ES;

步骤5：结合Levy飞行策略更新个体位置信息；

步骤6：判断个体位置信息是否越界；

步骤7：判断迭代是否结束，未结束则重复步骤3-步骤6。

3实验仿真与结果分析

为验证LERSA算法的性能，选择公开的测试函数进行验证。为提升实验说服力，选择对比算法为蚁狮算法（Ant lion optimizer， ALO）［16］、正余弦算法（Sine cosine algorithm， SCA）［17］、樽海鞘优化算法（SSA）、粒子群优化算法（Particle swarm optimization， PSO）［18］和RSA算法。其中ALO和SSA均为模拟相关生物捕食行为的仿生算法，该类算法在对比实验中较为常用。SCA是具有代表性的基于数学模型提出的一种优化算法。PSO是经典优化算法，为重要的对比算法。相关实验算法的重要参数设置如表1所示。

对比实验测试函数采用CEC常用的23组基准测试函数［19］。该组函数涵盖三类，分别是单峰测试函数（f1-f7）、多峰测试函数（f8-f13）和固定维多峰测试函数（f14-f23），具体函数名称、维度、最优值见参考文献［19］。

3.1算法性能测试

对比实验种群大小设置为30，最大迭代次数设置为500。为防止偶然实验的影响，本文的平均值和标准差由算法独立实验30次得到。实验测试函数为 f1-f15。结果表明，不同测试函数不同算法的实验结果存在差异。

测试函数f1-f7主要用于测试算法的局部搜索能力。在f1，f2，f3，f4上，RSA算法和LERSA算法均可以找到全局最优解，对于两者性能评估需要结合其他评价方式进行后续分析，而其他算法无法有效找到全局最优解。f5和f7测试函数的实验说明LERSA 算法能有效找到全局最优解，f6测试函数的实验结果LERSA算法表现相对较差。综合来看，改进后的LERSA算法具有更好的局部搜索性能，它能有效找到目标测试函数的全局最优解。

测试函数f8-f15主要用于全局搜索能力测试。在函数f9，f10，f11上，LERSA算法与RSA算法都能有效找到全局最优解。在其他测试函数上，LERSA算法的标准差更小，表明改进后算法的稳定性更强。综合来看，与对照算法相比较，改进后的算法稳定性更好，搜索能力更强。由于篇幅限制，此处展示具有代表性的f1和f13实验结果，如表2所示，其他测试函数详细实验数据略。

算法的收敛速度是评判算法效率的有效指标。从对比实验的结果来看，虽然部分算法在某些测试函数上可以探索到函数的全局最优解，但是算法所需要的时间资源开销远高于LERSA算法。由实验结果可知，在函数f1-f7，f9-f11和f13中，LERSA收敛速度和精度优于其他算法；在f8和f12中，收敛速度优于其他算法，但收敛精度排第二，略逊于RSA。

本文仅展示了f1和f13的收敛曲线，如图4所示，其他函数详细实验图略。从实验结果可知RSA和LERSA算法都可以探索到全局最优解，但结合收敛曲线可以发现改进算法LERSA的收敛速度更快，能更快逼近全局最优解。

综合实验结果可知，本文所提出的LERSA算法具有较高的收敛精度，同时具有相对较快的收敛速度。结合收敛曲线和实验数据可以发现LERSA算法具有较好的性能。

3.2改进策略贡献度消融分析

LERSA算法具有较好的算法性能，但该算法使用3种策略进行性能优化。所以，分析3种改良策略对算法性能贡献的多少是必不可少的实验环节。为方便实验分析，本文只讨论单一优化策略的性能贡献，并将3种不同策略优化的RSA算法进行统一标注。其中，基于精英反向种群初始化策略的RSA算法标记为ERSA算法；将基于Levy飞行个体位置更新策略的RSA算法标记为LRSA算法；基于自适应参数更新策略的RSA算法标记为IRSA算法。贡献度分析展示局部極值相对较多的f4和f13，如图5所示，其他测试详细实验结果图略。

Levy飞行策略的优化效果略优于自适应参数和精英反向种群优化策略，但每一种更新策略都为RSA算法的优化做出了正向贡献。综合来看，本文所提出的LERSA算法的3种改良策略都可以在一定程度上提升RSA算法的性能，因此改良策略是有效的。

3.3时间复杂度分析

设RSA算法的种群规模为N，问题的维度为D，最大迭代次数为T，初始化时间复杂度为O（N），位置更新复杂度为O（T×N）+O（T×N×D），则RSA的时间复杂度为O（N×（T×D+1））。

对于LERSA算法，精英反向种群初始化策略的时间复杂度为O（N），使用Levy飞行策略更新个体位置后，个体位置信息更新的时间复杂度为O（T×N）+O（T×N×D），同时因为自适应非线性加权参数只需要计算数值，没有引入额外的递归操作，因此该策略不会增加额外的时间复杂度。可以发现LERSA算法的时间复杂度为O（N×（T×D+1）），与RSA算法的时间复杂度保持一致，改良策略并没有消耗更多的实际资源。

3.4Wilcoxon秩和检验

算法性能优劣仅使用平均值和标准差来衡量是不够严谨的［20］，本文使用Wilcoxon秩和检验进一步测试算法性能。

本文以23个测试函数做秩和检验实验，分析结果可以发现，f15结果说明LERSA算法与ALO算法、SCA算法和SSA算法的秩和检验值大于5%，函数f1，f2，f3，f4，f9，f10和f11的实验结果为NaN，表明这些情况下，秩和检验不适用，原因是两种算法均能搜索到最优解；其他函数上不同算法的实验结果均小于5%，说明LERSA具有良好性能。详细实验数据略。

4工程实例验证——三杆桁架设计问题

三杆桁架问题是测试优化算法性能的实际工程问题，该问题具有较强的代表性，对算法性能要求较高，因此本文选择该问题验证改良算法LERSA对实际工程问题的优化性能。三杆桁架问题概要图如图6所示。

该问题的预期目标为重量最小，数学表达式如下：

minf（x）=（2x1+x2）×l（13）

s.t. g1（x）=2x1+x22x21+2x1x2P-σ0（14）

g2（x）=x22x21+2x1x2P-σ0（15）

g3（x）=12x2+x1P-σ0（16）

式中：0xi1，i=1，2；l=100 cm；P=2 kN/cm2；σ=2 kN/cm2。

在已有研究中，三杆桁架问题使用的优化解决方案有布谷鸟搜索算法（Cuckoo search algorithm， CS）［21］、算术优化算法（Arithmetic optimization algorithm， AOA）［22］、粒子群差分进化（Particle swarm optimization-Differential evolution， PSO-DE）［23］、飞蛾扑火算法（Mothflame optimization， MFO）［24］、蝗虫优化算法（GOA）和樽海鞘优化算法（SSA）等，本文将上述算法作为对照验证LERSA在解决该问题时的性能。

保持相同实验条件进行对照实验，实验结果如表3所示。可以发现，LERSA算法在求解三杆桁架设计问题时的性能略优于其他算法。

5结束语

本文使用精英反向学习策略提高初始化种群质量、Levy飞行改良种群的个体更新策略，结合非线性加权调节控制参数，提出一种改进的爬行动物搜索算法。实验证明，与当前流行的其他算法对比，改进后算法的综合性能较优，并在三杆桁架问题上取得了较好结果。改进的爬行动物搜索算法能有效解决工程优化问题，为工程优化问题提供了一种更优的解决方案。

参考文献

［1］ABUALIGAH L， ELAZIZ M A， SUMARI P， et al. Reptile search algorithm （RSA）： A natureinspired metaheuristic optimizer［J］. Expert Systems with Applications， 2022， 191： 116158.

［2］SAREMI S， MIRJALILI S， LEWIS A. Grasshopper optimisation algorithm： theory and application［J］. Advances in Engineering Software， 2017， 105： 30-47.

［3］MIRJALILI S， MIRJALILI S M， LEWIS A. Grey wolf optimizer［J］. Advances in Engineering Software， 2014， 69： 46-61.

［4］FARAMARZI A， HEIDARINEJAD M， MIRJALILI S， et al. Marine predators algorithm： A natureinspired metaheuristic［J］. Expert Systems with Applications， 2020， 152： 113377.

［5］DUAN Q， WANG L， KANG H W， et al. Improved salp swarm algorithm with simulated annealing for solving engineering optimization problems［J］. Symmetry， 2021， 13（6）： 1092.

［6］ALMOTAIRI K H， ABUALIGAH L. Hybrid reptile search algorithm and remora optimization algorithm for optimization tasks and data clustering［J］. Symmetry， 2022， 14（3）： 458.

［7］JIA H M， PENG X X， LANG C B. Remora optimization algorithm［J］. Expert Systems with Applications， 2021， 185： 115665.

［8］EL SHINAWI A， ALI IBRAHIM R， ABUALIGAH L， et al. Enhanced adaptive neurofuzzy inference system using reptile search algorithm for relating swelling potentiality using index geotechnical properties： a case study at el sherouk city， Egypt［J］. Mathematics， 2021， 9（24）： 3295.

［9］付華，许桐，邵靖宇.基于水波进化和动态莱维飞行的爬行动物搜素算法［J/OL］.控制与决策， 2023： 1-9.（2023-05-02）. http：//kzyjc.alljournals.cn/kzyjc/article/abstract/2022-0647.

［10］李新华， 崔东文. 基于WPD-RSA-ELM模型的水文时间序列多步预测［J］. 水利水电技术（中英文）， 2022， 53（11）： 69-77.

［11］EKINCI S， IZCI D， ABU ZITAR R， et al. Development of Lévy flightbased reptile search algorithm with local search ability for power systems engineering design problems［J］. Neural Computing and Applications， 2022， 34（22）： 20263-20283.

［12］HUANG L Q， WANG Y Y， GUO Y X， et al. An improved reptile search algorithm based on Lévy flight and interactive crossover strategy to engineering application［J］. Mathematics， 2022， 10（13）： 2329.

［13］WEI W H， ZHOU J L， CHEN F， et al. Constrained differential evolution using generalized oppositionbased learning ［J］. Soft Computing， 2016， 20（11）： 4413-4437.

［14］ZHOU Y Q， WANG R， LUO Q F. Elite oppositionbased flower pollination algorithm［J］. Neurocomputing， 2016， 188： 294-310.

［15］HOUSSEIN E H， SAAD M R， HASHIM F A， et al. Lévy flight distribution： A new metaheuristic algorithm for solving engineering optimization problems［J］. Engineering Applications of Artificial Intelligence， 2020， 94： 103731.

［16］MIRJALILI S. The ant lion optimizer［J］. Advances in Engineering Software， 2015， 83： 80-98.

［17］MIRJALILI S. SCA： a Sine Cosine Algorithm for solving optimization problems［J］. KnowledgeBased Systems， 2016， 96： 120-133.

［18］WANG D S， TAN D P， LIU L. Particle swarm optimization algorithm： an overview［J］. Soft Computing， 2018， 22（2）： 387-408.

［19］SUGANTHAN P N， HANSEN N， LIANG J J， et al. Problem definitions and evaluation criteria for the CEC 2005 special session on realparameter optimization［J］. Natural Computing， 2005： 341-357.

［20］DERRAC J， GARCA S， MOLINA D， et al. A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms［J］. Swarm and Evolutionary Computation， 2011， 1（1）： 3-18.

［21］GANDOMI A H， YANG X S， ALAVI A H. Cuckoo search algorithm： a metaheuristic approach to solve structural optimization problems［J］. Engineering with Computers， 2013， 29（1）： 17-35.

［22］ABUALIGAH L， DIABAT A， MIRJALILI S， et al. The arithmetic optimization algorithm［J］. Computer Methods in Applied Mechanics and Engineering， 2021， 376： 113609.

［23］LIU H， CAI Z X， WANG Y. Hybridizing particle swarm optimization with differential evolution for constrained numerical and engineering optimization［J］. Applied Soft Computing， 2010， 10（2）： 629-640.

［24］MIRJALILI S. Mothflame optimization algorithm： A novel natureinspired heuristic paradigm［J］. KnowledgeBased Systems， 2015， 89： 228-249.