发现概率参数自适应调节的布谷鸟改进算法

贾 涵，连晓峰

北京工商大学 计算机与信息工程学院，北京 100048

1 前言

迄今为止优化算法分为传统优化算法和智能优化算法。智能优化算法的理论研究主要包括算法的稳定性分析、收敛性分析、收敛速度分析及算法的计算复杂性分析等，这些研究中包含了对算法参数设置的一些理论性指导。其中，关于稳定性的研究结果相对较多，但收敛速度、收敛性分析和计算复杂性的研究相对较少[1-2]。智能优化算法的应用研究覆盖了计算机、航空、电力电子、电磁、地球物理、生物医学等大部分科技领域。

大量学者对常用优化算法进行改进研究，主要是通过对参数的动态调节，参数的动态调节可分为适应性调节、自适应性调节和非自适应调节三种基本类型。探索与开发的权衡问题源于智能优化算法，主要是针对一些基于种群的进化算法。探索-开发的权衡关系控制着算法的计算代价和收敛质量，在保证算法的计算时间较短的前提下，提高算法的收敛速度和寻优能力。改进算法的主要思想是借助探索-开发的平衡关系来动态调节某些相关参数。为了实现模态复杂问题的高效全局优化，任何优化算法必须兼具“全局探索”和“局部开发”能力，并在二者之间做出适当的权衡，有效的权衡有助于减少计算代价和实现高效的优化。

元启发式群体智能算法是受“集体智慧”启发而提出的高效算法。集体智慧是通过环境中大量相同因子的合作而出现的，例如鱼群、鸟群和蚂蚁群。在自然界中，集体智慧通常被用于解决动物觅食，逃避追捕或生存环境重新定位等问题。

群体智能优化算法主要受两个基本算法的启发：（1）蚁群算法，是受蚂蚁在寻找食物过程中发现路径的行为启发；（2）粒子群优化算法，是受鸟群和鱼群的觅食行为启发。群体智能“算法”或“策略”被认为是自适应策略，并且通常应用于搜索和优化领域。常用的群体智能优化算法有遗传算法（Genetic Algorithm，GA）、萤火虫算法（Glowworm Swarm Optimization，GSO）、蚁群算法（Ant Colony Optimization，ACO）、人工蜂群算法（Artificial Bee Colony algorithm，ABC）和粒子群优化算法（Particle Swarm Optimization，PSO）等。

布谷鸟搜索算法（Cuckoo Search algorithm，CS）是由英国牛津大学的Yang等学者提出的一种元启发式群体智能算法[3-5]。该算法是在长期研究布谷鸟生活习性的基础上提出的，主要利用了布谷鸟卵育寄生和莱维（Lévy）飞行的特性，其优点是具有良好的适应性，参数少，随机搜索路径优并且寻优能力强[6]。

该算法自提出以来得到了广泛的研究。在文献[7]中Yang和Rajabioun等人将CS算法应用于工程优化和多目标优化等实际问题中。文献[8-9]中Walton等人在布谷鸟寻找鸟巢的时候引入了交换信息，但是由于对CS算法中的随机步长进行了改进，导致算法极易陷入局部最优并且全局搜索能力过弱。在文献[10]中Tuba等学者对鸟巢的发现概率Pa和步长进行了动态自适应的调整，提高了算法的收敛性能，但是由于算法完全依赖随机游走，很难保证其搜索精度。在文献[11]中王凡等学者在迭代过程中对鸟窝位置加入高斯扰动，提高了CS算法的收敛速度，但是由于引入了高斯算子，使算法在搜索后期稳定性下降。在文献[12-13]中贺兴时等学者通过分析鸟窝位置的群体状态转移过程，提高了算法的全局搜索能力，但是由于加入Markov链，导致算法在搜索后期收敛速度慢。文献[14-15]通过对种群的再分组，并根据当前不同的搜索阶段对步长进行预先设置，提高了CS算法的搜索性能，但是算法在转换搜索阶段时增加了算法的计算时间并且存在很大的随机性。

从国内外的研究现状可以看出，CS算法还有很大的发展空间。但是CS算法也存在一些缺陷，比如在搜索后期收敛速度慢，全局寻优能力弱，不稳定并且易陷入局部最优，因此本文在深入分析CS算法的基础上，提出了发现概率参数自适应调节的布谷鸟搜索算法（Adaptive Probability of Cuckoo Search algorithm，APCS）。首先设置一个状态判别参数Ps用来切换探索和开发的状态，然后设置一个探索开发平衡参数Peb使探索和开发阶段达到一个互补，最后实现了对发现概率Pa的动态调整。实验结果表明了APCS算法较好地解决了CS算法后期存在的收敛速度慢、不稳定等缺点。

