基于拉丁超立方体的改进白骨顶鸡算法

何星月，张 靖，覃 涛，何必涛，杨 靖+

(1.贵州大学 电气工程学院，贵州 贵阳 550025；2.中国电建集团 贵州工程有限公司，贵州 贵阳 550025)

0 引 言

元启发式算法是对自然界的生物现象或物理现象进行模拟，可以在高维且复杂的约束条件下快速地找到问题的全局最优解。近年来一系列的元启发式算法被提出[1-4]，这些算法被广泛的应用于图像分割、参数估计、特征选择等领域[5-9]。

白骨顶鸡算法由Iraj Naruei等[10]提出。通过对白骨顶鸡的随机运动、链式运动和领导运动等行为的模拟，构建出一种有效的寻优机制。相较于传统算法，白骨顶鸡算法具有结构简单、性能稳定等优点，但仍存在收敛速度慢、易陷入局部最优等不足。

为改善上述缺陷，国内外学者们提出了不同的改进策略。文献[11]提出了一种刺激-响应机制，根据响应阈值，使蜜蜂在跟随蜂和雇佣蜂之间转换，以平衡算法的搜索与开发能力。文献[12]根据三角形相似性原理提出了动态演化理论，以增强麻雀算法后期的开发能力。文献[13]利用差分进化思想，在樽海鞘领导者位置更新中引入变异算子，帮助算法在后期跳出局部最优。文献[14]通过对正余弦算法搜索方程中引入社交和认知成分，结合灰狼算法良好勘探和开发平衡能力优化了算法的寻优性能。

为进一步提高算法寻优精度及工程应用价值，本文提出了基于拉丁超立方体的改进白骨顶鸡算法(improved COOT algorithm based on Latin Hypercube，LHCOOT)。首先利用拉丁超立方体抽样使种群分布更加均匀；引入非线性决策因子以权衡算法全局搜索和局部开发过程；采取动态边界机制，加速算法收敛；对最优个体进行柯西扰动并引入贪婪策略，避免算法陷入局部最优。通过对16个基准函数、高维函数和实际工程问题进行仿真实验，验证了LHCOOT算法的有效性。

1 白骨顶鸡算法COOT

白骨顶鸡是一种小型水鸟，在水面上有许多不同的群体行为，包括普通个体的随机运动、链式运动、引导运动以及领导者运动。该算法的具体步骤如下：

普通个体运动：该过程主要由3种运动状态构成，执行机制如式(1)所示

(1)

式中：Rb、Rc为常量0.5。lead、chain、random表示引导运动、链式运动和随机运动，分别如式(2)～式(4)所示

CootPos(i)=Lead(K)+2×R1×cos(2R)×
(Lead(K)-CootPos(i))

(2)

(3)

CootPos(i)=CootPos(i)+A×R2×(Q-CootPos(i))

(4)

式中：R是[-1，1]中的随机数，R1、R2是[0，1]中的随机数，K为领导者的索引，为普通个体分配领导者，如式(5)所示

K=1+(iMODNL)

(5)

式中：i是普通个体索引，NL为领导者的数量。

领导者运动：该运动根据式(6)，利用最优个体牵引领导者，帮助种群向最优区域收敛

(6)

式中：gBest是当前最优个体位置，R3和R4是[0，1]中的随机数。

2 改进白骨顶鸡算法LHCOOT

2.1 基于拉丁超立方体的初始化种群

元启发式算法的收敛速度和收敛精度通常与初始种群的分布结构息息相关。COOT算法以随机方式生成的初始种群会导致个体在求解空间分布不均，影响初始种群的多样性。相较于传统的混沌映射[15]、佳点集[16]等初始化策略，拉丁超立方体抽样[17](Latin Hypercube sampling，LHS)基于分层抽样原理，可以实现非重叠采样和变量范围全覆盖采样，兼顾种群初始化的随机性和均匀性。

(7)

式中：vij是与hij独立的(0，1)上均匀分布的独立蒙特卡洛样本。按照上述步骤选取的m个点ci=(ci1，ci2，…，cim)，i=1，2…m为一个拉丁超立方体样本。

假设搜索空间为2维，搜索范围为(0，1)。随机种群初始化和拉丁超立方体初始化分布如图1所示。

