多阶段动态扰动和动态惯性权重的布谷鸟算法

张珍珍，贺兴时，于青林，杨新社

1.西安工程大学理学院，西安 710600

2.汤普森大学数学与统计系，哥伦比亚 甘露 V2C0C8

3.密德萨斯大学科学与技术学院，伦敦 NW4 4BT

随着科学与技术的发展，优化问题在人们生活中发挥了越来越重要的作用，对于优化问题的解决方法要求也逐渐提高。传统的计算方法来解决这些复杂优化问题时，会出现求解精度低，收敛速度慢且耗时长、成本高等方面的缺点。针对传统算法解决复杂问题时出现的局限性，为了复杂的优化问题能够得到解决，找到更为合理和满意的近似解。众多学者开始设计了元启发式算法，并在过去的二三十年中得到迅速发展，成为当前最活跃的算法研究领域之一。常用的元启发式算法包括萤火虫算法[1]（firefly algorithm，FA）、飞蛾扑火算法[2]（moth-flame optimization algorithm，MFO）、粒子群优化算法[3]（particle swarm optimization，PSO）、花粉算法[4]（flower pollination algorithm，FPA）、樽海鞘算法[5]（salp swarm algorithm，SSA）等算法。这些算法都具有简单易行、参数少、运行时间短等特点，因此解决了众多非线性和多模态的现实寻优问题。

剑桥大学的Yang 和Deb[6]于2009 年通过模拟布谷鸟寻窝产卵的行为提出了一种新的搜索算法，并命名为布谷鸟搜索算法（cuckoo search，CS）。布谷鸟搜索算法因其通用性强，单高效、控制参数少、易于实现，而被广泛研究与应用于图像处理[7]、临床医学[8]、旅行商问题[9]、PID控制器调整[10]、工程优化[11]、信号处理[12]等诸多领域，并表现出良好的寻优性能。但布谷鸟算法同其他生物启发式算法一样都存在易限于局部最优，后期收敛速度偏慢，求解精度不高等问题，在处理一些多维复杂函数时，难以找到最优解，因此，需要改进布谷鸟优化算法来克服它的这些不足，使其能更好地应用于更多问题。针对以上问题，Gherboudj 等[13]提出了一种离散二进制布谷鸟搜索（binary cuckoo search，BCS）算法来处理二进制优化问题。Kanagaraj 等[14]将遗传算子嵌入到CS 算法中以平衡局部搜索和全局优，提出了CS-GA 算法。王凡等[15]通过分析鸟窝位的群体状态转移过程加入了Markov 链，提高算法全局搜索能力。宋庆庆等[16]将混沌序列引入到布谷鸟算法中初始化鸟窝位置。陈程等[17]提出了动态权重改变自适应概率的双重搜索布谷鸟算法（DECS）。针对布谷鸟算法在处理复杂函数时，求解精度不高，易陷入局部最优等缺陷，本文提出了基于多阶段动态扰动和动态惯性权重的布谷鸟算法（MACS），通过将多阶段动态扰动策略引入到布谷鸟算法的全局位置，对最优鸟巢位置进行根据方差可调的正太随机分布扰动，增加了种群的多样性和鸟窝的灵活性，提高全局搜索能力。并在局部位置处引入动态惯性权重，更大程度提高了鸟窝的开发与探索能力，使得算法有效克服易陷入局部最优的缺陷，提高局部寻优搜索能力。最后，引入了动态切换概率p代替固定概率，可以动态平衡全局搜索和局部搜索。实验结果表明，MACS 算法提高了求解精度，加快收敛速度，具有更好的优化性能。

1 基本布谷鸟算法

在大自然中，布谷鸟具有特殊的寻窝产卵行为，不自己筑巢，而将自己的卵悄悄的产在其他宿主鸟的巢穴中，由其他鸟帮它来卵化下一代。但是当宿主鸟一旦发现有外来鸟蛋，宿主鸟就会抛弃这些外来的鸟蛋或者重新筑巢，为了模拟布谷鸟特殊的寻窝和繁衍后代的行为。Yang和Deb假设了以下3个理想规则[18]：

（1）布谷鸟一次只产一个蛋，并随机选择鸟窝孵化；

（2）在随机选择的鸟窝中，最好的鸟窝将被保留到下一代；

