基于自适应权重的缎蓝园丁鸟优化算法

鲁晓艺， 刘 升， 韩斐斐， 于建芳

(上海工程技术大学 管理学院， 上海 201620)

引言

近年来，群智能算法作为一种新兴的演化计算技术，其良好的寻优性能已成为越来越多研究者关注的焦点。在管理科学和自然科学等领域中发挥着重要作用，广泛应用于解决工程调度[1]、组合优化[2]、风险预测[3]等复杂问题。群智能算法受自然规律的启迪，利用仿生原理进行设计，如人工蜂群(artificial bee colony，ABC)[4]算法模拟蜜蜂群体寻找优质花蜜源的过程，把蜜蜂分为引领蜂、跟随蜂和侦察蜂3种角色；萤火虫算法(firefly algorithm，FA)[5]模拟自然界萤火虫在晚上群聚活动的自然现象而提出的，在萤火虫的群聚活动中，每只萤火虫通过散发荧光素与同伴进行寻觅食物以及求偶等信息交流；人工鱼群(artificial fishswarm，AF)[6]算法通过模仿鱼群的觅食、聚群及追尾行为，从而实现寻优。

缎蓝园丁鸟优化算法(satin bower bird optimization algorithm，SBO)[7]是由Seyyed Hamid Samareh Moosavi和Vahid Khatibi Bardsiri于2017年模拟自然界成年雄性缎蓝园丁鸟的求偶行为而提出的一种新型群智能算法，并结合了自适应神经模糊推理系统(ANFIS)，发现能够有效地提高软件开发工作评估的准确性。该算法融合了动态步长和变异等操作，具有良好的寻优性能。但由于提出时间较短，目前国内外少有文献对其进行研究。

由于大多数的群智能算法，存在着求解精度粗糙、后期迭代速度缓慢等不足，这些新颖群智能算法在求解精度、寻优效果等方面仍存在较大的提升空间，国内外众多的专家学者针对这些不足进行了有效的改进。2015 年，孔飞和吴定会提出了一种改进的鸡群算法[8]，算法中对小鸡的位置更新公式中引入惯性权值和学习因子，解决了求解优化问题时易于跳过最优解及早熟收敛的问题。徐辰华等人于2017年基于Cat混沌与高斯变异改进灰狼优化算法[9]，该算法采用高斯变异扰动和优胜劣汰选择规则，对当前最优解进行变异操作以避免算法陷入局部最优。

本文鉴于改进的基础上，首先从原理上对算法的实现步骤进行阐述，并提出了基于自适应权重的缎蓝园丁鸟优化算法，通过自适应权重的方法改进SBO算法的局部搜索能力，提高了收敛精度；另外用修改后的高斯变异方法对缎蓝园丁鸟求偶亭的位置进行变异，提高了SBO算法的全局搜索能力，避免了陷入局部最优的问题。

1 基本缎蓝园丁鸟优化算法

缎蓝园丁鸟是一种以水果和昆虫为食的雀形目鸟，分布在澳大利亚东部的热带雨林。成熟的雄鸟在其各自的领地上以特殊的木棍结构建造求偶亭，装饰以鲜花、羽毛、浆果等，并发出嘹亮的鸣声来吸引雌鸟。雄性缎蓝园丁鸟建筑求偶亭的行为源于其天生的本能和对另类雄鸟的模仿。另外，并不是所有的成年雄鸟都能成功的构建和维护求偶亭，存在求偶亭被破坏的情况[10]。根据缎蓝园丁鸟的生活原理，SBO算法由以下几个步骤组成：

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

(2)计算每个求偶亭的吸引力。即该个体被选中的概率，由等式(1)计算。fiti代表第i个求偶亭的适应值，可通过等式(2)计算；f(xi)是第i个求偶亭的成本函数(目标函数)，每次迭代需保证成本函数值不断减小。

(1)

(2)

(3)位置更新。雄鸟会根据自身的历史经验和种群交流对求偶亭的位置不断进行调整，其更新公式如等式(3)所示。

(3)

其中，xikt表示第t次迭代第i个个体的第k维分量；j是通过轮盘赌机制确定的；xelite,k为当前整个种群的最优位置。λk是步长因子，由等式(4)确定。

(4)

其中，α是最大步长，Pj是目标求偶亭被选中的概率，概率值在0到1之间。从等式(4)中明显看出，步长与目标位置的概率成反比。换句话说，当目标位置的概率为0，步长最大为ɑ；当目标位置概率为1时，步长最小为ɑ/2。

(4)变异。在许多情况下，强壮的雄鸟会从较弱的雄鸟那里偷取材料，甚至破坏其求偶亭。因此，在算法的每个周期结束时，有一定的概率发生随机变异。在这个过程中，xik服从正态分布，如等式(5)所示。

