一种改进的自适应惯性权重布谷鸟算法

孙敏，韦慧

(安徽理工大学数学与大数据学院，安徽 淮南 232001)

20世纪后期，各种启发式算法已经成为智能计算领域的研究热点，如蚁群算法[1]、粒子群算法[2]等。近几年来，一些更高效的新型启发式算法不断脱颖而出，如在2009年，剑桥大学的Yang和Deb模拟布谷鸟寻窝产卵行为，提出了布谷鸟搜索算法(CS算法)[3]。CS算法具有参数少、鲁棒性强、高效易于实现以及随机搜索路径优等特点，已成功解决了许多实际难题，如商业优化问题[4]、铣削操作优化问题[5]等。

虽然CS算法有很多优点，但仍存在搜索速度较慢、易陷入局部最优、缺少活力等缺点。目前通过改进算法参数、调整算法结构提高算法性能是一个重要的研究方向。国内外众多学者对此进行研究，并给出了一些改进方法：文献[6]建议采用随迭代次数递减的步长因子来提高算法的收敛速度,但未改进偏好随机游动部分，算法的局部能力提升不足；文献[7]引入贪婪机制提高算法的计算精度，但是会增加计算时间；文献[8]将粒子群算法思想用于CS算法的位置更新过程，提出基于粒子群算法的布谷鸟搜索算法，进一步改善了算法的自适应性，然而对于高维问题该算法没有明显的优势；文献[9]利用布谷鸟的鸟窝位置和最优鸟窝位置之间的距离进行自适应调整，提出了一种基于自适应步长的布谷鸟算法，提高了算法的收敛速度，但计算精度没有明显增加。

由于布谷鸟算法完全依赖于Lévy飞行和偏好随机游走，二者平衡了算法的全局搜索和局部搜索[10]，而Lévy飞行主要受到步长参数的影响，偏好随机游动主要受发现概率参数的影响，因此对这2个参数进行合理调整，是提高CS算法计算效率的主要研究方向。Valian等[11]引入自适应步长和自适应发现概率，提出一种改进的CS算法(improved CS，记作ICS-1)。ICS-1算法的计算效率和精度优于基本的CS算法。基于CS算法的寻优过程，笔者给出了一种改进的自适应惯性权重布谷鸟搜索算法(ICS-2)：通过在寻优过程中自适应地改变发现概率和步长因子，以及在偏好随机游动机制中加入一种根据种群最优适应度值、最差适应度值以及个体适应度值自适应调整惯性权重，实现对算法的整体动态调整。

1 布谷鸟搜索算法

自然界中，布谷鸟繁衍后代的方式是将自己的卵悄悄的产入宿主鸟窝并由宿主鸟孵化。一旦宿主鸟发现自己的鸟窝有外来卵，就会将外来卵丢弃或者遗弃该鸟窝，并另筑新巢。为了模拟布谷鸟寻窝，Yang和Deb假定了以下3个理想规则[3]：①布谷鸟1次只产1个卵，并随机选择鸟窝孵化；②最好的鸟窝(解)将被保留到下一代；③可利用的鸟窝数量N是固定的,宿主鸟能发现外来卵的概率pa∈[0,1]，在这种情况下，宿主鸟可将该卵丢弃或放弃这个鸟窝，另寻地方重新建1个新鸟窝。

在以上3个规则的基础上，布谷鸟按Lévy飞行方式搜索鸟窝的路径和位置更新公式如下:

(1)

Lévy(λ)～μ=t-λ(1<λ≤3)

(2)

式(1)描述的随机游动是一个Markov链，即下一代的位置仅取决于当前的位置。为从当前最优解获取步长信息，采用文献[7]的步长因子：

(3)

式中：α0是常数，一般取0.01；xbest表示当前最优解。为了便于计算，文献[12]采用式(4)计算Lévy随机数：

(4)

结合公式(1)～(4)，在Lévy飞行过程中CS算法采用式(5)生成新的解：

(5)

(6)

2 改进的布谷鸟算法

2.1 自适应参数pa

CS算法中，自适应参数pa控制了全局随机搜索和局部精细搜索之间的平衡，当pa值越小，被更新的鸟窝数目越多，全局搜索的多样性越强；反之，pa越大，越有利于提高局部搜索的能力[13]。将pa取为固定值0.25不利于全局与局部搜索之间的平衡，因此，笔者提出使pa随算法进程动态变化的自适应策略：

pa=pa max-(pa max-pa min)exp(-η(ti/tmax)θ)

(7)

式中:ti为当前迭代次数；tmax为设置的最大迭代次数；pa max为最大发现概率；pa min为最小发现概率。