（3）可选择的鸟窝数量N是固定的，宿主鸟发现外来布谷鸟蛋的概率为pa∈[0,1] 。

基于以上的3 个理想状态，采用下列式（1）对下一代鸟窝位置x(t+1)进行位置更新：

由式（2）可知，布谷鸟在寻窝过程中的飞行路径变化是带有重尾的概率分布，使得布谷鸟的飞行路径表现出levy飞行的性质，即在寻优路径中频繁的短步长偶尔会出现长步长，这种性质使得CS 算法拥有更强大的全局搜索能力，也有效使布谷鸟算法避免陷入局部最优。

文献[18]采用式（3）计算莱维随机数：

为了便于对莱维飞行的计算，采用文献[18]步长因子：

其中α0为常数，一般取0.01，xbest为当前最优解。

结合公式（1）～（4），CS 算法采用式（5）来更新新的鸟窝位置：

2 多阶段动态扰动和动态惯性权重的布谷鸟优化算法

2.1 多阶段动态扰动策略

在布谷鸟算法的全局搜索阶段，所有鸟窝位置都朝着同一全局最优位置靠近，致使布谷鸟算法很容易陷入局部最优，导致算法在处理复杂多峰函数时，收敛精度低，收敛过早等缺点表现得尤为明显。针对这个问题，本文提出了一种多阶段动态扰动策略，对布谷鸟算法的最优鸟窝位置进行分阶段的动态扰动，更新最优鸟窝位置。即对全局最优鸟窝位置根据方差可调的正态随机分布进行扰动，从而得到新的全局最优鸟窝位置XNewbest，更新公式如（7）所示：

其中，σ表示相对于Xbest的不确定度，是关于迭代次数t的非增函数，其更新公式如下：

其中，σ表示对原最优鸟窝位置正态扰动的半径参数且σ1<σ2，本文取σ1=0.9，σ2.=0.000 001，α1、α2是半径变化的控制参数，且α1<α2，本文取α1=0.4，α2=0.7，t是当前迭代次数，T是最大迭代次数。其扰动半径变化图如图1所示。

图1 扰动半径σ 变化图Fig.1 Variation diagram of perturbation radius σ

由图1可以看出，扰动半径σ是一个分为三阶段的动态变化数值。本文在算法的迭代前期以固定较大的半径对布谷鸟算法的全局最优鸟窝位置进行扰动，得到新的变化较大的最优鸟窝位置，使全体鸟窝在朝着新的最优鸟窝位置靠近时，更具有广泛性和多样性，帮助算法在迭代前期更大范围内的去寻找全局最优，避免算法朝着固定最优鸟窝位置靠近，而在迭代前期就陷入局部最优的情况。当在迭代中期，算法在逐步缩小范围寻找全局最优时，本文也以线性递减的方式逐步降低对最优鸟窝位置的扰动半径，使全体鸟窝位置逐步稳定的向全局最优靠近。而在最后迭代后期，算法已经非常靠近寻求出全局最优解时，本文以固定非常微小的扰动半径对当前最优鸟窝位置进行扰动，不再大范围波动当前最优位置，使算法小范围内精细搜索出全局最优解。本文基于上述根据迭代过程而变化的多阶段扰动策略，充分灵活发挥了当前最优鸟窝位置的作用，有效避免算法易陷入局部最优的缺点，提高了算法的全局搜索能力和寻优性能。

2.2 动态惯性权重

在布谷鸟算法的偏好随机游动环节中，如式（6）所示，采用的是固定上一代鸟窝位置的更新方式，容易造成算法在迭代后期陷入局部最优值。而惯性权重因子是布谷鸟算法中的重要影响参数，当惯性权重较大时，有利于扩大搜索范围，增加全局搜索能力提高搜索速度。当惯性权重较小时，有利于帮助布谷鸟算法进行后期的精细搜索，提高搜索精度。所以动态惯性权重改进策略是一种能够动态平衡全局搜索和局部搜索的改进机制，能够提高算法的搜索速度和收敛精度。本文在上一代鸟窝位置处引入自适应动态惯性权重[19]对布谷鸟算法的偏好随机游动环节进行改进。

改进后的布谷鸟偏好随机游动环节式（6）如式（9）所示：

其中动态惯性权重ϖ公式如（10）所示：

