基于信息熵的布谷鳥搜索算法

張 燕,袁書卷

(陜西理工大學(xué) 教育科學(xué)學(xué)院,陜西 漢中 723000)

大自然中有一些布谷鳥會將自己的卵產(chǎn)在寄主鳥巢中，將巢寄生作為一種繁殖策略，在某些情況下，寄主鳥類有可能發(fā)現(xiàn)鳥巢中陌生的卵，這時寄主鳥類會丟棄布谷鳥所產(chǎn)的卵或直接重新筑巢．從進化的角度來看，布谷鳥的目標(biāo)是增加生存的概率[1]．受這些行為和策略的啟發(fā)，Yang和Deb(2009)開發(fā)了布谷鳥搜索(CS)算法，布谷鳥搜索算法成功地模仿了布谷鳥的行為，并與Lévy flights相結(jié)合，有效地搜索更好、最優(yōu)的生存策略．由于其具有很強的全局搜索能力，在解決不同的優(yōu)化問題中表現(xiàn)出了很好的性能，逐漸引起了關(guān)注，并被應(yīng)用到不同的領(lǐng)域，如水電管網(wǎng)系統(tǒng)、資源分配、圖像處理、多目標(biāo)優(yōu)化等方面[2]．與其他智能算法類似，CS算法也存在搜索速度慢和早熟收斂等缺陷，為了改善CS算法的性能，眾多學(xué)者針對布谷鳥算法進行了大量的研究．其中王李進[3]等提出逐維改進的布谷鳥搜索算法，改善解的質(zhì)量．周歡[4]等引入動態(tài)慣性權(quán)重改進鳥巢位置的更新方式，用于平衡種群探索能力和開發(fā)能力之間的關(guān)系，改進后的算法收斂速度和收斂精度均有不同程度的提高．薛益鴿[5]基于混沌擾動的改進布谷鳥算法，獲得了較快的收斂速度和較高的求解精度．田野[6]等針對布谷鳥搜索算法中解的發(fā)現(xiàn)及放棄策略的隨機性問題，將解的適應(yīng)度考慮進來，提出一種基于解的優(yōu)劣度的改進算法，提高算法的求解質(zhì)量．本文中針對算法易陷入局部最優(yōu)和早熟收斂的缺陷，提出了一種 CS算法的改進方法，通過信息熵權(quán)重來調(diào)控搜索范圍，將該權(quán)重引入到 CS算法中改善布谷鳥的局部搜索能力，提高收斂速度．

1 基本布谷鳥搜索算法

布谷鳥算法作為一種元啟發(fā)式算法[7]，其基本原理就是把布谷鳥所寄生的鳥巢位置映射為算法種群空間中的解，與所有進化算法一樣，布谷鳥優(yōu)化算法采用一個隨機生成的群體開始迭代搜索．由布谷鳥初始種群(Npop)開始，nesti=(nexti,1,nesti,2,…,nesti,var)代表一個候選解，iE{1,2,…,pop}，var為優(yōu)化問題的維度，因此，種群空間總體是一個大小為Npop×Nvar的矩陣．以寄生巢位置的優(yōu)劣作為算法的適應(yīng)度值，布谷鳥選擇寄生巢的過程即為算法尋優(yōu)的搜索過程，整個過程是局部隨機游動和全局探索隨機游動的平衡組合．

全局探索采用Lévy飛行執(zhí)行隨機游走，計算如公式(1)：

(1)

其中，nesti(t)表示第t代第i個待更新鳥巢，nesti(t+1)為更新后的下一代鳥巢，α是步長縮放因子，Levy(λ)是萊維隨機路徑，Levy(λ)～u=t-λ，⊕就是點對點乘積運算．

完成全局探索的Lévy飛行隨機游走后，在當(dāng)前解的基礎(chǔ)上，采用偏好隨機行走的方式(random walk)，完成局部搜索．根據(jù)發(fā)現(xiàn)概率Pa與產(chǎn)生的隨機數(shù)ε比較結(jié)果來完成尋優(yōu)，Pa的取值為0.25[8]，若Pa>ε，則表示鳥巢被發(fā)現(xiàn)，即當(dāng)前解為較差解，按公式(2)更新鳥巢的方向和位置，淘汰較差解，生成新的候選解．鳥巢位置更新公式描述如公式(2)：

