当前位置：文档库 › 逐维改进的布谷鸟搜索算法

逐维改进的布谷鸟搜索算法

软件学报ISSN 1000-9825, CODEN RUXUEW E-mail: jos@https://www.wendangku.net/doc/ce16799673.html,

Journal of Software,2013,24(11):2687?2698 [doi: 10.3724/SP.J.1001.2013.04476] https://www.wendangku.net/doc/ce16799673.html,

逐维改进的布谷鸟搜索算法

王李进1,2, 尹义龙2, 钟一文1

1(福建农林大学计算机与信息学院,福建福州 350002)

2(山东大学计算机科学与技术学院,山东济南 250101)

通讯作者: 尹义龙, E-mail: ylyin@https://www.wendangku.net/doc/ce16799673.html,, https://www.wendangku.net/doc/ce16799673.html,/ylyin.html

摘要: 布谷鸟搜索(cuckoo search,简称CS)算法是一种新兴的仿生智能算法,对解采用整体更新评价策略.在求

解多维函数优化问题时,由于各维之间相互干扰,采用整体更新评价策略将恶化算法的收敛速度和解的质量.为了弥

补此缺陷,提出了基于逐维改进的布谷鸟搜索算法.在改进算法的迭代过程中,针对解采用逐维更新评价策略.该策

略将各维的更新值与其他维的值组合成新的解,并采用贪婪方式接受能够改善解质量的更新值.实验结果说明,改进

策略能够有效地提高CS算法的收敛速度并改善解的质量.与相关的改进布谷鸟搜索算法以及其他演化算法的比较

结果表明,改进算法在求解连续函数优化问题上是具有竞争力的.

关键词: 布谷鸟搜索算法;逐维改进;函数优化;多维函数;干扰现象

中图法分类号: TP183文献标识码: A

中文引用格式: 王李进,尹义龙,钟一文.逐维改进的布谷鸟搜索算法.软件学报,2013,24(11):2687?2698.https://www.wendangku.net/doc/ce16799673.html,/

1000-9825/4476.htm

英文引用格式: Wang LJ, Yin YL, Zhong YW. Cuckoo search algorithm with dimension by dimension improvement. Ruan Jian

Xue Bao/Journal of Software, 2013,24(11):2687?2698 (in Chinese).https://www.wendangku.net/doc/ce16799673.html,/1000-9825/4476.htm

Cuckoo Search Algorithm with Dimension by Dimension Improvement

WANG Li-Jin1,2, YIN Yi-Long2, ZHONG Yi-Wen1

1(School of Computer and Information Science, Fujian Agriculture and Forestry University, Fuzhou 350002, China)

2(School of Computer Science and Technology, Shandong University, Ji’nan 250101, China)

Corresponding author: YIN Yi-Long, E-mail: ylyin@https://www.wendangku.net/doc/ce16799673.html,, https://www.wendangku.net/doc/ce16799673.html,/ylyin.html

Abstract: Cuckoo search (CS) is a new nature-inspired intelligent algorithm which uses the whole update and evaluation strategy on

solutions. For solving multi-dimension function optimization problems, this strategy may deteriorate the convergence speed and the

quality of solution of algorithm due to interference phenomena among dimensions. To overcome this shortage, a dimension by dimension

improvement based cuckoo search algorithm is proposed. In the progress of iteration of improved algorithm, a dimension by dimension

based update and evaluation strategy on solutions is used. The proposed strategy combines an updated value of one dimension with values

of other dimensions into a new solution, and greedily accepts any updated values that can improve the solution. The simulation

experiments show that the proposed strategy can improve the convergence speed and the quality of the solutions effectively. Meanwhile,

the results also reveal the proposed algorithm is competitive for continuous function optimization problems compared with other

improved cuckoo search algorithms and other evolution algorithms.

Key words: cuckoo search algorithm; dimension by dimension improvement; function optimization; multi-dimension function;

interference phenomena

自20世纪以来,人们利用蚂蚁、鸟类等群居生物的自组织行为,提出了粒子群算法(particle swarm

?基金项目: 新世纪优秀人才支持计划(NCET-11-0315); NSFC-广东联合基金重点支持项目(U1201258); 福建省自然科学基金

(2011J05044, 2013J01216); 山东省自然科学杰出青年基金(2013JQE27038)

收稿时间:2013-04-27; 修改时间: 2013-07-17; 定稿时间: 2013-08-27

2688 Journal of Software软件学报 V ol.24, No.11, November 2013

optimization,简称PSO)[1,2]和蚁群算法(ant colony optimization,简称ACO)[3]等群智能算法,并成功用于求解大量的实际问题[4].近几年来,源于生物系统的灵感,涌现了诸多新颖的仿生优化算法,如蜂群优化算法[5]、族群优化算法[6]、布谷鸟搜索(cuckoo search,简称CS)算法[7,8]等.

CS算法是一种新颖的群智能算法,其思想源于对布谷鸟寄生育雏行为以及鸟类或果蝇Lévy flights行为的模拟.CS算法不仅具有简单、参数少、易于实现等优点,而且其性能接近于标准的粒子群优化算法和差分演化算法(differential evolution,简称DE)[9,10].

CS算法具有显著的高效性,主要源于两个非常关键的组件:Lévy flights随机游动和偏好随机游动,二者平衡算法的局部搜索和全局搜索.鉴于简单和高效,众多学者对CS算法进行研究,并提出相关改进版本,主要涉及步长改进、自适应以及与其他算法混合等方面.Walton等人[11]针对Lévy flights随机游动中的Lévy随机步长大小提出一种改进版本以加强局部搜索,实验结果说明,对大多数测试函数而言,改进算法具有较好的性能,特别是在高维上能够较快地收敛于全局最优.Tuba等人[12]针对偏好随机游动中的步长提出一种基于种群排序的改进版本,实验结果显示,改进算法的性能略优于标准的CS算法.Valian等人[13]引入自适应机制,并提出了一种自适应步长和自适应发现概率的CS算法,实验结果说明,在大多数函数上解的质量优于标准CS算法的解.Layeb 等人[14]引入量子比特、量子纠缠以及量子变异等量子计算概念,以提高CS算法种群的多样性,并成功地应用于求解装箱问题.Ghodrati等人[15]借鉴PSO算法中全局最优和个体最优的概念,在CS算法Lévy flights随机游动和偏好随机游动之间引入PSO组件,其性能与相关算法相比具有一定的竞争力.Wang等人[16]将PSO与CS串行,在每次迭代过程中首先用PSO算法优化种群,并记录全局最优和个体最优,其次采用CS算法对种群个体最优继续寻优,仿真实验验证,改进算法比CS算法有更好的寻优能力.Srivastava等人[17]在Lévy flights进行局部搜索时引入禁忌搜索思想,将当前最优解存入禁忌搜索队列中,以避免陷入局部最优,并成功地应用于求解软件测试数据自动生成问题.Li等人[18,19]在偏好随机游动之后引入正交学习机制,以提高算法的搜索能力,在求解混沌系统的参数估算问题和连续函数优化问题上都获得了较好的性能.

上述改进策略都较好地改善了CS算法的收敛速度或解的质量,然而无论算法采用Lévy flights随机游动还是偏好随机游动生成新的解,都是在整体更新后才对这些解进行评价,即对每个新解修改其所有维的值,再对其评价.对于多维的目标问题而言,由于存在着维间互扰现象,整体更新评价策略将影响算法的收敛速度和解的质量[20].另一方面,前期的研究结果[20]表明,迭代改进策略能够较好地避免维间互扰.迭代改进策略为了降低算法对目标函数评价的依赖,重新构建新的评价算子对解的更新值进行评价.然而,对于非线性目标函数或者更复杂的优化问题,重新构建新的评价算子是困难的,甚至是不可行性的,这将降低算法的实用性.本文借鉴迭代改进策略的思想,提出逐维改进的布谷鸟搜索算法(cuckoo search algorithm with dimension by dimension improvement,简称DDICS).DDICS算法通过在偏好随机游动中引入逐维改进策略来避免维间互扰,同时改写偏好随机游动的步长更新方式,增加搜索方向,以便有效利用单维的信息加强算法的局部搜索能力,从而提高解的质量.需要指出的是,DDICS算法在逐维改进过程中直接采用目标函数,而不是重新构建新的评价算子对解的更新值进行评价,这有利于算法的实际应用和推广.实验结果说明,改进策略能够有效地提高CS算法的收敛速度并改善解的质量,而且在求解连续函数优化问题上是具有竞争力的.