图1 初始化种群分布

从图1可以观察到，随机种群初始化个体粘连严重，均匀性不佳。拉丁超立方体初始化分布在整个解空间，且均匀分散在每个坐标区间。因此，拉丁超立方体抽样能有效提高初始种群多样性，有助于加快算法收敛速度。

2.2 混合位置更新策略

2.2.1 非线性决策因子

是否能合理地平衡算法全局搜索和局部开发能力将直接影响算法的寻优能力。在COOT算法中，随机运动将会在解空间生成一个随机解，引导白骨顶鸡位置更新。链式运动将两个相邻索引个体的平均位置作为更新位置。因此，链式运动帮助种群向同一方向汇聚，适合在算法前期加速算法收敛。而随机运动在整个解空间生成一个随机解，牵引算法跳出局部最优。两种位置更新的执行机制如式(8)所示

(8)

因此，等于0.5的常量Rc，是控制算法全局搜索能力和局部开发能力的决策因子。常量型决策因子并不能适用于解决复杂高维的实际工程问题。因此，本文采用一种非线性决策因子，令算法在前期缓慢衰减，增大执行链式运动的概率，帮助算法快速收敛。在算法后期迅速衰减，增大执行随机运动的概率，从而帮助算法跳出局部最优。非线性决策因子的数学模型如式(9)所示

(9)

式中：Rv0为决策因子初值，本文取为1，t是模型控制因子，t的取值控制模型的衰减速度，t值越大，模型的衰减速度越慢。不同t值下非线性决策因子模型及常量0.5对比如图2所示。

图2 决策因子曲线

当决策因子曲线在常量0.5上方时，算法会以大概率执行链式运动。反之，会以大概率执行随机运动。经多次实验验证，当t取10时，算法效果最佳。

2.2.2 自适应动态边界

COOT算法在执行随机运动时，会在整个搜索空间中生成随机解。如果该搜索空间不随着迭代过程而相应收敛，将会增大寻优过程的盲目性和复杂度，造成算法收敛迟滞，迭代时间增加。因此，本文引入了自适应动态边界机制，加快算法收敛速度。动态边界的上下界如式(10)所示

UB=α×max(X)
LB=α×min(X)

(10)

式中：X为整个种群的位置矩阵，α为自适应映射系数，如式(11)所示

α=1+0.2×(eL/Iter-1)

(11)

式中：L是当前迭代次数，Iter是最大迭代次数。随机位置Q的生成如式(12)所示

Q=rand(1，d)×(UB-LB)+LB

(12)

从式(12)可以看出，边界将随着种群的移动而动态跟随，随着种群的收敛而相应缩小。同时，为了避免迭代后期，种群收敛陷入局部最优，将动态边界通过随着迭代次数增大的映射系数放大，增加动态牵引力度，从而增大跳出局部最优的概率。相较于逐维更新的动态边界，利用种群确定边界，可以避免不同维度间的相互干扰，提供一定裕量，提高寻优能力。

2.3 柯西变异

领导者的迭代更新由最优个体引导，向着最优位置靠近，导致算法后期种群多样性降低，算法易陷入局部最优。本文在原有算法中加入柯西变异算子，对最优个体进行柯西扰动，扩大算法的局部搜索能力，增强种群的多样性。

正态分布和柯西分布是两种经典的连续型概率分布，两者的概率密度函数曲线如图3所示，相较于正态分布，柯西分布原点处的峰值较小，从原点处的峰值到两端的下降趋势会更加平缓。因此，柯西变异扰动能力更强。通过融入柯西变异对最优个体产生扰动，能够帮助算法跳出局部极值。

图3 概率密度函数曲线

对最优个体添加柯西变异的模型为

Xnbest=Xbest×(1+cauchy(0，1))

(13)

式中：Xbest为最优个体，Xnbest为变异后的个体，cauchy(0，1) 是服从中心为0，尺度参数为1的柯西分布随机数。为保证变异之后的解优于原始解，算法引入贪婪策略，对比扰动前后解的适应度值，择优保留。贪婪策略的数学模型如式(14)所示

(14)

式中：f为适应度函数。

2.4 改进算法流程图

