基于扰动因子和贪心策略的白骨顶优化算法

李雪利， 杜逆索， 欧阳智， ， 朱 鹏

（1 贵州大学数学与统计学院， 贵阳 550025； 2 贵州大学贵州省大数据产业发展应用研究院， 贵阳 550025；3 贵州大学计算机科学技术学院， 贵阳 550025）

0 引 言

群智能优化算法通过模拟生物群体行为所构建的优化模型，帮助解决了实际复杂项目和工程的优化问题。 如蚁狮算法［1］、灰狼优化算法［2］、蝗虫优化算法［3］、正余弦算法［4］、多元宇宙优化算法［5］等，这些算法主要研究在复杂的多维解空间里寻得全局最优解。

白骨顶优化算法（Coot Optimization Algorithm，COOT）是Naruei 等［6］在2021 年提出的一种新型智能优化算法。 该算法通过模拟白骨顶在水中的不同运动方式，并将这些运动方式抽象于数学建模以实现全局寻优。 因该算法结构简单、控制参数少、求解精度高等优点，并在测试中试验结果良好，故具有广泛的应用前景。 虽然COOT 算法在优化方面具有一定优势，但寻优过程中依然存在一些不足。 如：白骨顶的种群随机初始化和参数随机化会影响算法的寻优性能，白骨顶个体的位置更新机制无法很好地平衡局部探索与全局开发的关系，以及收敛精度欠缺等问题。

目前，由于群智能算法都存在与COOT 相似的问题，促使研究者对此开展了相关研究。 为了实现更好的寻优性质，研究人员对群智能优化算法的参数进行调整，将群智能优化算法与反向学习［7］、莱维飞行［8］等策略相结合。 例如，魏伟一等［9］将精英反向学习与萤火虫算法相结合，并使用了自适应步长平衡算法的探索能力，使算法具有更快的收敛速度，更准确的收敛精度。 肖子雅等［10］将鲸鱼优化算法与精英反向学习和黄金分割数相结合，通过平衡算法的局部搜索和全局优化能力，来增强算法的稳定性，得到更优的搜索结果。 为了缓解算法容易陷入局部最优，无法寻得全局最优的问题，杨文珍等［11］将扰动机制和强化莱维飞行融入蝗虫优化算法，增强了算法的全局搜索能力。 唐海波等［12］在算法中加入模拟退火与贪心策略，有效的提高了算法性能。

综上所述，现已有许多研究针对各种群体智能优化算法的不足之处提出了不同的策略方法，并取得了一定程度的改进效果，而针对白骨顶优化算法不足的研究还较少。 本文针对COOT 算法存在收敛速度慢、收敛精度欠缺的问题，提出了基于扰动因子和贪心策略改进的白骨顶优化算法（PGCOOT）：一方面在白骨顶种群初始化阶段结合精英反向学习进行初始化，另一方面在白骨顶个体移动中融入扰动因子和贪心策略来改变移动机制。 因此，本文所提算法不仅改善了白骨顶种群的位置分布，而且能够更好的协调算法的局部搜索和全局优化能力，从而提高算法的收敛性能。

1 白骨顶优化算法

白骨顶优化算法（COOT）是在研究白骨顶在水中两种运动方式的基础上提出的一种新型智能优化算法。 在COOT 优化算法中，整个白骨顶种群由领导者（leader）和普通白骨顶鸟（coot）组成。 领导者是指种群前面的少数指引种群走向目标（食物）的白骨顶。 白骨顶有许多不同的集体行为，COOT 算法的目标是模拟白骨顶在水面上的集体运动。 算法中模拟了白骨顶在水面上4 种不同的移动，分别是：个体的随机移动、链式移动、根据群体领导者们调整位置以及leader 带领种群走向最佳区域（领导者运动）。

1.1 初始化阶段

使用公式（1）在空间中随机生成Coot 种群：

其中，CootPos（i） 为cooti的位置；d为一系列的变量或问题维度；lb为搜索空间的下限；ub为搜索空间的上限；.∗为点乘运算。

在生成初始群体并确定每个主体的位置后，随机选取NL个白骨顶个体作为leader，最后通过目标函数计算所有白骨顶的适应度。

