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

胡安明，李 偉

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

2)搜索過程

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

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

(1)

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

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

(2)

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

(3)

3)鳥巢更新選擇

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

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

(4)

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

4)算法結(jié)束

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

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

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

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

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

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

(5)

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

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

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

(6)

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

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

(7)

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

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

2)對所有鳥巢進(jìn)行適值fi計(jì)算；

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

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

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

6)對候選解Tj進(jìn)行適值FTj計(jì)算；

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

8)尋找新的解取代當(dāng)前候選解；

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

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

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

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

13)結(jié)束計(jì)算。

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

3.2.1 精英個體的確定

反向?qū)W習(xí)作為在智能計(jì)算領(lǐng)域中熱度極高的一種新算法，對于全局尋優(yōu)展現(xiàn)出了良好的性能。其基本思想為：對于任意給定的可行解[10]，通過反向?qū)W習(xí)策略得到該可行解的反向解，對比可行解和反向解，篩選出其中表現(xiàn)較優(yōu)的解，作為下一次迭代個體。反向?qū)W習(xí)具有強(qiáng)大的包容性，在計(jì)算的同時保持了種群的多樣性。但同時也出現(xiàn)一定的弊端，在面對數(shù)量巨大的種群個體時，如果對所有個體都進(jìn)行反向解運(yùn)算，計(jì)算量較大且極易降低搜索精度。因此，在運(yùn)用反向?qū)W習(xí)算法前，應(yīng)該確定好精英個體的有效信息，只針對精英個體進(jìn)行反向解運(yùn)算，引導(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)化變量加入混沌擾動策略，擴(kuò)大搜索區(qū)域，促使布谷鳥種群的多樣性相應(yīng)擴(kuò)大，減少陷入局部最優(yōu)的概率，提高算法的勘探能力。加入混沌擾動策略后，會降低算法整體的收斂速度，為此引入反向?qū)W習(xí)算法，通過對精英個體進(jìn)行反向解運(yùn)算，得到所有解中表現(xiàn)最優(yōu)的一個，從而得到最優(yōu)結(jié)果，在一定程度上提高了算法的收斂精度。

在計(jì)算過程中，還要考慮從當(dāng)前群體與反向群體中，如何選擇出N個解作為下一次迭代的個體。本文利用群體選擇機(jī)制，假設(shè)p(g)為當(dāng)前布谷鳥種群，根據(jù)反向?qū)W習(xí)算法得到m個精英個體，并產(chǎn)生與之相對應(yīng)的反向個體為Eop(g)，計(jì)算p(g)∪Eop(g)，從中選擇N個精英個體作為下一次迭代的個體p(g+1)。此時N表示精英種群，針對精英個體的數(shù)量會對最優(yōu)解的計(jì)算產(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習(xí)算法的概率值，rand∈[0，1]為隨機(jī)數(shù)，以均勻分布的形式存在。在算法實(shí)現(xiàn)過程中，δ為隨機(jī)值，可生成若干個不同的精英個體，從而使得每個精英個體反向?qū)W習(xí)后都能得到不同的反向解，這個過程可以提高算法的搜索能力。

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

1)對當(dāng)前布谷鳥種群p(g)進(jìn)行反向?qū)W習(xí)運(yùn)算；

2)當(dāng)FFS≤Max＿FFS時，繼續(xù)計(jì)算；

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

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

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

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

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

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

4 仿真研究

為驗(yàn)證本文方法提出的布谷鳥優(yōu)化算法的搜索性能，將本文方法與文獻(xiàn)[1]、文獻(xiàn)[2]方法進(jìn)行對比實(shí)驗(yàn)。實(shí)驗(yàn)選取如表1所示的四個函數(shù)作為實(shí)驗(yàn)測試內(nèi)容，其中，F(xiàn)1、F2表示單峰函數(shù)，F(xiàn)3、F4表示多峰函數(shù)。為了保證實(shí)驗(yàn)結(jié)果的公平性，對三種方法的參數(shù)進(jìn)行了統(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中各表達(dá)式的理論最優(yōu)值為0。用三種方法分別對上述表達(dá)式進(jìn)行實(shí)驗(yàn)測試，結(jié)果如表2所示。

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

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

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

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

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

5 結(jié)論

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

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

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)域進(jìn)行驗(yàn)證，在實(shí)際應(yīng)用過程中進(jìn)一步提升基于反向?qū)W習(xí)的布谷鳥算法的搜索性能。