综合上述改进策略，LHCOOT的算法流程如图4所示。

图4 算法流程

2.5 时间复杂度分析

时间复杂度作为评价算法性能的指标之一，可以间接反映算法的寻优效率。设标准白骨顶鸡算法种群数量为N，搜索空间维度为n，最大迭代次数为M，领导鸡群比例为NL，求解目标函数适应度时间为f(n)。 假设初始化参数时间为λ1，每一维产生服从均匀分布随机数的时间为λ2，找到并保存适应度最佳个体位置的时间为λ3，则算法总体初始化阶段的时间复杂度为

T1(n)=O(λ1+N(nλ2+f(n))+λ3)=O(n+f(n))

在迭代过程中，普通个体更新阶段，普通个体个数为N(1-NL)， 设随机运动、链式运动、领导运动每一维更新位置时间都近似为λ4，式(7)的决策机制时间为λ5，计算位置更新后的适应度并与最优位置比较的时间为λ6，根据式(3)更新参数A的时间为λ7，则此阶段时间复杂度为

T2(n)=O(N(1-NL)(nλ4+f(n)+λ5+λ6)+λ7)=
O(n+f(n))

在领导者更新阶段，领导者个数为N×NL，设白骨顶鸡领导者每一维位置更新所需的时间为λ8，计算位置更新后的适应度并与最优位置比较的时间也为λ6，根据式(9)更新参数B的时间为λ9，则这一阶段的时间复杂度为

T3(n)=O((N×NL)(nλ8+f(n)+λ6)+λ9)=
O(n+f(n))

由此，COOT算法总时间复杂度为

T(n)=T1(n)+M(T2(n)+T3(n))=O(n+f(n))

在LHCOOT中，在初始化阶段，引入了拉丁超立方体抽样初始化种群，相较于均匀分布初始化种群，算法时间复杂度保持不变，即T′1=T1； 在普通个体更新阶段，设引入非线性决策因子时间为t1，贪婪策略的时间为t2，自适应动态边界包含在随机运动更新位置时间仍然为λ4，因此LHCOOT算法这一阶段的复杂度为

T′2(n)=O(N(1-NL)(n(λ4+t1)+f(n)+
λ5+λ6+t2)+λ7)=O(n+f(n))

在领导者更新阶段，设柯西扰动的时间为t3，贪婪策略的时间仍为t2，则该阶段时间复杂度为

T′3(n)=O((N×NL)(nλ8+f(n)+λ6)+λ9+
t2+t3)=O(n+f(n))

因此，LHCOOT算法总时间复杂度为

T′(n)=T′1(n)+M(T′2(n)+T′3(n))=O(n+f(n))

综上所述，与COOT算法相比，LHCOOT算法所引入的改进策略并不会增加算法时间复杂度。

3 实验结果及分析

3.1 对比算法及参数设置

本文采用的仿真软件为MATLAB 2015b，实验环境为i7-10750H CPU，2.69 GHz主频，16 GB运行内存，操作系统为Windows 10(64位)。

选取粒子群算法(particle swarm optimization，PSO)、金豺优化算法(golden jackal optimization，GJO)、樽海鞘群算法(salp swarm slgorithm，SSA)、白骨顶鸡算法(COOT)、添加非线性决策因子的白骨顶鸡算法(NDFCOOT)、融合Tent映射和莱维飞行的改进白骨顶鸡算法[18](COOTTLCR)与本文LHCOOT算法进行对比实验，上述算法统一最大迭代次数为500，种群规模为30，为降低算法结果偶然性，皆独立运行30次。各算法参数设置见表1。

表1 对比算法参数设置

3.2 测试函数

为了检验LHCOOT算法的寻优能力，本文选取文献[18]中的16个基准测试函数进行仿真验证，分别是单峰测试函数中的f1～f7，多峰测试函数中的f8～f13，固定维测试函数中具有代表性的f20、f22、f23，其中单峰与多峰测试函数维度为30。

3.3 寻优精度分析