1.2 coot 的移动

在整个移动过程中，coot每次都从个体的随机移动、链式移动、根据群体领导者们调整位置这3 种移动方式中随机选取一种作为移动方式。

1.2.1 个体随机移动

个体的随机移动能对搜索空间的不同部分进行探索。 如果算法陷入局部最优，采用随机移动的方式能够缓解此类问题。 为了实现这种移动，首先随机选取一个位置， 再将coot移向这个位置，之后根据公式（2） 来更新coot的位置。

其中，R2 为区间［0， 1］ 中的随机数；CootPos（i） 表示cooti的位置；Q为随机选取的位置；A值可根据公式（3）计算得出。

其中，L表示当前迭代次数，Iter表示最大迭代次数。

1.2.2 链式移动

实现链移动时，首先计算两个白骨顶位置点之间的距离矢量，然后向其中一个白骨顶的方向移动另一个白骨顶，移动距离为矢量的一半。 新位置的计算方法为公式（4）。

其中，CootPos（i） 表示cooti的位置，CootPos（i －1） 表示cooti－1的位置。

1.2.3 根据群体领导者们调整位置

当前面的几个leader 领导族群走向最佳区域时，其余的coot 则根据leader 的位置调整自己的位置。 由于种群中不止一个leader，因此coot 在移动过程中根据公式（5）的机制来选择某一个leader 作为参考位置。

其中，i为当前coot 的索引号；NL为初始时设置的leader 数量；K为leader 的索引号；MOD 表示取余运算。

在选定某个leader 作为参考位置后，coot 则朝着参考位置移动。 移动后的新位置由公式（6）计算得出。

其中，CootPos（i） 表示cooti当前位置；LeaderPos（k） 为选定的leaderk的位置；R1 为区间［0，1］中的随机数；π 为圆周率；R为区间［－1，1］中的随机数。

1.3 leader 的移动

COOT 优化寻优过程中，领导者leader 的移动至关重要，leader 需要朝着目标（最优点）更新位置。有时领导者需要离开当前的最佳位置去寻找更好的位置。 更新领导者位置的计算如公式（7）。 这个公式展现了接近和远离当前最佳位置的策略。

其中，LeaderPos（i） 为leaderi的位置；gBest为迄今为止发现的最佳位置；R3、R4 为区间［0，1］中的随机数；π 为圆周率；R为区间［ －1，1］中的随机数；B可根据公式（8）计算所得。

其中，L表示当前迭代，Iter表示最大迭代。

随机选择接近或远离当前最佳位置，并以不同的半径在迄今最佳的位置周围进行搜索，意味着白骨顶优化算法在接近最优点的阶段也在进行探索，以便算法远离陷入局部最优的困境。

2 白骨顶优化算法的改进

2.1 精英反向学习

一般而言，算法的收敛精度和速度均与初始种群中个体的位置分布有关。 与其它算法类似，COOT算法在使用随机方式对coot 种群位置进行初始化后，才进行优化迭代。 但随机初始化会导致COOT算法的可行解范围较大，造成算法收敛时间较长，会降低算法的搜索能力，影响算法的搜索结果等问题。

一般而言，精英反向学习策略可以对种群初始化阶段进行优化来提升算法的收敛性能。 首先，在种群初始化阶段产生相应的反向种群。 生成反向种群的方式表示如公式（9）所示：

其中，CootPos（i） 为当前个体cooti的位置信息；为相应的反向种群个体的位置信息；lb为搜索空间的下限；ub为搜索空间的上限；k是产生于［0，1］之间的随机数。

其次，根据公式（10），在得到反向种群位置信息后，依序比较初始种群和反向种群的个体适应度，最后将同一位置的适应度更优的个体放入初始种群的对应位置中。

其中，CootPos（i） 为当前个体cooti的位置信息；为相应的反向种群个体的位置信息；为反向种群中个体的适应度值；fi为随机初始化种群中个体cooti的适应度值。

2.2 贪心策略移动机制