2 CS算法的基本原理

布谷鸟搜索算法是模拟布谷鸟寻窝产卵的行为和莱维飞行特性实现的元启发式群智能优化算法，其中布谷鸟的卵育寄生行为和莱维飞行机制是算法的核心内容。

2.1 布谷鸟的卵育寄生行为

根据生物学家长期观察，布谷鸟的卵育寄生行为的繁殖步骤如下[3-5]：

步骤1布谷鸟会在繁殖期寻找合适的宿主（大多为雀形目鸟类）。

步骤2布谷鸟趁宿主外出时快速产蛋并将自己的蛋放在宿主鸟巢里。

步骤3同时为了提高幼雏的成活率会移走一枚宿主自己的蛋，使得巢中鸟蛋数量不变，在宿主不发现的情况下代为孵化。

步骤4布谷鸟的蛋孵化时间短，通常最先孵出。之后会将同巢的其余鸟蛋推出巢外，以至于得到更高的成活率。

布谷鸟算法示意图如图1。

图1 布谷鸟算法示意图

2.2 布谷鸟的莱维飞行

以法国数学家保罗·莱维（Paul Lévy）命名的莱维飞行机制具有较强的随机性，其步长服从幂律分布。这是一种典型的随机游走过程，布谷鸟搜索算法使用的就是这种飞行机制。当布谷鸟在寻找鸟巢时，其飞行就是一种方向随机的运动，飞行轨迹和前一时刻的飞行轨迹存在一定的偏差。布谷鸟飞行的过程主要以小步长为主，但是偶尔有较大步长的位移，因此布谷鸟不会重复停留在一个地方进行搜索[16-17]。

2.3 CS算法的实现

在CS算法的具体实现中，首先提出以下三个理想化的条件：

（1）布谷鸟每次随机选择一个最优的鸟巢完成寄生；

（2）孵化效果最好的鸟巢将会继续利用；

（3）每次选择寄生的鸟巢数量是不变的，布谷鸟蛋在宿主巢中被发现的概率为Pa。在这种情况下，宿主可以抛出鸟蛋或者放弃当前鸟巢，并建一个新的巢。为了方便研究和计算，这个理想化规则可以近似为被新巢替换（新的随机解决方案）的概率为Pa[18]。

在理想化的条件下，布谷鸟的位置更新公式如下：

式中，t表示随机步长。

上述是布谷鸟卵育寄生行为、莱维飞行机制和布谷鸟搜索算法的具体实现步骤。通过上述内容可以看出，布谷鸟搜索算法具有参数少，对目标问题的初始状态低，随机搜索路径优和寻优能力强等优点。

3 发现概率参数自适应调节的布谷鸟搜索算法

CS算法在计算时比较繁琐，并且因为随机游走的飞行机制导致相关性能会受到影响[19]。于是本文将基本CS算法中的Pa由固定值调整为动态值，固定值将会影响算法的全局搜索（探索）和局部搜索（开发）性能，并且会导致算法收敛性能弱。

为此，本文提出一种发现概率参数自适应调节的布谷鸟改进算法（APCS）。该算法的核心思想是通过协调探索（全局）和开发（局部）的平衡关系，使参数Pa由固定值变成自适应的动态参数，以提高算法的收敛性能和寻优能力。

3.1 状态判别参数

若算法处在探索阶段的时候，局部搜索能力较弱，容易陷入局部最优；若算法处在开发阶段的时候，全局搜索能力较弱[20]。为了实现多目标问题的优化，任何优化算法必须兼具“全局探索”和“局部开发”能力，并在二者之间做出适当的权衡，才能使算法的性能达到最优。APCS算法将利用Pareto最优解，使探索和开发的性能在一定程度上达到最好的状态，在全局搜索能力最优的同时局部搜索能力也保持较优状态。从Pareto最优解集中选择合适的解来作为探索-开发的判别标准[21-22]。

在可行性区域 Xf中，对于 x∈(0,1)，不存在 x′∈Xf，使 得 F(x′)=(f1(x′),f2(x′),…,fk(x′)) 占 优 于 F(x)=(f1(x),f2(x),…,fk(x))，则称 x为Xf上的Pareto最优解。

