基于反向?qū)W習(xí)策略的深度搜索布谷鳥算法

何 慶，黃閩茗，周曉南

(1.貴州大學(xué) 大數(shù)據(jù)與信息工程學(xué)院，貴州 貴陽 550025;2.貴州大學(xué) 學(xué)報編輯部，貴州 貴陽 550025)

布谷鳥搜索(Cuckoo Search，CS)算法是在2009年開發(fā)的自然啟發(fā)式算法。該算法基于布谷鳥育雛行為的寄生性，并包含鳥類和果蠅的levy飛行行為[1]為雛形設(shè)計算法原理。由于其簡單性和有效性，從誕生之日起，吸引了很多學(xué)者的關(guān)注，并成功應(yīng)用于工程優(yōu)化和函數(shù)優(yōu)化問題[2-3]以及機器學(xué)習(xí)[4]等方面。但是，對于一些復(fù)雜的問題，CS算法也存在著局部搜索能力較差、后期收斂速度慢[5]等缺點，暫時無法滿足最優(yōu)解的精度要求，因此其性能需要進(jìn)一步改進(jìn)。

王凡等[6]通過分析CS算法的Markov鏈模型，證明了CS算法的收斂性。張燕[7]提出了一種基于Cubic混沌模型的自適應(yīng)布谷鳥優(yōu)化算法，自適應(yīng)的調(diào)整levy flights的隨機搜索補償因子，并Cubic混沌映射嵌入算法，通過實驗證明了有效性；汪峰坤等[8]提出的一種改進(jìn)的布谷鳥算法，通過交叉操作和變異操作，增強了布谷鳥算法的種群多樣性和搜索性能。

基于以上算法的啟發(fā)，本文設(shè)計了一種改進(jìn)的深度搜索布谷鳥(Deep Search Cuckoo Search，DSCS)算法。改進(jìn)算法引入反向?qū)W習(xí)策略和逐維深度搜索策略來改進(jìn)基本的CS。首先，對Levy飛行后的解進(jìn)行反向?qū)W習(xí)，提升最優(yōu)解的搜索效率；然后，對迭代結(jié)束后的全局最優(yōu)解進(jìn)行逐維深度搜索，捕捉潛在的最優(yōu)解，彌補搜索步驟可能出現(xiàn)的問題，提高了算法的全局搜索能力。通過5個測試函數(shù)的實驗結(jié)果證明，本改進(jìn)的DSCS算法具有更好的全局搜索能力，搜索精度和收斂速度。

1 相關(guān)工作

1.1 布谷鳥算法

CS算法通過模擬布谷鳥的寄生繁衍策略來尋找最優(yōu)解。尋找最適合產(chǎn)蛋的鳥巢是一種隨機的或類似隨機的方式。其基本原理就是把布谷鳥所寄生的鳥巢位置映射為算法種群空間中的解，以寄生巢位置的優(yōu)劣作為算法的適應(yīng)度值，為了模擬布谷鳥的繁衍機制，CS算法設(shè)定了三個理想規(guī)則[1]：

規(guī)則1每只布谷鳥只產(chǎn)一個蛋，并隨機放入所選擇的寄主鳥類的巢穴中。

規(guī)則2每次進(jìn)化都保留最優(yōu)蛋的巢穴到下一代。

規(guī)則3可用的寄主巢穴數(shù)量固定，且寄主鳥類以概率R∈(0,1)發(fā)現(xiàn)布谷鳥放的蛋。寄主發(fā)現(xiàn)布谷鳥的蛋，可以消滅該蛋或放棄舊巢另建新巢。

根據(jù)這三條規(guī)則，CS包括四個步驟，初始化，搜索，選擇和判斷。該步驟如下：

(1)初始化

定義目標(biāo)函數(shù)F(x)，并隨機生成N個鳥窩的初始位置Xi=(1,2,…,N)，設(shè)置問題維數(shù)、發(fā)現(xiàn)概率Pa和最大迭代次數(shù)等參數(shù)。

(2)搜索

選擇目標(biāo)函數(shù)并計算每個鳥窩位置的目標(biāo)函數(shù)值，得到當(dāng)前的最優(yōu)函數(shù)值，根據(jù)levy飛行生成新的鳥巢位置，計算每個蛋的適應(yīng)度函數(shù)Ft，比較存優(yōu)。levy飛行的隨機步長公式為[1]

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

(1)

式中：xt+1,i為巢穴位置更新后的位置；xt,i為當(dāng)前巢穴位置；α0為步長縮放因子，通常為0.01[2]。

萊維飛行隨機搜索路徑公式為

(2)

式中：u和v為標(biāo)準(zhǔn)正態(tài)隨機變量，β為萊維飛行的控制因子，通常為1.5[1]。Φ的計算公式為

