基于量子策略的布谷鳥搜索算法研究

基于量子策略的布谷鳥搜索算法研究

王健,丁學(xué)明,董新燕

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院,上海200093)

摘要針對(duì)基本布谷鳥搜索算法存在局部搜索能力較弱、收斂速度偏慢和精度較低等缺點(diǎn),文中研究了基于量子策略的布谷鳥搜索算法。借助于量子策略使布谷鳥的尋巢搜索行為具有多樣性,并在此基礎(chǔ)上提出3種改進(jìn)局部搜索能力的措施:引入慣性權(quán)值、自適應(yīng)減小鳥窩主人發(fā)現(xiàn)外來鳥蛋的概率、隨機(jī)擾動(dòng)增量的優(yōu)化,并通過對(duì)兩類基準(zhǔn)測(cè)試函數(shù)的尋優(yōu)結(jié)果對(duì)比,證明提出的改進(jìn)融合算法精度更高,且具有更大的優(yōu)勢(shì)。

關(guān)鍵詞CS算法;量子策略;基準(zhǔn)函數(shù);局部搜索

收稿日期:2015-04-24

作者簡(jiǎn)介:王健(1990—),男,碩士研究生。研究方向:優(yōu)化算法等。E-mail:15216772095@163.com

doi:10.16180/j.cnki.issn1007-7820.2015.12.011

中圖分類號(hào)TP273.4文獻(xiàn)標(biāo)識(shí)碼A

Research on Cuckoo Search Algorithm Based on Quantum Mechanism

WANG Jian,DING Xueming,DONG Xinyan

(School of Optical-Electrical and Computer Engineering,University of Shanghai for

Science and Technology,Shanghai 200093,China)

AbstractAiming at the disadvantages of the basic cuckoo search(CS) algorithm such as weaker local search ability,slower convergence rate and poorer optimization precision,this paper studies the quantum inspired cuckoo search algorithm.Firstly,we enabled the cuckoos with heterogeneous search behaviors towards the nests with the help of quantum mechanism.Then three measures which can improve the cuckoos’ local search capability were introduced on this basis,namely the introduction of a similar inertia weight to the equation of renewal of the nests positions,an adaptively decreased probability of the cuckoo nests being replaced with a randomly generated new one,and the improvement of increment with a random disturbance.A graphical comparison of the original CS algorithm and the quantum one used for optimization of two kinds of benchmark functions shows that the latter algorithm possesses greater advantages over the original one with a better precision.

Keywordscuckoo search algorithm;quantum mechanism;benchmark functions;local search

智能優(yōu)化算法的出現(xiàn)與發(fā)展,較好地解決了生產(chǎn)生活中的復(fù)雜優(yōu)化問題,為這些困難問題的求解提供一條新途徑。相對(duì)于傳統(tǒng)算法而言,智能算法以其高效性、靈活性、易用性,迅速被工程領(lǐng)域所接受及認(rèn)可[1]。

布谷鳥搜索算法(Quantum Inspired Cuckoo Search Algorithm,QCS)[2]是一種新穎的仿生優(yōu)化算法,主要基于布谷鳥的巢寄生繁殖機(jī)理和列維飛行(Lévy Flights)搜索原理兩方面,具有參數(shù)少、尋優(yōu)能力強(qiáng)的特點(diǎn),并被成功地應(yīng)用于經(jīng)典理論研究和工程應(yīng)用領(lǐng)域。

與此同時(shí),計(jì)算機(jī)科學(xué)與量子力學(xué)結(jié)合的前沿學(xué)科——量子信息技術(shù),近年來已有眾多杰出成果,其中量子機(jī)制與智能優(yōu)化方法相結(jié)合產(chǎn)生一系列的智能量子優(yōu)化算法,成為現(xiàn)代智能算法的里程碑,為工程生產(chǎn)打下了理論研究基礎(chǔ)[3]。

