一種簡化的布谷鳥搜索算法

李 輝

(福建水利電力職業技術學院 基礎部數學教研室， 福建 永安 366000)

0 引 言

優化問題廣泛存在于生活生產實踐的各個領域，其主要目的是從眾多方案中選取一個(一些)性能指標達到最優的方案，隨著人類社會的不斷進步和發展，優化對象越來越復雜，規模越來越大，條件越來越苛刻，傳統的優化手段很難處理，很多學者提出了智能優化算法，如遺傳算法、粒子群算法、蛙跳算法、人工魚群算法、蜂群算法等。該類算法模擬自然界動物特性進行尋優，對目標函數相關信息要求比較少，且便于改進和融合，因而日漸成為學界的研究熱點。

布谷鳥搜索算法(Cuckoo Search,CS)是由劍橋大學學者Yang和Suash于2009年提出的，該算法搜索機制簡單，參數少，易于實現，提出后受到很多學者的關注，如孫敏等人[1]通過自適應調整步長因子提高算法性能，葉亞榮等人[2]通過隨機擾動提高算法的收斂速度，張海南等人[3]將蟻群算法與布谷鳥搜索算法融合，提出了交互式學習的布谷鳥算法，而宋慶慶等人[4]則結合了擬牛頓算法對布谷鳥算法進行改進等。同時，也有學者將布谷鳥算法應用于梯級水庫調度優化[5]、邊坡滑面搜索[6]、色彩圖像分割[7]等。

但該算法搜索性能仍有待提高，本文進一步簡化布谷鳥搜索算法的機制，進化時充分利用群體信息，極大地提高了算法的收斂速度和精度，并且將本算法應用于求解約束優化問題，取得了較好的結果。

1 基本布谷鳥搜索算法

基本布谷鳥搜索算法通過引入鳥類的萊維飛行機制，模擬布谷鳥的產卵行為進行尋優，該算法設有3條規律，分別闡述如下。

(1)一只布谷鳥每年只產一個卵，并且隨機地選擇一個鳥巢進行孵化。

(2)具有最好的卵的鳥巢將被保留下來。

(3)鳥巢按一定概率被發現，鳥巢一旦被發現將被舍棄或者重新選位置修建。

在布谷鳥搜索算法中，個體位置更新利用萊維分布來實現，個體i的位置更新公式為：

xt+1i=xti+α·L(λ),

(1)

其中，α為步長因子，根據具體的優化問題而定，一般取值為1；L(λ)為服從參數為λ的萊維分布，即：

(2)

基本布谷鳥搜索算法首先在可行域內產生一組初始個體，確定最優個體xtb，然后保留最優個體，對其他個體按照式(1)進行位置更新，若新個體更優，則替換；對每一個個體按概率Pa進行變異，即對于個體i，若Pa小于一個均勻分布的隨機數，則重新隨機產生一個新個體xnew，若xnew優于個體i，則替換，否則不替換。循環進行，直到達到收斂條件。

分析可知，基本布谷鳥搜索算法中的萊維分布過于復雜，個體在更新過程中利用了自身信息和最優個體的信息，但是在變異時隨機產生新個體，沒有充分利用群體信息，容易延緩算法的收斂速度，且基本布谷鳥搜索算法收斂精度不高，考慮到這些不足，本次研究簡化了個體更新算法，將萊維分布函數進行了簡化，便于操作和實現，同時，利用個體自身適應度和最優個體的適應度進行變異，有效地解決了算法復雜，收斂性能較差的問題，本文提出了一種改進的簡化布谷鳥搜索算法(A simplified cuckoo search，SCS)。

2 一種簡化的布谷鳥搜索算法

萊維分布是鳥類的萊維飛行機制的反映，但是計算偏于復雜，不便于廣泛應用，且嚴重影響計算速度，因此，文中將萊維分布進行了簡化，即對于個體i按照以下方式進行位置更新：

xt+1i=xti+α·L,

(3)

(4)

其中，v～N(0,1)，u～N(0,2)，當隨機數r>Pa時，對個體i按下式進行更新：

(5)

其中，fit(xi)為個體i的適應度，ε為一個極小的數，防止分母為零。

改進的簡化布谷鳥搜索算法流程可表述為：

Step1初始化。在可行域內隨機產生n個初始個體，設置步長因子α，變異概率Pa，最大迭代次數T，記錄當前最優個體xtb。

Step2局部搜索。對除最優個體之外的所有個體按照式(3)和式(4)進行更新，若新個體更優，則替換，否則不替換。

Step3隨機變異。對于每一個個體xti，隨機產生一個均勻分布數r，若r>Pa，則對個體xti按式(5)進行變異，若新個體優于原個體，則替換；否則，保留原個體。

Step4判斷停機條件，達到則輸出最優解；否則，轉Step 2。

3 實驗及結果分析

本文使用常用的4個測試函數，對算法的性能進行檢驗，測試函數見表1。其中，函數f1為單極值函數，函數f3和函數f4為多極值函數，根據經驗，目標最優值設置也參見表1，由于函數f2的全局最優點位于一個平滑、狹長的拋物線形山谷內，由此可推得，目標精度通常為30。相關參數設置為：個體數為30，步長因子α=1，變異概率Pa=0.25。