式中，t是当前迭代次数，tmax是最大迭代次数，ϖ变化如图2所示。

图2 动态惯性权重ϖ 变化图Fig.2 Variation diagram of dynamic inertial weight ϖ

通过图2 可以看出，ϖ为（0，1）之间随迭代次数非线性递减的动态惯性权重，随着迭代过程的进行，惯性权重ϖ逐步减小。在标准布谷鸟偏好随机游动环节中，新的鸟窝位置的更新是采用固定上一代鸟窝位置的方式，而本文通过在上一代鸟窝位置处引入如图所示的动态惯性权重系数，灵活地将上一代鸟窝位置与迭代过程动态联系起来。在迭代前期，给上一代鸟窝位置赋予相对大的系数，使上一代鸟窝具有更大的作用能力与范围，帮助布谷鸟算法在前期扩大搜索空间，广泛寻找全局最优解。随着算法迭代过程的进行，惯性权重系数逐渐减小，直至到迭代后期，算法接近最优解时，对上一代鸟窝位置采用相对较小的惯性权重系数，有效的削弱了上一代鸟窝的保留信息，帮助布谷鸟算法有效跳出局部最优，使布谷鸟个体具有更好的局部寻优能力。本文通过动态惯性权重系数的引入，灵活处理上一代鸟窝的位置信息，提高了算法的局部寻优能力。

2.3 自适应切换概率

在基本布谷鸟算法中，用固定的切换概率p=0.25来控制全局搜索和偏好随机游走，不利于动态平衡算法的全局探索和局部开发能力。自适应概率p是布谷鸟算法的重要参数，当p较小时，增加了全局的多样性，提高全局搜索能力，当p较大时，增加局部搜索能力，提高了算法精度和效率。所以动态概率p是一种综合提高算法性能的优化改进策略。本文引入了动态切换概率p来随着迭代次数自适应地平衡全局和局部搜索能力，来更好地实现寻优能力，本文提出的动态概率公式如式（11）所示：

式中，t是当前迭代次数，tmax是最大迭代次数，p的变化如图3所示。

图3 自适应切换概率变化图Fig.3 Adaptive switching probability graph

由图3可以看出，本文提出的概率p是一个随迭代过程进行而自适应增大的动态切换概率。在算法迭代前期，以较小的概率p来控制全局搜索和局部搜索的切换，在这个阶段由于概率p较小，所以帮助算法在迭代前期多进行全局搜索，大范围寻找全局最优解，增加了算法的全局多样性，提高了算法的全局搜索能力。随着迭代过程的进行，概率p不断增大，直至在迭代后期，概率p相对较大，帮助算法在迭代后期已经靠近全局最优解时，多进行局部精细搜索，提高算法的运算精度和搜索效率。通过将布谷鸟算法的固定概率替换成自适应切换概率，将概率p与迭代过程动态联系在一起，帮助算法灵活平衡了全局搜索能力和局部搜索能力，提高算法性能。

2.4 MACS算法分析

2.4.1 MACS算法的理论客观分析

多阶段动态扰动和动态惯性权重的布谷鸟算法（MACS）着眼于对布谷鸟算法的整体优化，充分协调利用多阶段动态扰动策略、动态惯性权重ϖ和自适应切换概率p三者之间的关系。MACS 算法前期全局搜索阶段利用三阶段的动态可调方差σ灵活控制最优鸟窝位置的扰动半径范围，扰动半径变化范围从0.000 001到0.9，在保证算法稳定性的前提下，最大程度上增加了前期鸟窝的多样性，保证算法充分勘探搜索种群。与此同时，对偏好随机游动环节结合变化范围在[0，1]的非线性递减动态惯性权重ϖ进行补充，帮助进行算法后期精细搜索，提高算法寻找最优解的效率，并通过引入自适应切换概率p，确保p在整个算法迭代阶段保持一个在[0.15，0.25]间动态变化的状态，来动态平衡MACS算法的全局搜索和局部搜索阶段，使算法更具有灵活性。通过3个策略间的相互作用、相互联系，MACS算法对布谷鸟算法进行了整体优化，充分开发算法搜索性能。

2.4.2 MACS算法流程

MACS具体执行步骤如下：

