cs算法及改进算法

1、CS算法及改进算法2.1 cs算法说明2.1.1 算法背景2009年，英国剑桥大学的Xin-she Yang和C. V. Raman工程学院的Deb共 同开创了一种新的元启发算法，Cuckoo Search （CS）算法，该算法具有搜索速 度快，选择路径优，包含参数少等优点。目前，该算法已经被广泛运用于网络 架构，资源优化，多目标优化。自然界中布谷鸟的繁殖行为很特殊，和其他的鸟类不同，它是通过将自己 的鸟蛋下到其他鸟的鸟窝中让其他的鸟进行孵化的。有两种情况鸟蛋不能被成 功孵化，一种是其他鸟发现不是自己的蛋，于是放弃自己的鸟巢选择新的鸟 巢，另一种是其他鸟将布谷鸟的蛋扔出鸟窝，所以这种孵化方式是

2、有风险的， 所以这对布谷鸟的繁殖来说也是一种挑战。因此对布谷鸟来说最好的办法就是 选择刚刚孵化完小鸟的鸟巢下蛋，这样有可能不被其他鸟发现从而可以被和其 他鸟的鸟蛋一起孵化，这样就可以增加孵化的概率。并且，布谷鸟的鸟蛋还有 一个特性，就是它的孵化时间比较快，通常它都会比其他鸟提前孵化出来，而 且它的学习能力还很强，能够模仿其他鸟的叫声来骗取母鸟的哺育，并且它们 还会将其他未孵化的鸟蛋扔到鸟巢外面，无疑乂为它们的成长创造了有利条 件。Levy飞行是一种概率飞行模型，对于很多突发事件都会符合Levy飞行模 型，在大自然中也是，自然界中的许多动物和昆虫的飞行行为都被证明是符合 Levy飞行特性的，如果

3、动物在空中飞行时可能突然转一个弯继续飞行，这样 一个过程就符合levy飞行模式。2.1.2 算法介绍受布谷鸟的繁殖行为和levy飞行特性的启发，Yang等人提出了布谷鸟搜 索（cs）算法，并且做出了以下假定：（1）布谷鸟每次生产都只下一个蛋，并且孵化这个鸟蛋的鸟窝是随机选 择的；（2）保留到下一代的是最好的鸟蛋；（3）鸟窝的规模n是固定的，我们将宿主鸟发现蛋不是自己的概率设定 为2啊。CS算法的搜索路径与普通算法的路径不同，该算法使用的是随机性较强的Levy飞行的搜索方式，步长的大小s设计为(1)(2)(3)u s = 印其中u,v都服从正态分布，即N(O,b：),uN(O,cr：)这里_F(

4、l + /7)sin(羽/2)°、'= r(l + /?)/2/7x21)/'而方向的取法是服从均匀分布的。cs算法的具体搜索方式为，第t代的第i只布谷鸟，通过Levy飞行，产 生下一代的解玉，有引+i)=用 + a LevyA)(4 )其中是点对点乘法，心外义就是一个步长大小服从Levy分布的随机游走, 可以表示为Levy-u = t'(l<A<3)(5)此处，具体的步长大小是利用Mantegna法则来实现的。另外，。是步长控制量，主要用来控制方向和步长大小的a = 0()(6)10这里，L是优化问题的搜索空间大小。这样，新解的产生是经过最优解的

5、Levy飞行机制而逐渐达到最优，同时这 也加快了算法的局部搜索能力。I大I此偏离较远的位置随机产生的那些新解是远 离当前最优解的，这样就能够保证系统没有陷入局部最优。以上就是CS算法的假设和理论部分，接下来我们写出它的具体操作步骤：2.1.3 算法步骤(1)初始化：随机产生N个鸟窝位置X0 = (.v；，KA,x：.),用测试函数检测 这些问题的解，挑选最优的鸟窝位置，并保留到下一代；(2)搜索：通过位置更新公式，搜索下一代的鸟窝位置，我们会得到新的 鸟窝位置，用它们进行测试，和上一代相应的鸟窝位置进行比较，将测试值更 好的位置保留下来：(3)选择；我们定义一个随机数r0, 1,和发现概率Pa

6、 =0.25进行 比较，如果r几，则随机改变E"的值，相反就保持不变，然后测试改变 后的鸟窝位置，比较之上一代的位置，最终选择更优的位置X, =(X；,ZA ,匕),并挑出测试值最好的鸟窝位置pb；(4)判断：判断/(p)是否满足迭代终止的条件，如果满足，那么p就 是我们要找的最优解gb,如果不满足，那么我们保留p»到下一代，然后回到 第(2)步继续迭代。由上面步骤我们可以得到，cs算法应用的是优先保留策略，因为引入了 Levy飞行搜索方式，可以很好地避免算法陷入局部最优。这样结合了H部最优 解和全局最优解，增加了解的多样性。在布谷鸟算法中，仅仅包含了三个参数，我们这里的参

7、数选择与搜索空间 有关，不同的搜索空间和不同的步长对参数的要求都是不一样的。因此，cs算 法具有参数少，全H搜索占优的特点。2.2对cs算法的改进在多篇文章中对算法都进行了改进，例如在文献【7】中对算法增加了二进制 编码，这种方法应用到很多实际问题中都有了明显的效果，对于算法的稳定性和 高效性改进很多。还有文献8中运用了几种类似于变异的操作，在生成新的 鸟窝位置同时随机的对他们再进行不同的变化，再次增加了随机多样性，实验证 明这样可以提高算法的有效性。在文献【9】中，对算法增加了差分变化，这样 通过差分变化我们可以做到提前进行最优解的选择，通过对比选择更合适的位置, 避免在以后的运算中花费大量

8、的时间，也避免了算法陷入局部最优，提高了算法 的收敛速度。在文献【11】中，对算法增加了扰动因子，在计算最优解的同时随 机进行参数的变换，使得计算避免陷入H部最优，对于分散的情况有了更好的解 决。最后我们在文献12中介绍了一种小规模多种群的cs算法，它通过将整 个解空间划分成多个区域，分别在每个区域进行cs算法，得到每个区域的最优 解，然后将这些最优解的集合转换为整个区域的初始解，这样可以在计算初期减 少计算的复杂性，提高算法的效率。这些文章对cs算法的改进都在很大程度上 优化了此算法，在以后的研究中可以进一步提高算法的效率和可行性。这篇文章 的计算参照上面的每一种方法都可以很好地计算出所要的结果。2. 3本章小结本章主要介绍了 CS算法的产生背景以及C