cs算法及改进算法

cs算法及改进算法2.1 cs算法说明2.1.1 算法背景2009年，英国剑桥大学的Xin-she Yang和C.V.Raman工程学院的Deb共同开创了一种新的元启发算法，Cuckoo Search（CS）算法，该算法具有搜索速度快，选择路径优，包含参数少等优点。目前，该算法已经被广泛运用于网络架构，资源优化，多目标优化。自然界中布谷鸟的繁殖行为很特殊，和其他的鸟类不同，它是通过将自己的鸟蛋下到其他鸟的鸟窝中让其他的鸟进行孵化的。有两种情况鸟蛋不能被成功孵化，一种是其他鸟发现不是自己的蛋，于是放弃自己的鸟巢选择新的鸟巢，另一种是其他鸟将布谷鸟的蛋扔出鸟窝，所以这种孵化方式是有风险的，所以这对布谷鸟的繁殖来说也是一种挑战。因此对布谷鸟来说最好的办法就是选择刚刚孵化完小鸟的鸟巢下蛋，这样有可能不被其他鸟发现从而可以被和其他鸟的鸟蛋一起孵化，这样就可以增加孵化的概率。并且，布谷鸟的鸟蛋还有一个特性，就是它的孵化时间比较快，通常它都会比其他鸟提前孵化出来，而且它的学习能力还很强，能够模仿其他鸟的叫声来骗取母鸟的哺育，并且它们还会将其他未孵化的鸟蛋扔到鸟巢外面，无疑又为它们的成长创造了有利条件。Levy飞行是一种概率飞行模型，对于很多突发事件都会符合Levy飞行模型，在大自然中也是，自然界中的许多动物和昆虫的飞行行为都被证明是符合Levy飞行特性的 ，如果动物在空中飞行时可能突然转一个弯继续飞行，这样一个过程就符合levy飞行模式 。2.1.2 算法介绍受布谷鸟的繁殖行为和levy飞行特性的启发，Yang等人提出了布谷鸟搜索(cs)算法，并且做出了以下假定：（1） 布谷鸟每次生产都只下一个蛋，并且孵化这个鸟蛋的鸟窝是随机选择的；（2） 保留到下一代的是最好的鸟蛋；（3） 鸟窝的规模 n 是固定的，我们将宿主鸟发现蛋不是自己的概率设定为。CS 算法的搜索路径与普通算法的路径不同，该算法使用的是随机性较强的 Levy 飞行的搜索方式，步长的大小s设计为 （1）其中u,v都服从正态分布，即 （2）这里 （3）而方向的取法是服从均匀分布的。 cs算法的具体搜索方式为，第t代的第i只布谷鸟，通过Levy飞行，产生下一代的解，有 （4）其中是点对点乘法，就是一个步长大小服从Levy分布的随机游走，可以表示为 （5）此处，具体的步长大小是利用Mantegna法则来实现的。另外，是步长控制量，主要用来控制方向和步长大小的 （6）这里，L是优化问题的搜索空间大小。 这样，新解的产生是经过最优解的Levy飞行机制而逐渐达到最优，同时这也加快了算法的局部搜索能力。因此偏离较远的位置随机产生的那些新解是远离当前最优解的，这样就能够保证系统没有陷入局部最优。 以上就是CS算法的假设和理论部分，接下来我们写出它的具体操作步骤：2.1.3 算法步骤(1) 初始化：随机产生N 个鸟窝位置，用测试函数检测这些问题的解，挑选最优的鸟窝位置，并保留到下一代；(2) 搜索：通过位置更新公式 ，搜索下一代的鸟窝位置，我们会得到新的鸟窝位置，用它们进行测试，和上一代相应的鸟窝位置进行比较，将测试值更好的位置保留下来；(3) 选择：我们定义一个随机数 r0,1，和发现概率进行比较，如果r ，则随机改变的值，相反就保持不变，然后测试改变后的鸟窝位置，比较之上一代的位置，最终选择更优的位置，并挑出测试值最好的鸟窝位置p；(4) 判断：判断是否满足迭代终止的条件，如果满足，那么p就是我们要找的最优解gb，如果不满足，那么我们保留p到下一代，然后回到第（2）步继续迭代。由上面步骤我们可以得到，cs算法应用的是优先保留策略，因为引入了Levy飞行搜索方式，可以很好地避免算法陷入局部最优。这样结合了局部最优解和全局最优解，增加了解的多样性。在布谷鸟算法中，仅仅包含了三个参数，我们这里的参数选择与搜索空间有关，不同的搜索空间和不同的步长对参数的要求都是不一样的。因此，cs算法具有参数少，全局搜索占优的特点。2.2 对cs算法的改进 在多篇文章中对算法都进行了改进，例如在文献【7】中对算法增加了二进制编码，这种方法应用到很多实际问题中都有了明显的效果，对于算法的稳定性和高效性改进很多。还有文献【8】中运用了几种类似于变异的操作，在生成新的鸟窝位置同时随机的对他们再进行不同的变化，再次增加了随机多样性，实验证明这样可以提高算法的有效性。在文献【9】中，对算法增加了差分变化，这样通过差分变化我们可以做到提前进行最优解的选择，通过对比选择更合适的位置，避免在以后的运算中花费大量的时间，也避免了算法陷入局部最优，提高了算法的收敛速度。在文献【11】中，对算法增加了扰动因子，在计算最优解的同时随机进行参数的变换，使得计算避免陷入局部最优，对于分散的情况有了更好的解决。最后我们在文献【12】中介绍了一种小规模多种群的cs算法，它通过将整个解空间划分成多个区域，分别在每个区域进行cs算法，得到每个区域的最优解，然后将这些最优解的集合转换为整个区域的初始解，这样可以在计算初期减少计算的复杂性，提高算法的效率。这些文章对cs算法的改进都在很大程度上优化了此算法，在以后的研究中可以进一步提高算法的效率和可行性。这篇文章的计算参照上面的每一种方法都可以很好地计算出所要的结果。2.3 本章小结 本章主要介绍了cs算法的产生背景以及cs算法的主要