非均匀变异的互利自适应缎蓝园丁鸟优化算法*

王依柔，张达敏，樊 英

(贵州大学大数据与信息工程学院，贵州 贵阳 550025)

1 引言

近年来，在工程、经济学等多个领域出现许多复杂优化问题，这些问题通过传统方法在一定的时间或精度内得到最优解较为困难。运用群智能算法可以处理这类优化问题。近几年比较新颖的群智能算法包括樽海鞘群算法SSA(Salp Swarm Algorithm)、蝴蝶优化算法BOA(Butterfly Optimization Algorithm)、常用的粒子群优化PSO(Particle Swarm Optimization)算法等都具有简单易行、参数少、运行时间短等特点，因此在解决众多非线性和多模态的现实寻优问题中，群智能算法呈现出了优良的可操作性和寻优能力[1-5]。

缎蓝园丁鸟优化算法SBO(Satin Bowerbird Optimizer)是由Moosavi等人[6]提出的一种新的全局优化群智能算法，是受缎蓝园丁鸟求偶行为的启发而提出的。虽然这种算法在经典工程设计问题上具有优越性，但与其它群智能算法一样，其仍然存在求解精度低和收敛速度慢等缺陷。文献[7]利用SBO算法来实现固体氧化物燃料电池的精确参数测量，SBO能够为固体氧化物燃料电池的稳态和动态模型生成有竞争力的参数，这表明了SBO算法的有效性。文献[8] 针对无管制电力系统中的拥塞管理问题，提出使用SBO算法，该方法在拥塞代价和损失方面具有更好的效果。文献[9]采用复数编码增加了园丁鸟种群的多样性，增强了标准SBO算法的全局搜索能力，但是收敛速度不太理想。文献[10]为避免算法陷入局部最优，在SBO算法中引入自适应t分布变异算子，使用算法的迭代次数作为t分布的自由度参数来增强种群的多样性，但是搜索精度依然不算高。文献[11]提出了一种用非均匀变异算子代替高斯或柯西变异算子的进化规划算法，提高了算法跳出局部陷阱的概率。文献[12]为了提高路径规划的精度，在传统的粒子群优化算法中对惯性权重因子采用三角函数的变化方式进行自适应调整，以有效平衡算法的全局探索能力和局部开发能力。

为了解决标准缎蓝园丁鸟优化算法存在的求解精度不高和收敛速度慢等问题，本文提出一种非均匀变异的互利自适应SBO算法。改进的SBO算法引入非均匀变异算子，避免算法陷入局部最优；采用互利因子以增加种群多样性，获取更好的最优解；引入自适应惯性权重，平衡算法的局部与全局搜索能力。通过求解8个典型复杂函数的最优解、Wilcoxon检验统计和平均绝对误差来验证改进的缎蓝园丁鸟优化ISBO(Improve Satin Bowerbird Optimizer)算法的有效性和鲁棒性。

2 缎蓝园丁鸟优化算法

在缎蓝园丁鸟优化(SBO)[6]算法中，成年雄性园丁鸟在交配季节开始在自己的区域上用不同的材料建造凉亭。他们利用的各种各样的材料(如鲜花、水果)以及戏剧性的姿态，都是吸引雌性园丁鸟的变量。成年雌性园丁鸟由于凉亭的美丽和戏剧性的姿态，被吸引到凉亭。值得注意的是，雄鸟利用它们的自然本能和对其他雄鸟的模仿来筑窝。根据园丁鸟生活的着色原则，将SBO算法分为以下5个阶段：

(1)随机生成初始种群。在可行域内随机生成一个包含N个求偶亭的初始种群，每个求偶亭的位置定义为D维，当前进化代数为q。

(2)计算每个个体的适应度值，然后计算出此适应度值在群体适应度值总和中所占的比例，表示该个体在选择过程中被选中的概率。求偶亭被选中的概率通过式(1)和式(2)计算：

(1)

(2)

其中，fiti代表第i个求偶亭的适应度值，通过式(2)计算，f(xi)是第i个求偶亭的目标函数，每次迭代保证目标函数的函数值不断减小。