1 布谷鸟搜索算法

布谷鸟采用寄生育雏的特殊繁殖后代策略,总是将自己的蛋存放到其他鸟类的巢里,让其他鸟类为其孵化下一代.为了降低被发现的概率,一些布谷鸟将自己的蛋模仿成所选鸟类的蛋.当其他鸟类发现其巢里有外来的蛋,则会将外来的蛋丢弃或者放弃自己的巢,在其他地方构建新的巢.Yang和Deb基于上述的布谷鸟繁殖策略,抽象出布谷鸟搜索算法,且该算法基于3条理想规则[7,8]:

规则1. 每只布谷鸟1次只产1颗蛋,并随机选择1个鸟巢存放.

规则2. 蛋最好的鸟巢将会被保留至下一代.

规则3. 可用鸟巢的数量是固定的,而且鸟巢中外来蛋被发现的概率是p a∈[0,1].

王李进等:逐维改进的布谷鸟搜索算法 2689

基于上述的3条规则,CS 算法的基本流程如算法1所示. 算法1. CuckooSearch. Begin

初始化种群:n host nests X i (i =1,2,…,n ); 计算适应值:F i (i =1,2,…,n ). While (不满足停止条件)

采用Lévy flight 生成新的解X i ; 计算新解X i 的适应值F i ; 选择候选解X j ;

If (F i >F j )

用新的解替代候选解; End

按发现概率p a 丢弃差的解;

用偏好随机游动产生新的解替代丢弃的解; 保留最好的解. End

End

在CS 算法中,1个鸟巢表示1个候选解.CS 算法首先在当前解的基础上以Lévy flights 随机游动方式生成新的解,评价并保留较好的解;其次,按发现概率p a 丢弃部分解;最后,按偏好随机游动方式重新生成与丢弃解相同数量的新解,在评价并保留较好的解之后,完成一次迭代.

当采用Lévy flights 随机游动生成新的解X i 以后,执行公式(1)的操作:

X g +1,i =X g ,i +α⊕Lévy (β) (1)

其中,X g ,i 表示第g 代第i 个解;α是步长信息,用于控制随机搜索的范围.为了能够从当前最优解中获得更多有用的步长信息,文献[8]采用公式(2)计算步长信息:

α=α0(X g ,i ?X best ) (2)

其中,α0是常数(α0=0.01),X best 表示当前最优解.

公式(1)中,⊕是点乘积(entry-wise multiplications),Lévy (λ)服从Lévy 概率分布:

Lévy (β)~u =t ?1?β, 0<β≤2 (3)

为了便于计算,文献[8]采用公式(4)计算Lévy 随机数:

1/~||u

L v β

φ× (4)

其中,u ,v 服从标准正态分布,β=1.5.

1/(1)/2(1)sin(/2)122β

βΓββφβΓβ?+×π×??

??=??+????××?

???????

???? (5) 显然,综合公式(1)~公式(5),在Lévy flights 随机游动组件中,CS 算法采用公式(6)生成新的解X i :

1,,0,,1/()||

g i g i g i g best u

X X X X v βφα+×=+? (6)

在按一定的概率(发现概率)丢弃部分解之后,算法采用偏好随机游动重新生成相同数量的新解,见公式(7):

X g +1,i =X g ,i +r (X g ,j ?X g ,k ) (7)

其中,r 是缩放因子,是(0,1)区间的均匀分布随机数;X g ,j 和X g ,k 是表示第g 代的两个随机解.

Lévy

(β)

2690 Journal of Software 软件学报 V ol.24, No.11, November 2013

2 逐维改进的CS 算法

2.1 基于贪婪的逐维更新评价策略

在CS 算法中,虽然偏好随机游动组件有利于提高种群的多样性以及加强算法的全局搜索能力,但对于多维

目标函数而言,对解采用整体更新评价策略将影响算法收敛速度和解的质量.假设目标函数222

123(),f X x x x =++

以及在第g 代的第i 个解X g ,i =(0.5,0.5,0.5),此时,目标函数值f (X g ,i )=0.75.在算法迭代过程中,假设首先采用公式

(7)将X g ,i 的整体更新为X g +1,i =(0,1,?1),其次根据目标函数评价该解,则目标函数值f (X g +1,i )=2.由于f (X g +1,i )=2> f (X g ,i )未能改进当前代的解,算法将放弃新的解,保留当前代的解.然而,对比更新前后解的各维的值以及目标函数的全局最优解X opt =(0,0,0)可知,第1维的值由0.5进化为0,第2维和第3维的值却分别退化为1和?1.正因为第2维和第3维的退化,使整体的函数值变差,导致此解的质量不高而被抛弃,最终忽略第1维的进化,浪费函数评价次数,恶化收敛速度.

逐维更新评价策略能够较好地避免上述问题.该策略分别考虑各维值更新,当某一维的值通过公式更新后,将与其他维的值组合成一个新的解,继而评价该新解.而基于贪婪的逐维更新评价策略,只有能够改善当前解的更新值才被接受.例如,当X g ,i 第1维的值由0.5更新为0时,便与其他维的值组合成一个新解X g +1,i =(0,0.5,0.5),因为函数值f (X g +1,i )=0.5f (X g ,i ),更新的值未能改善当前的解,将放弃当前维的更新值,并进入下一维的更新操作.基于贪婪的逐维更新评价策略使得解的进化维不会因其他维的退化而被忽略,保障算法能够利用进化的单维信息引导当前解进行局部搜索,从而获得更高质量的解并提高算法的收敛速度. 2.2 改进算法的流程

DDICS 算法通过在偏好随机游动中引入逐维更新评价策略,以避免维间互扰.然而,偏好随机游动中的步长更新方式是基于双随机解,并没有充分利用解的本身信息,不利于逐维改进策略进行局部搜索.与此同时,公式

(7)中的缩放因子r 取(0,1)区间的均匀分布随机数,在一定程度上限制了偏好随机游动的搜索方向.然而,r 可取(?1,1)区间的均匀分布随机数以增加反向搜索,达到双向搜索,提高局部搜索能力.因此,DDICS 算法将公式(7)修改为公式(8):

X g +1,i =X g ,i +r (X g ,j ?X g ,i ) (8)

其中,r 是(?1,1)区间的随机数,X g ,j 是表示第g 代的随机解.

整个改进算法的流程可抽象为算法2. 算法2. DDICS.

Begin

初始化种群:n host nests X i (i =1,2,…,n ); 评价X i (i =1,2,…,n ).

While (不满足停止条件)

For i =1 to n

采用公式(6)生成新的解X g +1,i ; 选择候选解X g ,i ;

If (X g +1,i 优于X g ,i )

X g +1,i 替代X g ,i . End End For i =1 to n

王李进等:逐维改进的布谷鸟搜索算法 2691

If (r >p a )

For j =1 to d

X c =X i ;

X c [j ]=X c [j ]+r (X [k ,j ]?X [i ,j ]); If (X c 优于X i )

接受更新:X i =X c ;

End End End End

保留最好的解.

End End

3 实验与结果

为了观察改进算法求解多维函数优化问题的收敛速度和解的质量,实验选择3类测试函数,见表1.第1类是单峰函数,其中,f 1是简单的单峰函数,f 2在二、

三维时是简单的单峰函数,但在更多维时可看作多峰函数[21?23];第2类是具有众多局部极值点的多峰函数[24];第3类是具有变换或旋转的单峰或多峰函数[25].

Table 1 Test functions

表1 测试函数

测试函数搜索空间误差阈值函数名称211()D

i i f x x ==∑ [?100 100]10?6 Sphere [24] 单峰

222211

()(100()(1))D i i i i f x x x x ?+==?+?∑

[?100 100]10?6 Rosenbrock [24]231111()20exp(1)20exp 0.2exp cos(2)n n i i i i f x x x n n ==????

=+???π??????????

∑∑

[?32 32]10?6 Ackley [24] 2411()cos 14000D

i i i i x x

f x i ===?+∑

∏

[?600 600]10?6 Griewank [24]251

()(10cos(2)10)D

i i i f x x x ==?π+∑

