基于反向學習的布谷鳥算法優化搜索仿真

胡安明，李 偉

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

1 引言

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

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

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

2 布谷鳥搜索算法實現過程

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

規則一：每只布谷鳥只生產一個蛋，隨機放入其它鳥類的巢穴中。

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

規則三：其它鳥類巢穴被占領的數量[4]是固定的，布谷鳥寄生的蛋被發現后可被破壞或者停止孵化。

根據以上三條理想規則，可將CS算法的實現過程分為四步：

1)初始化設置參數

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

2)搜索過程

對所有鳥巢位置計算F(x)，獲得所有鳥巢位置的函數值，計算所有鳥巢函數值后，對比所得適應度函數值[5]，找出最優函數值，利用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、υ均表示標準正態隨機變量，一般情況下取值1.5。Φ的計算公式如式(3)所示

(3)

3)鳥巢更新選擇

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

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

(4)

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

4)算法結束

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

布谷鳥算法的實現過程如圖1所示。

圖1 布谷鳥算法實現流程圖

3 基于反向學習的布谷鳥算法優化搜索

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

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

(5)

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

1)隨機產生一個D維向量xi=(xi，1，xi，2，…，xi，D)，每個分量取[0，1]區間內的任意數值。

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

(6)

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

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

(7)

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

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

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

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

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

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

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

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

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

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

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

11)經過多次計算得到最優解，即最佳的鳥巢位置P；

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

13)結束計算。

3.2 加入反向學習的CH-CS

3.2.1 精英個體的確定

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

(8)

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

3.2.2 算法優化

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

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

本文的算法實現過程為：只有滿足反向學習的概率值pm條件后，才可執行反向學習運算；如果沒有滿足條件，僅執行CH-CS。具體描述如下所示：

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

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

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

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

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

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

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

至此實現基于反向學習的布谷鳥算法優化搜索。

4 仿真研究

為驗證本文方法提出的布谷鳥優化算法的搜索性能，將本文方法與文獻[1]、文獻[2]方法進行對比實驗。實驗選取如表1所示的四個函數作為實驗測試內容，其中，F1、F2表示單峰函數，F3、F4表示多峰函數。為了保證實驗結果的公平性，對三種方法的參數進行了統一設定：

表1 測試函數

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

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

表2 三種方法仿真對比結果

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

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

圖2 三種方法尋優收斂曲線圖

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

5 結論

由于標準布谷鳥算法在處理復雜的多峰函數時，通常表現出過低的收斂精度和搜索能力，因此，本文提出了基于反向學習的布谷鳥算法優化搜索方法。

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

2)仿真測試結果表明，本文方法在單峰函數和多峰函數中，均取得了全局最優解，單峰函數F1、F2中，F2取得了全局最優輸出值為0.38；多峰函數F3、F4中，F3取得了全局最優輸出值為0.00；

3)下一步的研究過程中將把優化后的布谷鳥搜索算法應用到相關領域進行驗證，在實際應用過程中進一步提升基于反向學習的布谷鳥算法的搜索性能。