量子優(yōu)化算法是自量子計(jì)算發(fā)展后產(chǎn)生的一個(gè)新興領(lǐng)域,將傳統(tǒng)的智能優(yōu)化算法與量子計(jì)算結(jié)合,提高智能優(yōu)化算法的求解性能,有著廣闊的應(yīng)用前景。Han等人在文獻(xiàn)[4]用量子位編碼的方式編碼染色體,同時(shí)依賴量子旋轉(zhuǎn)門作為更新染色體的方式,并將其用于經(jīng)典的0-1背包問題,實(shí)驗(yàn)結(jié)果表明量子遺傳算法具有優(yōu)良的優(yōu)化效果。Sun等人提出一種具有量子行為的量子粒子群算法[5],以量子力學(xué)為參考,將搜索空間中的粒子看作是具有量子行為的個(gè)體。

本文將量子策略引入布谷鳥搜索算法中,結(jié)合量子計(jì)算與布谷鳥搜索算法的優(yōu)勢(shì),并對(duì)融合算法提出3種改進(jìn)的措施,通過4個(gè)不同類型的基準(zhǔn)函數(shù)的測(cè)試,表明改進(jìn)算法相對(duì)于原始算法而言具備較大的優(yōu)勢(shì)。

1布谷鳥算法

布谷鳥搜索算法是Yang和Deb模擬布谷鳥選巢產(chǎn)卵和昆蟲的列維飛行習(xí)性的行為,提出的一種具有全局收斂性的新型仿生智能搜索算法。研究表明:生物的覓食、尋巢等路線實(shí)際上是一種高效的隨機(jī)游走過程,將這種行為運(yùn)用到工程優(yōu)化問題上有著潛在的能力[6]。

Yang和Deb基于布谷鳥繁殖策略,建立CS算法的3條理想規(guī)則[2]:

規(guī)則1每只布谷鳥一次只產(chǎn)一顆卵,并隨機(jī)選擇一個(gè)鳥巢存放;

規(guī)則2好的鳥巢將會(huì)被保留至下一代;

規(guī)則3可用鳥巢的數(shù)量固定,且鳥巢中外來卵被發(fā)現(xiàn)的概率是Pa∈[0,1]。

基于上述規(guī)則,基本CS算法模擬布谷鳥尋找適合產(chǎn)卵的鳥窩位置的流程如下:

(1)在d維解空間隨機(jī)產(chǎn)生n個(gè)鳥窩Nesti=(xi1,xi2,…,xid),1≤i≤n,計(jì)算其適應(yīng)度值f(Nesti),1≤i≤n,保留適應(yīng)度最優(yōu)的鳥窩位置進(jìn)行迭代。

(2)設(shè)鳥窩主人發(fā)現(xiàn)外來鳥蛋的概率為Pa,隨機(jī)生成一個(gè)均勻分布的數(shù)r∈[0,1],若r>Pa,則對(duì)所發(fā)現(xiàn)的鳥窩位置進(jìn)行擾動(dòng),否則不變。

(3)每次迭代按照如下公式進(jìn)行鳥窩位置更新,每個(gè)鳥窩位置與上一代鳥窩對(duì)應(yīng)位置進(jìn)行比較,保留適應(yīng)度最高的鳥窩位置

(1)

(2)

上式,λ-1一般記為β,其取值范圍是0<β<2,在原始算法[9]中取β=1.5,參數(shù)μ、v為正態(tài)分布隨機(jī)數(shù),服從式(3)所示的正態(tài)分布;式(3)所對(duì)應(yīng)的正態(tài)分布的標(biāo)準(zhǔn)差σμ、σv的取值見式(4)所示

(3)

(4)

2量子策略

在量子空間中,粒子的速度和位置不能同時(shí)確定,因此粒子的狀態(tài)必須用所謂的波函數(shù)Ψ(X,t)來描述,其中X=(x,y,z)是粒子在三維空間中的位置向量。波函數(shù)的物理意義是:波函數(shù)模的平方是粒子在空間某點(diǎn)出現(xiàn)的概率密度,即[10]

dxdydz=Qdxdydz

(5)