(3)

(3)選擇

依據(jù)布谷鳥的蛋發(fā)現(xiàn)概率Pa丟棄不好的巢穴位置，用式(3)更新巢穴中蛋的位置，并計算目標(biāo)函數(shù)Ft，選擇存優(yōu)。位置更新式(3)為

xt+1,i=xt,i+r(xt,j-xt,k)。

(4)

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

(4)結(jié)束判決

若滿足預(yù)設(shè)的求解精度或最大迭代次數(shù)，則結(jié)束，否則返回步驟(2)。算法的實現(xiàn)過程如圖1描述。

1.2 反向?qū)W習(xí)

反向?qū)W習(xí)(Opposition based Learning，OBL)被TIZHOOSH[9]2005年提出，是智能計算領(lǐng)域中的一種新技術(shù)。直到2008年，它才被RAHNAMAYAN等[10]用于差分進(jìn)化算法。OBL是計算可行解決方案的基于反向的解決方案，同時評估原始解決方案和基于反向的解決方案，并選擇更好的解決方案[11]。

定義1若x∈[a,b]之間的任意實數(shù)，則x的基于反向?qū)W習(xí)的數(shù)如下所示：

x′=a+b-x。

(5)

圖1 布谷鳥算法流程圖Fig.1 The schematic diagram of CS algorithm

可得，x到a的距離為|x-a|=x-a，根據(jù)式(5)可得x′到b的距離為|b-x′|=|b-(a+b-x)|=|a-x|=x-a，因此，這兩個距離是相等的，如圖2所示。

圖2 任意實數(shù)與它的反向?qū)W習(xí)數(shù)Fig.2 A real number and its opposition based learning number

定義2反向點[12]，設(shè)X=(x1,x2,…,xD)為D維空間中的一點，xj∈[aj,bj]，其對應(yīng)的反向點為：

(6)

由于可行解決方案和基于反向的解決方案位于搜索空間的兩側(cè)，因此當(dāng)引入OBL策略時，可以擴大搜索區(qū)域并增強全局搜索能力。

2 DSCS算法

在DSCS算法中，引入了兩個改進(jìn)點。第一個是生成具有OBL策略的反向群體，并將其用于位置替換更新步驟中。第二個是在每一代結(jié)束時圍繞當(dāng)前全局最優(yōu)解決方案深入尋找潛在的更好的解決方案。

2.1 反向?qū)W習(xí)策略

反向?qū)W習(xí)被RAHNAMAYAN等[10]證明了當(dāng)前可行解的基于反向的解有50%的概率更接近全局最優(yōu)解。雖然可行解決方案和基于反向的解決方案在相同條件下具有相同的概率保留給下一代，評估兩者的解決方案，并選擇更好的解決方案，它的生成算法能夠提高獲得最優(yōu)解的概率。

本文在CS的搜索階段，本文將levy飛行之后的目標(biāo)函數(shù)值，與其在作用域范圍內(nèi)的反向解的目標(biāo)函數(shù)和當(dāng)前最優(yōu)解的目標(biāo)函數(shù)值進(jìn)行比較，對最優(yōu)解和當(dāng)前最優(yōu)解進(jìn)行更新。通過反向?qū)W習(xí)減少搜索范圍，從而提升解的搜索效率。具體步驟如下：

在反向?qū)W習(xí)策略中，設(shè)種群規(guī)模為N，維度為D，迭代過程選擇更新位置時的位置矩陣為nestN×Di。每個維度的上下限分別為upN×Di，lowN×Di，則解的每維的基于反向?qū)W習(xí)的位置矩陣如下：

nestN×Di′=upN×Di+lowN×Di-nestN×Di

(7)

在DSCS中，產(chǎn)生的三個隨機位置將會被反向群體nestN×Di選擇，這種變化有效地擴大了搜索范圍，并加快了全局最優(yōu)解的搜索速度。

比較Levy飛行獲得的解、Levy飛行獲得的解的反向解以及當(dāng)前最優(yōu)解的目標(biāo)函數(shù)值，本文將三個解中最小的目標(biāo)函數(shù)值的解作為下一次迭代的最優(yōu)解；蛋的位置更新，選擇Levy飛行獲得的解與Levy飛行獲得的解的反向解中獲得的位置更新。

2.2 逐維深度搜索

圖3 A和B之間的位置關(guān)系Fig.3 Location relationship between A and B

步驟1對第i維的深度搜索：

1)計算A和B的坐標(biāo)差：

XAB=XB-XA

(8)

2)計算局部搜索步長Δ：

Δ=ηXAB。

(9)

3)從位置B搜索可能更好的位置，對位置B做深度搜索有以下7個步驟：