[?5.12 5.12]

10?6 Rastrigin [24](

)()61

()418.9829sin

i i i f x n x x ==+∑

[?500 500]

10?6

Schwefel [24]

222271111

()10(sin())((1)[110(sin())])(1) (,10,100,4)

(), 1where 1(1), (,,,)0, 4(), n i i n i n

i i m i i i i i i m i i f x y y y y n u x k x a x a

y x u x a k m a x a

k x a x a

?+==π??=

π+?+π+?+??????>?

=++=?????

∑∑≤≤

[?50 50]

10?6

Generalized

Penalized 1[24]

多峰

222281111

()0.1(sin(3))((1)[1(sin(3))])(1)[1(sin(2))2] (,5,100,4)

n i i n n i n

i i f x x x x x x u x ?+==??

=π+?+π+?+π+

????

∑∑[?50 50]

10?6

Generalized Penalized 2[24]

2692 Journal of Software软件学报 V ol.24, No.11, November 2013

Table 1 Test functions (Continued)

表1测试函数(续)

同时,表1给出了各函数的收敛误差阈值[25].函数误差计算见公式(9):

Error=f(X)?f(X*) (1) 其中,X表示算法得到的解,X*是函数全局最优解.从公式(9)可知:函数值误差越小,解的质量越好.

在实验中,DDICS算法与ICS[13],OLCS[18,19]和CSPSO[16]等改进的CS算法,以及DEahcSPX[24],jDE[26],

CLPSO[27]和CoDE[28]等其他演化算法作性能比较,以便分析改进算法的竞争力.同时,每个算法解的质量以“平

均误差±标准差”形式表示,并给出0.05显著水平下的双侧t-检验.

? “≈”表示算法的平均误差与DDICS算法的平均误差在0.05显著水平下的双侧t-检验是不显著的,解的

质量相似;

? “?”表示算法的平均误差与DDICS算法的平均误差在0.05显著水平下的双侧t-检验是显著的,解的质

量比DDICS算法要差;

? “?”表示算法的平均误差与DDICS算法的平均误差在0.05显著水平下的双侧t-检验是显著的,解的质

量比DDICS算法要好.

3.1 解的质量分析

表2给出了CS算法以及DDICS算法在D=30维空间上的函数值平均误差及标准差.其中,种群的规模

N P=D,发现概率p a=0.25,最大函数评价次数FES=10000×D,每个算法独立运行50次.

Table 2Mean function value errors of CS and DDICS (D=30)

表2CS与DDICS的平均函数值误差(D=30)

函数CS DDICS

f18.46E?31±1.19E?30? 3.15E?79±7.62E?79f8 4.64E?29±1.37E?28? 1.35E?32±1.11E?47

f2 1.07E+01±9.44E+00? 7.20E?01±1.25E+00f9 4.21E?30±9.91E?30?0.00E+00±0.00E+00

f3 3.73E ?02±1.84E ?01? 3.41E?14±3.93e?15f10 2.76E+01±2.34E+01? 4.18E+00±6.67E+00

f4 3.29E?16±1.75E?15? 0.00E+00±0.00E+00f11 8.30E?04±2.24E?03? 1.97E?02±5.60E?03

f5 2.54E+01±4.39E+00? 0.00E+00±0.00E+00f12 2.09E+01±4.67E?02? 2.07E+01±5.95E?02

f6 1.25E+03±3.04E+02? 0.00E+00±0.00E+00f13 2.66E+01±5.29E+00?0.00E+00±0.00E+00

f7 2.05E?20±7.28E ?20? 1.57E?32±5.53E?48

从表2可看出,对单峰函数而言,DDICS算法与CS算法相比,显著提高了解的质量,且具有较高的精度.在有

众多局部极值点的多峰函数中,DDICS算法在f3,f7和f8函数上显著提高了解的质量,并且在f4,f5和f6函数上

取得全局最优解.在第3类函数中,无论是变换的单峰函数f9,还是变换的多峰函数f10和f13,DDICS算法都能较

好地提高解的质量,特别是在f9和f13上获得全局最优解;对旋转且变换的多峰函数f12而言,DDI策略能够有效

王李进等:逐维改进的布谷鸟搜索算法

2693

提高CS 算法解的质量.然而对于旋转且变换的多峰函数f 11,DDICS 算法虽然获得了较好的解,却未能提高解的质量.DDICS 算法之所以能在大多数的函数上改善解的质量,是因为采用DDI 策略使算法避免了维间互扰,充分利用单维有用的信息加强算法局部搜索,从而改善算法的性能.而在f 11上未能改善解的质量,则归因于该函数没有边界,且最优解在初始化搜索空间之外,导致单维的信息无法引导算法展开局部搜索,最终影响解的质量. 3.2 收敛速度分析

表3给出了算法收敛于指定误差阈值所需的平均函数评价次数和标准差及成功次数.“?”表示未能收敛于指定误差阈值.由于CS 算法采用整体更新评价策略存在维间互扰,在一定程度上浪费了函数评价次数,未能获得较好的解,使得收敛较慢.反之,虽然DDICS 算法逐维评价消耗一定的函数评价次数,但逐维更新能够加强局部求精能力,有利于获得较好的解,从而加快算法的收敛.从表3的实验结果也可以看出:对单峰函数而言,CS 算法和DDICS 算法都只在f 1函数上收敛于指定误差阈值,但借助于平均函数评价次数,DDICS 算法明显具有较快的收敛速度.在复杂的多峰函数中,针对f 4,f 7和f 8函数,两算法都以相同的成功次数收敛于指定误差阈值,但根据平均函数评价次数,DDICS 算法以较快的速度收敛.对于f 3,f 5和f 6函数,借助于平均函数评价次数,DDICS 算法快速收敛于指定误差阈值,而且借助于成功次数,DDICS 算法的收敛具有较好的稳定性.针对f 12函数,由于

DDICS 算法未能获得较好的解,从而几乎未能收敛于指定误差阈值,但在f 9和f 11函数上,DDICS 算法快速且稳定地收敛于指定误差阈值.

Table 3 Mean FES of CS and DDICS to reach specified error threshold (D =30)

表3 CS 与DDICS 收敛于指定误差阈值的平均函数评价次数(D =30)

函数 CS DDICS 函数CS DDICS f 1 87890.9±2706.3(50)? 38764.2±1452.8(50) f 7 148538.2±20898.2(50)?33410.0±1718.5(50) f 3 162313.3±34687.8(48)? 64676.3±1265.8(50) f 8 99216.0±4868.5(50)? 37549.4±1535.1(50) f 4 124996.5±22839.0(50)? 49461.9±6207.9(50) f 9 91621.1±3116.0(50)? 40536.1±1155.5(50) f 5 ? 78996.3±6353.0(50) f 11 155926.6±25420.5(50)?283974.0±0.0(1) f 6 ? 115460.4±11417.7(50)f 13 ? 88962.7±8390.8(50)

为了进一步说明DDICS 算法的收敛速度优于CS 算法,图1~图4图形化展示两算法收敛于指定误差阈值的部分函数的收敛过程.从图3~图6可以看出:DDICS 算法的收敛过程明显有较好的收敛曲线,而且在前期具有较快的收敛速度,在后期具有较好的求精能力,从而验证了表2的结果.

对f 2,f 10和f 12函数而言,虽然DDICS 算法与CS 算法都未能收敛于指定误差阈值,但是图5~图7说明DDICS 算法的收敛过程同样有较优的收敛曲线.例如,DDICS 算法优化f 2和f 10函数在早期具有较快的收敛速度,在后期虽然收敛速度放缓,但与CS 算法相比仍然具有较好的求精能力.在求解f 12函数过程中,DDICS 算法在早期收敛速度虽显著优于CS 算法,但随着迭代的进行,表现出较好的收敛速度和求精能力.

函数评价次数

0?10?20?30?40?50?60?70?80

CS DDICS

L o g 10(平均误差)

300000

0 100000 200000 函数评价次数

0?2?4?6?8?10?12?14

L o g 10(平均误差)

300000

100000

200000 CS DDICS

Fig.1 Convergence curves of DDICS

and CS for f 1 function

图1 DDICS 和CS 求解f 1函数的收敛曲线

Fig.2 Convergence curves of DDICS

and CS for f 3 function