(3)种群位置更新。雄性园丁鸟根据历史经验并利用信息共享机制，不断调整求偶亭的位置，其位置更新公式如式(3)所示：

(3)

(4)

其中，α为步长的最大阈值；Pj是目标求偶亭的被选中概率，取值为0～1。当目标位置被选中概率越大时，步长越小；当目标位置被选中概率为0时，步长最大为α；当目标位置的被选中概率为1时，步长最小，为α/2。

(4)个体变异。在大多数情况下，强壮的雄鸟会从其它雄鸟那里偷材料，甚至破坏它们的求偶亭，因此在算法循环的最后，以一定的概率随机变异，在变异过程中，xik服从正态分布，如式(5)所示：

(5)

(6)

在式(6)中，标准差σ的计算公式如式(7)所示：

σ=z×(varmax-varmin)

(7)

其中，z是缩放比例因子，varmax和varmin分别是变量xik的上限和下限。

(5)组合旧种群和从变异中获得的种群。在每次循环的最后，对旧种群和从变异获得的群体进行组合，形成组合种群，并对组合种群中的所有个体的目标函数值从小到大进行排序，保留函数值最小的个体，其余个体被淘汰掉。此时若满足终止条件，则输出最佳位置及其对应的最优值；反之，则继续进行迭代.

3 改进缎蓝园丁鸟优化算法

3.1 非均匀变异

在SBO算法早期的迭代中，园丁鸟个体的求偶亭位置通常是远离最优解的，搜索半径太小会造成群体陷入局部最优。在算法后期，园丁鸟个体的求偶亭位置接近最优解，只需要一个非常小的范围进行解向量的微调。标准算法的个体变异寻优方式不利于快速高效地寻求全局最优值。本文引入非均匀变异[11]算子，在前期寻优时，整个种群大范围地搜索，伴随着迭代次数的增加，逐步地缩小搜索范围，动态地调整每次迭代每个园丁鸟个体的求偶亭的搜索步长。

假设对求偶亭位置xi={xi1,xi2,…,xid,…xiD}T的第k个分量执行变异运算，xik的下限和上限分别记为varmin和varmax，则变异后的分量由式(8)计算：

(8)

其中，q是当前迭代次数；r是均匀产生的[0,1]随机数；Δ(q,y)由式(9)给出，它是一种自适应调节步长的变异算子，在迭代前期它能在定义域内搜索较大范围，以期发现可能的潜在区域，随着算法的进行，搜索半径依概率减小，算法临近结束时仅在当前解的狭小邻域内搜索，这样就能避免位置矢量陷入局部最优。

Δ(q,y)=y·(1-r(1-q/Q)b)

(9)

其中，q是当前迭代次数；Q是最大迭代次数；b是决定变异运算非均匀度的系统参数，本文参照文献[11]取值为5。

3.2 互利因子

标准SBO算法的求偶亭位置更新公式产生的新求偶亭位置会直接替换原求偶亭位置，存在以下缺点：第i个求偶亭位置会根据由轮盘赌方式选择的第j个求偶亭位置和当前种群最优求偶亭位置进行更新，对随机选择的第j个求偶亭个体依懒性较强，缺乏与其它个体学习的部分。为增加SBO算法的种群多样性，本文引入互利因子[13]对园丁鸟的求偶亭位置进行更新，如式(10)所示：

(10)

其中，φ是(0,1)的随机数；C为互利因子，代表园丁鸟种群中2个求偶亭的关系特征;R为受益参数，随机选取1或2。由式(10)产生的新位置需判断其适应度值优劣后才能替换原有位置。

在式(10)所示的园丁鸟求偶亭位置更新策略中，增加了社会部分φ×(xbest,k-C×R)，使种群中的随机2个求偶亭参与进化，实现较优位置的共享。与原来的位置更新公式(3)只使用由轮盘赌方式选择的第j个求偶亭位置和当前种群最优求偶亭位置进行信息交流的方式相比，社会部分引入更多组合模式，使其不再单一围绕前一个园丁鸟附近搜索，即增加了园丁鸟的种群多样性，以获得更好的全局最优解。

3.3 自适应惯性权重

(11)