式(7)实现了pa随算法进程ti/tmax的增加而由小到大动态变化的自适应策略，使得改进后的算法能够在全局和局部搜索之间保持好的平衡，具体来说，ICS-2算法通过pa的自适应动态变化，在算法前期能够保持很强的全局搜索能力，同时兼顾局部搜索，而在后期，局部搜索逐渐增强，同时也兼顾全局搜索，从整体上提高了算法的收敛速度和精度，避免陷入局部最优。

2.2 自适应Lévy飞行

Lévy飞行机制中，步长因子α0的选取影响着布谷鸟算法的寻优特性，在寻优过程中，步长因子越大，全局搜索能力越强，但降低了算法的寻优精度，相反，步长因子越小，搜索速度变得越慢，提高了寻优精度[14]。CS算法中将步长因子固定，显然不是最好的解决方法，使得寻优过程缺乏自适应性，进而降低了算法的收敛速度和精度。为此，笔者提出了一种步长的自适应策略：

(8)

式中：ti为当前迭代次数；tmax为设置的最大迭代次数。

此时，式(5)修改为：

(9)

由式(8)可知，步长因子α0按照非线性递减的方式，在寻优前期，加快了收敛速度，同时较大的步长扩大了搜索范围，有利于搜索全局最优。随着算法进程的增加，较小的步长提高了寻优精度。

2.3 动态惯性权重的偏好随机游动

图1 ICS-2算法流程图

在基本CS算法的偏好随机环节中，鸟巢位置更新是采用固定上一代位置为参考的更新方式，容易造成算法在迭代后期陷入局部最优值。动态惯性改进策略[15]是一种能够合理的控制算法全局探索能力和局部开发能力的机制，有效提高算法的搜索能力。Nickabadi等[16]对基于常数、线性递减、非线性递减和自适应,4种动态惯性权重作了总结并比较，笔者在偏好随机游动过程中引入一种由鸟巢位置适应度值变化决定的动态惯性权重，动态惯性权重w为：

(10)

式中：fi、fmin和fmax分别为每代种群中第i个个体、最优个体以及最差个体的适应度值。

改进的偏好随机游动可表示为：

(11)

在算法运行中，如果个体的适应度与最优个体的适应度之间差异较大，则此时惯性权重w较小，从而加强了局部寻优能力。若算法陷入局部最优，则个体的适应度与最优个体的适应度之间差异较小，此时w增大，扩大了搜索空间，使得算法跳出局部极值，提高全局寻优能力。因此，w随着鸟窝适应度值的变化而动态改变，能够平衡全局与局部之间的搜索且提高了其跳出局部最优的能力。

2.4 ICS-2算法步骤

改进的自适应惯性权重布谷鸟算法(ICS-2算法)的具体步骤如下：

步3 通过动态发现概率pa淘汰部分鸟窝，并用改进的偏好随机游动搜索方式式(11)产生与淘汰鸟窝数量相同的新鸟窝。

ICS-2算法的流程图如图1所示。

3 测试

为验证ICS-2算法具有更快的收敛速度和更高的计算精度，以求解4个标准测试函数的最小值为例，同时将CS[3]和ICS-1[11]这2种算法加入对比。

3.1 试验设计

选取的测试函数包括单峰函数和复杂多峰函数，如表1所示。

表1 测试函数

表2 试验参数设置

试验中算法参数选取如表2所示：对于CS算法，采用文献[3]的参数；对于ICS-1算法，取文献[11]中的参数；并且η=8，θ=0.3。

ICS-1算法针对Lévy飞行步长及参数pa进行自适应改进，具有代表性，与ICS-2算法在不同维度的情况下进行对比。试验中，各算法独立运行30次，3种算法终止条件为满足最大迭代次数1000次或精度达到10-10。获取统计数据与相应仿真曲线，以便进行比较。

3.2 试验结果与分析

表3～表5分别给出了3种算法对测试函数f1～f4在维数n=10、30、50下的最优值、最差值、平均值、平均运行时间及算法达到精度时所需的平均迭代次数，表中，“-”表示最大迭代次数达到1000次时，没有收敛于所设置的精度。

表3 10维情况下各算法的性能比较

从表3可以看出，当n=10时，对测试函数f1和f2，3种算法都能达到所要求的精度，但ICS-2算法明显具有较快的收敛速度(平均迭代次数和运行时间)；对于复杂的多峰函数f3，ICS-2算法的优势更加明显，最优值比CS和ICS-1分别高出了13、12个数量级，运行时间分别减少了近77、33ms，并且ICS-2算法只需511次左右就可以达到目标精度，而CS和ICS-1至少需要1000次，因此ICS-2算法计算精度较高同时拥有更快的收敛速度；对于复杂的多峰函数f4，ICS-2比CS和ICS-1的最优值分别提高了7个和4个数量级，虽然在平均值和运行时间上优势不大，但ICS-2算法迭代856次左右就可以达到目标精度，而CS和ICS-1至少需要1000次。

