基于种群信息的布谷鸟算法

高淑芝,高 越

(1.沈阳化工大学 装备可靠性研究所， 辽宁 沈阳 110142； 2.沈阳化工大学 信息工程学院， 辽宁 沈阳 110142)

元启发式算法是复杂函数最优值问题的一个重要解决方法.它们的灵感来自自然界中某种生物的某种行为,如启发自鸟群觅食行为的粒子群算法(PSO)[1]、启发自萤火虫闪光行为的萤火虫算法(FA)[2]、启发自蜂群群体行为的人工蜂群算法(ABC)[3]等，这些算法已经在实际问题中被证明了具有良好的性能[4-6].最近，出现了一种布谷鸟算法[7-8]，该算法模拟自然界中布谷鸟的产卵行为进行寻优，并使用模拟果蝇飞行过程的Levy飞行策略进行搜索.该策略采用一系列具有突变序列特征的随机游走，以较高概率在小范围内搜索的同时以较小概率作大步长的随机游动.其优势在于，只要经过迭代的次数足够多，Levy飞行总能找到搜索域内每一个点，即总能找到最优解.布谷鸟算法的优势在于，其控制参数只有2个，即搜索步长α和个体被发现的概率Pa.只要控制其中一个保持不变，就可以很容易观察到另一个参数的值对结果的影响.但是，CS算法在处理多模态函数时的效果还略有不足，虽然已经有许多布谷鸟算法的变种被提出[9-11]，但是仍然存在很多问题.在某个个体陷入局部最优时，它可能无法根据它的近邻跳出局部极值，因为这些个体很可能也具有相似的属性.但是，如果依靠群体中最优个体的位置以及整个种群位置的均值，就可以跳出该极值区域，并进一步找到全局最优.为了证明所提出方法具备以上特点，使用几个常见的目标函数用于测试，通过与其他算法的比较来证明这一方法的有效性.

1 布谷鸟算法

在自然界中，布谷鸟寻找适合自己产卵巢穴的方式是一种随机的方式，为了模拟其产卵的过程，引入以下3条理想化的规则：

(1) 每个布谷鸟的蛋代表一个解，布谷鸟每次只产一个蛋，并随机选择某个鸟巢将蛋放入其中.

(2) 布谷鸟们每一代都会寻找到许多鸟巢产卵，其中一部分鸟巢中放着优质的蛋，这些蛋代表位置较好的解，这些鸟巢将被保存到下一代.

(3) 寄主巢的数量不变，且寄主有一定的概率pa∈(0,1)发现布谷鸟放的蛋.被发现的蛋将被宿主舍弃.

在布谷鸟算法中，鸟巢中的每个蛋都代表一个解，布谷鸟所产的蛋代表新解,采用更好的解或者新解来取代鸟巢中的劣解.该算法可以拓展得更加复杂，一个巢可以有多个卵的情况，即一群解.但是，本文仅考虑最简单的情况，即一个巢中仅包含一个解.这样，不论是蛋、巢还是布谷鸟，都表示为算法中的解.根据以上假设的布谷鸟产卵行为，得出以下布谷鸟算法的解的更新公式：

(1)

(2)

其中:u～N(0,1);v～N(0,1);