(5)

(6)

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

σ=z*(varmax-varmin)

(7)

其中，varmax和varmin分别是变量xi的上界和下界，z是上下限之间差值的百分比，是可变的。

(5)将旧种群和从变异中获得的种群进行组合。在每个周期的最后，对旧种群和从变异中获得的种群进行评价。评估后，这两个种群被组合并对组合种群中的所有个体的成本函数值进行排序，保留函数值最小的个体，其余个体被删除。若此时满足终止条件，则输出最佳位置及其对应的最优值，否则继续进行步骤(2)到(4)。SBO算法的伪代码设计如下：

Initialize the first population of bowers randomly

Calculate the cost of bowers

Find the best bower and assume it as elite

While the end criterion is not satisfied

Calculate the probability of bowers using Eqs. (1) and (2)

For every bower

For every element of bower

Select a bower using roulette wheel

Calculate λkusing Eq. (4)

Update the position of bower using Eqs. (3) and (6)

End for

End for

Calculate the cost of all bowers

Update elite if a bower becomes fitter than the elite

End while

Return best bower

2 改进的缎蓝园丁鸟优化算法

2.1 自适应权重

惯性权重是粒子群中很重要的一个参数，如果惯性权重较大，算法搜索能力较强，便于进行全局搜索；如果惯性权重较小，则有利于算法在最优解周围精确搜索。本文受文献[11]的启发，运用自适应权重策略。当所有个体的适应值差异较大时，将惯性权重减小，当所有个体的适应值趋于一致或趋于局部最优时，将惯性权重增大。惯性权重W求解如式(8)所示。

W=Wmax-(Wmax-Wmin)*(t/itmax)＾2

(8)

式中，Wmax、Wmin分别表示W设置的最大值和最小值，t为当前迭代次数，itmax是最大迭代次数。运用上述方法设置权重，在迭代初期，W较大，有利于在全局范围进行搜索；在迭代后期，W较小，便于向最优解靠近。

2.2 改进原高斯变异形式

高斯分布又叫正态分布，是数理统计中非常重要的概率分布。高斯变异就是在原有的个体上加一个服从高斯分布的随机扰动项来取代原先的个体[12]。高斯变异能以较大的概率产生较小的变异值，在小范围内具有良好的搜索能力，不易像柯西变异因其过大的步长而跳离最优值。在智能优化算法中引入变异算子，既可以增强种群的多样性，又可以避免使算法陷入局部极小。基本的缎蓝园丁鸟优化算法采用了公式(6)的高斯变异策略对个体进行变异，但效果不太理想。经过多次实验，本文对原本的高斯变异方法进行了修改如公式(9)，不仅能使个体跳出局部极值点的束缚收敛于全局极值点，同时也提高了SBO算法的收敛速度和精度。

(9)

其中，N(0,1)为服从均值为0、方差为1的高斯分布。

2.3 混合优化的SBO算法

为了能够较好地避免基本缎蓝园丁鸟算法存在的收敛速度慢，寻优精度低等问题，本文通过上述方法将原SBO算法进行了改进，称为基于自适应权重的缎蓝园丁鸟优化算法(WSBO)。WSBO的基本步骤如下：

(1)初始化最大步长α、变异概率P、最大迭代次数Maxit等参数，随机初始化种群；

(2)计算每个求偶亭的成本函数值，确定最佳求偶亭的位置xelite及最优值；

(3)采用公式(2)计算每个求偶亭的适应值，并根据公式(1)计算每个求偶亭被选中的概率；

(4)采用公式(4)计算步长；

(5)采用公式(8)更新惯性权重W；

(6)采用公式(3)更新求偶亭的位置；

(7)如果rand

(8)将旧种群和从变异中获得的种群进行组合，并计算组合种群中的最优解和最优值。判断此时是否满足终止条件，若达到最大迭代次数，则终止算法，输出最佳位置及其对应的最优值；反之，继续迭代转向(3)。

2.4 算法流程图

改进的缎蓝园丁鸟算法从两个方面优化了雄鸟的求偶行为，一方面通过自适应权重，使算法有更好的局部勘探能力，另一方面通过改进的高斯变异形式使算法获得了更好的全局寻优能力，使求偶亭获得更好的全局最优解，改进后的缎蓝园丁鸟优化算法流程如图1所示。

图1 改进的SBO算法流程图

3 WSBO性能分析

3.1 函数测试及参数设置

为了进一步验证混合优化SBO算法的性能和收敛情况，本文对8个基准测试函数进行仿真实验来检验算法的改进效果，表1中详细地列出了各个测试函数的信息。