表2中的平均值和标准差分别反映出算法的寻优能力和稳定性。对于单峰测试函数，LHCOOT算法在f1～f4函数上远优于其它算法，能够100%寻到函数的理论最优值。在测试函数f6上LHCOOT算法仅仅以微弱的差距次于SSA算法。在f5与f7测试函数上，LHCOOT算法也都优于其余元启发式算法。LHCOOT算法对单峰函数良好的寻优效果体现了其有着出色的全局搜索能力。

表2 基准测试函数寻优结果对比

对于多峰测试函数，LHCOOT算法在寻优精度上均优于其它算法。其中，在函数f9、f11上，LHCOOT算法达到了100%的寻优率。在函数f12、f13上，LHCOOT算法的寻优精度远远高于其它元启发式算法，超过了2～3倍数量级的寻优精度。在函数f8上，LHCOOT算法虽然标准差稍次于COOTTLCR算法，但寻优精度仍然保持最优。对于固定维度测试函数，在函数f14上，LHCOOT算法仅次于COOTTLCR算法，且已较接近理论最优值。在函数f15、f16上，LHCOOT算法也保持着最好的寻优精度。

相较于COOT算法，NDFCOOT算法与LHCOOT算法在f1～f4以及f6函数上都取得了明显得进步，说明引入非线性决策因子，可以提高算法的全局搜索能力，加快算法收敛。而在多峰函数上NDFCOOT算法表现不佳，说明单一的非线性决策因子策略对后期跳出局部最优帮助较低。而添加了柯西变异的LHCOOT算法，可以有效解决多峰函数上陷入局部极值点的问题。

综上，LHCOOT算法在选取的测试函数上的表现优于其它6种算法，验证了算法良好的搜索能力和寻优精度。

3.4 算法收敛曲线

为了更清晰刻画算法的动态寻优性能，图5给出了PSO、SSA、GJO、NDFCOOT、COOTTLCR、COOT、LHCOOT这7种算法在上述基准测试函数(部分)的收敛曲线。从选择出的9个测试函数的收敛曲线上，可以看出LHCOOT算法比标准的COOT算法以及其余各个算法收敛速度更快，收敛精度更高。

图5 对比算法收敛曲线

其中，函数f1和f2寻优效果远远好于其它算法，分别迭代了150次和340次便成功找到理论最优值。这归功于拉丁超立方体抽样的非重叠采样和全覆盖采样，使得初始种群多样性远高于其它算法的随机初始化种群，有效加速算法收敛速度和收敛精度。在函数f7、f8、f9和f10上，虽然LHCOOT算法寻优精度优势微弱，但收敛速度均为第一，收敛曲线在迭代前期便能迅速下降。在函数f6上，虽然收敛精度略次于SSA算法，但收敛速度在前期远远超过SSA算法。这表明自适应动态边界机制，生成的边界空间可以动态跟随种群的变化，大大加快算法收敛速度。同时依赖于非线性决策因子有效平衡了算法全局搜索和局部开发过程，增强了算法的寻优能力。

在多峰测试函数f12上，LHCOOT算法在500次迭代结束时仍然保持着收敛状态，寻优精度仍会随着迭代次数增加而增加。相较于GJO算法和COOT算法等过早陷入局部最优，收敛精度提升缓慢甚至停滞，LHCOOT算法由于对最优解使用了柯西扰动策略，逃离局部最优能力显著增加。

通过综合对比分析，相较于其它6种元启发式算法，LHCOOT算法的收敛速度和收敛精度占优，且有着较好逃离局部最优能力。

3.5 不同维度下算法对比分析

为了检验算法在高维度、大规模问题下的寻优能力，选择LHCOOT算法与PSO、SSA、GJO、COOT算法对比。对表1中的单峰函数f1～f4和多峰函数f11～f13这7个基准测试函数在维度D=50/100/300时进行寻优。得出的实验结果见表3。

表3 不同维度对比结果

从实验结果可以看出，在各种高维情况下的单峰测试函数和多峰测试函数，LHCOOT算法的寻优精度均高于PSO、SSA、GJO、COOT算法。

对于单峰测试函数，LHCOOT算法在50/100/300维中，都能够收敛到理论最优值，且标准差皆为0，体现了算法良好的鲁棒性和寻优能力。而其它4种算法在一定程度上收敛精度会随着维度的增加而降低。由此可见，LHCOOT算法在求解单峰问题上未陷入“维数灾难”。