COOT 优化算法寻优过程中，由于coot 的移动方式是从上述3 种移动方式中随机选取的。 这种个体移动选择方式容易出现收敛速度慢、收敛精度低等问题。 因此，考虑在coot 的移动方式选取过程中加入贪心策略，来减少移动过程的盲目性。 将贪心策略加入到coot 的移动中表现为：先通过比较上次迭代移动后的位置是否有进步，再决定本次迭代过程中移动方式的选取［14］。 当上次移动后的位置有进步时，本次移动过程选取与上次相同的移动方式；当上次移动后的位置表现更差时，本次移动过程选择与上次不同的移动方式，以求更好的移动表现。其基本规则如公式（11）所示：

其中，Move（i）l为cooti在第l次移动时所选择的移动方式；～表示非运算；random表示随机选取；f（i）l为cooti的第l次移动的适应度值。

2.3 带扰动因子的领导者

在整个寻优过程中，领导者的位置关乎整个种群的动向［15］。 在leader 的移动过程中添加扰动因子，能够改变leader 的探索范围，协调局部搜索和全局优化能力，从而得到更优的搜索结果［13］。 当leader 朝着接近最优点移动时，勘探范围由大到小过渡，增强局部搜索能力［16－17］；而leader 朝着远离最优点移动时，搜索范围由小到大变化，增强了全局探索能力，能有效的避免陷入局部最优的问题。 扰动因子q定义如公式（12）所示［11，14－15］：

其中，L是当前迭代；Iter是最大迭代；π 为圆周率。

通过对α和β在［0，20］区间内依次取值进行组合实验，实验结果表明，当α＝4、β＝5 时，全局勘探能力与局部探索能力能够得到较好的平衡，此时寻优效果最好。 改进后的领导者移动公式如公式（13）所示：

2.4 PGCOOT 算法描述

综上所述，本文将精英反向学习、贪心策略和扰动因子与COOT 算法融合得到PGCOOT 算法。 该算法能更好的协调局部搜索和全局优化，具有更优的搜索性能，从而提升算法的收敛效果。 PGCOOT算法实现流程如图1 所示。 算法步骤如下：

图1 PGCOOT 算法流程图Fig. 1 PGCOOT algorithm flow diagram

Step 1确定白骨顶种群个数N，最大迭代次数Iter，空间维度d，搜索空间上下限等参数；

Step 2随机产生种群个体，初始化种群，随机选取NL个leader，并计算种群适应度值；

Step 3采用精英反向学习产生反向种群，再选取每个序号下最好的个体作为种群个体；

Step 4进入主循环，While 当前迭代次数l＜Iter；

Step 5coot 选取移动方式。 当l＝1 时，coot随机选取移动方式；当l ＞1 时，coot 根据贪婪策略改进的机制（式（11））选取移动方式；

Step 6coot 根据已选取移动方式，依据式（2）～式（6）实现位置信息更新；

Step 7leader 根据加入扰动因子的领导者运动式（13）进行位置信息更新；

Step 8计算种群适应度，获取当前适应度最好的值，并更新leader；

Step 9判断是否达到停止条件，满足则迭代过程结束；否则返回Step 4 继续迭代；

Step 10输出最优适应度值和最佳位置。

2.5 PGCOOT 算法复杂度分析

在标准COOT 算法中，假设种群规模为N，求解空间维数为d， 标准COOT 进行参数初始化的复杂度为O（1），则个体适应度为O（N），种群复杂度为O（N×d），此时标准COOT 算法的整体复杂度如公式（14）所示：

PGCOOT 算法在初始化阶段使用精英反向学习策略，替换随机初始化后复杂度为O（N×d）；在个体适应度计算阶段使用贪心策略后，复杂度为O（N×d），干扰因子复杂度为O（N×d）；算法整体复杂度如公式（15） 所示：

显然O（COOT）＝O（PGCOOT）。 可见，相比于标准COOT 算法，本文所提算法与标准COOT 算法时间复杂度一致。

3 仿真实验结果与分析

为证明PGCOOT 算法加入不同改进策略的有效性，并且具有更好的性能，将其算法与其他算法进行仿真实验对比分析。 实验从以下3 方面进行：

