胡安明，李 偉

(1.廣州理工學院計算機科學與工程學院，廣東 廣州 510540；2.集美大學理學院，福建 廈門 361021)

1 引言

布谷鳥搜索(Cuckoo Search，CS)算法是依據(jù)布谷鳥在其他鳥巢中的育雛行為與其它鳥類的Levy flight行為，提出的搜索算法。布谷鳥算法由于其簡單高效的特點，自提出之日起，就在工程優(yōu)化和函數(shù)優(yōu)化等方面廣泛應(yīng)用。但是也存在相應(yīng)的弊端，在處理一些復(fù)雜的問題時，布谷鳥算法無法展現(xiàn)出高效的搜索能力和收斂速度，以至于后期無法滿足最優(yōu)解的精度需求，因此還需對其進行深入的優(yōu)化和研究。

黃閩茗等人[1]針對布谷鳥算法搜索性能不足和收斂速度較慢等問題提出了優(yōu)化方案。對更新后的解進行逐維反向?qū)W習，將影響計算的干擾因素控制在最低；利用精英反向?qū)W習提高算法和動態(tài)適應(yīng)的縮放因子，對當前解的信息做進一步控制，以此提高算法的收斂速度和搜索性能。雖然該方法提升了布谷鳥算法的搜索能力，但存在搜索繁瑣的問題，不適用于大范圍搜索；張燕等人[2]為了提高布谷鳥算法求解多維函數(shù)的能力，通過局部搜索增強策略增加布谷鳥的種群范圍，增加可選擇性，避免陷入局部最優(yōu)；然后利用自適應(yīng)發(fā)現(xiàn)概率使得局部求精和全局尋優(yōu)之間獲得平衡；最后加入反向?qū)W習擾動機制增強算法找到最優(yōu)解的概率。該方法提高了布谷鳥算法的尋優(yōu)性能，但是搜索性能有待進一步提升。

基于以上方法的啟發(fā)和出現(xiàn)的問題，本文在反向?qū)W習的基礎(chǔ)上提出了一種布谷鳥算法優(yōu)化搜索方法。通過確定布谷鳥種群中的精英個體，對其求得反向解，丟棄較差解，在較優(yōu)解中找到最優(yōu)解作為下一次迭代個體；同時，本文引入了混沌擾動策略，對較優(yōu)的鳥巢位置進行混沌擾動操作，擴大種群范圍，使算法尋優(yōu)范圍更廣，搜索能力更強。在仿真中，本文方法提高了處理單峰函數(shù)和多峰函數(shù)的收斂精度，提升了布谷鳥算法性能。

2 布谷鳥搜索算法實現(xiàn)過程

CS算法的實現(xiàn)是根據(jù)布谷鳥找到最佳巢穴的位置[3]映射到種群空間中的解，并根據(jù)選擇的鳥巢的好壞作為評價算法適應(yīng)度的標準。為了更形象地展示出布谷鳥的育雛行為，將CS算法控制在三個理想規(guī)則之下：

規(guī)則一：每只布谷鳥只生產(chǎn)一個蛋，隨機放入其它鳥類的巢穴中。

規(guī)則二：在布谷鳥繁衍后代的整個過程中，都將最優(yōu)蛋的鳥巢保留給下一代。

規(guī)則三：其它鳥類巢穴被占領(lǐng)的數(shù)量[4]是固定的，布谷鳥寄生的蛋被發(fā)現(xiàn)后可被破壞或者停止孵化。

根據(jù)以上三條理想規(guī)則，可將CS算法的實現(xiàn)過程分為四步：

1)初始化設(shè)置參數(shù)

假設(shè)有n個鳥巢，原始位置為Xi=(1，2，…，n)，目標函數(shù)為F(x)，發(fā)現(xiàn)概率值為Pa，并對最大迭代次數(shù)和問題維數(shù)進行初始化設(shè)置。

2)搜索過程