图2 DDICS 和CS 求解f 3函数的收敛曲线

2694 Journal of Software 软件学报 V ol.24, No.11, November 2013

Fig.7 Convergence curves of DDICS and CS for f 12 function

图7 DDICS 和CS 求解f 12函数的收敛曲线

3.3 维数变化分析

为了观察并分析DDICS 算法随维数变化的性能,表4列出了DDICS 算法在不同维数上的平均函数值误差和标准差及成功次数.由于第3类函数最高维是50维,表4给出50维的实验结果,而其他函数分别完成50维、

100维和200维的实验结果.其中,规模N P =D ,发现概率p a =0.25,FES =10000×D ,每个算法独立运行50次.

从表4可知,在50维上,DDICS 算法性能可以得到与第3.1节相同的结论.在100维和200维上,CS 算法收

函数评价次数

1.3321.3301.3281.3261.3241.3221.3201.3181.316

L o g 10(平均误差)

300000

100000200000CS DDICS

函数评价次数

100?10?20?30

L o g 10(平均误差)

300000

0 100000 200000 CS DDICS

函数评价次数

50?5?10?15?20?25

L o g 10(平均误差)

300000

100000

200000

CS DDICS

Fig.3 Convergence curves of DDICS

and CS for f 7 function

图3 DDICS 和CS 求解f 7函数的收敛曲线

Fig.4 Convergence curves of DDICS

and CS for f 9 function

图4 DDICS 和CS 求解f 9函数的收敛曲线

函数评价次数

1086420

L o g 10(平均误差)

300000

0 100000 200000 CS

DDICS

Fig.5 Convergence curves of DDICS

and CS for f 2 function

图5 DDICS 和CS 求解f 2函数的收敛曲线

函数评价次数

121086420L o g 10(平均误差)

300000

100000

200000

CS DDICS

Fig.6 Convergence curves of DDICS

and CS for f 10 function

图6 DDICS 和CS 求解f 10函数的收敛曲线

王李进等:逐维改进的布谷鸟搜索算法2695

敛于指定误差阈值的成功次数越来越少,特别是在200维的空间上已无法成功地收敛于指定的误差阈值.反之, DDICS算法在100维和200维的空间上仍然有部分函数稳定收敛于指定误差阈值,体现出算法在求解该类函数

上具有较强的稳定性.随着维数的增加,借助于平均函值数误差,DDICS算法与CS算法相比仍有更高质量的解.

Table 4Mean function value errors with different dimensions

表4不同维数的平均函数值误差

D=50

函数CS DDICS函数CS DDICS

f1 3.61E?17±2.76E?17(50)? 9.68E?46±1.1E?45(50)f8 6.00E?15±1.04E?14(50)? 1.35E?32±1.11E?47(50)

f2 4.51E+01±1.99E+01? 5.22E?01±1.13E+00 f9 1.20E?16±9.69E?17(50)?0.00E+00±0.00E+00(50)

f3 1.91E?02±1.20E?01? 6.19E?14±5.52E?15(50)f10 6.93E+01±3.18E+01? 1.82E+00±2.60E+00

f4 1.48E?04±1.05E?03? 0.00E+00±0.00E+00(50)f11 6.31E?04±8.62E?04(50)? 6.58E?02±1.81E?02

f58.55E+01±1.10E+01? 0.00E+00±0.00E+00(50)f12 2.09E+01±4.67E?02≈ 2.09E+01±4.81E?02

f6 4.40E+03±3.78E+02? 1.84E?11±1.14E?12(50)f13 1.25E+02±1.16E+01? 0.00E+00±0.00E+00(50)

f7 3.88E?04±2.60E?03(16)? 9.42E?33±1.38E?48(50)???

D=100D=200

函数CS DDICS函数CS DDICS

f17.01E?07±2.41E?07(46)? 4.56E?21±3.23E?21(50)f19.34E?02±1.28E?02? 1.22E?07±5.92E?08(50)

f2 1.13E+02±3.18E+01? 7.71E?01±7.74E?01 f28.05E+02±1.52E+02? 1.01E+02±2.45E+01

f3 1.83E+00±3.42E?01? 1.50E?10±3.88E?11(50)f3 2.29E+00±1.33E?01? 5.88E?04±1.29E?04

f4 1.18E?05±3.69E?05? 0.00E+00±0.00E+00(50)f4 3.71E?02±1.60E?02? 1.17E?07±6.39E?08(50)

f5 2.86E+02±2.22E+01? 9.53E?02±2.46E?01(13)f58.68E+02±5.22E+01? 2.57E+01±2.16E+00

f6 1.40E+04±7.42E+02? 4.47E+02±1.14E+02 f6 3.35E+04±1.39E+03? 4.21E+03±2.84E+02

f7 3.10E?01±1.83E?01? 4.67E?23±3.06E?23(50)f77.87E?01±1.60E?01? 4.43E?10±2.12E?10(50)

f8 6.65E?04±1.23E?03(20)? 2.12E?21±1.32E?21(50)f8 1.36E+01±4.33E+00? 3.29E?08±1.55E?08(50)

3.4 与其他CS算法比较

表5给出了DDICS算法与其他改进的CS算法的性能比较.其中,维数D=30,规模NP=D,FES=10000×D,每

个算法独立运行50次,其他改进算法的参数根据其文献设置.从表中可知,各改进算法针对不同的函数,呈现的

性能不一样.针对f1函数,DDICS算法的性能弱于OLCS算法,但优于其他算法;而在f2函数上,DDICS算法的性

能最优.在复杂的多峰函数中,虽然DDICS算法优化f3函数的性能逊色于ICS和OLCS算法,但在其他的函数

上,DDICS算法获得的性能是最优的,特别是在f4,f5和f6函数上,DDICS算法稳定收敛于全局最优解.针对变换

或旋转的函数,DDICS算法优化f11函数的性能最不理想,但在f9,f10,f12和f13函数上的性能是最优的,而且在f9

和f13函数上,DDICS算法稳定收敛于全局最优解.借助于表中“?”的统计结果,DDICS算法总体上优于其他改进

算法,体现出较强的竞争力.

Table 5Comparison results of the DDICS algorithm and other CS algorithms (D=30)

表5 DDICS算法与其他CS算法的比较结果(D=30)

DDICS 函数ICS OLCS CSPSO

f1 6.13E?49±8.19E?49(50)? 3.20E?128±2.13E?127(50)? 1.03E?44±3.43E?44(50)? 3.15E?79±7.62E?79(50)

f29.51E+00±3.21E+00? 2.49E+00±8.45E?01? 7.21E?01±1.55E+00(4)≈7.20E?01±1.25E+00

f39.81E?15±3.25E?15(50)? 2.66E?15±0.00E+00(50)? 1.86E?02±1.32E?01(49)? 3.41E?14±3.93E?15(50)

f40.00E+00±0.00E+00(50)≈ 0.00E+00±0.00E+00(50)≈ 4.29E?03±5.00E?03(27)?0.00E+00±0.00E+00(50)

f5 1.71E+01±3.76E+00? 0.00E+00±0.00E+00(50)≈ 3.08E+01±1.07E+01? 0.00E+00±0.00E+00(50)

f67.53E+02±3.12E+02? 2.13E+03±2.87E+02? 4.22E+03±7.48E+02? 0.00E+00±0.00E+00(50)

f7 1.57E?32±5.53E?48(50)≈ 5.01E?30±7.48E?30(50)? 7.88E?02±1.37E?01(31)? 1.57E?32±5.53E?48(50)

f8 1.35E?32±1.11E?47(50)≈ 4.46E?29±5.83E?29(50)? 6.59E?04±2.64E?03(47)? 1.35E?32±1.11E?47(50)

f90.00E+00±0.00E+00(50)≈ 2.41E?26±6.21E?26(50)? 3.28E?28±3.52E?28(50)?0.00E+00±0.00E+00(50)

f10 1.28E+01±4.72E+00? 2.45E+01±1.99E+01? 4.50E+00±1.15E+01(23)≈ 4.18E+00±6.67E+00

f11 2.03E?03±2.94E?03 (48)? 4.72E?04±1.13E?03(50)? 7.40E?03±1.02E?15(50)? 1.97E?02±5.60E?03(1)

f12 2.09E+01±4.87E?02? 2.09E+01±5.31E?02? 2.09E+01±4.96E?02? 2.07E+01±5.95E?02

