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

李 輝

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

0 引 言

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

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

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

1 基本布谷鳥搜索算法

基本布谷鳥搜索算法通過引入鳥類的萊維飛行機制，模擬布谷鳥的產(chǎn)卵行為進行尋優(yōu)，該算法設(shè)有3條規(guī)律，分別闡述如下。

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

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

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

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

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

(1)

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

(2)

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

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

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

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

xt+1i=xti+α·L,

(3)

(4)

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

(5)

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

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

Step1初始化。在可行域內(nèi)隨機產(chǎn)生n個初始個體，設(shè)置步長因子α，變異概率Pa，最大迭代次數(shù)T，記錄當前最優(yōu)個體xtb。

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

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

Step4判斷停機條件，達到則輸出最優(yōu)解；否則，轉(zhuǎn)Step 2。

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

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

表1 測試函數(shù)

Tab. 1 The test functions

名稱公式維數(shù)搜索范圍理論最優(yōu)值目標最優(yōu)值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個函數(shù)的進化對比如圖1所示。圖1中，橫軸為算法迭代次數(shù)，縱軸為全局最優(yōu)值，最大迭代次數(shù)為100，CS為基本布谷鳥搜索算法進化曲線，SCS為本文算法進化曲線。從圖1中可以清楚地看出：改進的簡化布谷鳥搜索算法對4個測試函數(shù)的搜索速度和精度都非常出色，都可以在極少的迭代次數(shù)下找到目標最優(yōu)值。

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

(a) 函數(shù)f1

(b) 函數(shù)f2

(c) 函數(shù)f3

(d) 函數(shù)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

函數(shù)算法最優(yōu)值最差值平均值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

函數(shù)算法收斂所需最小迭代次數(shù)收斂所需最大迭代次數(shù)收斂所需平均迭代次數(shù)收斂率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 算法的應(yīng)用

4.1 帶約束的單目標優(yōu)化問題

單目標約束優(yōu)化問題基本模型如下：

minf(x1,x2,…,xn)

(6)

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

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

(7)

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

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

4.2 數(shù)值實驗

通過以下約束優(yōu)化問題檢驗DCBA算法的性能：

(8)

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

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

(9)

設(shè)置最大迭代次數(shù)為500次，步長因子取5，設(shè)置不同懲罰因子時搜索到的最優(yōu)值見表4。當懲罰因子逐漸增大時，最優(yōu)值不斷穩(wěn)定于2.2。

表4 不同懲罰因子下目標函數(shù)的最優(yōu)值

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

懲罰因子λ懲罰因子 γ最優(yōu)值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 結(jié)束語

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