表4 30维情况下各算法的性能比较

从表4可以看出，当n=30，对于函数f1，f2，ICS-2算法的搜索精度远优于CS和ICS-1算法，并且ICS-2算法以最少的迭代次数收敛于目标精度；对于函数f3，ICS-2算法用最短时间收敛至全局最优值，平均运行时间比CS和ICS-1分别减少了近382、301ms，然而此时CS算法无法收敛于全局最优值，ICS-1算法达到目标精度比ICS-2算法多迭代479次左右；对于函数f4，3种算法寻优能力相当，但ICS-2的计算结果仍优于其他2种算法。

从表5可以看出，当n=50，对于函数f1，在CS算法无法收敛于全局最优值的情况下，ICS-2算法以最少的运行时间收敛于全局最优值，并且只需迭代224次左右就可以达到目标精度；ICS-1虽然可以收敛于全局最优值，但是耗费的时间较多，达到所设置的目标精度至少迭代1000次，相比之下，ICS-2算法的计算精度较高，具有较快的收敛速度；对于函数f2，3种算法都可以收敛于全局最优值，ICS-2算法仍然比CS和ICS-1算法有更快的计算效率(平均运行时间和迭代次数)；对于函数f3，ICS-2的最优值、最差值和平均值都达到理论最优，平均运行时间比CS和ICS-1分别减少了520、462ms，且ICS-2算法只需要346次就可以达到目标精度，其他2种算法至少需要1000次，因此，对于函数f3在高维情况下，ICS-2算法的收敛速度和计算精度的优势更加明显；对于函数f4，虽然3种算法都没有达到所需求的精度，ICS-2算法明显具有较快的收敛速度(平均运行时间)。

表5 50维情况下各算法的性能比较

图2 f1，f2，f3，f4收敛曲线

图2给出了3种算法在维数n=30下的4个测试函数收敛曲线。从图2(a)可以看出，对于函数f1，ICS-2算法寻优时最小适应度值的下降速度明显最快，ICS-1次之，CS最慢；当迭代次数达到1000次时，ICS-2的精度明显比CS和ICS-1算法高，寻优精度的优势较为明显。从图2(b)可以看出，对于函数f2，由于该函数的全局最优点位于一个平滑、狭长的抛物线形山谷内，计算复杂度随问题维度增加而增大，CS和ICS-1算法无法找到有效的搜索方向，皆陷入局部最优位置；ICS-2算法虽然在前期收敛速度优势并不明显，但当迭代300次后，ICS-2算法最小适应度值下降的速度明显加快，克服局部极值能力更强，在收敛性能上更优，改进的效果较为明显。从图2(c)可以看出，对于函数f3，寻优前期，ICS-1的适应度值下降速度和CS相比优势不大，然而迭代400次之后，适应度值下降速度明显比CS快；而整个寻优过程中，ICS-2最小适应度值的下降速度一直明显最快。从图2(d)可以看出，对于函数f4，由于该函数本身具有强烈震荡性，不易求得全局最优解，ICS-1的寻优曲线差于标准的CS算法；ICS-2寻优精度虽然不高，但仍高于其他2种算法，且当迭代500次之后，ICS-2算法的适应度值下降速度明显比CS、ICS-1快。

不同维度下的函数测试结果表明，ICS-2算法在整体性能上优于CS、ICS-1算法，且能较好地解决标准CS算法存在的收敛速度慢、易陷入局部最优等问题，这是因为该算法在其寻优过程中采用自适应步长进行搜索，且在偏好随机游动中引入了自适应惯性权重策略，提高了算法的搜索能力，平衡了局部搜索和全局搜索，同时，参数pa的自适应使得种群能够保持多样性。所以，算法用时较少，收敛精度和速度明显提高。

4 结语

分析了布谷鸟搜索算法的寻优过程与特性，给出了一种改进的自适应惯性权重布谷鸟算法。该算法通过对发现概率和步长因子自适应调整，并将动态惯性权重引入偏好随机环节中，由所给的经典测试函数，讨论了CS、ICS-1和ICS-2算法的收敛速度快慢和精度高低问题。仿真试验结果表明，无论是简单的单峰函数还是复杂的多峰函数，改进的布谷鸟算法具有更好的寻优能力，加快了算法的收敛速度，提高了计算精度，克服了标准CS算法易陷入局部最优等不足，在求解连续函数问题上具备优势。