f13 1.67E+01±4.62E+00? 3.54E+01±6.64E+00? 1.55E+02±2.49E+01? 0.00E+00±0.00E+00(50)

? 7 8 10 ?

≈ 4 2 2 ?

? 2 3 1 ?

2696 Journal of Software软件学报 V ol.24, No.11, November 2013

3.5 与其他演化算法比较

DDICS算法与其他演化算法的比较结果见表6.其中,维数D=30,规模NP=D,FES=10000×D,每种算法独立

运行50次,其他演化算法的详细参数见文献[24,26?28].针对单峰函数,DDICS算法稍逊色于jDE算法,但优于其

他算法.在多峰函数中,DDICS算法优化f3的性能最差,但在优化其他5个函数时的性能最优.对于变换与旋转的

函数,DDICS算法性能优于CLPSO,稍优于jDE算法和DEahcSPX算法,略逊色于CoDE算法.表6中的“?”统计

结果说明DDICS算法总体上具有一定的竞争力.

Table 6Comparison results of the DDICS algorithm and other evolution algorithms (D=30)

表6 DDICS算法与其他演化算法的比较结果(D=30)

函数CLPSO DEahcSPX jDE CoDE DDICS f1 2.14E?40±1.54E?40? 1.75E?31±4.99E?31?0.00E+00±0.00E+00? 3.04E?67±4.41E?67? 3.15E?79±7.62E?79

f2 4.61E+00±6.32E+00? 4.52E+00±1.55E+01≈8.77E?01±1.67E+00≈ 3.19E?01±1.09E+00≈ 7.20E?01±1.25E+00

f37.60E?15±1.44E?15? 2.66E?15±0.00E+00? 6.68E?15±2.84E?15? 3.55E?15±0.00E+00? 3.41E?14±3.93E?15

f40.00E+00±0.00E+00≈ 2.07E?03±5.89E?03? 2.80E?03±8.85E?03? 1.48E?04±1.05E?03? 0.00E+00±0.00E+00

f50.00E+00±0.00E+00≈ 2.14E+01±1.23E+01? 2.19E?01±4.62E?01?0.00E+00±0.00E+00≈0.00E+00±0.00E+00

f6 4.74E+00±2.34E+01? 4.70E+02±2.96E+02?7.82E+01±8.83E+01? 2.37E+00±1.67E+01? 0.00E+00±0.00E+00

f7 1.57E?32±5.53E?48≈ 2.07E?02±8.46E?02? 2.07E?03±1.47E?02? 2.07E?03±1.47E?02? 1.57E?32±5.53E?48

f8 1.35E?32±1.11E?47≈ 1.71E?31±5.35E?31? 5.68E?02±2.82E?01? 1.35E?32±1.11E?47≈ 1.35E?32±1.11E?47

f90.00E+00±0.00E+00≈ 0.00E+00±0.00E+00≈8.05E?29±2.14E?28?0.00E+00±0.00E+00≈0.00E+00±0.00E+00

f108.95E+00±1.64E+01≈ 3.84E+00±3.75E+00≈7.97E?01±1.61E+00?7.97E?02±5.64E?01? 4.18E+00±6.67E+00

f11 4.51E?01±8.47E?02? 7.39E?03±6.32E?03? 1.75E?02±1.22E?02≈ 1.08E?02±1.00E?02? 1.97E?02±5.60E?03

f12 2.09E+01±5.72E?02? 2.09E+01±1.12E?01? 2.09E+01±5.89E?02? 2.02E+01±1.34E?01? 2.07E+01±5.95E?02

f130.00E+00±0.00E+00≈ 2.04E+01±8.19E+00? 3.38E?01±8.67E?01? 3.98E?02±2.81E?01? 0.00E+00±0.00E+00

5 8 8 5 ?

≈7 3 2 4 ?

1 2 3 4 ?

4 结束语

布谷鸟搜索算法是一种新颖的仿生优化算法,具有简单和高效的特点,并被成功地应用于经典理论研究和

工程应用领域.算法求解连续函数优化问题,采用整体更新评价解,由于存在维间互扰现象,算法的局部求精能

力和收敛速度将受到一定的影响.本文引入逐维更新评价策略,并改写偏好随机游动组件的步长公式,使得算法

在逐维更新过程中充分利用单维的进化信息,加强局部搜索,改善算法的收敛速度和解的质量.实验结果说明:

对于单峰函数、多峰函数以及变换旋转的函数,改进算法都能显著提高其收敛速度和解的质量.不同维数的实

验结果说明:随着维数的增加,逐维改进策略稳定改善算法的收敛速度和解的质量.与相关的改进CS算法及其

他演化算法相比,结果显示,改进算法在求解多维函数优化问题上是具有竞争力的.

所提出的改进策略虽然能够有效改善CS算法的性能,但针对无边界的函数却未能有效改善收敛速度和解

的质量;而且随着维数的增加,迭代将消耗大量的函数评价次数.因此,后续工作将考虑分块更新并评价的策略.

此外,还需要在更多的实际优化问题中应用改进算法进行分析并验证.

致谢在此,我们感谢本文的评审专家,同时也感谢向我们提供相关算法源代码以及实验数据的学者. References:

[1] Kennedy J, Eberhart RC. Particle swarm optimization. In: Proc. of the IEEE Int’l Conf. on Neural Networks. Piscataway: IEEE Inc.,

1995. 1942?1948. [doi: 10.1109/ICNN.1995.488968]

[2] Eberhart RC, Kennedy J. A new optimizer using particle swarm theory. In: Proc. of the 6th Int’l Symp. on Micro Machine and

Human Science. Piscataway: IEEE Inc., 1995. 39?43. [doi: 10.1109/MHS.1995.494215]

[3] Dorigo M, Maniezzo V, Colorni A. The ant system: Optimization by a colony of cooperating agents. IEEE Trans. on Systems, Man,

and Cybernetics, Part B, 1996,26(1):29?41. [doi: 10.1109/3477.484436]

王李进等:逐维改进的布谷鸟搜索算法2697

[4] Clerc M. Particle Swarm Optimization. Landon: Wiley-ISTE, 2006.

[5] Karaboga D. An idea based on honey bee swarm for numerical optimization. Technical Report, TR-06, Computer Engineering

Department, Engineering Faculty, Erciyes University, 2005.

[6] Chen H, Cui DW, Cui YA, Tao YQ, Liang K. Ethnic group evolution algorithm. Ruan Jian Xue Bao/Journal of Software, 2010,

21(5):978?990 (in Chinese with English abstract). https://www.wendangku.net/doc/ce16799673.html,/1000-9825/3484.htm [doi: 10.3724/SP.J.1001.2010.

03484]

[7] Yang XS, Deb S. Cuckoo search via Lévy flights. In: Abraham A, Carvalho A, Herrera F, et al., eds. Proc. of the World Congress

on Nature and Biologically Inspired Computing (NaBIC 2009). Piscataway: IEEE Publications, 2009. 210?214. [doi: 10.1109/ NABIC.2009.5393690]

[8] Yang XS, Deb S. Engineering optimisation by cuckoo search. Int’l Journal of Mathematical Modeling and Numerical Optimisation,

2010,1(4):330?343. [doi: 10.1504/IJMMNO.2010.03543]

[9] Yang XS, Deb S. Multi-Objective cuckoo search for design optimization. Computers & Operations Research, 2013,40(6):

1616?1624. [doi: 10.1016/j.cor.2011.09.026]

[10] Civicioglu P, Besdok E. A conceptual comparison of the cuckoo search, particle swarm optimization, differential evolution and

artificial bee colony algorithms. Artificial Intelligence Review, 2013,39(4):315?346. [doi: 10.1007/s10462-011-9276-0]

[11] Walton S, Hassan O, Morgan K, Brown MR. Modified cuckoo search: A new gradient free optimization algorithm. Chaos, Solitons

& Fractals, 2011,44(9):710?718. [doi: 10.1016/j.chaos.2011.06.004]

[12] Tuba M, Subotic M, Stanarevic N. Modified cuckoo search algorithm for unconstrained optimization problems. In: Leandre R,