對所有鳥巢位置計算F(x)，獲得所有鳥巢位置的函數(shù)值，計算所有鳥巢函數(shù)值后，對比所得適應(yīng)度函數(shù)值[5]，找出最優(yōu)函數(shù)值，利用Levy flight的隨機步長計算公式如式(1)所示

xt+1，i=xt，i+α0?Levy(β)

(1)

式中，xt+1，i表示更新后的鳥巢位置；xt，i表示未更新前的鳥巢位置；α0為步長縮放因子，一般情況下取值0.01；?為卷積運算；β為Levy flight的控制因子。

Levy flight的路徑選擇具有隨機性，可用式(2)表示為

(2)

其中，u、υ均表示標準正態(tài)隨機變量，一般情況下取值1.5。Φ的計算公式如式(3)所示

(3)

3)鳥巢更新選擇

計算Pa的值，放棄容易被其它鳥類發(fā)現(xiàn)的巢穴，對保留下來的蛋重新計算其位置信息和適應(yīng)度函數(shù)[6]值Ft，選擇最優(yōu)值留下來。更新后蛋所在的鳥巢位置信息如式(4)所示

xt+1，i=xt，i+r(xt，j-xt，k)

(4)

式中，r表示比例因子，為區(qū)間(0，1)中的均勻分布隨機數(shù)；xt，j、xt，k分別為t代中的兩個隨機解。

4)算法結(jié)束

通過上述求解過程，如果得到滿足條件的求解精度和最大迭代次數(shù)，則停止計算，否則返回步驟2)重新計算。

布谷鳥算法的實現(xiàn)過程如圖1所示。

圖1 布谷鳥算法實現(xiàn)流程圖

3 基于反向?qū)W習的布谷鳥算法優(yōu)化搜索

3.1 加入混沌擾動的CS(CH-CS)

nextbest，d=nextbest，d-1+Rd[2xd(i)-1]

(5)

式中，xd(i)表示當前計算過程中產(chǎn)生的混沌序列，具體過程如下所示

1)隨機產(chǎn)生一個D維向量xi=(xi，1，xi，2，…，xi，D)，每個分量取[0，1]區(qū)間內(nèi)的任意數(shù)值。

2)優(yōu)化混沌序列[8]，本文選擇kent混沌映射實現(xiàn)優(yōu)化，算法如式(6)所示

(6)

其中，a=0.4。根據(jù)式(6)做迭代計算，再進行第j次迭代后，產(chǎn)生第j次混沌序列：x(j)=x1(j)，x2(j)，…，xD(j)。

確定混沌擾動的區(qū)域半徑是實現(xiàn)混沌擾動策略的關(guān)鍵步驟。如果區(qū)域半徑過大，導(dǎo)致對鳥巢位置的確定偏差過大。對于不同的維數(shù)值，選取擾動區(qū)域半徑也有所不同，本文選擇逐維變化混沌擾動的方法確定不同的區(qū)域半徑大小，如式(7)所示

(7)

加入混沌擾動策略后，原始的CS轉(zhuǎn)換為CH-CS，算法流程如下所示：

1)遍歷當前所有的布谷鳥群體，確定n個鳥巢的初始化位置信息；

2)對所有鳥巢進行適值fi計算；

3)通過Levy flight得到新的解Ti；

4)對新求得的解Ti進行適值FTi計算；

5)確定候選解Tj的具體數(shù)值；

6)對候選解Tj進行適值FTj計算；

7)如果FTi?FTj，則停止計算；否則返回步驟4)；

8)尋找新的解取代當前候選解；

9)計算布谷鳥的蛋被其它鳥類發(fā)現(xiàn)概率值，并丟棄不理想解；

10)計算式(1)得到新的解，取代被丟棄的解；

11)經(jīng)過多次計算得到最優(yōu)解，即最佳的鳥巢位置P；

12)利用式(5)對P進行混沌擾動學習，從而得到布谷鳥選取的新鳥巢位置信息P1。測試P和P1中的所有鳥巢，并對比其測試值，表現(xiàn)不好的鳥巢可直接舍棄。對所有鳥巢計算完成后，得到最佳鳥巢位置；

13)結(jié)束計算。