（1）将PGCOOT 算法与贪心策略下的改进算法COOT1、精英反向学习初始化与加入扰动因子的领导者运动改进后的算法COOT2、标准COOT 算法进行实验对比，验证不同策略的有效性。 同时，为了验证PGCOOT 的时间复杂度，与COOT 进行了比较分析。

（2）将PGCOOT 算法与蚁狮算法（ALO）、 灰狼优化算法（GWO）、蝗虫优化算法（GOA）、正余弦算法（SCA）、多元宇宙优化算法（MVO） 和原始的COOT算法在d＝ 30 条件下做实验比较，通过实验数据论证PGCOOT 算法的可行性、有效性和优越性。 再根据寻优能力的表现，选取前三名算法在d＝ 100 时进行对比实验。

（3）将PGCOOT 算法与蚁狮算法（ALO）、 灰狼优化算法（GWO）、蝗虫优化算法（GOA）、正余弦算法（SCA）、多元宇宙优化算法（MVO） 和原始的COOT算法进行Wilcoxon 秩和检验，以此验证PGCOOT 算法相较于其他算法具有显著性差异。

为了检验本文所提PGCOOT 算法的寻优能力，实验使用8 种标准测试函数来对算法进行不同寻优特征上的测试。 标准测试函数见表1。 其中F1、F2、F3、F4为单峰函数，F5、F6、F7、F8是多峰函数，存在多个局部极值，求解难度较高。

表1 标准测试函数Tab. 1 Standard test function

实验环境：本文所有实验均在Intel® CoreTMi5－7500 CPU＠3.40 GHz，RAM 8.0 GB，运行环境为64位Window10 操作系统，MATLAB 2018b 软件上进行。 为了与其它算法进行公平比较，将种群规模都设为N＝30，设置领导者数量占比为0.1，最大迭代次数Iter为500、α为4，β为5。 每个测试函数都进行了30 次独立实验，以排除随机性对实验结果的影响，并记录最优值（Best）、平均值（Mean）与标准差（Std），来整体评价各算法的性能。 其中，平均值用于表示算法的平均寻优能力，最优值用于表示算法的寻优极限，标准差表示算法的鲁棒性。

3.1 不同策略比较

为验证PGCOOT 算法中各策略的有效性，将原始算法COOT 与COOT1、COOT2、PGCOOT 在d＝30时，进行实验比较，从而验证各策略的有效性。 各策略算法独立运行30 次后的实验结果见表2，可视化结果如图2 所示。 从对表2 和图2 的分析可知：

表2 PGCOOT 与COOT、COOT1、COOT2 结果Tab. 2 Results of PGCOOT and COOT， COOT1 and COOT2

图2 各策略算法的平均收敛曲线Fig. 2 Average convergence curves of several strategy algorithms

（1）对于F1和F3，COOT、COOT2 和COOT1 并未收敛至最优值。 COOT1 与原始算法相比，收敛精度略有提升；COOT2 的精度则比原始算法提升了至少200 个数量级。 而融合了COOT1 和COOT2 策略的PGCOOT 算法则在迭代接近450 次时就收敛至理论最优值，并且PGCOOT 的收敛平均值（Mean）和标准差（Std）均为0。 这表明在30 次实验中，PGCOOT 能100%取得理论最优解。

（2）对于F2和F4，各策略算法均未收敛至理论最优值，但PGCOOT 最接近理论最优值，与原始算法相比提升了170 个数量级左右，并且COOT1 和COOT2 的改进策略结果也优于原始的COOT。

在相同条件下，对于单峰函数F1～F4的对比分析结果，展现了改进策略COOT1 和COOT2 在收敛速度与收敛精度的有效性，而PGCOOT 算法融合了COOT1 和COOT2 的优点，在各函数上都获得了更高的准确性和更快的收敛速度，表明了所提算法的优越性。