其中,Q為概率密度函數(shù),且滿足歸一化條件。在量子空間中粒子運(yùn)動(dòng)的動(dòng)力學(xué)方程是Schr?dinger方程為

(6)

其中,i是虛數(shù)單位;?稱為普朗克常數(shù);是拉普拉斯算子;m是粒子的質(zhì)量;V(X)是粒子所在的勢(shì)場(chǎng)。

現(xiàn)假定布谷鳥群系統(tǒng)是一個(gè)量子個(gè)體系統(tǒng),每一個(gè)個(gè)體具有量子行為,由波函數(shù)來描述其狀態(tài)。根據(jù)對(duì)CS算法中個(gè)體收斂行為的分析,必然存在以點(diǎn)pi為中心某種形式的吸引勢(shì)。為簡(jiǎn)單起見,先考慮單個(gè)個(gè)體在一維空間中運(yùn)動(dòng)的情形,且將pi記為p,個(gè)體位置為X。在p點(diǎn)建立一維δ勢(shì)阱,其勢(shì)能函數(shù)表示為

V(X)=-γδ(X-p)=-γδ(Y)

(7)

其中,Y=X-p。

故粒子在δ勢(shì)阱中的定態(tài)Schr?dinger方程為[11]

(8)

其中,E是粒子的能量。于是得到推論:粒子在以p點(diǎn)為中心的一維δ勢(shì)阱中運(yùn)動(dòng),對(duì)應(yīng)的定態(tài)Schr?dinger方程的解為[5]

(9)

其中,L=1/β=?2/mγ。

3改進(jìn)布谷鳥搜索算法

(10)

其中,η是(0,1)上的均勻分布隨機(jī)數(shù)。

(11)

其中,δ是控制參數(shù)。

文獻(xiàn)[12]在基本CS算法的基礎(chǔ)上引入基于量子策略的多行為搜索方式

(12)

(13)

據(jù)文獻(xiàn)[2],CS算法具有顯著的高效性,主要得益于兩個(gè)關(guān)鍵的部分:列維飛行隨機(jī)游動(dòng)和“差”的鳥巢的更換策略,二者平衡算法的局部搜索和全局搜索。其中更換策略具體是

(14)

其中,ran是一個(gè)介于(0,1)的均勻分布隨機(jī)數(shù),r′=rand·(xi∈[1,n]-xj∈[1,n]),xi∈[1,n]和xj∈[1,n]是從整個(gè)群體隨機(jī)取出的鳥巢的位置向量。

針對(duì)上文提到的局部尋優(yōu)能力差等劣勢(shì),提出以下3種改進(jìn)措施:

(1)借鑒文獻(xiàn)[13]粒子群優(yōu)化算法(Particles Swarm Optimization,PSO)的慣性權(quán)重策略,引入ω參數(shù)

ω=ωmax-(ωmax-ωmin)·iter/iter_max

(15)

其中,iter表示當(dāng)前迭代次數(shù);iter_max表示最大迭代次數(shù),而ω的兩個(gè)參數(shù)根據(jù)經(jīng)驗(yàn)值設(shè)定為ωmax=0.9,ωmin=0.4。隨著進(jìn)化代數(shù)iter的增大,ω逐漸減小,并將ω用于式(12)的第一個(gè)分式,其余兩個(gè)分式不變。即

(16)

分析可知:在算法尋優(yōu)的前期,ω較大,上式的第二部分所占的比重較大,算法具有較大的隨機(jī)性,因此有著良好的探測(cè)能力,則算法的全局尋優(yōu)能力較強(qiáng);而當(dāng)算法進(jìn)入后期,ω較小,上式第二部分所占的比重減小,其隨機(jī)性減弱,布谷鳥個(gè)體將在找到的最優(yōu)(或次優(yōu))位置附近進(jìn)行精細(xì)化搜索,有著良好的開發(fā)能力,則算法的局部尋優(yōu)能力較強(qiáng)。