3.2 加入反向?qū)W習的CH-CS

3.2.1 精英個體的確定

反向?qū)W習作為在智能計算領(lǐng)域中熱度極高的一種新算法，對于全局尋優(yōu)展現(xiàn)出了良好的性能。其基本思想為：對于任意給定的可行解[10]，通過反向?qū)W習策略得到該可行解的反向解，對比可行解和反向解，篩選出其中表現(xiàn)較優(yōu)的解，作為下一次迭代個體。反向?qū)W習具有強大的包容性，在計算的同時保持了種群的多樣性。但同時也出現(xiàn)一定的弊端，在面對數(shù)量巨大的種群個體時，如果對所有個體都進行反向解運算，計算量較大且極易降低搜索精度。因此，在運用反向?qū)W習算法前，應(yīng)該確定好精英個體的有效信息，只針對精英個體進行反向解運算，引導(dǎo)搜索結(jié)果更靠近最優(yōu)解，具體過程如下所示。

(8)

式(8)中，bi，j∈[xj，yj]，[xj，yj]表示搜索范圍的動態(tài)邊界信息，ε∈[0，1]為一般化系數(shù)。

3.2.2 算法優(yōu)化

對于布谷鳥算法的優(yōu)化，本文主要從勘探能力和收斂速度兩方面著手。首先，通過對優(yōu)化變量加入混沌擾動策略，擴大搜索區(qū)域，促使布谷鳥種群的多樣性相應(yīng)擴大，減少陷入局部最優(yōu)的概率，提高算法的勘探能力。加入混沌擾動策略后，會降低算法整體的收斂速度，為此引入反向?qū)W習算法，通過對精英個體進行反向解運算，得到所有解中表現(xiàn)最優(yōu)的一個，從而得到最優(yōu)結(jié)果，在一定程度上提高了算法的收斂精度。

在計算過程中，還要考慮從當前群體與反向群體中，如何選擇出N個解作為下一次迭代的個體。本文利用群體選擇機制，假設(shè)p(g)為當前布谷鳥種群，根據(jù)反向?qū)W習算法得到m個精英個體，并產(chǎn)生與之相對應(yīng)的反向個體為Eop(g)，計算p(g)∪Eop(g)，從中選擇N個精英個體作為下一次迭代的個體p(g+1)。此時N表示精英種群，針對精英個體的數(shù)量會對最優(yōu)解的計算產(chǎn)生一定的局限性的問題，經(jīng)過反復(fù)研究確定，m/N=0.1為最佳參數(shù)值，因此本文確定精英個體數(shù)量為m/N=0.1。假設(shè)FFS為適應(yīng)度函數(shù)評價次數(shù)，Max＿FFS表示適應(yīng)度函數(shù)最大評價次數(shù)，pm表示執(zhí)行反向?qū)W習算法的概率值，rand∈[0，1]為隨機數(shù)，以均勻分布的形式存在。在算法實現(xiàn)過程中，δ為隨機值，可生成若干個不同的精英個體，從而使得每個精英個體反向?qū)W習后都能得到不同的反向解，這個過程可以提高算法的搜索能力。

本文的算法實現(xiàn)過程為：只有滿足反向?qū)W習的概率值pm條件后，才可執(zhí)行反向?qū)W習運算；如果沒有滿足條件，僅執(zhí)行CH-CS。具體描述如下所示：

1)對當前布谷鳥種群p(g)進行反向?qū)W習運算；

2)當FFS≤Max＿FFS時，繼續(xù)計算；

3)如果rand≤pm，停止計算；

4)從種群p(g)中找出m個最優(yōu)個體構(gòu)建精英個體種群Xe1，Xe2，…，Xem；

5)對精英個體的搜索范圍[xj，yj]進行具體計算；

6)通過計算得到精英個體的反向解，并對反向解求得適應(yīng)度函數(shù)值，組建反向種群Eop(g)；

7)從p(g)∪Eop(g)中選擇N個最優(yōu)個體作為下一代種群p(g+1)；