Demiralp M, Tuba M, et al., eds. Proc. of the European Computing Conf. (ECC 2011). Athens: WSEAS Press, 2011. 263?268. [13] Valian E, Mohanna S, Tavakoli S. Improved cuckoo search algorithm for global optimization. Int’l Journal of Communications and

Information Technology, 2011,1(1):31?44.

[14] Layeb A, Boussalia SR. A novel quantum inspired cuckoo search algorithm for bin packing problem. Int’l Journal of Information

Technology and Computer Science, 2012,4(5):58?67. [doi: 10.5815/ijitcs.2012.05.08]

[15] Ghodrati A, Lotfi S. A hybrid CS/PSO algorithm for global optimization. In: Pan JS, Chen SM, Nguyen NT, eds. Proc. of the

ACIIDS 2012, Part III. LNAI 7198, Berlin, Heidelberg: Springer-Verlag, 2012. 89?98. [doi: 10.1007/978-3-642-28493-9_11] [16] Wang F, He XS, Luo LG, Wang Y. Hybrid optimization algorithm of PSO and cuckoo search. In: Proc. of the 2nd Int’l Conf. on

Artificial Intelligence, Management Science and Electronic Commerce (AIMSEC). Piscataway: IEEE Inc., 2011. 1172?1175. [doi:

10.1109/AIMSEC.2011.6010750]

[17] Srivastava PR, Khandelwal R, Khandelwal S, Kumar S, Ranganatha SS. Automated test data generation using cuckoo search and

tabu search (CSTS) algorithm. Journal of Intelligent Systems, 2012,21(2):195?224. [doi: 10.1515/jisys-2012-0009]

[18] Li XT, Yin MH. Parameter estimation for chaotic systems using the cuckoo search algorithm with an orthogonal learning method.

Chinese Physics B, 2012,21(5):050507-1?050507-6. [doi: 10.1088/1674-1056/21/5/050507]

[19] Li XT, Wang JN, Yin MH. Enhancing the performance of cuckoo search algorithm using orthogonal learning method. Neural

Computing & Applications. Publised online: 09 February 2013. [doi: 10.1007/s00521-013-1354-6]

[20] Zhong YW, Liu X, Wang LJ, Wang CY. Particle swarm optimization algorithm with iterative improvement strategy for multi-

dimensional function optimization problems. Int’l Journal of Innovative Computing and Application, 2012,4(3-4):223?232. [doi:

10.1504/IJICA.2012.050051]

[21] Hansen N, Ostermeier A. Completely derandomized self-adaptation in evolution strategies. Evolutionary Computation, 2001,9(2):

159?195. [doi: 10.1162/106365601750190398]

[22] Deb K, Anand A, Joshi D. A computationally efficient evolutionary algorithm for real-parameter optimization. Evolutionary

Computation, 2002,10(4):371?395. [doi: 10.1162/106365602760972767]

[23] Shang YW, Qiu YH. A note on the extended rosenbrock function. Evolutionary Computation, 2006,14(1):119?126. [doi: 10.1162/

106365606776022733]

[24] Noman N, Iba H. Accelerating differential evolution using an adaptive local search. IEEE Trans. on Evolutionary Computation,

2008,12(1):107?125. [doi: 10.1109/TEVC.2007.895272]

2698 Journal of Software软件学报 V ol.24, No.11, November 2013

[25] Suganthan PN, Hansen N, Liang JJ, Deb K, Chen YP, Auger A, Tiwari S. Problem definitions and evaluation criteria for the

CEC2005 special session on real-parameter optimization. Technical Report, KanGAL Report #2005005, Singapore: Kanpur Genetic Algorithms Laboratory, Nanyang Technological University, 2005.

[26] Brest J, Greiner S, Boskovic B, Mernik M, Zumer V. Self-Adapting control parameters in differential evolution: A comparative

study on numerical benchmark problems. IEEE Trans. on Evolutionary Computation, 2006,10(6):646?657. [doi: 10.1109/TEVC.

2006.872133]

[27] Liang JJ, Qin AK, Suganthan PN, Baskar S. Comprehensive learning particle swarm optimizer for global optimization of

multimodal functions. IEEE Trans. on Evolutionary Computation, 2006,10(3):281?295. [doi: 10.1109/TEVC.2005.857610]

[28] Wang Y, Cai ZX, Zhang QF. Differential evolution with composite trial vector generation strategies and control parameters. IEEE

Trans. on Evolutionary Computation, 2011,15(1):55?66. [doi: 10.1109/TEVC.2010.2087271]

附中文参考文献:

[6] 陈皓,崔杜武,崔颖安,陶永芹,梁琨.族群进化算法.软件学报,2010,21(5):978?990. https://www.wendangku.net/doc/ce16799673.html,/1000-9825/3484.htm [doi:

10.3724/SP.J.1001.2010.03484]

王李进(1977－),男,福建泉州人,博士,副教授,主要研究领域为计算智能及应用.

E-mail: lijinwang@https://www.wendangku.net/doc/ce16799673.html,

钟一文(1968－),男,博士,教授,CCF会员,主要研究领域为计算智能,生物信息学.

E-mail: yiwzhong@https://www.wendangku.net/doc/ce16799673.html,

尹义龙(1972－),男,博士,教授,博士生导

师,CCF高级会员,主要研究领域为机器学

习,数据挖据,图像处理.

E-mail: ylyin@https://www.wendangku.net/doc/ce16799673.html,

基于优化问题的多目标布谷鸟搜索算法

基于优化问题的多目标布谷鸟搜索算法关键字：布谷鸟搜索、元启发式算法、多目标、最优化摘要：在工程设计方面，很多问题都是典型的多目标问题，而且，都是复杂的非线性问题。现在我们研究的优化算法就是为了解决多目标化的问题，使得与单一目标问题的解决有明显的区别，计算结果和函数值有可能会增加多目标问题的特性。此时，元启发式算法开始显示出自己在解决多目标优化问题中的优越性。在本篇文章中，我们构造了一个新的用于解决多目标优化问题的算法——布谷鸟搜索算法。我们通过一系列的多目标检验函数对其的有效性已经做出来检验，发现它可以应用于解决结构设计等问题中去，例如：光路设计、制动器设计等。另外，我么还对该算法的主要特性和应用做了相关的分析。 1.简介在设计问题中经常会考虑到很多多重的复杂问题，而且这些问题往往都具有很高的非线性性。在实际中，不同的目标之间往往会有分歧和冲突，有时候，实际的最优化解决方案往往不存在，而一些折中的和近似的方案往往也可以使用。除了这些挑战性和复杂性以外，设计问题还会受到不同设计目标的约束，而且还会被设计代码、设计标准、材料适应性、和可用资源的选择，以及

设计花费等所限制，甚至是关于单一目标的全局最优问题也是如此，如果设计函数有着高度的非线性性，那么全局最优解是很难达到的，而且，很多现实世界中的问题经常是NP-hard的，这就意味着没有一个行之有效的算法可以解决我们提出的问题，因此，对于一个已经提出的问题，启发式算法和科学技术与具体的学科交叉知识经常被用于其中，用来作为解决问题的向导。另一方面，元启发算法在解决此类优化问题方面是非常有效的，而且已经在很多刊物和书籍中得以运用，与单一目标的优化问题相反的是，多目标优化问题具有典型的复杂性和困难性，在单一目标的优化问题中我们必须去找出一个最优化的解决方法，此方法在问题的解决中存在着一个单一的点，并且在此问题中不包括那些多重的、平均优化的点，对于一个多目标的优化问题，存在着名为Pareto-front的多重的复杂的优化问题，为了了解我们所不熟悉的Pareto-front问题，我们需要收集并整理很多不同的方法，从而，此计算结果将会随着近似解的变化、问题的复杂度和解决方法的多样性而有所变化甚至增加。在理论上，此类解决方法应包括问题并且应相对的有一致无分歧的分布情况，然而，还没有科学的方法可以证明这种解决方法可以在实际中得以应用。从问题的出发点我们可以得知，算法可以在单一目标优化问题中运行的很好，但是却不能在多目标的优化问题中直接的运用，除非是在特殊的环境与条件下才可以应用。例如，使用一些

基于优化问题的多目标布谷鸟搜索算法

布谷鸟算法