(2)考慮到自然界生物的種群進(jìn)化,后代往往比上一代種群更能適應(yīng)壞境,更能夠生存下來,因此將這種概念應(yīng)用于仿生智能優(yōu)化算法中?；诖?布谷鳥會(huì)進(jìn)化以至于產(chǎn)下更適應(yīng)環(huán)境,即宿主鳥巢的鳥蛋,這種鳥蛋更加不容易被宿主發(fā)現(xiàn),也就更不容易被宿主扔出巢外,則布谷鳥無需再重新尋找鳥巢。故而Pa不再是一個(gè)固定值,而是一個(gè)逐漸減小的自適應(yīng)值。算法優(yōu)化前期,Pa較大,鳥巢被隨機(jī)生成的新的鳥巢替換的概率較大;算法優(yōu)化后期,Pa較小,被替換的概率減小,能夠有助于增強(qiáng)算法的局部搜索能力。經(jīng)過斟酌,一種可行的Pa更新的表達(dá)式如下

Pa=Pamin+(Pamax-Pamin)·(1-iter/iter_max)

(17)

經(jīng)過優(yōu)化算法的多次仿真運(yùn)行并比較結(jié)果,確定上式中的參數(shù)如下:Pamax=0.3,Pamin=0.1。

(3)更新策略的改進(jìn),考慮到算法的隨機(jī)性過強(qiáng),為增強(qiáng)其局部搜索能力,可考慮對(duì)式(14)中的隨機(jī)擾動(dòng)增量r′進(jìn)行改進(jìn)。具體改進(jìn)方法為:增加一個(gè)分式,并增設(shè)一個(gè)控制兩個(gè)分式的權(quán)重的因數(shù)θ,其中xopt是當(dāng)前迭代次數(shù)最好的鳥巢位置

r′=θ·(xi∈[1,n]-xj∈[1,n])+(1-θ)·(xopt-xk∈[1,n])

(18)

式中,i≠j≠k。

4函數(shù)測(cè)試

采用文獻(xiàn)[14]中的4個(gè)基準(zhǔn)函數(shù)F1、F2、F3和F4對(duì)改進(jìn)算法進(jìn)行測(cè)試:

變量范圍[-100,100]n。

變量范圍[-10,10]n。

變量范圍[-500,500]n。

變量范圍[-32,32]n。

上面4個(gè)函數(shù),F1和F2是單峰函數(shù),對(duì)于此類函數(shù)而言,優(yōu)化算法的收斂速度比最終尋找到的最優(yōu)值更值得關(guān)注和研究;F3、F4是多峰函數(shù),且有許多局部極小值點(diǎn),考察優(yōu)化算法的尋優(yōu)能力以及逃離局部極值點(diǎn)的能力[15]。除F3的最優(yōu)值是-418.982 9×n,其余3個(gè)函數(shù)的最優(yōu)值都是0。選取空間維數(shù)D為30,群體規(guī)模為40,進(jìn)化代數(shù)為1×103代。每個(gè)函數(shù)分別用原始布谷鳥搜索算法(Original CS)[2]和改進(jìn)量子布谷鳥搜索算法(Quantum CS)獨(dú)立運(yùn)行20次。圖1~圖4是4個(gè)測(cè)試函數(shù)分別用原始算法和改進(jìn)算法進(jìn)行優(yōu)化的仿真結(jié)果。

表1給出獨(dú)立運(yùn)行20次后的一些統(tǒng)計(jì)結(jié)果,包括20次的平均值、中值、最佳值和標(biāo)準(zhǔn)偏差。其中,F4函數(shù)的局部極小值點(diǎn)較多,優(yōu)化算法易陷入局部極值點(diǎn)從而找不到全局最優(yōu)值,但是20次獨(dú)立運(yùn)行中有8次能找到a×10-14或更優(yōu)值;而原始算法一次都沒有找到。綜上,結(jié)合表格的對(duì)比結(jié)果分析,表明改進(jìn)量子布谷鳥算法是一種優(yōu)化能力、效率和可靠性均較高的優(yōu)化算法。