至此實現(xiàn)基于反向?qū)W習的布谷鳥算法優(yōu)化搜索。

4 仿真研究

為驗證本文方法提出的布谷鳥優(yōu)化算法的搜索性能，將本文方法與文獻[1]、文獻[2]方法進行對比實驗。實驗選取如表1所示的四個函數(shù)作為實驗測試內(nèi)容，其中，F(xiàn)1、F2表示單峰函數(shù)，F(xiàn)3、F4表示多峰函數(shù)。為了保證實驗結(jié)果的公平性，對三種方法的參數(shù)進行了統(tǒng)一設(shè)定：

表1 測試函數(shù)

固定不可變參數(shù)：布谷鳥種群數(shù)量為30，精英個體的第D維向量為20，維度范圍為[-20，20]，迭代次數(shù)最大值為5000，收斂精度為10-5。可變參數(shù)：布谷鳥的蛋被其它鳥類發(fā)現(xiàn)的概率為0.05%，Levy flight的步長縮放因子為0.1，控制因素為1.3。本文方法參數(shù)：比例因子為150，單向位置搜索最大數(shù)量為15。

表1中各表達式的理論最優(yōu)值為0。用三種方法分別對上述表達式進行實驗測試，結(jié)果如表2所示。

表2 三種方法仿真對比結(jié)果

從表2中可以看出，較其它兩種方法相比，不管是單峰函數(shù)還是多峰函數(shù)，本文方法都取得了更優(yōu)的結(jié)果，總體上提升了解的質(zhì)量，尤其是在F3函數(shù)上更是得到了全局最優(yōu)解。

為了進一步驗證三種方法改進后的性能，分別測試不同方法下單峰函數(shù)和多峰函數(shù)的最優(yōu)值，得到圖2所示的三種方法對五個函數(shù)的尋優(yōu)收斂對比圖。

圖2 三種方法尋優(yōu)收斂曲線圖

從圖2中可以看出，在處理F3和F4復(fù)雜的多峰函數(shù)時，本文方法較其它兩種方法相比，展現(xiàn)出了更高的收斂速度和收斂精度，達到了理論最優(yōu)值；并且在函數(shù)的收斂過程中，本文方法比其它兩種方法的尋優(yōu)收斂曲線斜率更小。這是因為本文引入了反向?qū)W習算法，通過對精英個體進行反向解運算，搜索出所有解中的最優(yōu)解，進一步優(yōu)化布谷鳥算法性能。綜上所述，本文方法較現(xiàn)有方法相比，在布谷鳥算法的搜索能力方面得到了有效提升。

5 結(jié)論

由于標準布谷鳥算法在處理復(fù)雜的多峰函數(shù)時，通常表現(xiàn)出過低的收斂精度和搜索能力，因此，本文提出了基于反向?qū)W習的布谷鳥算法優(yōu)化搜索方法。

1)本文方法主要從以下兩點進行優(yōu)化：第一點是在計算過程中加入混沌擾動策略，擴大算法的搜索范圍，從而使布谷鳥種群也得到了擴大，提高了尋優(yōu)效率；第二點是加入精英反向?qū)W習策略，在進行尋優(yōu)時僅針對精英個體求反向解即可，擴大了搜索空間范圍，使得最終結(jié)果更接近于最優(yōu)解。在迭代計算后期，加入混沌擾動策略，在一定程度上還提升了算法整體的勘探能力和開采能力。

2)仿真測試結(jié)果表明，本文方法在單峰函數(shù)和多峰函數(shù)中，均取得了全局最優(yōu)解，單峰函數(shù)F1、F2中，F(xiàn)2取得了全局最優(yōu)輸出值為0.38；多峰函數(shù)F3、F4中，F(xiàn)3取得了全局最優(yōu)輸出值為0.00；

3)下一步的研究過程中將把優(yōu)化后的布谷鳥搜索算法應(yīng)用到相關(guān)領(lǐng)域進行驗證，在實際應(yīng)用過程中進一步提升基于反向?qū)W習的布谷鳥算法的搜索性能。