ω(q)=(ωmin+ωmax)/2+(ωmax-ωmin)cos(qπ/T)

(12)

其中，ωmax为初始惯性权重。ωmin为迭代结束时的惯性权重。惯性权重ωmax=0.95，ωmin=0.4时算法具有最佳性能。因此，随着迭代的进行，惯性权重从0.95非线性递减至0.4，迭代初始阶段较大的惯性权重能使算法保持较好的搜索能力，而迭代后期较小的惯性权重则有助于提高算法的开发能力。

3.4 ISBO算法步骤

结合3.1节～3.3节对算法的改进，即引入非均匀变异算子避免算法陷入局部最优；采用互利因子以增加种群多样性，获取更好的最优解；引入自适应惯性权重，平衡算法的局部与全局搜索能力。非均匀变异的互利自适应优化SBO算法ISBO流程图如图1所示，其中rand是[0,1]的随机数。ISBO步骤如下所示：

Step1设置算法参数，初始化园丁鸟个体求偶亭的位置。根据搜索空间的上下限，随机生成一个N×D的矩阵。

Step2计算初始适应度值。根据式(2)计算N个园丁鸟求偶亭位置的适应度值。

Step3选定最优求偶亭。把Step 2中得到的适应度值进行升序排列，适应度值最好的求偶亭位置选定为最优求偶亭位置，并根据式(1)计算每个求偶亭位置被选中的概率。

Step4求偶亭位置更新。根据式(8)、式(10)和式(11)对应更新每个园丁鸟求偶亭的位置。

Step5计算适应度值。计算更新后每个求偶亭所处位置的适应度值，并更新最优位置。

Step6重复Step 4和Step 5的迭代过程，如果达到设置的精度要求或规定的最大迭代次数，则终止算法，输出全局最优解。

Figure 1 Flow chart of ISBO algorithm图1 算法流程图

4 仿真实验与结果分析

为验证ISBO算法在求解优化问题上的有效性和鲁棒性，用ISBO算法与SBO[6]、SSA[2]、BOA[3]、PSO[4]、加入非均匀变异算子的缎蓝园丁鸟优化(NSBO)算法、加入互利因子的缎蓝园丁鸟优化(MSBO)算法和加入自适应权重的缎蓝园丁鸟优化(WSBO)算法，利用8个典型的标准测试函数在不同的维度下对最优值进行求解，然后独立进行50次对比实验。本文采用如表1所示的8个复杂函数作为适应度函数，选取的测试函数中包含单峰、多峰等不同特征的测试函数。单峰函数为在定义上下限内只有一个严格上的极大值(或极小值)，通常用来检测算法收敛速度。多峰函数为含有多个局部最优解或全局最优解的函数，经常用于检测算法探索能力和开发能力。

Table 1 Benchmark functions表1 基准函数

实验环境为：Windows 10操作系统，CPU为Intel Core i5-8300H，主频2.3 GHz，内存8 GB，算法基于Matlab R2014b用M语言编写。

实验最大迭代次数为500，种群数为40，各算法其余的参数设置如表2所示。

实验1函数优化结果比较。

为了更好地研究ISBO算法的优化性能，各算法分别在不同的维度下进行50次独立寻优，并记录这50次的最佳值、平均值、最差值和标准差进行比较，结果如表3所示。

Table 2 Algorithm parameter setting表2 算法参数设置

Table 3 Analysis of experimental results表3 实验结果分析

续表