步骤6 判断算法的终止条件，若满足，就输出当前最优值fmin；若不满足，就重复步骤2～6。

详细算法流程图，如图4所示。

图4 MACS算法流程图Fig.4 MACS algorithm flow chart

2.4.3 MACS算法的计算复杂度分析

在标准布谷鸟算法CS 中，假设种群大小为N，解空间维数为n，最大迭代次数为tmax，那么原布谷鸟算法CS的计算复杂度可以用Ο(N×n×tmax)表示。

该方程的推导基于算法初始化大小为N的种群，维数因子n决定了算法的复杂性，对于每个布谷鸟种群中的个体，都需要执行Ο(n)次操作，导致复杂度为Ο(N×n)。这是针对单次迭代的复杂性，但是一般来说，布谷鸟算法运行需要许多次迭代，所以算法总计算复杂度取决于算法的最大迭代次数，这个过程给出了原布谷鸟算法的总复杂度为Ο(N×n×tmax)。

与原布谷鸟算法CS 相比，MACS 算法在原算法的基础上添加了多阶段动态扰动策略更新最优鸟窝位置，动态惯性权重和自适应切换概率的改进。原则上，所提出的新改进都没有额外的计算负担，从第3章的比较实验结果也可以明显看出，对于变化的种群大小，MACS算法的结果随着CS 算法的变化而变化，维数大小的影响也保持一致，因此MACS算法的计算复杂度相较于原CS算法并没有提升，仍为Ο(N×n×tmax)。

3 仿真实验

3.1 测试函数

为了证明MACS 算法的寻优性能，本文选取了11个不同难度的函数，其中涵盖简单低峰函数和复杂多峰函数，高维函数和低维函数，函数设置见表1。分别对MACS 算法的收敛速度，收敛精度进行测试。同时与ASCSA算法、CS算法、FPA算法、BA算法，进行对比分析。

表1 测试函数Table 1 Test functions

3.2 测试环境及算法参数

实验环境如下：CPU为i5-4288U 2.60 GHz，运行内存4 GB，操作系统Windows10，编程环境Matlabr2020a。CS算法、FPA算法、BA算法、ASCSA算法设置参数如表2所示。

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

3.3 算法求解精度比较分析

表3～11 分别给出了5 种算法对测试函数f1～f9，在维数n=10、n=50、n=100 下的方差、最优值、平均值、最差值结果。表12 和表13 分别给出了5 种算法对低维测试函数f10、f11在维数n=2 下的方差、最优值、平均值、最差值结果。

表3 f1( x )Rastrigin函数仿真结果Table 3 Simulation resutls of f1( x )Rastrigin function

表4 f2( x )Schaffer函数仿真结果Table 4 Simulation resutls of f2( x )Schaffer function

表5 f3( x )Zakharov函数仿真结果Table 5 Simulation resutls of f3( x )Zakharow function

表中，f1(x)函数是典型的非线性多模态函数，局部最小值个数与维数成正比且起伏不定，从表3中可以看出，MACS表现出良好的性能，取到全局最优值，而其他4 种算法后期都陷入了局部最优。f2～f5为复杂多峰函数，MACS 算法在不同维度下均表现出良好的寻优能力，而其他算法都无法获得全局最优解。

f6～f8为单峰函数，在定义域内只有一个极值点，MACS 也仍能取到全局最优解，表现出良好的寻优性能。从表格中可以看出，对测试函数f1～f8中的不管是单峰函数还是复杂多峰函数，MACS算法均取到了全局最优值。并且随着维度的增加，仍能保持取到最优结果，表现出良好的寻优能力和稳定性，而其他4 个算法在迭代后期都陷入了局部最优，并随着维度的提高，求解精度逐渐下降。对测试函数f9，MACS 算法虽然也陷入了局部最优8.881 8E-16，但相较于其他4个算法仍不同程度上的提高了收敛精度，并随着维度的提高，当其他4个算法求解精度都在明显下降时，MACS仍能表现出良好的稳定性。

对于低维函数f10～f11，由表12 和表13 可以看出，MACS 算法仍能收敛到全局最优，证明了MACS 算法在低维测试函数条件下也仍具有良好性能，具有普适性。

表6 f4( x )Griewank函数仿真结果Table 6 Simulation resutls of f4( x )Griewank function

