论文研究-基于TemperedLévyFlight随机游走模型的布谷鸟搜索算法.pdf

所需积分/C币:35 2019-07-22 22:18:16 1.36MB .PDF
135
收藏 收藏
举报

布谷鸟搜索算法是一种启发式算法,利用Lévy Flight能够快速寻找到全局最优解。通过研究复杂网络随机游走模型,并根据经典布谷鸟搜索算法,提出了一种新的改进的Tempered Lévy Flight搜索算法。通过几个经典函数测试表明,改进的算法提高了其搜索精度,加快了搜索算法的收敛速度。此外,改进的搜索算法还能够调整搜索范围,增加种群多样性,增强自适应效果,提高算法的整体性能。
2994· 计算机应用研究 第33卷 (5)是随机游走过程的方程表达式。一般情形下,一个随机游更新 走是一个马尔可夫链,未来的位置与当前的位置和转移概率有 +1)=x()+6L(a) 关。对v分布函数简化和Foue变换后得到相应的概率其中:x2表示新的鸟巢位置;是步长控制量;符号⊕表示 密度函数为Lewy~u=t,1<A≤3。这是一个带有重尾的桃点对点的乘法;L(a)表示跳跃步长服从参数a的Lewy分布 率分布,其中A为幂指数。布谷鸟搜索算法使用的是具有牛的一个随机搜索向量,即 Ivy分布特征的 Mantegna法则来选择步长向量的。在Min ta1<a≤3 teana法则中,移动步长s的定义式为 在此,布谷乌搜索的迕续跳跃过程就形成了一个随机游走 (6)过程。 第二个更新方式是用来模拟布谷鸟的卵被鸟巢主人发现 这里的B同式(6)中的A关系为A=1+B,0<B≤2,在该算法 后会抛弃该鸟巢,其卵也会被移走的思想和机制,一部分差的 中取β=1.5,其中n、是满足正态分布的随机数,服从式(7) 的正态分布 鸟巢以一定的概率P被抛弃掉。具体操作如下 首先,生成一个满足均匀分布的随机数re[0,1],并与布 L~N(0,2) 7)谷鸟的卵被鸟巢主人发玩的概率P,∈0,1]进行比较。如果 ~N(0,2) P,则随机产生一个新的解对x+进行改变;反之不变,则 其标准差σ。和σ,为 保留测试值较好的一组鸟巢的位置x+1)=x r(1+B)i(m2) 在经典布谷鸟搜索算法中,布谷乌寻巢的移动步长满足 (8)下分布:1(A)=,其中1<A≤3,满足幂律的概率密度函 数,它在0点处是发散的,而且该概率分布的方差和均值都是 无界的,这就失去了其本身的物埋意义。因此,考虑对该函数 其中:、可大可小,可正可负。布谷鸟搜素的步长和方向都进行 Tempered操作,也就是对原函数进行一定的处埋。此时 是随机变化实时更新的,并且可以从某一位置区域跳转到其原函数变为b(x)-ex,由此,当A足够大时,e近似等 他区域,这样可以増加算法的多样性和全局搜索能力。又依据于1,对函数值本身没有太大的影响,但是能够从根本上保讦 宿主鸟发现外来鸟蛋的概率P。拋弃乌蛋或者鸟巢,优质的鸟函数的性质,该算法就是基于这种思想进行改进的。 巢被保留到下一代,从而产生优秀的个体。算法采取的这种随 (x)~c^x"(1<α≤3)在原点处发散,也就是说Lek 机洵汰机制,又能有效避免陷入局部最优解,使得算法具有较 强的收敛性。 x“dx=∞,根据(x)在x比较大时的渐进性质,可以取 这种Levy分布只有在|s≥|so时成立,其中s。表示最小步 o(x) 长,而且理论上讲,S趋近于0,在实际操作时,令s0是0.01 的数。 这时(x)不再发散且当x比较大时,“+1=1,因此比有 布谷鸟搜索算法的主要步骤描述如下 a)定义目标函数,对参数进行初始化,产生N个鸟巢的随 (x) (12) 机初始位置。 接下来还需要对ψ(x)进行单位化,以使得它确实表小概 b)计算目标函数的值,求出鸟果的适应度,标记当前最好率密度函数。令q=c-1,,则 的鸟第。 c)保留上一代产生的最优鸟巢位置,根据lvy飞行新 (13) 公式对鸟巢位置进行更新。 d)评估鸟巢位置(与上一代鸟巢位置进行比较),若鸟巢 式(13)就是所要求的概率密度函数。在此,解析地精确算出 位置较好,则在当前鸟巢中产蛋,并寻找当前最优鸟巢和位置。的值是比较困难的,因此,本文使用数值计算方法来得到 e)鸟巢卞人发现外来鸟蛋的概率是山产牛的随机数(r∈ 2.2算法的实现 0,1])来确定。将r与发现概率P。进行比较,若r>P,表示发 在生成满足式(13)的慨率密度函数的随机变量时,无法 现了外来鸟蛋,则放当前鸟巢,随机构建一组新的鸟巢位置 使用常用的逆变换法,在此,本文使用 Acceptance-Rejection算 f)再次评估乌巢位置,如果鸟巢适应度更优,则在当前鸟法。该算法的思想是:假设(x)和g(x)都是集合x上的概率 巢中产蛋,并寻找当前最优鸟巢和位置。 密度函数,且满足∫(x)≤ag(x),a≥1,Ⅴx∈¥,能够比较容易 g)若未满足设置的终止条件,则返回b)。 地从g(x)中生成样木X,则可以用如下步骤生成Y: ln)得到最优鸟巢的位置。 a)生成g(x)的样本X。 b)生成l~b(0,1)的均匀分布,并且l和X是独立的。 2改进的布谷鸟搜索算法 c)如果U≤f(x)/ag(x),那么取Y=X,并返叫步骤a);否 则舍去X,返回步骤a) 2.1算法的原理 为了验证该方法的可靠性,接下来证明由上述步骤生成的 改进的布谷鸟算法的两个核心更新方式为 随机数Y的确具有概率密度函数f(x)。 第·个更新方式是基于 Levy flight特征的位置夏新,假设 对于任何的A∈x,有 x表示第i个鸟巢在第t代的位置,新的鸟巢位置山以下公式 P(Y∈A)=P(X=AU≤f(x)ag(X))= 第10期 邓凯英,等:基于 Tempered Levy Flight随机游走模型的布谷鸟搜索算法 2995· P(X∈Af(x)/ag(X) P(U≤f(x)/ag(X)) (14)函数的全局最优解位于一个平滑且狄长的抛物线形的山谷内, 该函数为布谷鸟搜索等优化算法提供的信息量较少,使算法很 f( 由于P(U≤m(X)kw(x)(x)dx=,所以P(Y∈难辨别搜索方向,因此也用此函数来评价优化算法的执行效率 和效果。 A)=n02+)d=y(x)d,即y的概率密度函数为6m函数是多峰值函数,并且存在多个局部最优点。 f(x) Rastrigin函数为不可分离多峰函数,当变量为0时,达到全局极 山以上证明过程可以看出,每次接受的概率为P(U≤小值,求解区域内存在很多局部最优解(极小值),函数的尖峰 ∫(x)/ag(x)=1/a换句话说,为了生成一个f(x)的样本,需个数随着维数的增加而增加,一般算法很难获得全局最优倌。 要生成a个g(x)和U(0,1)均匀分布的样本。 Rastrigin函数是较难找到全局最优值的多峰函数。因此,本文 以上是 Acceptance-Rejection算法的描述和证明,接下来通使用 Rastrigin函数来检验算法的全局寻优能力和收敛能力 过 Acceptance- Rejection算法,首先生成随机变量y,其中φ(y)232实验结果及分析 Ae4,y=-log(u)/A,u是在[0,1]间的均匀分布,表达式为 表1中的C是 cuckoo search的缩写,代表经典布谷鸟算 法;"(S代表 ch,是改走的布谷 止(x) (15)鸟搜索算法。表1中的数据是这两种搜索算法分别独立运行 20次后统计的实验结果。对于 Sphere、 Rosenbrock、 Rastrigin和 令=a,改进布谷鸟核心算法的描述如下 Criewank函数,它们的全局最优值都为0。为了使实验数据尽 A 生成U1([0,1]上的均匀分布),Y=-bog(U1)A 可能可靠,本文讨论了两种算法分别运行20次后各个函数产 b)牛成U2([0,1]上的均匀分布) 生的最优值、最差值和平均值。其中,平均值貝冇更大的指导 c)计算v(Y)/(a(Y))。 意义,囚为它能够更为真实地反映实验结果。从表1的实验结 d)如果U2<(Y)/(ag(Y),则X=Y;否则,继续a)b) 果可以看出,改进的布谷鸟搜索算法在 Sphere、 Rosenbrock 基于 Tempered Levy Flight的布谷鸟搜索算法的伪代码如 astrigin和 Griewank函数这四个测试函数实验中,求解精度都 高于传统的布谷鸟搜索算法, Rosenbrock、 fastrigin函数的求解 下 优化效果更为明显。 begin Object function f(x), r=(xI, ". I)T 表1独立还行20次的实验结果 Generate initialize a population of n host nest x;, i=l, 2, 3,-,n 函数算法最优值量差值平均值平均达代次数 Initialize parameter n.A,a for all x. do Cs6.2940e-069.9455e-068.8336e-062115.21 Calculate fitness F=f(x;) lCS6.2473c-069.7115。-068.1295c-0 end for while( Number Evaluations Max) or( Stop criterion Cs2.2812e-0698510e-065.0905e-06414.60 Generate a solution according to Acceptance-Rejection algorithm TCs1.0847e-069.5830e-064.9974e-06412.15 while(U2>A) CS2.6852e-079.9948e-6066.5084e-06980.20 Generate uniform distribution U,E 0, 1, Y=-log(U/n Gcncratc uniform distribution U2 E0, 1 TCS1.8732e-077.6582e-064.1317e-0 832 Evaluate the fitness F CS1.4484-069.9529e-065.7082c-06673.23 if(/i>fi) then lCS1.2742c-069.304c-065.3749c-06 Replace i by the new solution 从表1中可以看出,针对同一测试函数,在相同实验环境 nd if Abandon a fraction p of the worst nests and new ones are bulit 相同维数和精度的要求下,经过20次独立实验运行,针对 Keep the best solt Sphere测试函数,改进的TCS算法的平均最优值8.1295e Rank Ihe solutions ar find the currenl besl end while 06,优丁经典的C:算法的平均最优值8.8336-06。同样,对 Postprocess results and visualization 其他 Rosenbrock、 Rastrigin和 Griewank这三个测试函数,改进 的TCS算法的最优值以及平均最优值都优于经典的CS算法 2.3实验仿真 这表明改进的TCS算法相对具有更高的收敛精度。对于 2.3.1测试函数 Sphere、 Rosenbrock rastrigin和 Griewank这四个测试函数,在 为了评估算法的求精能力和收敛速度,验证算法的有效迭代次数上,改进的TCS算法也是比传统的CS算法有较为明 性。本章选取了四个经典的基准测试函数进行测试20: Sphere显的下降,这说明改进的TCS算法的收敛速度更快 函数f= Rosenbrock函数/=2[(1-x)2+10(x 改进的算法使用 Tempered Levy Flight随机游走搜索策略 该策咯是短距离的探索和偶尔较长距离的跳跃相间的,能使鸟 x2)2-; Rastrigin函数=(x2-10cs(2mx)+10), Griewank巢的位置变化更具活力,增强了全局搜索能力,同时又通过对 函数/4 参数λ的调整能够有效地控制搜索范闱,能够在保持强大的 3400+1 全局搜索能力的同时,尽可能地提高局部搜索能力。在此兼顾 这些测试函数的搜索范围为[-5,5],全局最小值是0。了局部搜索能力,取得了全局随机搜索与局部搜索之间的战略 Sphere函数为单峰函数,点处得到全局极小值,用于检测算平衡,能够时凋整搜索范围,增加种群多样性,增强自适应效 法的收敛精度。 Rosenbrock函数在二、三维时是简单的单峰函果,提高算法的整休性能。 数,通常用此函数检测算法的局部搜索能力。由于 Rosenbrock 本文米用的几个测试函数中,不仅选用了单峰函数,还包 2996· 计算机应用研究 第33卷 括多峰函数,而且对低维和多维的情形也进行了测试。山表1较好的性能,主要是因为 可知,该算法对四个不同的测试函数进行测试,改进的布谷鸟 a)该算法能够很好地平衡仝局搜索和局部搜索。一方面 搜索算法比经典的布谷鸟搜索算法能获得较好的适应值。接通过 Tempered levy Flihgt中的大步长跳饫能够冇效地避免陷 下来继续实验过程,通过讨论迭代次数和求解最优值的准确性人入局部最优;艻一方面该算法又能够通过调整参数λ来控制 来衡量算法的搜索速度和收敛情况。实验结果如图5~8所搜索空间以达到局部个放弃的原则。 示。从图5~8可以看出,改进的布谷鸟搜索算法和经舆的布 b)控制算法的参数数量不多,对于大多数元启发式算法 谷鸟搜索算法对于 Sphere、 Rosenbrock、 Rastrigin和 Griewank这在能够有效控制搜索区域和搜索空间的情况下,通过适当加强 四个测试函数均能成功收敛。在达到相同精度的条件下,改进局部拽索,就能够成为一种比较有效的搜索算法。该算法由于 的布谷鸟搜索算法比原来的算法搜索速度快、搜索时间短。由参数少,实现也就相对简单,并且更加通用。 图5~8还可以看出,木文提出的改进的布谷鸟搜索算法收敛参考文献: 效果好于经典的布谷鸟搜索算法,此结果可以由测试函数的收 Eustace J, Wang Xingyuan, Cui Yaozu. Community detection using 敛曲线看出。从实验结果还可知,改进的布谷鸟搜索算法的收 local ncighborhood in complex nctworks[J]. Physica A: Statistical 敛能力较强。 Mechanics and its Applications, 2015, 436(2015): 665-677 [2 Milgram S. The small world problem[ J]. Psychology Today, 1967 2 40 [3 Travers J, Milgram S. An cxpcrimental study of the small world prob 40 len[J]. Sociometry,1969,32(4):425-443 [4 Dodds P S, Muhamad R, Watts D J. An experimental study of search 20 rks[J]. Science,2003,301(5634):827-829. 0100020030040030 100200 300 400500600 [5. Watts D J, Dodds P S, Newman M E J. ldentity and scarch in social etworks[J. Science,2002,296(1302):1302-1305 图5f函数的收敛曲线对比图6/2函数的收敛曲线对比 [6. Adamic L A, Lukose R M, Puniyani A R, et al. Search in power-law 0.25 networks[J. Physical Review E, 2001, 64(4): 046135 16 [7 Kim B Yoon C N, Han SK, et al. Path finding strategies in scale 14 把12 015 free networks[ J]. Physical Review E, 2002, 65(2): 027103 [8ˉ温巧林,司守奎,任东彦,等.基于最大度和随机游走的混合搜索 0.05 算法[J].海空航空工程学院学报,2010,25(5):577-580. [9王天骄,汪小帆,李翔.无标度网络的最大一最小度搜索算法[J] 产一 2004006008001000 迭代次数 计算机仿真,2007,24(9):161-163 迭代次数 图7函数的收敛曲线对比图8/函数的收敛由线对比 [10]冯立雪.结合最大度与最小聚类系數的复杂网络搜索策略研究 在迭代次数相同的情況下, Sphere、 Rosenbrock、 Rastrigin和 [D].北京:北京交通大学,2011. [11] Klcinbcrg J M. Navigation in a small world J]. Nature, 2000,406 Griewank这四个测试函数都表现出了达到最优值较快的事实, 6798):845-845 收敛精度较高。改进的布谷鸟算法的收敛速度和收敛性能都[12] Kleinberg J M. The small-world phenomenon: an algorithmic perspec 优于经典的布谷鸟搜索算法。仿真实验结果表明,无论是简单 tive[ Cl//Proc of the 32nd Annual ACM Symposium on Theory of 的单峰函数还是复杂的多峰函数,改进的布谷鸟搜索算法都优 Computing.2000:163-170. 于经典的布谷鸟算法。另外,通过参数调整发现,对于小型的[13] Adamic L a, Adar. Ilow to search a social network[ J. Social 低维函数和大型的高维函数,改进的布谷鸟搜索算法的寻优能 Networks,2005,27(3):187-203 力也超过经典的布谷鸟波索算法,这体现了改进的布谷乌搜索144km,uRM,Hg,1oueu 算法具有更好的性能和更优的仝局寻优搜索能力。 Graphs and Nelworks. Berlin: Wiley, 2003 本文提出的基于 Tempered Levy Flig随机游走模型的布[15] Watts D J, Stogatz sh., Collective dymamics of small-world networks 谷鸟擭索算法是一种新型元启发式搜索算法,与其他相关智能 [J]. Nature,l998,393(6684):440-442 算法对比,该算法具有较强的鲁棒性和可移植性。该算法利用[16] Thadakamalla h h, Albert r, Kumara s r. Scarch in weighted Levy Flight能较快地寻找到全局最优解,通过对 Levy Flight进 complex networks[ J. Physical Review E, 2005, 72(6): 066128 行 Tempered处理,能够增强搜索位置变化的活力,有效地控制 17]Zhao Yi, Weng Tongfeng, Huang Defeng. Levy walk in complex net 搜索范围。由于 Levy Flight具有随机游走特性,局部极值点附 ient way of mobility original research article[ J. phy- 近通常能够产生新解, Levy Fligl的短步长搜索能够提高解的 sica A: Statistical Mechanics and its Applications, 2014, 396 (2014):212-223 质量。此外,偶尔的大步长搜寻,能够使算法不谷易陷人局部[181 Yang xinshe,Dbs. Cuckoo search: recent advances and appl 极值,也就提高了算法的收敛速度。 tions[ J. Neural Computing and Applications, 2014, 24 ( 1): 169 3结束语 [19 Moravej,, Akhlaghi A. A novel approach based on cuckoo seareh for DG allocation in distribution network[ J. Electrical Power and En 本文从复杂网络的搜索模型出发,基于此算法进行理论分 ergy systems,2013,44(1):672-679 析硏究,提出了一种新的改进的复杂网络搜索策略,并进行数201 Hansen N, Ostermcicr A. Complctcly dcrandomizcd sclf-adaptation in 值模拟和算法实现,最后验证算法的可行性和冇效性,从而达 evolution strategies [J]. Evolutionary Computation, 2001, 9(2) 到提高搜索效率的目的。改进的布谷鸟搜索算法之所以具有 159-195

...展开详情
试读 5P 论文研究-基于TemperedLévyFlight随机游走模型的布谷鸟搜索算法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
关注 私信
上传资源赚钱or赚积分
最新推荐
论文研究-基于TemperedLévyFlight随机游走模型的布谷鸟搜索算法.pdf 35积分/C币 立即下载
1/5
论文研究-基于TemperedLévyFlight随机游走模型的布谷鸟搜索算法.pdf第1页

试读结束, 可继续读1页

35积分/C币 立即下载