表3中的最佳值和平均值都可以反映算法的收敛精度和寻优能力。ISBO在求解单峰函数(f1～f5)时精度最高达到1e-188，随着搜索空间维度的增加，5种算法的寻优收敛精度有所下降，对于函数f4，ISBO求解的精度为1e-90，相较于函数f2降低了5个数量级。因为伴随求解维度的增加，算法求解难度也呈指数级别递增，所以算法的收敛精度有所降低属于正常现象。另外，当维度增加到120维(函数f2)和200维(函数f4)时，SSA、BOA和PSO算法的求解精度较差，并与理论最优值存在最大1e-3级的误差。而ISBO相对于其它几种算法寻优精度要高很多，且与其它算法精度最大能达到1e-182级的差距。对于f6～f8这一类复杂的多峰函数，算法求解精度相对于单峰函数要稍微低一些。在求解函数f8时，相较于SSA、BOA和PSO算法，SBO算法表现出更强的寻优能力。对于NSBO、MSBO和WSBO，加入一个改进点以后收敛精度都比原始算法、SSA、BOA和PSO的要高。这是因为SBO容易陷入局部极值，在算法中加入了非均匀变异算子、互利因子和自适应权重，一定程度上使得算法拥有跳出局部最优区域的能力，而伴随着维度的增加时，ISBO的精度是最高的，说明不同的改进策略对算法的寻优能力都有促进作用，从而达到了良好的寻优效果，进而证明了本文所提的改进思想的可行性。ISBO算法求解函数f6和f8时均达到理论最优值0。ISBO算法比其他算法的精度都要高。由此可见，ISBO算法在求解单峰、多峰和高维的基准函数时都有明显的优势。

其次，表3中的标准差和最差值也反映了算法在求解中的稳定性和跳出局部最优的能力。ISBO算法的最差值在8个函数的求解中都是最好的，说明有效改善了原始算法易陷入局部最优的缺点。ISBO算法求解的标准差相较于PSO、BOA、SSA、SBO、NSBO、MSBO和WSBO都要优秀，甚至求解函数f1和f7时均达到理论最优值，进一步说明其稳定性更好。

实验2统计检验。

基于50次独立运行的平均值和标准差的算法不会比较每次运行的结果。因此，尽管在50次运行中发生偶然优势的概率很低，但仍需用其他方法对算法有效性进行校验。Derrac等在文献[14]中提出，对于改进进化算法性能的评估，仅基于平均值和标准偏差值来比较是不够的，需要进行统计检验以证明所提出的改进算法比特定问题的其他现有算法具有显著的改进。为了判断ISBO的每次结果是否与统计上显著的其他算法的最佳结果不同，在5%的显著性水平下进行Wilcoxon统计检验[15]。表4给出了所有基准函数的ISBO和其他算法的Wilcoxon秩和检验中计算的p值。例如，如果最佳算法是ISBO，则在ISBO/BOA、ISBO/SSA等之间进行成对比较。由于最佳算法无法与自身进行比较，因此，针对每个函数中的最佳算法标记为N/A，表示“不适用”，这意味着相应的算法可以在秩和检验中没有统计数据与自身进行比较。根据Derrac等人的研究，那些p<0.05的算法(即算法进行秩和检验计算出的p值)可以被认为是拒绝零假设的有力证据。根据表4中的结果，ISBO的p值基本小于0.05，这表明该算法的优越性在统计上是显著的。

Table 4 p value of Wilcoxon rank sum test表4 Wilcoxon 秩和检验的p值

所有算法的定量分析基于8个基准函数的平均绝对误差MAE(Mean Absolute Error)。MAE[16]是一种有效的性能指标，用于对优化算法进行排序。表5给出了这些基准函数的MAE，其计算如式(13)所示：

(13)

其中，mi为算法产生的最优结果的平均值，oi为相应基准函数的理论最优值，Nf为基准函数个数。由表5可知，ISBO排名为1，因为它提供了最小的MAE。与其它优化算法相比，进一步说明了ISBO的有效性。

Table 5 MAE algorithm ranking表5 MAE算法排名

实验3收敛迭代曲线对比。

图2给出了8个基准函数的平均收敛曲线图，各函数分图图例同图2a一致。由于ISBO收敛精度较高，为了便于观察收敛情况，本文对寻优适应度值(纵坐标)取10为底的对数。由图2a～图2h可看出，SSA和BOA算法作为较新的算法，也依然存在容易陷入局部最优的缺点。原始SBO算法的收敛曲线下降缓慢，出现不同程度的停滞，基本陷入局部极值且收敛精度较低。NSBO、MSBO和WSBO算法性能都比SBO算法更好。而无论单峰、多峰，还是低维和高维，对于每个基准函数，ISBO比其他算法的收敛速度和寻优精度都要好,随着迭代次数的增加，ISBO的曲线下降非常快，并且在迭代后期具有持续寻优的能力。对于函数f1，ISBO在300代左右搜索到函数的最佳值0，所以图2a中，ISBO的曲线后面部分没有显示。图2f～图2h是多峰函数的平均收敛曲线，ISBO算法的寻优适应度值是8个算法中最好的。对于函数f7，ISBO算法在150代左右即搜索到全局最优解，表现了较强的鲁棒性。由此说明对于这一类的多峰函数，ISBO具有很强的搜索能力，可以快速跳出局部最优值束缚向全局最优点靠近。