今天我要讲的内容是布谷鸟算法，英文叫做Cuckoo search (CS algorithm)。首先还是同样，介绍一下这个算法的英文含义，Cuckoo是布谷鸟的意思，啥是布谷鸟呢，是一种叫做布谷的鸟，o(∩_∩)o ，这种鸟她妈很懒，自己生蛋自己不养，一般把它的宝宝扔到别的种类鸟的鸟巢去。但是呢，当孵化后，遇到聪明的鸟妈妈，一看就知道不是亲生的，直接就被鸟妈妈给杀了。于是这群布谷鸟宝宝为了保命，它们就模仿别的种类的鸟叫，让智商或者情商极低的鸟妈妈误认为是自己的亲宝宝，这样它就活下来了。Search指的是搜索，这搜索可不是谷歌一下，你就知道。而是搜索最优值，举个简单的例子，y=(x-0.5)^2+1，它的最小值是1，位置是(0.5,1)，我们要搜索的就是这个位置。现在我们应该清楚它是干嘛的了吧，它就是为了寻找最小值而产生的一种算法，有些好装X的人会说，你傻X啊，最小值不是-2a/b吗，用你找啊? 说的不错，确实是，但是要是我们的函数变成y=sin(x^3+x^2)+e^cos(x^3)+log(tan(x) +10，你怎么办吶？你解不了，就算你求导数，但是你知道怎么解导数等于0吗？所以我们就得引入先进的东西来求最小值。为了使大家容易理解，我还是用y=(x-0.5)^2+1来举例子，例如我们有4个布谷鸟蛋（也就是4个x坐标），鸟妈妈发现不是自己的宝宝的概率是0.25，我们x的取值范围是[0,1]之间，于是我们就可以开始计算了。目标：求x在[0,1]之内的函数y=(x-0.5)^2+1最小值（1）初始化x的位置，随机生成4个x坐标，x1=0.4，x2=0.6，x3=0.8，x4 =0.3 ——> X=[0.4, 0.6 ,0.8, 0.3]

布谷鸟算法

布谷鸟算法 1、概述布谷鸟搜索算法[CuckooSearch（CS）],也叫杜鹃搜索,是由剑桥大学Xin-SheYang(杨新社)教授和S.Deb于2009年提出的一种新兴启发算法CS算法通过模拟某些种属布谷鸟(CuckooSpecies)的寄生育雏(BroodParasitism)来有效地求解最优化问题的算法.同时，CS也采用相关的Levy飞行搜索机制。 2、优点全局搜索能力强、选用参数少、搜索路径优、多目标问题求解能力强，以及很好的通用性、鲁棒性等特点，同时其特有的莱维特性能够有效地扩大搜索范围，是一种高效的全局随机搜索算法．并且实例测试结果证明了它比遗传算法、粒子群算法、萤火虫算法具有更高寻优性能。布谷鸟搜索算法凭借参数少，算法简单，易于实现的特点被广泛应用在各个领域，是群体智能算法中的一个新亮点 3、应用领域布谷鸟算法自提出之后引起了许多学者的关注，并在许多项目调度、工程优化问题、求解置换流水车间调度和计算智能方面得到了应用。在工程设计领域，布谷鸟算法对于一系列连续优化问题如弹簧设计和焊接梁设计等问题有着优于其他算法的性能。Vazquez利用布谷鸟算法训练脉冲神经网络模型，Chifu等人利用布谷鸟算法优化语义

Web服务组合流程, Bhargava等人在求解复杂相平衡问题中，用布谷鸟算法获得了可靠的热力学计算。在组合优化问题方面，Tein和Ramli针对护士调度问题提出了离散化的布谷鸟算法，布谷鸟算法还成功的应用于软件测试中数据生成程序问题独立路径的产生。Speed修改了CS并成功应用于处理大规模问题。Moravej和Akhlaghi用CS研究了分布式网络中的DG分配问题。对于多目标问题的研究，Deb针对工程应用提出了多目标CS算法，Simon等人则利用CS算法针对多目标调度问题取得了很好的效果。综上所述，虽然布谷鸟算法于2009年才刚刚提出，但己经被成功应用到各个领域的优化问题中，布谷鸟算法可以求解大部分优化问题，或者是可以转化为优化问题进行求解的问题。 4、应用延伸 4.1车辆调度、路径最优《求解带时间窗车辆路径问题的混合智能算法》文中提出：基于布谷鸟搜索算法和单亲遗传算法，设计了一种求解带时间窗车辆路径问题的混合智能算法。该算法首先对客户位置进行聚类分析，然后再进行各区域的路径优化。混合智能算法不仅改进了布谷鸟搜索算法中当鸟卵被鸟窝主人发现后需要随机改变整个鸟窝位置的操作，同时引入的单亲遗传算法加快了最优配送路线的搜索速度。 4.2 项目调度

布谷鸟搜索算法简介

布谷鸟搜索算法维基百科，自由的百科全书布谷鸟搜索（Cuckoo Search，缩写 CS），也叫杜鹃搜索，是由剑桥大学杨新社（音译自：Xin-She Yang）教授和S.戴布（S.Deb）于2009年提出的一种新兴启发算法[1]。 CS算法是通过模拟某些种属布谷鸟的寄生育雏（Brood Parasitism），来有效地求解最优化问题的算法。同时，CS也采用相关的Levy飞行搜索机制。研究表明，布谷鸟搜索比其他群体优化算法更有效。布谷鸟搜索布谷鸟搜索（CS）使用蛋巢代表解。最简单情况是，每巢有一个蛋，布谷鸟的蛋代表了一种新的解。其目的是使用新的和潜在的更好的解，以取代不那么好的解。该算法基于三个理想化的规则： ?每个杜鹃下一个蛋，堆放在一个随机选择的巢中； ?最好的高品质蛋巢将转到下一代； ?巢的数量是固定的，布谷鸟的蛋被发现的概率为。实际应用布谷鸟搜索到工程优化问题中的应用已经表现出其高优效率，经过几年的发展，为了进一步提高算法的性能，CS算法的很多变体与改进逐步涌现。瓦尔顿（Walton）等提出了修正布谷鸟搜索（Modified Cuckoo Search，缩写 MCS）；伐立安（Valian）等提出了一种可变参数的改进CS算法，提高了收敛速度，并将改进算法应用于前馈神经网络训练中；马里切尔凡姆（Marichelvam）将一种混合CS算法应用于流水车间调度问题求解中；钱德拉塞卡兰（Chandrasekaran）等将集成了模糊系统的混合CS算法应用于机组组合问题。杨（Yang）和戴布（Deb）提出多目标布谷鸟搜索（Multiobjective Cuckoo Search，缩写 MOCS），应用到工程优化并取得很好的效果；詹（Zhang）等通过对种群分组，并根据搜索的不同阶段对搜索步长进行预先设置，提出了修正调适布谷鸟搜索（Modified Adaptive Cuckoo Search，缩写 MACS），提高了CS的性能。

基于K―means和布谷鸟算法的流程模型聚类

基于K―means和布谷鸟算法的流程模型聚类摘要：流程模型聚类是流程管理领域的一个热门话题。本文提出一种基于布谷鸟算法的K-means算法，该算法弥补了K-means算法的依赖初始解、易陷入局部最优等缺点。本文从流程模型结构性能、成本、效率、顾客满意度以及质量等五个方面模拟数据集，并选择权重较高的属性进行试验操作，结果表明算法的具有较高的可行性和有效性。 Abstract：Process model clustering is a hot topic in the field of process management. This paper presents a new K-means algorithm based on cuckoo algorithm，which compensates drawbacks of traditional K-means algorithm，such as relying on initial solution and being easily trapped in local optimums. In this paper，simulated data sets consist of five features （process model structure performance，cost，efficiency，customer satisfaction and quality），but experiments are conducted by only two indicators with higher weight. Experimental results show that the method has relatively higher feasibility and effectiveness. 关键词：布谷鸟算法;K-means算法;流程模型聚类 Key words：cuckoo algorithm;K-means;process model

改进二进制布谷鸟搜索算法求解TSP问题

改进二进制布谷鸟搜索算法求解TSP问题：According to the characteristics TSP problem ，we design an improved TSP problem solving binary cuckoo algorithm. The algorithm uses a binary code string showing the location of the nest ，the nest of the cuckoo to find a new flight path of Levi binary code conversion ，this paper introduces the binary coded control coefficient transform binary coding mixed update ，the paper retains the cuckoo egg method being eliminated mechanisms ，and introduces greedy thought ，this article will search for new and efficient cuckoo （CS）algorithm to improve a binary search cuckoo （BCS）algorithm. The BCSalgorithm for solving TSP. By testing multiple sets of data ，compared to "TSP problem of data collection catalog （standard test set ），" The results show that better than tabu search algorithm ，genetic algorithm ，ant colony algorithm ，particle swarm optimization. Keywords：Binary ；Cuckoo search algorithm ；traveling salesman problem ；greedy algorithm 1 引言 TSP（旅行商）问题是指已知n个城市之间的相互距离，寻

逐维改进的布谷鸟搜索算法

软件学报ISSN 1000-9825, CODEN RUXUEW E-mail: jos@https://www.wendangku.net/doc/ce16799673.html, Journal of Software,2013,24(11):2687?2698 [doi: 10.3724/SP.J.1001.2013.04476] https://www.wendangku.net/doc/ce16799673.html, +86-10-62562563 ?中国科学院软件研究所版权所有. Tel/Fax: ? 逐维改进的布谷鸟搜索算法王李进1,2, 尹义龙2, 钟一文1 1(福建农林大学计算机与信息学院,福建福州 350002) 2(山东大学计算机科学与技术学院,山东济南 250101) 通讯作者: 尹义龙, E-mail: ylyin@https://www.wendangku.net/doc/ce16799673.html,, https://www.wendangku.net/doc/ce16799673.html,/ylyin.html 摘要: 布谷鸟搜索(cuckoo search,简称CS)算法是一种新兴的仿生智能算法,对解采用整体更新评价策略.在求解多维函数优化问题时,由于各维之间相互干扰,采用整体更新评价策略将恶化算法的收敛速度和解的质量.为了弥补此缺陷,提出了基于逐维改进的布谷鸟搜索算法.在改进算法的迭代过程中,针对解采用逐维更新评价策略.该策略将各维的更新值与其他维的值组合成新的解,并采用贪婪方式接受能够改善解质量的更新值.实验结果说明,改进策略能够有效地提高CS算法的收敛速度并改善解的质量.与相关的改进布谷鸟搜索算法以及其他演化算法的比较结果表明,改进算法在求解连续函数优化问题上是具有竞争力的. 关键词: 布谷鸟搜索算法;逐维改进;函数优化;多维函数;干扰现象中图法分类号: TP183文献标识码: A 中文引用格式: 王李进,尹义龙,钟一文.逐维改进的布谷鸟搜索算法.软件学报,2013,24(11):2687?2698.https://www.wendangku.net/doc/ce16799673.html,/ 1000-9825/4476.htm 英文引用格式: Wang LJ, Yin YL, Zhong YW. Cuckoo search algorithm with dimension by dimension improvement. Ruan Jian Xue Bao/Journal of Software, 2013,24(11):2687?2698 (in Chinese).https://www.wendangku.net/doc/ce16799673.html,/1000-9825/4476.htm Cuckoo Search Algorithm with Dimension by Dimension Improvement WANG Li-Jin1,2, YIN Yi-Long2, ZHONG Yi-Wen1 1(School of Computer and Information Science, Fujian Agriculture and Forestry University, Fuzhou 350002, China) 2(School of Computer Science and Technology, Shandong University, Ji’nan 250101, China) Corresponding author: YIN Yi-Long, E-mail: ylyin@https://www.wendangku.net/doc/ce16799673.html,, https://www.wendangku.net/doc/ce16799673.html,/ylyin.html Abstract: Cuckoo search (CS) is a new nature-inspired intelligent algorithm which uses the whole update and evaluation strategy on solutions. For solving multi-dimension function optimization problems, this strategy may deteriorate the convergence speed and the quality of solution of algorithm due to interference phenomena among dimensions. To overcome this shortage, a dimension by dimension improvement based cuckoo search algorithm is proposed. In the progress of iteration of improved algorithm, a dimension by dimension based update and evaluation strategy on solutions is used. The proposed strategy combines an updated value of one dimension with values of other dimensions into a new solution, and greedily accepts any updated values that can improve the solution. The simulation experiments show that the proposed strategy can improve the convergence speed and the quality of the solutions effectively. Meanwhile, the results also reveal the proposed algorithm is competitive for continuous function optimization problems compared with other improved cuckoo search algorithms and other evolution algorithms. Key words: cuckoo search algorithm; dimension by dimension improvement; function optimization; multi-dimension function; interference phenomena 自20世纪以来,人们利用蚂蚁、鸟类等群居生物的自组织行为,提出了粒子群算法(particle swarm ?基金项目: 新世纪优秀人才支持计划(NCET-11-0315); NSFC-广东联合基金重点支持项目(U1201258); 福建省自然科学基金 (2011J05044, 2013J01216); 山东省自然科学杰出青年基金(2013JQE27038) 收稿时间:2013-04-27; 修改时间: 2013-07-17; 定稿时间: 2013-08-27

布谷鸟算法的杂七杂八

关于布谷鸟算法的相关说法又是一个不大常见的拥有一定的自带机制可以对付局部极小值点的算法，但是这个年代还是不大多见。布谷鸟搜索（Cuckoo Search，CS）是由Xin-She Yang 和Suash Deb 于2009 年开发的自然启发式算法。CS 基于布谷鸟的寄生性育雏（brood parasitism，又巢寄生）行为。该算法可以通过所谓的Levy 飞行来增强，而不是简单的各向同性随机游走。研究表明，该算法可能比遗传算法、PSO 以及其他算法更有效。不过这也是看具体的数据集的。 1 关于鸟类的育雏行为布谷鸟（杜鹃）是一种神奇的鸟，不仅因为它们动听的啼鸣，还因它们的积极的繁殖策略。杜鹃科中的犀鹃（Ani Cuckoo）和圭拉鹃（Guira Cuckoo），将它们的蛋放在其他鸟的巢中，通过去除其他鸟（寄主）的蛋来增加自己蛋的孵化几率。有相当多种类的鸟都有将自己的蛋放在其他鸟的巢中这种寄生性育雏行为。这种方法使得一些科学家突发奇想，于是就有了现在的布谷鸟算法寄生性育雏分为三种：种内寄生（intraspecific brood parasitism）、合作养育（cooperative breeding）和巢占据（nest takeover）。一些寄主鸟会与入侵的布谷鸟发生直接冲突。如果一个寄主鸟发现这些蛋不是他们自己的，那么他们要么将这些外来蛋清除掉。这是比较温和的生物，有的物种就比较暴脾气，他们直接放弃整个巢穴，在别处建造一个新的巢。一些布谷鸟，例如New World brood-parasitic Tapera，已经进化成这样一种方式，雌杜鹃通常非常善于模仿几种特定寄主的卵的颜色和纹理。这减少了它们蛋被遗弃的可能性，从而增加了它们的繁殖力。这种物种对产蛋时机的把握也非常到位。布谷鸟通常会选择那些寄主刚刚产下自己蛋的巢。一般来说，布谷鸟蛋的孵化时间要比寄主蛋的孵化时间要早一些。一旦第一只布谷鸟雏鸟孵化出来，第一个本能的动作就是通过盲目地推动将其他蛋从巢中推出，从而增加寄主对布谷鸟雏鸟的食物供给。研究还表明，杜鹃雏鸟还可以模仿寄主雏鸟的叫声，以获得更多的被喂食机会。 2 Levy飞行 Levy是征收的意思，同著名的枪战动漫《黑礁》的女主Revy要区分开。另一方面，各种研究表明，许多动物和昆虫的飞行行为表现出了具有幂律规律的Lévy 飞行的典型特征。Reynolds 和Frye 最近的一项研究表明，如同很多像我一样的RTS玩家的习惯一样，很多人在开始探路开视野的时候喜欢无规律的乱画路径进行探路操作，在生物圈中，有的生物也有这种奇怪的习惯，诸如果蝇（或Drosophila melanogaster）利用一系列直线飞行路径和突然的90°转弯来探索景观，从而产生Lévy飞行式的间歇无标度搜索模式。针对人类行为的研究也表明，如Ju hoansi 狩猎采集觅食模式等也表现出了Lévy 飞行的典型特征。即使是光线也与Lévy 飞行有联系。另外，该行为已被应用于优化搜索，结果表明其具有潜力。