将本文所提出的基于自适应权重的缎蓝园丁鸟优化算法(WSBO)与人工蜂群算法(artificial bee colony algorithm，ABC)和萤火虫算法(firefly algorithm，FA)以及基本缎蓝园丁鸟算法进行对比实验。为了尽量保证各算法在实验中的客观性，所有算法种群规模统一设置为20，迭代次数为500次，各种算法的其它参数设置如下：基本SBO算法和WSBO算法的最大步长α=0.94，缩放比例因 子z=0.02，变异概率p=0.05；ABC算法的放弃阈值limit=60；FA算法参数：β0=2，α=0.2，γ=1。

表1 测试函数

3.2 实验结果分析

为减少实验中随机性的影响，每种算法对每个测试函数均独立运行30次，分别记录其最优值、均值和标准差，实验结果见表2。对于每个测试函数，在固定迭代次数下，均值反映了算法的寻优精度，标准方差反映了算法的鲁棒性和稳定性。

表2列出了4种算法在单峰、多峰函数上的测试结果，根据数值结果可以看出：在进行单峰函数测试中，相较于SBO、ABC和FA 3种算法，WSBO算法在最优值、平均值和标准差上都显著优于这3种算法，说明WSBO算法具有较高的搜索精度和较好的稳定性。

WSBO算法在处理多峰函数优化中同样也表现出了优越的性能。多峰值函数存在许多局部极小点，很难优化查找到全局最优值，但在Rastrigrin函数f2和Griewank函数f4的测试中，WSBO算法都能够快速找到理论最优值，且标准方差均为0；对于函数f3和f6，WSBO 算法同样也获得了最优的精度值，收敛速度和稳定度都明显优于其它3种算法。

通过以上分析表明，在大部分函数优化问题中，本文提出的改进算法的寻优精度以及稳定性要优于SBO、ABC以及FA 3种算法，并且在多极值、多峰函数上，WSBO算法仍然寻找到了最优的精度值，说明WSBO算法具有较好的全局和局部搜索性能，并且在函数寻优过程中表现出较好的鲁棒性，相较于原SBO算法有了很大程度的提高。

表2 4种算法实验结果比较

为了能更直观地显示WSBO 算法的优化效果，图2给出了4 种算法在8个标准测试函数f1～f8上搜索函数最优值过程中随迭代次数增加的收敛曲线。从图中可以看出，WSBO 算法不管对于多峰函数还是单峰函数，变化近似于直线，说明其速度下降快，能够在较短的时间内找到或者接近理论最优值，并不断向最优解靠近，达到很高的精度。这体现了WSBO算法的寻优速度、收敛精度都优于其余3种算法。函数f2和f4的优化图表明，在迭代次数不到500次时,WSBO 算法已经找到理论最优值；函数f1、f3、f5、f6、f7和f8的优化图表明，在迭代过程中, WSBO算法能够快速接近理论最优值。这充分证明了WSBO 算法的可行性及其寻优性能的提升。同时表明，改进的WSBO算法能有效提升全局搜索能力，并在算法后期，有效提升局部开发能力。

(a) f1函数收敛曲线对比

(c) f3函数收敛曲线对比

(e) f5函数收敛曲线对比

(g) f7函数收敛曲线对比

(b) f2函数收敛曲线对比

(d) f4函数收敛曲线对比

(f) f6函数收敛曲线对比

(h) f8函数收敛曲线对比

图24种算法在函数f1～f8上的收敛曲线

Fig.2Theconvergencecurvesof4algorithmsonfunctionf1～f8

3.3 WSBO时间复杂度分析

对WSBO算法的时间复杂度进行分析，设算法的种群规模为NP；问题维度为numbervar，最大迭代次数为MaxIt,则每个操作的时间复杂度如下：初始化：O(NP*numbervar)；计算求偶亭个体被选择概率：O(NP*numbervar)；自适应参数：O(NP*numbervar)；位置更新：O(NP*numbervar)；适应度计算：O(NP)；整体复杂度为：O(MaxIt*NP*numbervar)，这与基本SBO的时间复杂度相同，没有增加计算负担。

4 结束语

为提高SBO算法的收敛精度，避免算法陷入局部最优，本文提出了基于自适应权重的缎蓝园丁鸟优化算法—WSBO 算法。该算法通过使用自适应权重和改变高斯变异形式提升了基本SBO算法的全局搜索能力和局部寻优能力，从而在很大程度上提高了算法的收敛精度。本文还进行了8个函数的仿真测试，实验结果表明，改进的SBO 算法是可行有效的，在收敛速度和收敛精度方面都要优于原缎蓝园丁鸟算法、人工蜂群算法和萤火虫算法，其寻优性能有了很大的提高。如何将改进算法应用到更多的领域，是今后的研究工作。