APCS算法的探索-开发模式如式（3）所示：

式中，Ps主要用于判断当前搜索过程处于探索阶段还是开发阶段；nupdate为更新的鸟巢数量；nall为全部的鸟巢数量。当Ps＜x时，APCS算法处于开发阶段，正在进行局部搜索，此时算法极易陷入局部最优解，导致算法的种群多样性下降，并且收敛性能不佳；当Ps＞x时，APCS算法处于探索阶段，正在进行全局搜索，此时虽然算法保持了种群多样性，但是全局性太强并且易陷入局部最优，使算法的性能不能达到最优状态。

3.2 探索开发平衡参数

探索（Exploration）是指在搜索优化过程中从整个解空间范围内获取目标函数的信息，以便定位全局最优解所在的局部区域。开发（Exploitation）是指在搜索优化过程中对解空间中有希望包含最优解的局部区域进行搜索，以便找到局部最优解甚至全局最优解的搜索策略。通常将探索和开发分别视为全局搜索和局部搜索。

为了协调两个阶段的不足并发挥各阶段的优势，设置参数Peb使探索和开发阶段达到一个互补状态，使APCS算法的收敛性能和寻优能力在兼具“全局探索”和“局部开发”两个阶段下发挥出最好的性能，如式（4）所示：

当Ps较大时，算法处于探索阶段，那么为了提高算法的开发能力，使得Peb为较小值；同理，当Ps较小时，算法处于开发阶段，那么为了提高算法的全局搜索能力，此时需要Peb为较大值。

3.3 发现概率参数

APCS算法将发现概率Pa由一个固定值改成动态值，主要通过对参数Ps和Peb的动态调整而提出用式（5）实现算法参数Pa的自适应调整：

其中，i为当前迭代次数；imax为最大迭代次数；μ是在区间[0,1]内均匀分布随机产生的实数；λ为随机搜索轨迹(1＜λ≤3)；表示当Ps的状态处于探索（开发）阶段时，可以对开发（探索）的性能进行互补，达到一种平衡状态。

当Ps＞x时，虽然计算时间短，但是收敛性能极差，算法的全局搜索性能过强，因此通过对算法进行改善。以全局搜索为主，局部搜索为辅，使探索阶段和开发阶段保持平衡，最后求出使算法收敛性能和寻优能力较好的动态Pa值。当Ps＜x时，算法的局部搜索性能过强，将会极易陷入局部最优。同理通过对算法进行改善，进行局部搜索的同时也在进行全局搜索，最终将会随着迭代的增加而达到全局最优和局部最优的一种平衡。

APCS算法将参数Pa由固定值调整成动态值，实现了自适应的搜索策略，通过迭代次数的增加Pa的值也同时增大，使算法同时兼具探索性和开发性。算法的全局搜索能力往往会随着迭代的进行而减弱，逐渐向局部搜索转变，随着算法的逐渐收敛，多数解将集中到较小的局部区域，最终使算法的各项性能得到提升。

3.4 算法实现

根据上述的条件，APCS算法的具体实现步骤如下：

步骤1定义目标函数 f(x)，并随机生成nall个鸟巢的初始位置xi(i=1,2,…,nall)。

步骤2计算每个鸟巢对应的目标函数，得到最优值，并且利用位置更新公式对其余鸟巢的位置进行更新。

步骤3对比目前函数最优值，并作出相应改变。

步骤4计算参数Ps并与Pareto最优解求出的判别标准x进行对比，若Ps＜x时，处于开发阶段，反之则处于探索阶段。

步骤5计算参数Peb实现对当前阶段性能的互补。

步骤6在位置更新后，用随机数r∈[0,1]和更新后的Pa进行对比，若r＞Pa，则对x(t+1)i进行改变，相反则保持不变。最后保留最好的一组鸟巢位置y(t+1)i。

步骤7若未达到最大迭代次数或最小误差要求，则返回步骤2，否则，继续下一步。

APCS算法的流程图如图2所示。

图2 APCS算法流程图

4 数值仿真与分析

通过仿真实验，测试上述改进算法的性能，并与CS算法的性能进行比较。仿真环境为Windows 7操作系统，Intel处理器，2.10 GHz，内存为4 GB，仿真软件为MATLAB 2014a。

4.1 测试函数

