布谷鸟搜索算法的优化研究

布谷鸟搜索算法的优化研究

1改进的cs算法随着现代科学技术的快速发展，人们需要解决更复杂的优化问题。为了寻找解决这些优化问题的有效方法,自20世纪后期始,模拟自然界生物行为的各种元启发式算法不断涌现,如模拟生物遗传和进化过程的遗传算法、模拟蚁群觅食行为的蚁群算法、模拟鸟类群体运动行为的粒子群优化算法等。近年来,一些模拟生物行为的更高效的新型元启发式算法还在不断脱颖而出,如在2009年,剑桥大学的YangXS和DebS模拟布谷鸟寻窝产卵行为,创立了布谷鸟搜索算法(CuckooSearch,CS)。CS算法具有控制参数少、简单易实现、搜索路径优、全局搜索寻优能力强等优点,在许多优化问题上较著名的遗传算法和粒子群优化算法更具潜力和高效,已成为元启发式算法领域的1个新亮点。文献对CS算法改进后得到的二进制布谷鸟搜索算法(BCS),用于求解离散型NP完全问题,其性能也好于遗传算法、蚁群算法和粒子群优化算法。但CS算法同其他元启发式算法一样,也存在局部搜索能力相对较弱,导致后期搜索速度慢、寻优精度不高等缺点。为了改进CS算法的缺点,文献将局部搜索能力很强的共轭梯度法引入CS算法中,能大幅度提高CS算法的收敛速度,但它在寻优过程要用到函数的梯度信息,这对于大型复杂的工程优化问题,若梯度的计算量大,则该算法就体现不出优势。文献提出步长控制因子α随着迭代次数与最大迭代次数的比值而变的自适应方法,文献将1种随着迭代次数与最大迭代次数的比值而变的自适应权重因子引入CS算法中,虽然这2种改进的CS算法都能够提高CS算法的性能,但是均未涉及到布谷鸟搜索路径步长的参数β和布谷鸟蛋被宿主鸟发现的概率pa的自适应调整。本文拟将影响CS算法中布谷鸟搜索路径步长的参数β和布谷鸟蛋被宿主鸟发现(淘汰)的概率pa这2个重要参数由固定值改为随搜索过程自适应变化的动态参数,并对越界的布谷鸟提出1种新的处理方法,将这种改进的CS算法称为自适应布谷鸟搜索算法(AdaptiveCuckooSearch,ACS),ACS算法试图在保留CS算法强大的全局搜索寻优能力的同时,在不需要利用函数的梯度信息的前提下,能较大幅度地提高算法的局部搜索能力和收敛速度。2cs算法及其机制的分析2.1布谷鸟随机线模式搜索鸟窝在自然界中,布谷鸟寻找适合自己产蛋的鸟窝位置是随机的或是类似随机的方式,为了模拟布谷鸟寻窝的方式,首先,需要设定以下3个理想的状态:(1)布谷鸟1次只产1个蛋,并随机选择鸟窝来孵化它;(2)在随机选择的1组鸟窝中,最好的鸟窝将会被保留到下1代;(3)可利用的鸟窝数量n是固定的,1个鸟窝的主人能发现1个外来鸟蛋的概率pa∈,在这种情况下,宿主鸟可能会将外来的鸟蛋移除或者放弃现有的鸟窝,另觅地方再重新建1个新的鸟窝。在以上3个理想状态的基础上,布谷鸟按莱维飞行(Lévyflights)模式搜索鸟窝的路径和位置更新公式如下:式中和分别表示第i(i=1,2,...,n)个鸟窝在第和第(k+1)代的位置向量(Xi=xi1,xi2,…;xij…xid,d为每个鸟窝的维数,j为鸟窝的任意第j维);为点对点乘法;α表示步长控制因子;Lévy(λ)为Lévy随机搜索路径。Lévy飞行的随机搜索路径与时间t的关系服从Lévy分布,YangXS将Lévy分布函数经过简化和傅里叶变换后得到其幂次形式的概率密度函数:通过位置更新后,用随机数rand∈与pa对比,在CS算法中取pa=0.25。若rand>pa,则对进行随机改变,即布谷鸟蛋被宿主鸟发现,因而鸟窝被新的巢穴取代,反之则不变,最后保留测试值较好的1组鸟窝位置,此时仍记为。在实际的优化问题中,鸟窝的位置代表所有变量的有效取值空间,而鸟窝的适应度代表变量取不同值所对应的目标函数。具体的CS算法流程和步骤详见文献。2.2cs算法的理论分析CS算法主要基于布谷鸟的巢寄生繁殖机理和莱维飞行搜索原理2个方面。2.2.1巢寄生虫繁殖机理布谷鸟是典型的巢寄生鸟类,自己从不筑巢而是将自己的蛋产于蛋的颜色和大小、孵化期和育雏期等与已相似,雏鸟食性也基本相同的鸟类如黄莺、云雀等的宿主鸟巢窝里,让这些鸟替自己精心孵化。而且,它每飞到1个巢窝里,只生产1个鸟蛋。因宿主鸟发现寄生的布谷鸟蛋,就会将其推出鸟窝之外或者在别的地方新建1个鸟窝繁殖后代,故布谷鸟多在宿主鸟开始孵蛋之前,乘宿主鸟离巢外出时快速寄生产蛋。一旦巢寄生的布谷鸟蛋被保留在宿主鸟窝里,宿主鸟就会同时孵化自己的蛋和布谷鸟的蛋,往往布谷鸟蛋会比宿主鸟蛋先被孵出,且巢寄生的雏鸟一旦孵出,它有将宿主鸟的鸟蛋推出巢外的习性,从而独享宿主鸟的抚育。YangXS和DebS在2009年创立CS算法时,对布谷鸟的巢寄生繁殖机理做了深入的研究后,将其抽象为2.1节中提到的3个理想状态的假设和式(1)。其中第1个假设可简单陈述为1个鸟窝里的每个蛋代表1个解决方案,1个布谷鸟蛋则代表1种新的解决方案,目的是利用新的以及潜在的更好的解决方案,来取代1个在鸟窝里的不那么好的解决方案。目前CS算法只采用每个鸟窝只有1个布谷鸟蛋的最简单的方法,至于每个鸟窝有多个布谷鸟蛋的更复杂的方法,有待今后深入研究。第2个假设可促使布谷鸟在搜索过程向优秀的解逼近,以提高算法的收敛速度,但该假设没有涉及到可调整的算法参数。第3个假设可以近似地认为:n个鸟窝被随机产生的新巢替换(新的随机解决方案)的概率为pa。在CS算法中,取概率pa为固定值0.25,用随机数rand∈是否大于pa来决定是否对鸟窝的位置进行随机改变(更新),若rand>pa则进行随机改变,否则不变。据此不难推出,当pa值愈小时,被淘汰(更新)的鸟窝亦愈多,全局随机搜索的多样性就愈强,局部搜索的收敛性则愈弱,反之亦然。对于任何元启发式算法,全局高效的随机搜索和局部精细搜索战略之间保持好的平衡会使算法更有效,在CS算法中,一旦n固定,主要是pa控制了全局随机搜索和局部搜索之间的平衡,故在CS算法中,将pa取为固定值0.25并不是好的解决方法。如何使pa随搜索过程自适应变化,将是本文研究的重点之2.2.2布谷鸟寻窝优化算法20世纪30年代,法国数学家莱维Lévy提出了Lévy分布,认为Lévy飞行的随机搜索路径与时间的关系服从Lévy分布。之后很多学者对其进行了研究,并用于解释自然界的随机现象,如布朗运动、随机行走等。自20世纪90年代起,自然界的许多动物和昆虫如信天翁、蜜蜂和果蝇的觅食轨迹被证明符合莱维飞行(Lévyflights)模式,并当目标位置随机且稀疏分布时,对于M个相互独立的探索者来说,莱维飞行是最理想的搜索策略。莱维飞行属于随机行走(randomwalk)的1种,行走的步长满足1个重尾(heavy-tailed)的稳定分布,在这种形式的行走中,短距离的探索与偶尔较长距离的行走相间。2006年,ShlesingerMF的研究表明,在智能优化算法中采用莱维飞行,能扩大搜索范围、增加种群多样性,更容易跳出局部最优点。YangXS和DebS在2009年创立CS算法时,认为布谷鸟寻窝过程是按莱维飞行搜索路径进行的,这体现在他们导出的式(1)中。式(1)本质上是随机行走方程,一般情况下,1个随机行走是1个马尔可夫链,其未来位置取决于当前位置(式(1)中的第1项)和转移概率(式(1)中的第2项αLévy(λ))。转移概率项中的Lévy(λ)为莱维飞行随机搜索路径,它与时间t的关系服从Lévy分布,可用YangXS导出的式(2)表达。式(2)是1个带有重尾的概率分布,虽然能够从本质上描述布谷鸟按莱维飞行随机行走(搜索)寻窝过程,但尚未能进一步用更简洁且易编程的数学语言描述这一分布,以实现CS算法,故YangXS和DebS在实现CS算法时是采用MantegnaRN于1992年提出的模拟莱维飞行随机搜索路径的公式,即式(3)中s即为式(1)中的Lévy飞行随机搜索路径Lévy(λ):参数β同式(2)中λ的关系为λ=1+β,β∈(0,2],在CS算法中取β=1.5;参数μ、v为正态分布随机数,服从式(4)所示的正态分布;式(4)中的正态分布的标准差σμ、σv根据式(5)计算由式(3)～式(5)可知,s取决于2个正态分布随机数μ和v,μ和v可大可小、可正可负,故布谷鸟每次寻窝过程的莱维飞行随机搜索路径s即Lévy(λ)的步长和方向都是高度随机改变的,很容易从1个区域跃入另外1个区域,使CS算法的全局多样性即全局搜索寻优能力很强,这特别有利于在算法前期随机搜索锁定最优值所在的区域,但若在算法后期随机性太强,则不利于局部区域的精细搜索,造成收敛速度和收敛精度降低。若要使CS算法更高效,则需在全局性和收敛性两方面能够兼顾、达到好的平衡。除μ和v2个正态分布随机数控制了莱维飞行随机搜索路径的步长和方向外,参数β亦会影响搜索步长,但在CS算法中将β取为固定值1.5,这不是很好的解决方法。如何使β随搜索过程自适应变化,以使CS算法在全局性和收敛性两方面达到好的平衡,从而进一步提高CS算法的效率,这将是本文研究的重点之二。另外,在CS算法的运行过程中,所有鸟窝的位置均根据式(1)来进行更新,但由于实际约束条件的限制,鸟窝只能安置在界内即变量的定义域内,而由式(1)计算得到的新的鸟窝位置并不能均保证都在界内。在CS算法中,统一将越界的鸟窝设定为边界上的值,再根据这个值进行下1代的更新,这种处理越界鸟窝的方式,可能会失去这些鸟窝位置变化的活力,使算法的收敛速度降低。如何更好地处理越界鸟窝,将是本文研究的重点之三。3acs算法3.1模型3:个人局部搜索能力根据2.2.1节的分析可知,将参数pa(即鸟窝被淘汰或更新的概率)取为固定值0.25不利于保持CS算法的全局随机搜索和局部搜索之间的战略平衡,这将影响算法的性能。为使CS算法更高效,ACS算法提出使pa随算法进程动态变化的自适应策略:在算法前期取相对小的pa值,被更新的鸟窝数相对多,使算法保持很强的全局搜索能力,同时兼顾局部搜索能力;在算法后期取相对大的pa值,被更新的鸟窝数相对少,使算法保持很强的局部搜索能力,同时兼顾全局搜索能力;在算法由前期到后期的进化过程,使pa随迭代次数的增加而增大。为实现pa的自适应策略,进行了大量的仿真实验,结果表明:当pa<0.1时,被更新的鸟窝数太多,全局多样性太强,收敛性很弱;当pa>0.75时,被更新的鸟窝数太少,收敛性太强,全局多样性很弱,易陷入局部最优,故pa在[0.1,0.75]之间随迭代次数的增加而逐渐增大效果较好。根据仿真实验结果,提出用式(6)实现参数pa的自适应策略:式中k为算法当前迭代次数,kmax为人为设定的最大迭代次数。根据式(6),当k=0时,pa=0.1,当k=kmax时,pa=0.73。实际上,算法在寻优过程中k是从1开始逐渐增大直至收敛为止,一般收敛时k<kmax,最大当k=kmax时,若算法仍未找到最优值也终止计算。因此,由式(6)计算的pa在(0.1,0.73]的区间内随迭代次数的增加而增大,完全实现了本文提出的使pa随算法进程(k/kmax)的增加而由小到大动态变化的自适应策略,这将使改进后的CS算法即ACS算法能够在全局随机搜索能力和局部搜索能力之间保持好的平衡。换言之,ACS算法通过pa的自适应动态变化,实现了在算法前期以全局搜索为主、局部搜索为辅,以期能在全局范围内快速锁定最优值可能存在的若干区域;而后随算法进程全局搜索逐渐减弱,局部搜索逐渐加强,至算法后期以局部搜索为主、全局搜索为辅,以期能提高收敛的速度和精度,又不至于陷入局部最优,从而从整体上提升算法的性能。3.2模型2:随机步长s根据2.2.2节的初步分析可知,参数β的取值将影响步长s的大小,而CS算法将其取为固定值1.5,不利于使算法在全局性和收敛性两方面保持好的平衡,这将影响算法的性能。为了进一步研究参数β究竟如何影响步长s,对0<β≤2范围内的β和步长s的关系进行了大量的仿真实验,结果表明:在0<β≤0.8的范围内,随参数β的逐渐增大,根据式(3)计算的步长s的波动范围从1个极大的范围(如β取0.1时,步长s在-10～10范围内波动)逐渐减小到β取0.8时的-35～35范围,显然当β∈(0,0.8)时,步长s的取值以及波动范围太大,全局搜索寻优的能力太强,局部搜索精度太低,收敛性太差;在0.8≤β≤1.8的范围内,随参数β的逐渐增大,步长s的波动范围从-35～35范围继续逐渐减小到β取1.8时的-3～3范围,图1列举了在0.8<β≤1.8的范围内4个β值下,步长s的波动情况,图2为β取1.8时步长s波动情况的放大图。显然在0.8≤β≤1.8范围内,步长s的波动范围相对较合理;在1.8≤β≤2的范围内,随参数β的逐渐增大,步长s的值及其波动范围又逐渐增大,算法后期的随机性又逐渐增强,这不利于算法后期局部区域的精细搜索,会造成收敛速度和收敛精度降低。综上分析,参数β在[0.8,1.8]之间取值较好。为使CS算法更高效,ACS算法提出使参数β随算法进程动态变化的自适应策略:从算法第1代k=1开始,β取0.8左右的值并随算法进程(k/kmax)的增加而随机波动增大,直至收敛时(k/kmax接近1)β取1.8左右的值。这种β自适应策略,使β在算法的前期取相对较小的值,相应的步长s的取值较大且波动范围也较大,使算法保持很强的全局搜索寻优能力,同时兼顾一定的局部精细搜索能力即收敛能力;随着算法进程(k/kmax)的增加,β呈随机波动增大,相应的步长s则呈随机波动减小;至算法的后期,使β的值逐渐波动增大尽可能的接近1.8,相应的步长s的取值较小且波动范围也较小,使算法保持很强的局部精细搜索能力即收敛能力,同时兼顾全局搜索寻优能力。若能实现上述参数β随算法进程动态变化的自适应策略,有望使算法在全局性和收敛性两方面保持好的平衡,从而较大幅度提升算法的性能。根据上述分析,提出用式(7)实现参数β的自适应策略:式中randn(0.8,0.3)表示平均值为0.8,方差为0.3的正态分布随机数;radn(0,0.05)表示平均值为0,方差为0.05的正态分布随机数;k与kmax的符号意义与2.1节中所述的相同。式(7)由[randn0.8,0.3)+0.3+k/kmax]和[1.8+randn(0,0.05)]2项构成,且在算法的进程中取2项中小的1项。前项中的随机数randn(0.8,0.3)和0.3这两者相加已由仿真实验证明其值是随机波动的且通常都略大于0.8,而k/kmax的值随算法进程(k由1逐渐增大至收敛时接近kmax)在区间(0,1)的范围内由小到大逐渐增大,故前项[randn(0.8,0.3)+0.3+k/kmax]的值随算法进程从大约0.8逐渐随机波动增大至大约1.8,若β取前项的值,也即β做同样的变化,但在算法后期,因k/kmax接近1,前项的值有可能大于1.8较多,为避免β大于1.8过多,β取2项中小的1项,因后项[1.8+randn(0,0.05)]是在1.8附近很小的范围随机波动的数,故这样取β值可保证在算法后期其值即使大于1.8也不会大太多。这样就实现了参数β随算法进程(k/kmax)的增加而随机波动从约0.8增大至约1.8的自适应策略,相应的步长s则从大到小随机波动减小,在算法进化过程中较好地保持了全局性和收敛性之间的平衡,因而能够较大幅度地提升算法的性能。3.3边界上的布谷鸟窝在CS算法中,统一将越界鸟窝设定为边界上的值,这在一定程度上丧失了这些鸟窝位置变化的活力,使算法的收敛速度降低。该怎么样处理越界鸟窝比较好呢?联想到在残酷的自然界,有些种群的动物为了生存选择了群居生活的方式,它们共同觅食、防御外敌并繁育后代。每个群居体都有自己的首领,都会圈定自己的生活领域,当群居体中的某个个体偶尔越界误入其它群居体的领域时,可能会遭受攻击。受攻击的越界个体一般会产生2种情况:一种是受攻击后没有受伤或者是受轻伤的个体,会选择折返回自己的领域寻找首领并在首领所在区域附近生活,这会给它带来安全感,减少其今后再越界的概率;另一种是受攻击后受重伤的个体,一时无法折返回自己的领域内,只好选择在领域的边界附近养伤和生活。受动物群居生活的上述行为的启发,将CS算法中当前代(第k代)的最优布谷鸟个体视为布谷鸟群体的首领,将待优化求解的函数的定义域视为布谷鸟群体的生活领域,将布谷鸟个体超出定义域寻找到的鸟窝称为越界鸟窝,提出按随机数r∈的不同分2种情况处理越界鸟窝的新方法:一种是当0≤r≤0.9时,即越界的布谷鸟有90%的概率放弃越界鸟窝,选择折返回定义域内当前代(第k代)最优鸟窝(首领的位置)附近的区域随机建立1个新鸟窝开始生活(相当于前述受攻击的越界个体的情况一);另一种是当0.9<r≤1时,即越界的布谷鸟有10%的概率放弃越界鸟窝,选择折返回定义域的边界上重新建立鸟窝(相当于前述的情况二)。这种处理越界鸟窝的新方法可由式(8)实现。式中为第k代越界的布谷鸟i折返回定义域内或边界上新建的鸟窝;为第k代的最优鸟窝;randn(0,0.001)表示平均值为0,方差为0.001的正态分布随机数;为第k代当0.9<r≤1时,越界的布谷鸟i折返回边界上新建的鸟窝。根据式(8),越界的布谷鸟中有90%的概率选择折返回自己的领域内,在第k代最优鸟窝附近的区域(该区域的范围由正态分布随机数randn(0,0.001)随机确定)内随机建立1个鸟窝,这相当于越界的布谷鸟向当前代最优布谷鸟的一次学习过程,不仅新建的鸟窝位置靠近最优鸟窝,增强了安全感,减少了今后再次越界的可能性;而且新鸟窝与安置在边界上的鸟窝相比,拥有更优秀的位置信息,有利于算法沿更高效的寻优途径进化,可提高算法的寻优能力和收敛速度。根据式(8),另外还有约10%的越界布谷鸟与CS算法一样,选择在自己领域的边界上建立新鸟窝,这样处理的目的是为了避免所有越界的布谷鸟都向最优鸟窝靠拢,以保持种群的多样性,降低算法陷入局部最优的可能性。综上所述,与CS算法统一将全部越界鸟窝设定在边界上的值的僵化处理方法相比,式(8)所提出的处理越界鸟窝的新方法,能使这些鸟窝的位置变化更具活力,有利于提升算法的性能。4模拟实验4.1测试函数的选取为了测试ACS算法的性能,选用如表1所示的8个各具典型特点的标准测试函数,通过仿真实验测试其性能,并与CS算法的测试结果进行比较。仿真环境为Windows7操作系统,intel处理器,2.10GHz,内存2GB,仿真软件为MATLAB7.0。表1中,Easom函数是1个简单的单谷函数,它的特点是谷很窄,最小值在1个很小的范围内变化;Master函数是1个余弦波式的测试函数;Ackley函数是1个多谷函数,各小谷同最小值对应的谷都较浅,算法较容易跳出局部最优,这3个测试函数常用于测试算法的收敛精度。NiH测试函数又名大海捞针函数(NeedleinaHaystack)是1个典型的欺骗问题,随着参数a和b的变化,该函数将形成不同严重程度的欺骗性,在进行测试的过程中a和b分别取值3.0与0.05,此时函数在(0,0)处取得全局最大值3600,在(5.12,5.12)、(-5.12,5.12)、(5.12,-5.12)和(-5.12,-5.12)处取得局部极大值约为2748.782(在函数进行测试的时候转化为求最小值问题)。Schaffer函数在距全局极小值约3.14的范围内隆起有无限多局部极小值,由于该函数的强烈震荡性质以及它的全局极小值被局部极小值所包围的特性使得一般算法很难找到它的全局最优解。Shubert函数和Langermann函数属于多峰多谷的测试函数,Shubert函数具有18个极小值,而Langermann函数也具有多个不均衡分布的极小值,都很容易陷入局部最优。Rastrigin函数为典型的不可分离的多峰多谷的测试函数,全局极小值在变量为0时达到,求解域内存在大量的局部极小值,一般算法难以获得全局最优值。综上所述,选取这8个不同特点的函数检验算法的综合优化能力即全局寻优能力和收敛能力。4.2算法性能分析为了公平的比较ACS算法和CS算法的性能,对2种算法、不同的测试函数分别独立运行100次,鸟窝数量均取n=30,步长控制因子α为0.01,收敛精度为10-7,大体上简单、低维的函数优化问题最大迭代次数kmax的取值相对小,复杂、高维的函数优化问题最大迭代次数kmax的取值相对大,若收敛精度低于10-7或迭代次数超过kmax,则认为算法未能成功收敛。为了对2种算法的收敛水平和寻优能力进行比较分析,分别记录了2种算法最大收敛代数kc,max、最小收敛代数kc,min、平均收敛代数kc,avg、收敛率η,如表2所示。最佳适应度随进化代数的变化曲线如图3～图5所示(5个2维函数最佳适应度随进化代数的变化曲线图形基本类似,仅画出NiH函数的变化曲线作为代表)。由表2和图3～图5可知,ACS算法和CS算法对5个2维测试函数均能够成功收敛,但达到同样的收敛精度10-7,ACS算法所需的最大收敛代数、最小收敛代数和平均收敛代数均低于CS算法,且ACS算法的收敛率均高于CS算法,说明ACS算法的收敛速度、收敛性能均优于CS算法。若在相同迭代次数的条件下,则能得到ACS算法的收敛精度优于标准CS算法的结论。对于高维的Master函数和Rastrigin函数,CS算法在设定的最大迭代次数内均不能收敛,而ACS不仅能够收敛,还能够达到较高的收敛率。对于高维的Ackley函数ACS算法和CS算法都能够成功收敛,但相比于CS算法而言,ACS算法收敛代数明显减少,说明无论是对于低维函数还是高维