在多峰函数时，对于F5来看，各策略算法均未收敛至最优值。 收敛平均值（Mean）表明，与COOT相比，COOT1 收敛精度相对更高，COOT2 的收敛精度则大幅提升，而融合了COOT1 和COOT2 策略的PGCOOT 收敛精度最高，最接近理论值。 通过最优值（Best）和标准差（Std）的比较，表明了PGCOOT 的寻优极限更高、收敛效果更加稳定。 分析F6与F8时的结果，各策略算法均实现最优值（Best）与理论值相等；但收敛平均值（Mean）和标准差（Std）结果则表明了COOT 和COOT1 并不能保证100%取得理论最优解，而PGCOOT、COOT2 的30 次运行均能够100%取得理论最优解。 从收敛速度来看，PGCOOT的收敛速度比COOT2 更快。

综上，在多峰函数F5～F8时，融合了COOT1 和COOT2 策略的PGCOOT 在寻优精度、稳定性和收敛速度上都表现出了远优于其他算法的性能。

为了验证PGCOOT 的时间复杂度，在上述条件下，将PGCOOT 与COOT 在相同函数下独立运行30次的总时间进行记录，结果见表3。 从表3 可以看出，PGCOOT 与COOT 运行30 次所用时间均在3 s左右，不存在较大的差异。 说明本文算法在标准COOT 算法中使用多种策略后，时间复杂度并没有上升，运行效率也未受到影响。

表3 PGCOOT 与COOT 独立运行30 次时间（s）比较Tab. 3 Comparison between PGCOOT and COOT when running independently for 30 times

3.2 不同算法比较

本次实验运用8 个测试函数，在参数设置统一的条件下，测试PGCOOT 算法的寻优速度与寻优精度。 通过最优值（Best） 、平均值（Mean） 与标准差（Std） 3 个指标，评价PGCOOT 的寻优能力。

本文选取蚁狮算法（ALO）、 灰狼优化算法（GWO）、蝗虫优化算法（GOA）、正余弦算法（SCA）、多元宇宙优化算法（MVO） 和原始的COOT 算法等，与改进算法PGCOOT 在d＝30 时进行对比实验。实验结果见表4，收敛曲线如图3 所示。

表4 PGCOOT 及其他算法结果Tab. 4 Results of PGCOOT and other algorithms

图3 PGCOOT 及其他算法收敛曲线Fig. 3 Convergence curves of PGCOOT and other algorithms

由对表4 和图3 的分析可知：

（1）对于单峰函数F1～F4，PGCOOT 能迅速收敛至最优值或最优值附近，而其余算法收敛精度较低，收敛速度较慢。 其中，在F1、F3上只有本文所提出的PGCOOT 获得了理论最优值，其余算法均未寻到理论最优值。 从平均值与标准差来看，PGCOOT寻优成功率高达100%，具有比其他算法更好的稳定性。 从对应的收敛曲线中可以看到，虽然GWO与COOT 有着不错的效果，但是PGCOOT 在收敛速度上占有明显优势。 对于F2、F4而言，虽然所有算法均未寻到理论最优值，但PGCOOT 的结果最接近理论值；从平均值与标准差来看，PGCOOT 也具有更好的鲁棒性和平均寻优能力。

（2）从多峰函数F5～F8的结果可见，在F5函数上，虽然所有算法均未寻到理论最优值，但从接近理论最小值的程度来看，PGCOOT 的结果最接近于理论最优值。 在F6和F8函数上，PGCOOT、GWO 与COOT 均跳出局部最优，寻到理论最优值，但是从平均值与标准差来看，PGCOOT 具有更好的稳定性，能够100%寻得理论最优值。 对于F7， 虽然PGCOOT与其他算法均未寻到理论最优值，但PGCOOT 获得的最优值8.881 8E－16 是所有算法中最接近理论值的结果之一。 并且从平均值与标准差的结果可以看到，PGCOOT 的稳定性最好。 这表明了在F7函数下，PGCOOT 相对于其它算法仍然最具竞争力。

为了进一步验证本文所提PGCOOT 算法，将与上述结果中表现最好的GWO 和COOT 在d＝ 100 时再次进行实验。 所得实验数据见表5，收敛曲线见图4。

表5 PGCOOT、GWO、COOT 结果Tab. 5 Results of PGCOOT、GWO、COOT

图4 PGCOOT、GWO、COOT 收敛曲线Fig. 4 Convergence curves of PGCOOT， GWO and COOT