对于多峰测试函数，在函数f11上，LHCOOT算法取得了不错的收敛精度，且收敛精度与30维条件下一致，可见算法对高维度、大规模问题具有不错的鲁棒性。在函数f12、f13上，虽然LHCOOT算法的收敛精度和标准差未达到理想值，但收敛精度仍然高出其余各算法1～5个数量级不等。体现了LHCOOT算法具有良好的全局搜索和局部开发能力。

综上所述，LHCOOT算法在解决高维度、大规模问题时，对维度的变化不敏感，仍然保证了良好的寻优精度。其算法鲁棒性、寻优能力均优于其余4种算法。

3.6 Wilcoxon秩和检验

秩和检验又称为维尔克松两样本检验，是一种非参数统计检验。可以作为算法性能的评价指标之一，用于验证算法之间是否存在显著差异。本文基于上文的16个基准测试函数，采用显著水平p=5%情况下的秩和检验对LHCOOT算法与6种原启发式算法(PSO、SSA、GJO、NDFCOOT、COOTTLCR、COOT)进行差异性检验。当p<5%时，记为“+”，表示LHCOOT算法优于对比算法；当p>5%时，记为“-”，表示LHCOOT算法劣于对比算法；当p为“NaN”时，表示不适应于显著性判断，LHCOOT算法显著性与对比算法相近。对比结果见表4，在各算法对比中，大多数的秩和检验p值小于显著水平5%，表示LHCOOT算法整体上与其它算法具有显著性差异，即LHCOOT算法具有更好的寻优性能。

表4 秩和检验p值

4 工程问题应用分析

为进一步验证LHCOOT算法在处理实际工程优化问题的可行性和有效性。本节使用标准焊接梁设计问题作为参考验证。

焊接梁设计问题属于典型的非线性规划问题。在满足设计变量的边界条件和剪切应力τ、弯曲应力σ、梁条屈曲载荷Pc、末端偏差δ这4个工程约束指标下尽可能降低焊接梁设计的制造成本。本节采用死刑惩罚函数机制作为非线性约束[19]。4个设计变量分别是焊缝宽度h、横梁长度l、高度d和厚度b。

设计变量如式(15)所示

x=[x1，x2，x3，x4]=[h，l，d，b]

(15)

目标函数如式(16)所示

(16)

约束条件如式(17)所示

(17)

式中：τmax=136000 psi，σmax=3000 psi，δmax=0.25 in，P、L、E、G为焊接梁问题工程常量，P=6000 lb，L=14 in，E=3×106psi，G=1.2×107psi。psi：磅平方英寸，lb：磅，in：英尺。

表5统计了LHCOOT算法与粒子群算法(PSO)、算数优化算法(arithmetic optimization algorithm，AOA)[10]、海洋捕食者算法(marine predators algorithm，MPA)[20]、金豺优化算法(GJO)[4]、斑点鬣狗优化算法(spotted hyena optimizer，SHO)、变色龙群算法(chameleon swarm algorithm，CSA)[21]在求解焊接梁设计问题的4个设计变量和制造成本。从表中可以看出，LHCOOT算法的焊接梁制造成本最低，说明LHCOOT算法在求解此类工程问题的寻优精度较高，进一步验证了算法在实际应用中的优越性。

表5 焊接梁设计问题仿真结果

5 结束语

针对COOT算法的寻优精度低，易陷入局部最优等问题，提出了基于拉丁超立方体的改进白骨顶鸡算法。利用拉丁超立方体抽样使白骨顶鸡初始种群更加均匀化；引入非线性决策因子和自适应动态边界的混合位置更新策略以完善3种运动的执行机制，权衡算法全局搜索和局部开发过程；最后引入柯西变异和贪婪策略对最优位置进行扰动，避免算法过早收敛。通过对16个基准测试函数、部分高维函数以及算法秩和检验的实验，表明LHCOOT算法在收敛速度、收敛精度以及逃离局部最优的能力均有了不同程度的提升。通过实际工程优化问题验证算法在解决工程问题上的可行性。在下一步工作中，将考虑把算法应用到深度学习领域，结合神经网络进行风电功率的短期预测[22]，拓展算法的实用价值。