表1　兩種算法對(duì)4個(gè)基準(zhǔn)函數(shù)尋優(yōu)仿真結(jié)果對(duì)比

圖1　原有算法和改進(jìn)算法對(duì)函數(shù)F 1的尋優(yōu)結(jié)果比較

圖2　原有算法和改進(jìn)算法對(duì)函數(shù)F 2的尋優(yōu)結(jié)果比較

圖3　原有算法和改進(jìn)算法對(duì)函數(shù)F 3的尋優(yōu)結(jié)果比較

圖4　原有算法和改進(jìn)算法對(duì)函數(shù)F 4的尋優(yōu)結(jié)果比較

5結(jié)束語

研究了基本布谷鳥搜索算法,分析出原有算法的不足之處,通過借助于當(dāng)前比較熱門的量子計(jì)算的概念和機(jī)制,并將其引入原始CS算法中,進(jìn)而提出基于量子機(jī)制的改進(jìn)布谷鳥搜索算法。通過對(duì)比原有算法和改進(jìn)算法對(duì)4個(gè)經(jīng)典基準(zhǔn)測(cè)試函數(shù)的尋優(yōu)速度和精度,仿真結(jié)果證明提出的改進(jìn)算法具有較大的優(yōu)越性,精度更好,找到函數(shù)最優(yōu)值所耗時(shí)間更小。

參考文獻(xiàn)

[1]Pinar Civicioglu,Erkan Besdok.A conceptual comparison of the cuckoo-search,particle swarm optimization,differential evolution and artificial bee colony algorithms[J].Artificial Intelligence Review,2013,39(4):315-346.

[2]Yang X S,Deb S.Cuckoo search via Lévy flights[C].Paris:Proceding of World Congress on Nature & Biologically Inspired Computing,2009.

[3]Salvador Elías Venegas-Andraca.Quantum walks:a comprehensive review[J].Quantum Information Processing,2012,11(5):1015-1106.

[4]Han K H,Kim J H.Genetic quantum algorithm and its application to combinatorial optimization problem[C].Proceding of IEEE Congress on Evolutionary Computation,2000.

[5]Sun J,Feng B,Xu W B.Particle swarm optimization with particles having quantum behavior[C].Roma:Proceding of Congress on Evolutionary Computation,2004.

[6]Pavlyukevich I.Lévy flights,non-local search and simulated annealing[J].Computational Physics,2007,226:1830-1844.

[7]杜利敏,阮奇,馮登科.基于共軛梯度的布谷鳥搜索算法[J].計(jì)算機(jī)與應(yīng)用化學(xué),2013,30(4):406-410.

[8]Mantegna R N.Fast,accurate algorithm for numerical simulation of Lévy stable stochastic processes[J].Physical Review E,1992(49):451-458.

[9]Yang X S,Deb S.Engineering optimization by cuckoo search[J].International Journal of Mathematical Modeling and Numerical Optimization,2010,1(4):330-343.

[10]Schrdinger E.An undulatory theory of the mechanics of atoms and molecules[J].Physics Review,1926,28(6):1049-1070.

[11]孫俊.量子行為粒子群優(yōu)化算法研究[D].無錫:江南大學(xué),2009.

[12]Ding X,Xu Zhenkai,Ngaam J,et al.Parameter estimation of takagi-sugeno fuzzy system using heterogeneous cuckoo search algorithm[J].Neurocomputing,2015,151(3):1332-1342.

[13]Bansal J,Singh C,Saraswat P K,et al.Inertia weight strategies in particle swarm optimization[C].Kunming:2011 Third World Congress on Nature and Biologically Inspired Computing(NaBIC),2011.

[14]Suganthan P W,Hansen N,Liang J J,et al.Problem definitions and evaluation criteria for the CEC 2005 special session on real parameter optimization[R].Singapore:Nanyang Technological University,2005.

[15]Sarafrazi S,Nezamabadi-pour H,Saryazdi S.Disruption:a new operator in gravitational search algorithm[J].Scientia Iranica,2011,18(3):539-548.