Figure 2 Average convergence curves of benchmark functions图2 基准函数平均收敛曲线

综上可知，ISBO算法对于所有基准函数都有很好的寻优结果。特别是对于高维、多峰的函数，具有较好的稳定性和寻优能力，有效地解决了原始缎蓝园丁鸟优化算法收敛速度缓慢、求解精度不高的问题。

实验4在认知无线电中的应用。

随着无线电通信技术的飞速发展和人们对高传输速率的需求，频谱资源匮乏的问题越显突出，而导致频谱资源缺乏的原因之一是无线接入技术的不合理。近年来，认知无线电CR(Cognitive Radio)[17]技术是解决当前频谱供需矛盾的有效方法。针对传统算法容易早熟、收敛速度慢等缺陷，本文采用改进缎蓝园丁鸟优化算法优化频谱分配效率，以最大化系统效益为评价指标，进而验证算法的性能。其中最大化系统效益表示为：

(14)

其中，al,m∈{0，1}表示认知用户l是否分配到信道，bl,m表示认知用户l在使用信道m能获得的最大收益,L表示认知用户数，M表示可用信道数。值得注意的是，本文算法为十进制，而认知无线电频谱分配系统中al,m∈{0，1}，所以本文使用常用的Sigmoid函数[18]来实现十进制到二进制的转换。

(15)

(16)

在实验中，将认知无线电系统分别与改进缎蓝园丁鸟优化算法(ISBO)、原始缎蓝园丁鸟优化算法(SBO)、粒子群优化算法(PSO)和遗传算法(GA)结合，以验证本文改进算法是否在通信系统中同样有良好的性能。30次系统效益比较结果如表6所示。

Table 6 30 times system benefit comparison表6 30次系统效益比较

如图3所示是ISBO与SBO、PSO和GA算法的一次迭代速度对比图。系统总效益随着迭代次数的增加而增大，ISBO算法在53代时，系统总效益达到最大，即此刻为认知智能电网的邻域网中频谱分配问题的最优解，在此以后系统总效益不再改变；ISBO算法的最优解明显大于SBO算法的，说明了改进算法的有效性；PSO算法和GA算法分别在第178代和第211代时系统总效益才达到最大值，而且它们的效益值明显低于ISBO算法的。

Figure 3 Convergence rate of different algorithms图3 不同算法的收敛速度

为了说明ISBO算法在不同频谱环境下均具有更好的优化性能，将4种算法在30种不同的频谱环境下进行仿真，得到不同频谱环境下的系统总效益图，如图4所示。从表6可以看出，ISBO算法最终的系统总效益比GA算法分别高出31.8%，比PSO算法高出14.6%，比未改进前的SBO算法高出8.8%。这也进一步说明了本文所提算法在频谱分配当中的有效性。

Figure 4 Total systematic benefit of different spectrum environments图4 不同频谱环境的系统总效益

5 结束语

本文在标准缎蓝园丁鸟优化算法的基础上，引入非均匀变异算子、互利因子和自适应惯性权重，提出一种非均匀变异的互利自适应SBO算法ISBO。并将ISBO算法应用于复杂函数的寻优问题中，使用最优值、标准差等指标对算法进行检验，使用Wilcoxon秩和检验以及MAE对算法显著性水平进行验证，而且将ISBO算法应用于认知无线电频谱分配问题中。研究表明，ISBO算法可以获得更好的全局搜索和局部搜索能力，且能收敛到质量更好的最优解，算法的有效性和鲁棒性也得到了验证。ISBO算法在频谱分配当中也表现出了较好的性能。