φ=[Γ(1+β)·sin(π·β/2)/

(3)

β是一个常数，它的值在区间[1,2]上，一般取1.5;Γ(•)是Gamma函数.

2 基于种群信息的布谷鸟算法

布谷鸟算法单一地使用Levy飞行策略导致整个搜索过程过于依赖随机游走，搜索效率不佳，难以在期望的时间内寻找到最优值，浪费了大量的计算成本，在处理一些有许多局部极小值的多模态函数时，需要很多次迭代才能收敛.Levy飞行策略步长的选择也极为重要，选择的步长较大会导致个体徘徊在最优值附近，难以找到其精确的位置，达到预想的精度就会变得较为困难；选择的步长较小可能会导致难以找到最优解，收敛于局部极小值.这就意味着需要大量的先验性试验确定步长的大小.

整个种群信息的引入给布谷鸟算法提供了跳出局部最优的能力以及局部搜索的能力.引入整个种群个体的平均位置帮助个体跳出局部极值，该搜索策略的个体位置更新公式为

(4)

(5)

其中p代表种群大小.

种群中的个体将根据整个种群和自身的位置生成新个体，从自身与平均位置连线上的另一端跳出局部极值，保证算法的全局探索能力.拥有足够的全局探索能力能够保证算法成功找到全局最优值所在的区域，但是找到的解并不一定能够找到具有足够精度的值，这可能会导致最终的解不满足需要的精度要求.所以还应该有一种搜索策略保证算法的局部搜索能力.一种依靠种群最优位置的搜索策略如等式(6)所示.

(6)

在迭代过程中，这两种策略和Levy飞行策略将具有相同的概率被选择，个体选择搜索策略的方式为

(7)

其中θ是一个[0,1]上服从均匀分布的随机数.每个个体在每一代都将随机选择一种搜索策略，生成新的个体.算法的过程如下：

步骤1：算法初始化，设置种群大小popsize、迭代总次数Gmax、Levy飞行的步长以及布谷鸟被发现的概率.

步骤2：初始化种群，计算每个个体的适应度值，并比较出最优个体.

步骤3：每个个体根据式(7)随机选择策略并生成新一代个体.

步骤4：计算每个个体的适应度值.

步骤5：根据布谷鸟被发现的概率随机舍弃部分个体.

步骤6：计算每个个体的适应度值，并更新最优个体.

步骤7：判断迭代终止条件是否满足，若终止条件未满足，则转步骤3，否则转步骤8.

步骤8：终止循环，输出最优值.

3 实验与分析

3.1 实验函数与参数设置

为了证明基于种群信息的布谷鸟算法具有更强的全局探索能力和局部搜索能力，将其与基本布谷鸟算法和粒子群算法在6种常见的基准函数上进行仿真，这6种函数以及他们的参数和搜索域如下：

Ackley函数：

Bohachevsky 函数：

0.4cos(4πx2)+0.7,-100≤x≤100；

Schewefel 函数：

Griewank 函数：

|xi|≤600;

Rastrigin 函数：

xi∈[-5.12,5.12]；

Weierstrass 函数：

a=0.5,b=3,kmax=20,x∈[-0.5,0.5]D.

在这些函数中，Bohachevsky函数是二维的，其他函数都在十维上进行仿真，所有函数的真实最小值都是0.布谷鸟被发现的概率被设置为0.25，粒子群算法的权重设置为0.7，学习因子c1和c2的值都是1.4.这些参数来源于原始布谷鸟算法和粒子群算法作者们的仿真实验，仿真过程见文献[1-2].在每个函数上的仿真都将进行30次，结果取平均值.

3.2 实验结果与分析

基于种群信息的布谷鸟算法和CS算法及PSO算法的比较结果如图1所示.

图1 基于种群信息的布谷鸟算法与其他两种算法在6种基准函数上的比较

从图1中可以看出:PBCS在6种测试函数中都体现出了绝对优势.横坐标迭代次数反映了算法的运行时间.他们具有相同的迭代次数，每一次迭代中各个函数的评估次数决定3种算法的总评估次数.虽然每个算法的个体更新公式不同，但是每一代的每一个个体在使用复杂的适应度函数进行评估所占用的计算量远远超过个体更新时的计算量，所以，因算法个体更新公式不同而产生的时间差可以忽略不计.纵坐标代表适应度值，对数坐标轴可以很清晰地比较算法的性能.

Ackley函数在全局最优值附近有许多局部极小值，这使得算法不容易寻找到真正的全局最小值.从图1中可以看出：PSO和CS算法在搜索时困于1附近，难以找到真正的全局最小值所在的位置，而PBCS则成功地找到了全局最小值；此外，在Weierstrass函数上，它们也面临着相似的情况，而PBCS成功地找到了全局最优解.在这种情况下，即使增加迭代次数也不能使PSO和CS找到理想的值，因为它们并没有发现全局最优值所在的区域.

在Schwefel函数上，3种算法都成功地找到了全局最优值所在区域，但在相同的时间内，PBCS找到的解更加精确.Rastrigin函数在整个搜索域内都具有许多局部极小值，是一个非常“崎岖”的函数，非常考验算法的全局搜索能力.PSO和CS算法的搜索陷于局部极小值中，PBCS虽然可以找到最优值所在区域，但是精确度并不高，这种情况可以用增加迭代次数的方式解决.

在Bohachevsky函数、Griewank 函数上，PSO和PBCS算法的曲线在迭代到一定次数时“消失”了.这是因为图像的纵坐标轴是对数坐标轴，它们在算法迭代结束前找到了真正的最小值0，而对数坐标轴不能显示出0.虽然它们都能找到真正的最小值，但是PBCS的速度显然更快一些.

通过以上6个测试函数的对比，PBCS算法的全局探索能力和局部寻优能力都明显强于其他两种算法.

4 结 论

基于种群信息的布谷鸟算法中，每个个体参考整个种群的均值和最优值生成下一代个体，能成功地跳出局部极值，也可以寻找到具有足够精度的值，性能超越了未改进前的布谷鸟算法和粒子群算法.在6种常见的基准函数上，实验证明了PBCS算法的全局探索性能和局部搜索性能.实验结果表明：PBCS的性能明显优于CS算法和PSO算法.本文提出的种群信息策略以及依赖全局最优位置的局部搜索策略在一定程度上弥补了原有Levy飞行策略收敛速度慢和容易陷入局部极值的不足.