为了充分测试算法的性能和特点，选择8个标准函数进行测试，其中涵盖了单模态和多模态函数，包括Sphere、Shelter、Griewank和Rastrigin等。各基准函数的参数设置如表2所示，CS算法和APCS算法分别进行30次独立实验，鸟巢n=30，最大迭代次数imax为600，发现概率Pa按式（10）进行动态调整，若收敛精度小于1.00E-15视为0。

4.2 实验结果与分析

表2和表3分别记录了APCS算法和CS算法在10维和30维的情况下，通过表1的8种测试函数得到的全局最优值、最差值和平均值的相关实验数据，来对比两种算法的收敛性能和全局寻优能力。

在10维的状态下实验结果如表2所示，最佳适应度值随迭代次数变化的曲线如图3所示。

f1和 f2是一类简单的单峰且可分函数，这类函数在整个搜索空间内只有一个峰值，APCS算法分别比CS算法的最优值提高了43个和28个数量级，并且APCS基本接近了理论最优值。从图3（a）和图3（b）可以看出APCS算法的收敛性能优于CS算法，就稳定性而言，也比CS算法更加稳定；f3也是简单的单峰且可分函数，APCS算法的最优值提高了54个数量级，在该基准函数下，APCS算法具有更强的收敛性；f4和 f6是一类复杂的多峰、可分且高维的函数，并且这两个函数都是典型的多模态非线性全局优化函数，整个搜索空间中存在多个局部最优值，适用于衡量算法的寻优能力，并且使算法的全局寻优能力和局部寻优能力保持平衡。随着迭代次数的增加，APCS算法可以更快地收敛，并且减少了计算代价。在这两个基准函数的测试下，APCS算法的最优值、最差值和平均值均为0，说明该算法的稳定性较好；f5和 f7是一类复杂的多峰、不可分且高维的函数，通过图3（e）和图3（g）可以看出，APCS算法的收敛速度明显优于CS算法，并且从表2的实验数据中可以看出APCS算法的最优值分别提高了50个和65个数量级，因此较CS算法而言，其收敛精度和全局搜索能力得到了较大的改善；f8是一类复杂的多峰、不可分且低维的函数，如图3（h）所示，APCS算法和CS算法皆避免了过早收敛，但是APCS算法较CS算法在寻优能力上更能兼顾全局搜索和局部搜索，使算法不易陷入局部最优又能在较短时间内寻找到局部最优。

在30维的状态下实验结果如表3所示，最佳适应度值随迭代次数变化的曲线如图4所示。

表1 基准测试函数

图3 10维测试结果

表2 10维实验结果分析

表3 30维实验结果分析

图4 30维测试结果

表3列出了在30维情况下的测试结果，通过对比分析全局最优值、最差值和平均值的实验数据验证了APCS算法的各项性能指标优于CS算法。对于 f1、f2和 f3函数，APCS算法的优化程度较CS算法的优化程度虽然不是十分明显，但是收敛速度还是得到了改善，并且通过表3的实验数据可以看出，APCS算法具有更好的全局搜索能力，同时又增强了局部搜索能力；f5函数是高维且多峰函数，不易找到全局最优解，但是通过对概率的自适应调整以后，寻优能力得到了提高，并且APCS算法的收敛速度较快，同时节省了计算时间；f6和 f8在30维的情况下，APCS算法的收敛速度远远高于CS算法的收敛速度，并且迭代次数减少。

通过8个基准函数，对APCS算法和CS算法的各项性能指标在10维和30维的状态下进行了对比分析。实验数据和曲线图表明，APCS算法的收敛速度、寻优能力、稳定性和计算时间都优于CS算法，验证了算法的有效性和改进后的优势。

5 结束语

本文在原始的CS算法基础上，着重研究了发现概率参数自适应调节的布谷鸟改进算法。由于基本的CS算法在搜索后期存在收敛速度慢，寻优能力低，易陷入局部最优并且不稳定等问题，通过对概率的自适应调整加快了算法的收敛速度，提升了算法在兼顾全局搜索和局部搜索时的寻优能力，并且在多峰函数下都不易陷入局部最优。实验结果更一步验证了，APCS算法的收敛性能优并且相对稳定。从本文参考的文献中观察到，CS算法及相关改进算法在医疗、图像处理、经济负荷调度、工程设计和数据聚类等各个领域均有涉及，具有十分广阔的研究前景。与其他算法相比，CS算法的相关参数少，并且易于与其他算法相融合，若能针对上述问题展开深入研究，将会极大地促进该算法的发展，未来将在理论分析方面对CS算法做进一步的研究。