表12 f 10( x )Bohachevsky函数仿真结果Table 12 Simulation results of f10( x )Bohachevsky function

表13 f11( x )Mytyas函数仿真结果Table 13 Simulation results of f11( x )Mytyas function

表7 f5( x )Alpine函数仿真结果Table 7 Simulation resutls of f5( x )Alpine function

表8 f6( x )Sphere函数仿真结果Table 8 Simulation resutls of f6( x )Sphere function

表9 f7( x )Sum square函数仿真结果Table 9 Simulation resutls of f7( x )Sum square function

表10 f8( x )Schwefel’s 2.2函数仿真结果Table 10 Simulation resutls of f8( x )Schwefel’s 2.2 function

表11 f9( x )Ackley函数仿真结果Table 11 Simulation resutls of f9( x )Ackley function

3.4 算法收敛曲线分析

图5～15 分别是11 种函数的收敛曲线图，直观地反映出了5 种算法的收敛速度和收敛精度。f1～f5为多峰函数，在定义域内存在多个极值点，可以考察算法的寻优能力，是否能跳出局部最优。

由图5、图6、图9 可以看出，其他4 个算法都在迭代后期都陷入了局部最优，而MACS 成功跳出局部最优，取得全局最优值。由图7 和图8 可以看出，CS 算法和BA 算法都陷入了局部最优，FPA 算法和ASCSA 算法在300 次后取得最优值，而MACS 算法在50 次迭代后就达到了全局收敛，取得最优值。f6～f8为单峰函数，在定义域内只有一个极值点，可以测试算法的收敛速度。

图5 Rastrigin函数收敛曲线图Fig.5 Convergence curve of Rastrigin function

图6 Schaffer函数收敛曲线图Fig.6 Convergence curve of Schaffer function

图7 Zakharov函数收敛曲线图Fig.7 Convergence curve of Zakharov function

图8 Griewank函数收敛曲线图Fig.8 Convergence curve of Griewank function

图9 Alpine函数收敛曲线图Fig.9 Convergence curve of Alpine function

由图10～12 可以看出，MACS 算法均在50 次迭代就取得全局最优解，相较于其他4 个算法明显有更高的收敛速度。f10～f11为低维函数，由图14 和图15 可以看出，MACS 算法也都在50 次迭代左右就达到全局最优。

图10 Sphere函数收敛曲线图Fig.10 Convergence curve of Sphere function

图11 Sum square函数收敛曲线图Fig.11 Convergence curve of Sum square function

图12 Schwefel’s 2.2函数收敛曲线图Fig.12 Convergence curve of Schwefel’s 2.2 function

图13 Ackley函数收敛曲线图Fig.13 Convergence curve of Ackley function

图14 Bohachevsky函数收敛曲线图Fig.14 Convergence curve of Bohachevsky function

图15 Mytyas函数收敛曲线图Fig.15 Convergence curve of Mytyas function

综上所述，经过对这5种算法的收敛曲线进行比较分析，可以看出，无论是单峰函数还是复杂多峰函数，无论是高维函数还是低维函数，无论是寻优能力还是寻优精度上，MACS 算法的寻优表现都优于其他四个算法，表现出良好的性能。

4 结束语

针对布谷鸟仿生智能优化算法存在着的易陷入局部最优、求解精度低以及收敛速度慢等问题，本文提出了基于多阶段动态扰动策略和动态惯性权重的布谷鸟搜索算法（MACS）。在布谷鸟全局搜索阶段，引入多阶段动态扰动策略对布谷鸟算法的全局位置的最优鸟巢位置根据方差可调的正态随机分布进行扰动；引入动态方差概念，根据迭代次数，灵活调整扰动半径，增加种群的多样性和鸟窝位置的灵活性，提高算法的全局搜索能力。在布谷鸟局部搜索阶段，在上一代鸟窝位置处引入动态惯性权重ϖ，使得算法有效克服易陷入局部最优的缺陷，提高算法局部寻优搜索能力。最后，引入了动态切换概率p代替原有的固定概率，可以动态平衡全局搜索和局部搜索。通过与4 种算法相比和11 个测试函数的仿真结果表明：改进布谷鸟算法（MACS）的寻优性能明显提高，收敛速度更快，求解精度更高，具有更强的全局搜索能力和跳出局部最优能力。