(2)

基本CS算法的具體步驟如下:

Step 1.初始化．隨機產(chǎn)生N個鳥巢(即問題的解)，記錄最優(yōu)的解；

Step 2.利用萊維飛行進行解的位置更新，獲取新的候選解的位置，利用貪心選擇策略保留更好的

解；

Step 3.根據(jù)發(fā)現(xiàn)概率 Pa，丟棄部分解，并用偏好隨機游動產(chǎn)生新的解替代丟棄的解；

Step 4.如果滿足終止條件，則輸出最好的解；否則，返回Step 2繼續(xù)迭代．

2 改進布谷鳥搜索算法

與其他基于群體智能的啟發(fā)式算法一樣，雖然布谷鳥搜索算法具有很強的全局搜索能力，然而其本身也存在優(yōu)化精度不高、容易早熟、搜索速度慢等缺陷．本文將信息熵權(quán)重引入到基本布谷鳥算法，來調(diào)控布谷鳥搜索鳥巢的范圍，改善布谷鳥算法的局部搜索能力．

2.1 信息熵

“熵”是德國物理學(xué)家克勞修斯(R·Clausius)在 1850 年提出的一個概念，是反映系統(tǒng)微觀粒子無序程度的宏觀物理量[9]．它在控制論、概率論、數(shù)論、天體物理、生命科學(xué)等領(lǐng)域都有重要應(yīng)用，在不同的學(xué)科中也有引申出的更為具體的定義，是各領(lǐng)域十分重要的參量．1948 年，香農(nóng)( C·E·Shannon)在 Bell System Technical Journal 上發(fā)表了《通信的數(shù)學(xué)原理》(A Mathematical Theory of Communication)一文，將熵的概引入信息論中，把熵作為一個隨機事件的不確定性信息量的量度，稱為“信息熵”，按照Shannon的觀點，信息熵與系統(tǒng)的有序化程度呈反比，其值隨著系統(tǒng)有序化程度的升高而逐漸降低，系統(tǒng)越是有序，信息熵就越低；反之，系統(tǒng)越是混亂，信息熵就越高[10]．

(3)

其中,H(X)代表信息系統(tǒng)的信息熵，Xi是系統(tǒng)中的隨機事件，Pi為隨機事件的概率．

2.2 信息熵權(quán)重計算

在信息論中，信息熵是對系統(tǒng)的有序化程度不確定性的一種度量，可以通過計算熵值來判斷一個事件的隨機性或系統(tǒng)中某個指標(biāo)的離散程度，指標(biāo)的熵值越小，其離散程度越大，該指標(biāo)對綜合評價的影響越大，其賦予的權(quán)重就越大[12-13]．現(xiàn)有布谷鳥優(yōu)化算法生成的一個隨機種群

(4)

其中，Nestt表示第t代的種群空間矩陣，由N個個體組成，每個個體包含D個分量，若第j個分量xij～xNj的信息熵值越大，則表示個體間該分量的離散程度越小，取值分布均勻，分量間差異性小，那么在決策過程中該分量影響力就越小，其權(quán)重也就越?。喾吹?，若該分量的信息熵值越小，那么表示選擇過程該分量影響力就越大．根據(jù)上述分析，信息熵值的大小與分量影響力作用相反，定義種群空間第j個分量的權(quán)重為公式(5)：

wj=1-Hj.

(5)

信息熵Hj越大，其賦予的權(quán)重Wj越小，影響力越?。?/p>

2.3 信息熵加權(quán)的布谷鳥算法

在此，把種群看作是一個系統(tǒng)，根據(jù)信息熵值法得到種群中個體分量權(quán)重為W= (w1，w2，…，wj)，1≤j≤D，將標(biāo)準(zhǔn)布谷鳥算法的偏好隨機游走局部搜索改進為如下公式：

(6)

根據(jù)上述改進思路，算法框架如下：

Step 1:設(shè)置初始化參數(shù)．種群數(shù)N，維數(shù)D，發(fā)現(xiàn)概率Pa和最大迭代次數(shù)，隨機產(chǎn)生N個鳥巢，記錄最優(yōu)的解；