①將搜索p設(shè)置為單位坐標(biāo);

②設(shè)置位置p的坐標(biāo)Xp，則

XP=XB-p·Δ。

(10)

③分析位置p和當(dāng)前的最優(yōu)位置的目標(biāo)函數(shù)值。如果位置p更小，則轉(zhuǎn)到下一步，否則跳到步驟⑦。

④更新最優(yōu)位置。

⑤比較位置p和B的目標(biāo)函數(shù)值，如果位置p的目標(biāo)函數(shù)值小，則用位置p代替B，轉(zhuǎn)到下一步。

⑥如果p的值達(dá)到單向位置搜索最大數(shù)量Pmax，則轉(zhuǎn)到下一步，返回步驟②。

⑦結(jié)束對當(dāng)前位置的深度搜索。

步驟2判斷當(dāng)前維度是否為最后一維，若是對該蛋的最后一維更新，則對該蛋各維的深度搜索結(jié)束；否則更新該蛋的深度搜索維度：i=i+1，返回步驟1。

3 實驗與結(jié)果分析

本節(jié)將DSCS與CS進(jìn)行比較，以驗證其有效性。實驗平臺是Windows7 MATLAB R2014b，5個測試函數(shù)如表1所示，F(xiàn)1—F3是單峰函數(shù)，F(xiàn)4—F5是多峰函數(shù)[14]。在實驗過程中，DSCS和CS的參數(shù)如下：

固定參數(shù)：種群數(shù)量為N=30，個體維度D=20，每個維度的范圍為[-20,20]，收斂精度δ=10-5，最大迭代次數(shù)tmax=5 000。

可變參數(shù)：被發(fā)現(xiàn)概率Pa=0.05，levy飛行的步長縮放因子α0=0.1；控制因素β=1.3。

DSCS參數(shù)：比例因子η=150，單向位置搜索最大數(shù)量Pmax=15。

每個實驗分別運行30次，實驗結(jié)果如表2所示。從表中可以看出，DSCS的性能相比CS算法，總體改善了解的質(zhì)量，特別地，在F4函數(shù)上取得全局最優(yōu)解。

表1 測試函數(shù)Tab.1 Test functions

表2 DSCS和CS函數(shù)實驗結(jié)果對比Tab.2 The optimization accuracy values of CS and DSCS

為了更好地觀察改進(jìn)算法的性能，實驗設(shè)置算法結(jié)束條件為最大迭代次數(shù)，設(shè)置為5 000次，即tmax=5 000，其他參數(shù)保持不變。圖4(a)～(e)以算法的迭代次數(shù)為橫軸，適應(yīng)度函數(shù)的對數(shù)值為豎軸，圖形化的展示了改進(jìn)算法和CS算法在5個測試函數(shù)中的尋優(yōu)搜索收斂過程，其中，測試函數(shù)的維度為20?？梢钥闯觯瑹o論測試函數(shù)是簡單的單模函數(shù)還是復(fù)雜的多模函數(shù)，DSCS的收斂速度和收斂精度都高于CS的收斂速度和收斂精度。特別的，在函數(shù)F4和F5中，函數(shù)能夠收斂到理論最優(yōu)值，并且在函數(shù)的收斂過程中，相比較于CS算法，尋優(yōu)收斂曲線斜率更小；因此，改進(jìn)算法具有更好的后期搜索能力和更強的搜索活力。由此可得，本文改進(jìn)的算法有效提高了CS算法的收斂精度和收斂速度。

圖4 DSCS與CS尋優(yōu)收斂曲線圖Fig.4 The optimization convergence curves of DSCS and CS

實驗結(jié)果表明，針對本文選取的5個測試函數(shù)，本文提出的算法在引入基于反向?qū)W習(xí)策略和局部增強搜索操作后，算法的收斂速度，收斂精度和全局搜索能力都得到了不同程度的提高。

4 結(jié)語

在算法DSCS的選擇階段，基于初始化群體生成基于反向群體，然后隨機選擇三個新的個體替換初始化群體中丟棄的個體。在每一代的演化中，它類似于同時搜索兩個對稱區(qū)域，這加速了收斂速度并提高了全局搜索能力。對5種標(biāo)準(zhǔn)測試函數(shù)的實驗表明，DSCS的性能明顯優(yōu)于CS。DSCS的全局搜索能力，收斂速度和收斂精度要好得多。對于簡單的單模函數(shù)和復(fù)雜的多模態(tài)函數(shù)，DSCS在優(yōu)化實驗上表現(xiàn)出良好的魯棒性。此外，本文的算法還需要在實際優(yōu)化問題中進(jìn)行分析驗證，例如，應(yīng)用于機器學(xué)習(xí)中的參數(shù)優(yōu)化等。