表1 測試函數

Tab. 1 The test functions

名稱公式維數搜索范圍理論最優值目標最優值Sphere f1f1(x)=∑ni=1x2i30[-100,100]n01E-15Rosenbrock f2f2(x)=∑n-1i=1(100(xi+1-x2i)2+(xi-1)2)30[-100,100]n030Rastrigrin f3f3(x)=∑ni=1(x2i-10cos(2πxi)+10)30[-100,100]n01E-15Griewank f4f4(x)=14 000∑ni=1x2i-cosxii+130[-600,600]n01E-15

DCBA和BA對4個函數的進化對比如圖1所示。圖1中，橫軸為算法迭代次數，縱軸為全局最優值，最大迭代次數為100，CS為基本布谷鳥搜索算法進化曲線，SCS為本文算法進化曲線。從圖1中可以清楚地看出：改進的簡化布谷鳥搜索算法對4個測試函數的搜索速度和精度都非常出色，都可以在極少的迭代次數下找到目標最優值。

將改進布谷鳥搜索算法的搜索性能與基本布谷鳥搜索算法和文獻[8]中的算法進行比較，所得結果見表2和表3。其中，CS表示基本布谷鳥搜索算法，MPCS表示文獻[8]中的算法，SCS表示本文中的改進算法；所有算法的最大迭代次數均為500次，超過500次仍沒有達到目標最優值，則認為算法不收斂?？梢钥闯觯倪M布谷鳥搜索算法的收斂精度比其它算法都高，且所需迭代次數非常少。該算法可在極少的迭代次數下搜索到函數1、函數3和函數4的理論最優值，也可以迅速找到函數2的目標最優值、且收斂率都是100%。

(a) 函數f1

(b) 函數f2

(c) 函數f3

(d) 函數f4

Fig. 1 The convergence speed and accuracy of 100 times' iteration

表2 SCS算法與其他算法收斂精度的比較

Tab. 2 Comparison of search accuracy between SCS with other algorithms

函數算法最優值最差值平均值f1CS1.252E-166.578E-151.459E-15MPCS2.617E-179.610E-162.252E-16SCS000f2CS67.3941 720.215459.460MPCS60.2801 110.784272.477SCS28.01329.89628.214f3CS1.7319.0686.179MPCS1.4294.9803.213SCS000f4CS2.357E-031.365E-017.017E-02MPCS1.166E-031.539E-013.707E-02SCS000

表3 SCS算法與其他算法收斂速度的比較

Tab. 3 Comparison of search speed between SCS with other algorithms

函數算法收斂所需最小迭代次數收斂所需最大迭代次數收斂所需平均迭代次數收斂率f1CS955998982.2012/20MPCS913997956.2020/20SCS936.1320/20f2CS691994831.300/20MPCS540947722.500/20SCS122015.2020/20f3CS500991802.400/20MPCS189984416.900/20SCS18712.3220/20f4CS753986908.000/20MPCS664931806.300/20SCS1158.3020/20

4 算法的應用

4.1 帶約束的單目標優化問題

單目標約束優化問題基本模型如下：

minf(x1,x2,…,xn)

(6)

本文在可行域內給定初始解，通過改進布谷鳥搜索算法進行不斷迭代，直到找到最優解。對于約束條件，文中使用罰函數法，即做如下數學定義：

F(x1,x2,…,xn)=f(x1,x2,…,xn)+

(7)

其中，λ,γ為懲罰因子，取比較大的正數。

因此，帶約束的單目標優化問題解決思路為：在可行域內給定初始解，作為初始個體，按照式(7)計算適應度值，記錄最優個體和當前最優值，并根據改進的簡化布谷鳥搜索算法進行尋優，直至找到最優值，記錄最優個體，計算求出原目標函數的最優值。

4.2 數值實驗

通過以下約束優化問題檢驗DCBA算法的性能：

(8)

該函數的理論最優值為2.2。采用本文提出的簡化布谷鳥搜索算法進行尋優，定義適應度函數為：

F=4x1+x2+x3+λ((2x1+x2+x3-4)2+(3x1+3x2+x3-3)2)+γ(x12+x22+x32).

(9)

設置最大迭代次數為500次，步長因子取5，設置不同懲罰因子時搜索到的最優值見表4。當懲罰因子逐漸增大時，最優值不斷穩定于2.2。

表4 不同懲罰因子下目標函數的最優值

Tab. 4 Optimal value of objective function under different penalty functions

懲罰因子λ懲罰因子 γ最優值2002002.435 12005002.301 22001 0002.295 15001 0002.300 11 0005 0002.248 51 00010 0002.202 22 00010 0002.201 710 0001 000 0002.200 1

5 結束語

本文將布谷鳥搜索算法中的萊維分布函數進行了簡化，提出了一種簡化的布谷鳥搜索算法。該算法中不僅個體更新的萊維分布函數更加簡單易算，而且在個體變異時，還引入了適應度信息，加快了算法的尋優速度，數值實驗發現，該算法不僅操作簡單，且尋優性能非常理想。同時，本文將新算法用于求解約束優化問題，發現其尋優效果也非常好。因此，改進的簡化布谷鳥搜索算法是一種簡單易行、魯棒性高、融合性強的高性能尋優算法。