从图4 可见，对于F1～F4来看，PGCOOT、GWO、COOT 的寻优表现结果相似。 PGCOOT 的收敛曲线下降迅速，而GWO、COOT 的收敛曲线则较为缓和。从表5 和图4 来看，PGCOOT 在F1能够100%寻得理论最优值，其余算法均未寻到理论最优值。 在F2、F4函数下，PGCOOT 虽未取得理论最优值，但与GWO 和COOT 相比，接近程度更胜一筹。 并且PGCOOT 在平均值与标准差上具有更好的稳定性。 在F3函数下，PGCOOT 虽不能够保证100%寻得理论最优值，但仍保持收敛精度和收敛速度第一。 由此可见，在高维单峰函数的实验中，GWO 和COOT 在寻优能力和收敛速度上都会产生波动，甚至是下降的情况，与之相比PGCOOT 仍能保持良好的寻优能力，进一步表明了PGCOOT 整体性能的优越性。

在多峰函数F5～F8中，PGCOOT 在F5函数上表现了更好的寻优能力，从表5 和图4 的结果可以看到，与GWO 和COOT 相比PGCOOT 更接近于理论最优值。 在F6～F8函数上，PGCOOT 的收敛速度比GWO 与COOT 快，能够迅速收敛至最优值附近。 与d＝ 30 时相比，PGCOOT 的收敛精度、速度和稳定性均保持一致，这表明PGCOOT 具有保持较强的鲁棒性和稳定性。 综合F5～F8函数的结果来看，在高维多峰函数的情况下，PGCOOT 仍保持良好的寻优能力和收敛速度，而GWO、COOT 在高维度求解复杂函数时会出现稳定性不强，寻优能力骤降的情况。

因此，不管在低维还是高维条件下，PGCOOT 都具有更好的寻优精度和稳定性、更快的寻优速度，这也表明了PGCOOT 能够有效解决低维和高维的函数优化问题。

3.3 Wilcoxon 秩和检验

为验证PGCOOT 算法与蚁狮算法（ALO）、 灰狼优化算法（GWO）、蝗虫优化算法（GOA）、正余弦算法（SCA）、多元宇宙优化算法（MVO） 和原始的COOT 算法在全局寻优上是否存在显著性区别，对各算法进行了性能测试比较。 考虑到数据为非正态分布，因此使用均值的非参数检验方法，本文采取Wilcoxon 秩和检验。

Wilcoxon 秩和检验的步骤为：首先，提出原假设H0：PGCOOT 算法与其他算法之间性能不存在明显差异。 备择假设H1：PGCOOT 算法与其他算法之间性能有着明显差异。 然后，根据Wilcoxon 秩和检验原理计算出P值。 最后，利用检验结果的P值来比较两种算法是否存在差异。 当P值小于0.05 时，拒绝H0，即认为两种算法在性能上存在明显区别；当P值大于0.05，不拒绝H0， 即不认为两种算法之间存在明显差异，两种算法在全局寻优上性能相当。Wilcoxon 秩和检验结果见表6。

从表6 Wilcoxon 秩和检验可以看出，PGCOOT算法与其他算法之间由Wilcoxon 秩和检验所得的P值最大值为2.495 5E－95，最小值为3.015 3E－183，大部分值处于9.35E－162 附近，远远小于0.05。 因此拒绝H0， 认为PGCOOT 算法与其他算法之间存在明显差异。 结合PGCOOT 算法的优异表现，即认为本文所提改进算法PGCOOT 比其他算法具有更好的搜索能力。

4 结束语

本文针对COOT 优化算法易陷入局部最优、收敛精度低等问题，提出了融合扰动因子和贪心策略的PGCOOT 算法。 将PGCOOT 与其他多个算法在8 个经典测试函数上对收敛速度、精度进行比较。仿真实验结果验证了所提出的精英反向学习初始化和贪心策略以及扰动因子相结合的PGCOOT 算法的有效性，表明了PGCOOT 算法在全局寻优以及局部搜索具有更优秀的寻优精度与速度。 今后的研究将继续改进算法，进一步提高算法的寻优性能，同时将PGCOOT 算法应用于实际问题。