Step 2:根據(jù)公式(1)進行鳥巢的位置更新，獲取新的候選解的位置，利用貪心選擇策略保留更好的解；

Step 3:根據(jù)公式(3)和公式(5)計算信息熵權(quán)重w；

Step 4:根據(jù)發(fā)現(xiàn)概率Pa，丟棄部分解，根據(jù)公式(6)更新鳥巢位置，并保留更好的解；

Step 5:若終止條件滿足，輸出最優(yōu)值；否則，返回Step 2繼續(xù)迭代．

3 實驗仿真

本次實驗在Matlab R2016a版本中，采用8個典型的測試函數(shù)進行實驗，用以檢驗本文改進算法的性能．算法初始參數(shù)：種群規(guī)模N=30，發(fā)現(xiàn)概率Pa=0.25，最大迭代次數(shù)為1 000，測試函數(shù)見表1．

表1 典型測試函數(shù)

基本CS算法和改進算法在30維的情況下，每個測試函數(shù)被兩種算法獨立調(diào)用30次, 30次運行后結(jié)果如表2所示．本文改進算法對F1-F8函數(shù)優(yōu)化結(jié)果求解精度均高于CS算法且方差均為0，其中F1-F3、F6、F8找到全局最優(yōu)解．而對于噪音函數(shù)Quartic，雖未達到理論最優(yōu)結(jié)果，但解的精度比CS算法高．綜上可以看到，在求解精度方面本文改進算法較基本CS算法具有一定的優(yōu)勢．

表2 兩種算法最優(yōu)值、平均值和方差

為更進一步驗證本文改進算法的性能，選擇經(jīng)典和聲搜索算法(HS)、粒子群算法(PSO)、本文改進算法和基本CS算法，對8個測試函數(shù)的進化過程進行模擬，進化曲線圖如圖1中(a)～(h)所示．最大迭代次數(shù)1 000.從圖中可以觀察到(a)-(h)的函數(shù)F1-F8利用本文算法均快速收斂，且函數(shù)F1-F3、F6和F8收斂至全局最優(yōu)解．另外，由進化圖曲線也反映出CS算法進化過程中缺乏活性，早熟收斂的特性．本文算法收斂速度和尋優(yōu)精度與其它算法相比較，有顯著的改善．

圖1 四種算法進化曲線圖

4 種群規(guī)模對算法執(zhí)行效率影響分析

本文改進算法把鳥巢種群空間看作是一個系統(tǒng)，根據(jù)信息熵值法計算種群個體分量權(quán)重為W=(w1，w2，…，wD)，種群規(guī)模不同，會影響算法的效率．圖2中以F1為測試函數(shù)，從種群規(guī)模N和維度D兩個方面，來檢驗兩者改變對本文算法效率的影響程度．(a)圖是算法精度達到1E-300，所完成的迭代次數(shù)，實驗中當(dāng)種群數(shù)N=30，維數(shù)D從5增加到500，需要的迭代次數(shù)從260增加到377；當(dāng)維數(shù)D=30，種群數(shù)N從5增加到500，迭代次數(shù)從312到339，變化幅度較?。?b)圖為迭代次數(shù)為1 000時，隨種群數(shù)和維度的變化，消耗的運行時間．當(dāng)種群數(shù)N=30，維數(shù)D增加到350維時，運行時間大幅增加；當(dāng)維度D=30，種群數(shù)N改變時，運行時間變化幅度較?。畯膱D2的算法運行效率評價圖看出，種群數(shù)的增加較之維度的增加，需要更少的迭代次數(shù)，消耗更少的運行時間，由此得出問題維數(shù)的變化對本文算法效率的影響更大，特別是高維的時候，而種群數(shù)的改變影響相對較小．

圖2 算法運行效率評價圖

5 結(jié)論

改進后的CS算法克服了尋優(yōu)過程的完全隨機性，在基本CS算法中引入了信息熵權(quán)重，用種群中個體分量的信息熵加權(quán)來衡量種群中個體的差異程度，并賦予不同的權(quán)重，有效避免了算法陷入局部最優(yōu)和早熟的缺陷，同時算法的求解精度有大幅度提高．仿真實驗的模擬和對比分析結(jié)果顯示，文中提出的改進布谷鳥算法是可行有效的，但在高維運行效率會降低．