陳 程，賀興時+，楊新社

1.西安工程大學理學院，西安710600

2.密德薩斯大學科學與技術(shù)學院，英國劍橋CB2 1TN

眾所周知，隨著人類和科技的發(fā)展，無論是在工程實踐領(lǐng)域還是在研究領(lǐng)域，都會遇到越來越復雜的優(yōu)化問題。人們使用一些傳統(tǒng)的計算方法來解決這些問題時，求解精度以及收斂速度等方面均不能滿足實際的需求，且耗時長、成本高。為解決復雜的優(yōu)化問題，能找到更為合理和滿意的近似解，科研工作者設計了大量的啟發(fā)式算法，而在對自然啟發(fā)式優(yōu)化算法的研究中，群體智能算法在過去的二三十年中得到迅速發(fā)展，并成為當前最活躍的算法研究領(lǐng)域之一。群體智能算法主要有：螢火蟲算法（firefly algorithm，F(xiàn)A）[1]、蝙蝠算法（bat algorithm，BA）[2]、蛙跳算法（shuffled frog leading algorithm，SFLA）[3]、粒子群優(yōu)化算法（particle swarm optimization，PSO）[4]等。諸多學者也提出許多改進策略：學習因子獨立調(diào)整策略[5]、自適應交叉策略[6]、早熟擾動[7]等策略，使群體智能算法在解決復雜優(yōu)化問題時更加有效和高效。

2009 年，劍橋大學的Yang 和Deb 通過模擬布谷鳥尋窩產(chǎn)卵的行為提出了一種新的搜索算法，即布谷鳥搜索算法（cuckoo search，CS）[8]，由于這種算法簡單高效、參數(shù)少、易于實現(xiàn)、隨機搜索路徑優(yōu)等特點，已成功應用于醫(yī)學圖像優(yōu)化[9]、多目標優(yōu)化[10]、圖像處理[11]、系統(tǒng)設計優(yōu)化[12]、BT 神經(jīng)網(wǎng)絡（back propagation，BP）[13]、旅行商問題（traveling salesman problem，TSP）[14]等實際問題中。但也存在著求解精度低，易陷入局部最優(yōu)，收斂速度慢等方面問題，針對這些問題諸多學者也提出了相應的改進方案。王凡等[15]提出了一種在迭代過程中對鳥窩位置加入高斯擾動的方法，它增加了鳥窩位置變化的活力，從而有效地提高了算法的收斂速度。羅東等[16]將函數(shù)動態(tài)遞減因子引入到步長和發(fā)現(xiàn)概率中，并對步長和發(fā)現(xiàn)概率進行自適應調(diào)整，改進后的布谷鳥算法在收斂速度和求解精度方面均有效提高。葉亞榮等[17]在布谷鳥尋找最優(yōu)鳥窩的時候增加了一個擾動因子，提高算法的收斂速度。王凡等[18]通過分析鳥窩位的群體狀態(tài)轉(zhuǎn)移過程加入了Markov 鏈，提高算法全局搜索能力。宋鈺等[19]提出了一種基于自適應機制的改進布谷鳥算法，提高了算法的局部和全局尋優(yōu)能力。賈涵等[20]利用狀態(tài)判別參數(shù)Ps，通過探索-開發(fā)平衡狀態(tài)計算出平衡參數(shù)Peb，最終實現(xiàn)鳥蛋的被發(fā)現(xiàn)概率Pa的自適應動態(tài)調(diào)整。但是，對于CS 算法的局部搜索能力弱，易陷入局部最優(yōu)，算法后期收斂速度慢，求解精度不高等問題，上述改進策略的優(yōu)化效果仍是有限的。針對CS 算法存在的諸多問題，本文提出了動態(tài)調(diào)整概率的雙重布谷鳥搜索算法（double cuckoo search algorithm with dynamically adjusted probability，DECS），并增加以下策略：將搜索空間分區(qū)化，計算種群分布熵確定種群的分布特性，同時與算法的迭代階數(shù)共同決定發(fā)現(xiàn)概率P0的大??；通過在尋優(yōu)過程中引入的新型步長因子以及記憶策略，實現(xiàn)算法雙重搜索模式的能力；在隨機偏好游走更新公式中，引入了非線性慣性權(quán)重對數(shù)遞減策略及高斯擾動，更大程度地提高鳥窩的探索和開發(fā)能力，增強了鳥窩位置的變化活力。通過以上策略，有效改善了布谷鳥搜索算法求解精度低，收斂速度慢，易陷入局部最優(yōu)的問題。

1 基本的布谷鳥搜索算法

在大自然中，布谷鳥具有特殊的繁衍后代的方式，它們不筑巢，將自己的后代用寄生的方式來養(yǎng)育，通過將自己的卵悄悄地產(chǎn)在其他鳥的巢穴中，由其他鳥為它來卵化和撫養(yǎng)自己的下一代。然而如果宿主鳥一旦發(fā)現(xiàn)有外來的鳥蛋，宿主鳥就會拋棄這些外來的鳥蛋或者重新筑巢，為了模擬布谷鳥尋窩和繁衍后代的行為，Yang 和Deb 假設了以下三個理想規(guī)則：

（1）布谷鳥一次只產(chǎn)下一個蛋，并且隨機選擇鳥窩來孵化；

（2）最好的鳥窩將被保留到下一代；

（3）可選擇的鳥窩數(shù)量N是固定的,宿主鳥發(fā)現(xiàn)外來卵的概率Pa∈[0,1]。

基于以上三個理想狀態(tài)，Yang 等采用式（1）對下一代鳥窩位置x(t+1)進行位置更新：

由式（2）可知，布谷鳥在尋窩過程中，它的飛行路徑變化帶有重尾的概率分布，使得布谷鳥飛行路徑表現(xiàn)出了Levy 飛行的本質(zhì)，即在尋優(yōu)路徑中頻繁的短步長偶爾會出現(xiàn)長步長，使得CS 算法擁有更大的全局搜索能力，也可以有效避免陷入局部最優(yōu)。

文獻[21]采用式（3）計算萊維隨機數(shù)：

其中，υ和μ服從標準的正態(tài)分布，β=1.5，φ=

為了便于對萊維飛行進行計算，采用文獻[21]步長因子：

其中，α0為常數(shù)，一般取0.01，xbest為當前最優(yōu)解。

結(jié)合式（1）～式（4），CS 算法通過Levy 飛行采用式（5）來更新新的鳥窩位置：

發(fā)現(xiàn)概率Pa表示為宿主鳥發(fā)現(xiàn)外來鳥蛋的概率，如果發(fā)現(xiàn)有外來的鳥蛋，宿主鳥就會拋棄這些外來的鳥蛋或者重新筑巢，即CS 算法通過萊維飛行更新位置后，產(chǎn)生一個隨機數(shù)r∈[0,1]，若r＞Pa時，則對采用偏好游走的方式生成相同數(shù)量的新解。偏好游走如式（6）所示：

式中，γ是(0,1) 區(qū)間均勻分布的壓縮因子，表示第t代的兩個隨機解。

2 動態(tài)調(diào)整概率的雙重布谷鳥搜索算法

2.1 動態(tài)權(quán)重下改變自適應概率P0

在基本CS 算法中固定發(fā)現(xiàn)概率P=0.25 不利于全局搜索和局部搜索之間的平衡，因此諸多學者在發(fā)現(xiàn)概率中引入了自適應性Pa，使得算法更具有靈活性，自適應Pa是CS 算法重要的參數(shù)之一，控制著全局和局部之間的平衡。當Pa值小時，增加了全局的多樣性，增強了全局的探索性和開發(fā)性。當Pa越大時，加強了局部搜索能力，提高了算法的效率。設立一個合理的Pa可以平衡全局和局部的搜索能力，提高算法的整體性能。在關(guān)于Pa的大小控制，國內(nèi)外諸多學者做出了大量的研究，文獻[22]提出自適應布谷鳥搜索算法（adaptive cuckoo search algorithm，ACS），其中自適應性概率Pa的方法如式（7）：

式中，采用文獻[22]的參數(shù)θ，θ=0.6。自適應性概率Pa方法簡單，易實現(xiàn)，但是只考慮到發(fā)現(xiàn)概率P隨著迭代次數(shù)的變化而變化。這樣不利于全局和局部的搜索，對一些復雜的、高維的函數(shù)求解很難適應。因此在考慮發(fā)現(xiàn)概率Pa隨迭代次數(shù)變化的同時，也應該考慮到每次迭代種群分布情況。發(fā)現(xiàn)概率P0的大小由自適應性Pa和空間種群分布位置分布信息共同決定，如式（8）：

式中，Gi是慣性權(quán)重的變異算子，其大小由解空間中種群分布的位置情況來決定。

因此本文采用文獻[23]提出的分布熵來表達，如式（9）：

式中，j=1,2,…,K，K是解空間Ω被等分劃分的個數(shù)；N是布谷鳥的總個數(shù)；nj是每次迭代后每個等分子空間中布谷鳥分布的個數(shù)。

Si表明種群分布情況。每次迭代后Si越大，說明布谷鳥越分散，Gi應該賦予一個較小的值，使發(fā)現(xiàn)概率P0越小，加強全局搜索能力。反之Si越小說明布谷鳥越集中，Gi應該賦予一個較大的值，使發(fā)現(xiàn)概率P0越大，加強局部探索能力。Gi的具體表達式為式（10）：

其中，Sd=lnK是種群分布熵的上界，即為在平分的解空間Ω中，每一個子空間中有著相同數(shù)目的種群個數(shù)；Sc是種群分布熵的下界，即為在被平分的解空間Ω中，N個布谷鳥全部分布在其中的某一個子空間Ωj中；δ是參數(shù)。

當布谷鳥全部集中在某個子空間Ωj時，由式（10）可得Gmax=δ，經(jīng)大量實驗測試[24]，P0max=0.55 為最佳取值。由式（8）可得，因此參數(shù)δ取值為0.751 3。

2.2 自適應雙重搜索萊維飛行

基本的布谷鳥搜索算法中的萊維飛行機制，在尋優(yōu)過程中偶爾出現(xiàn)的大步長，雖然增強了全局搜索能力，但是還是會存在陷入局部最優(yōu)的情況。步長因子α一直較大，全局搜索能力強，無法獲得高精度的解。步長因子α一直較小，算法要達到高精度的解時，就要付出更多的迭代次數(shù)，算法的效率低下。針對以上問題，本文提出了自適應雙重搜索萊維飛行機制。步長因子由固定的α改為隨迭代次數(shù)增加而變化的動態(tài)變化步長因子ω，如式（11）：

改進的萊維飛行更新公式（12）為：

式中，ti是當前迭代次數(shù)，tmax是最大迭代次數(shù)，?為參數(shù)。

ω1=因子動態(tài)變化范圍[0,0.367 9]，使動態(tài)因子ω變化在[0,1]范圍內(nèi)，由式（11）得?=，?取值為2.718 3。

式（11）中ω在（0,1）之間的隨著迭代次數(shù)增加的變化如圖1。

Fig.1 Factor ω curve圖1 因子ω 變化曲線

由圖1 可知，在DECS 算法中前期，由于記憶策略引入到Levy 飛行搜索機制中，即用上一代鳥窩反饋位置信息決定下一代鳥窩位置，實現(xiàn)種群由子空間Ω1,Ω2,…,Ωk到整體解空間Ω進行Levy 飛行機制搜索過程，整個解空間種群分布信息決定Gi值的大小，使得DECS 算法前期的多樣性更強。DECS 算法中后期種群全局探索能力逐漸減弱，局部開發(fā)能力增強，實現(xiàn)雙重搜索機制。發(fā)現(xiàn)概率P0與雙重搜索形成了一個互補的狀態(tài)，使得DECS 算法有效克服了易陷入局部最優(yōu)的缺陷，提高算法性能。

2.3 對數(shù)遞減慣性權(quán)重偏好游走

在基本的CS 算法中，偏好隨機游走對全局搜索能力和局部搜索能力起著平衡作用，新的鳥巢位置采用固定的上一代鳥窩位置信息，容易造成算法迭代后期陷入局部最優(yōu)。慣性權(quán)重策略可以提高算法的搜索能力，平衡局部搜索和全局搜索之間的關(guān)系，因此本文在偏好游走的更新位置中引入了對數(shù)遞減慣性權(quán)重κ，如式（13）：

式中，rmax是慣性權(quán)重最大值，rmin是慣性權(quán)重最小值；取參考文獻[24]rmax=0.1，rmin=0 。ti為當前迭代次數(shù)，tmax為最大迭代次數(shù)；ξ為對數(shù)壓縮系數(shù)，N(μ,σ)是高斯擾動。慣性權(quán)重κ前兩項利用對數(shù)遞減的特性，隨著迭代次數(shù)的增加而減小，而第三項利用高斯擾動，使得慣性權(quán)重κ更具有靈活性。

偏好游走更新公式更新為式（14）：

式中，κ是對數(shù)遞減慣性權(quán)重；γ是（0,1）區(qū)間均勻分布的壓縮因子；表示第t代的兩個隨機解。

在DECS 算法中，偏好游走位置更新引入了對數(shù)遞減慣性權(quán)重的策略，使得布谷鳥算法在尋優(yōu)前期較為完整保留上一代鳥窩的信息，有利于跳出子空間Ωj中的局部最優(yōu)。隨著迭代次數(shù)的增加慣性權(quán)重的減小，布谷鳥算法在尋優(yōu)后期，有效削弱了上一代鳥窩的保留信息，更有利于跳出全局局部最優(yōu)解。

2.4 DECS 算法的流程

動態(tài)調(diào)整概率的雙重布谷鳥搜索算法（DECS）著眼于對算法整體優(yōu)化，充分利用新型步長因子、發(fā)現(xiàn)概率P0和隨機偏好游走搜索方式三者之間的關(guān)系。DECS 算法前期利用新型步長因子和種群位置更新的記憶策略，保證種群在子空間中充分勘探和尋找最優(yōu)解的效率；與此同時發(fā)現(xiàn)概率P0中引入的種群分布熵，確保了P0在整個迭代期保持著一個動態(tài)變化的狀態(tài)，使得算法更具有活力，增強了算法前期鳥窩的多樣性，提升了全局搜索能力，也兼顧了算法后期局部開發(fā)的能力。DECS 算法的步驟如下：

步驟1初始化設置：最大迭代次數(shù)t，布谷鳥的個數(shù)N，解空間劃分個數(shù)K，發(fā)現(xiàn)概率Pa，搜索空間的維數(shù)nd，搜索上下界。初始化鳥窩位置，算出每個鳥窩的適應度值fi=f(xi)，i=1,2,…,N，得到最好鳥窩位置，最優(yōu)的適應度值fmin。

步驟2保留最好的鳥窩位置，按式（12），對每一個鳥窩進行Levy 飛行位置更新，得到一組新的鳥窩解，并計算新的適應度值，與上一代鳥窩位置進行比較，適應度值優(yōu)的位置替代適應度值差的位置，得到一組較優(yōu)的鳥窩位置

步驟3通過種群的分布情況計算出當前第t次迭代的發(fā)現(xiàn)概率Pa，與隨機數(shù)r進行比較。若r＞Pa，則用式（14）進行偏好游走搜索方式，淘汰鳥窩數(shù)量相同的新解。

步驟4計算出淘汰的新解的適應度值，與Gt=的適應度值進行比較，適應度值優(yōu)的位置替代適應度值差的位置，得到一組較優(yōu)的鳥窩位置

步驟5找出中最好的鳥窩位置和最優(yōu)的適應度值fmin。

判斷是否滿足終止條件，若滿足則停止搜索，輸出全局最優(yōu)值fmin，否則，重復步驟1～步驟4 進行迭代搜索。

3 仿真實驗

為了驗證DECS 算法的尋優(yōu)性能，本文選取了19個不同難度的測試函數(shù)，如表1 所示。同時與基本的CS算法、花粉算法（flower pollination algorithm，F(xiàn)PA）[25]、BA 算法以及自適應步長布谷鳥搜索算法（adaptive step-size cuckoo search algorithm，ASCSA）[26]四種算法進行了比較，針對不同算法獨立運行50 次。其中f1(x)～f7(x) 為多峰函數(shù)，f8(x)～f12(x)為單峰函數(shù)，維數(shù)D=10,50,100。f13(x)～f14(x)為固定維度單峰函數(shù)，f15(x)～f19(x)為固定維度多峰函數(shù)，維數(shù)D=2。記錄每次測試結(jié)果并計算平均值、最佳值、最差值、標準差。

3.1 測試環(huán)境及算法參數(shù)

實驗環(huán)境如下：CPU 為i5-4258U 2.4 GHz，運行內(nèi)存4 GB，操作系統(tǒng)Windows10，編程環(huán)境Matlab r2016。CS 算法、FPA 算法、BA 算法、ASCSA 算法種群數(shù)目為25，迭代次數(shù)1 000次，其他參數(shù)見表2所示。

3.2 算法求解精度比較分析

算法求解精度比較如表3～表21 所示。

本文運用5 種算法對19 個測試函數(shù)進行了比較，分別在相同的測試環(huán)境下運行了50 次，f1(x)為復雜的多峰函數(shù)，擁有無數(shù)局部極小值和局部最大值，常常導致算法在求解時陷入局部最優(yōu)。由表3 可見，DECS算法在求解精度上和穩(wěn)定性上遠遠高于其他4種算法，在后期求解時卻陷入了局部最優(yōu)8.881 8E-16。f2(x)函數(shù)為典型的非線性多模態(tài)函數(shù)，它的局部極小值的個數(shù)與維數(shù)成正比且跌宕起伏不定，由表4 可見，其他4 種算法隨著維數(shù)的增加尋優(yōu)能力減弱，DECS 算法卻表現(xiàn)出顯著的尋優(yōu)能力，均可以尋到全局最優(yōu)。f3(x)是典型多模態(tài)函數(shù)，搜索空間大并擁有許多局部極小點，通常被認為是智能算法很難求解的問題。由表5 可見，DECS 算法均可收斂到理論最優(yōu)值，表現(xiàn)出了較好的搜索能力和跳出局部最優(yōu)的能力。f4(x)～f7(x)為復雜的多峰函數(shù)，DECS 算法也表現(xiàn)出顯著的尋優(yōu)能力，均可以尋到全局最優(yōu)。CS 算法、FPA 算法、BA 算法、ASCSA 算法卻無法獲得全局最優(yōu)點，在精度上DECS 算法表現(xiàn)出了卓越的性能。DECS 算法在維度增加的過程中，仍然表現(xiàn)出卓越的搜索能力和穩(wěn)定的收斂性。CS 算法、FPA 算法、BA 算法、ASCSA 算法隨著維度的增加，求解精度也明顯下降，且無法尋找到全局最優(yōu)點。ASCSA算法與DECS 算法相比較，在10 維的情況下，有著尋優(yōu)精度上的差別，但是在50 維和100 維的情況下，ASCSA 算法卻無法尋找到全局最優(yōu)。f8(x)～f12(x)均為單峰函數(shù)，f9(x)函數(shù)由于它的全局最小值附近函數(shù)變化極慢，因此常被用于評價算法的后期搜索性能。f12(x)函數(shù)常用于檢查算法的尋優(yōu)能力。DECS算法在10 維、50 維、100 維情況下，均可收斂到理論最優(yōu)值。對于二維函數(shù)f13(x)～f19(x)，DECS 算法均可收斂到理論最優(yōu)值，對于f15(x)、f17(x)、f18(x) 函數(shù)ASCSA 算法和FPA 算法也均可收斂到理論最優(yōu)值，但在標準差上DECS 算法優(yōu)于ASCSA 算法和FPA 算法，表明DECS 算法在尋優(yōu)穩(wěn)定性方面優(yōu)于CS 算法、FPA 算法、BA 算法、ASCSA 算法，且表現(xiàn)出更強的魯棒性。

Table 1 Test functions表1 測試函數(shù)

Table 2 Algorithm parameter settings表2 算法參數(shù)設置

Table 3 Simulation results of f1(x)Ackley function表3 f1(x)Ackley 函數(shù)仿真結(jié)果

Table 4 Simulation results of f2(x)Rastrigin function表4 f2(x)Rastrigin 函數(shù)仿真結(jié)果

Table 5 Simulation results of f3(x)Griewank function表5 f3(x)Griewank 函數(shù)仿真結(jié)果

Table 6 Simulation results of f4(x)Zakharov function表6 f4(x)Zakharov 函數(shù)仿真結(jié)果

Table 7 Simulation results of f5(x)Alpine function表7 f5(x)Alpine函數(shù)仿真結(jié)果

Table 8 Simulation results of f6(x)Exponential function表8 f6(x)Exponential函數(shù)仿真結(jié)果

Table 10 Simulation results of f8(x)Schwefel 2.22 function表10 f8(x)Schwefel 2.22 函數(shù)仿真結(jié)果

Table 11 Simulation results of f9(x)Sphere function表11 f9(x)Sphere函數(shù)仿真結(jié)果

Table 15 Simulation results of f13(x)Beale function表15 f13(x) Beale函數(shù)仿真結(jié)果

Table 16 Simulation results of f14(x)Booth function表16 f14(x) Booth 函數(shù)仿真結(jié)果

Table 17 Simulation results of f15(x)Goldstein&Price function表17 f15(x) Goldstein&Price函數(shù)仿真結(jié)果

Table 18 Simulation results of f16(x)Bohachevsky function表18 f16(x) Bohachevsky 函數(shù)仿真結(jié)果

Table 19 Simulation results of f17(x)Easom function表19 f17(x) Easom 函數(shù)仿真結(jié)果

Table 20 Simulation results of f18(x)Branin function表20 f18(x) Branin 函數(shù)仿真結(jié)果

Table 21 Simulation results of f19(x) Shubert function表21 f19(x) Shubert函數(shù)仿真結(jié)果

3.3 算法收斂曲線分析

圖2～圖20 分別是5 種算法f1(x)～f19(x)的收斂曲線圖，直觀地反映出了5 種算法的收斂速度和收斂精度。圖2～圖13 是維數(shù)D=10，f1(x)～f12(x)函數(shù)收斂曲線圖，圖14～圖20 是維數(shù)D=2，f13(x)～f19(x)函數(shù)收斂曲線圖。在D=10 維測試情況下，由圖2～圖13可知，DECS 算法在收斂速度上優(yōu)于CS 算法、FPA 算法、BA 算法、ASCSA 算法，且?guī)缀踉?00 代之內(nèi)可以收斂到全局最優(yōu)，表明DECS 算法具有較快的收斂速度和較好的收斂精度。f2(x)～f7(x)、f15(x)～f19(x)為多峰函數(shù)且存在多個局部極小點，測試算法的跳出局部最優(yōu)和尋優(yōu)能力。由圖3～圖8，圖16～圖20 可以看出DECS 算法具有較強的尋優(yōu)能力，克服了易陷入局部最優(yōu)的缺點。f8(x)～f14(x)為單峰函數(shù)，測試算法的收斂速度。由圖9～圖15 可以看出DECS 算法在100 代以內(nèi)可以收斂到理論最優(yōu)值。通過對這5 種算法的收斂曲線比對分析可知，無論是高維、低維還是單峰或多峰函數(shù)，DECS 算法都具有較好的尋優(yōu)能力和較快的收斂速度。

Fig.2 Convergence curves of Ackley function圖2 Ackley 函數(shù)收斂曲線圖

Fig.3 Convergence curves of Rastrigin function圖3 Rastrigin 函數(shù)收斂曲線圖

Fig.4 Convergence curves of Griewank function圖4 Griewank 函數(shù)收斂曲線圖

Fig.5 Convergence curves of Zakharov function圖5 Zakharov 函數(shù)收斂曲線圖

Fig.6 Convergence curves of Alpine function圖6 Alpine函數(shù)收斂曲線圖

Fig.7 Convergence curves of Exponential function圖7 Exponential函數(shù)收斂曲線圖

Fig.8 Convergence curves of Schaffer function圖8 Schaffer函數(shù)收斂曲線圖

Fig.9 Convergence curves of Schwefel 2.22圖9 Schwefel 2.22 函數(shù)收斂曲線圖

Fig.10 Convergence curves of Sphere function圖10 Sphere函數(shù)收斂曲線圖

Fig.11 Convergence curves of Schwefel 1.2 function圖11 Schwefel 1.2 函數(shù)收斂曲線圖

Fig.12 Convergence curves of Chung Reynolds function圖12 Chung Reynolds函數(shù)收斂曲線圖

Fig.13 Convergence curves of Sum squares function圖13 Sum squares函數(shù)收斂曲線圖

Fig.14 Convergence curves of Beale function圖14 Beale函數(shù)收斂曲線圖

Fig.15 Convergence curves of Booth function圖15 Booth 函數(shù)收斂曲線圖

Fig.16 Convergence curves of Goldstein&Price function圖16 Goldstein&Price函數(shù)收斂曲線圖

Fig.17 Convergence curves of Bohachevsky function圖17 Bohachevsky 函數(shù)收斂曲線圖

Fig.18 Convergence curves of Easom function圖18 Easom 函數(shù)收斂曲線圖

Fig.19 Convergence curves of Branin function圖19 Branin 函數(shù)收斂曲線圖

Fig.20 Convergence curves of Shubert function圖20 Shubert函數(shù)收斂曲線圖

3.4 三種策略下發(fā)現(xiàn)概率P 的比較分析

在布谷鳥搜索算法中發(fā)現(xiàn)概率P為重要的參數(shù)之一，為了比較三種策略下發(fā)現(xiàn)概率P的曲線變化，選取本文表1 中的f3(x)函數(shù)進行測試。f3(x)是典型的非線性多模態(tài)函數(shù)，搜索空間大并具有許多局部極小點。CS 算法、ACS 算法參數(shù)設置與表2 中DECS算法參數(shù)設置相同。

這里CS 算法發(fā)現(xiàn)概率P=0.25；ACS 算法發(fā)現(xiàn)概率Pa是典型性的自適應概率；DECS 算法發(fā)現(xiàn)概率P0是在典型的自適應概率Pa的基礎(chǔ)上，引入種群分布熵的策略。

由圖21 可知，CS 算法發(fā)現(xiàn)概率P=0.25 概率分布圖為一條直線，在整個迭代過程中發(fā)現(xiàn)概率為一個固定值。由圖22 可知，ACS 算法發(fā)現(xiàn)概率Pa概率分布圖為一條拋物線，發(fā)現(xiàn)概率Pa隨著迭代次數(shù)的增加而增加，在ACS 算法中迭代次數(shù)為200 次時，發(fā)現(xiàn)概率Pa已經(jīng)達到0.416 6，不利于算法前期的種群多樣性。DECS 算法發(fā)現(xiàn)概率P0概率分布圖為一條不規(guī)則且跌宕起伏的曲線圖。由式（8）可知發(fā)現(xiàn)概率P0的大小由自適應性Pa和空間種群分布位置分布信息共同決定。Si表明著種群分布情況，種群越分散Si越大，由式（10）可知慣性權(quán)重的變異算子Gi越小，使得P0越小，反之P0越大。例如由圖23 可知，P0概率分布前200 次迭代中，概率在0.1～0.2 之間呈不規(guī)則分布，表明布谷鳥在解的子空間Ωj中位置信息比較分散且不斷尋優(yōu)。在第399 次迭代P0=0.363 8，400 次迭代P0=0.352 5，401 次迭代P0=0.385 8。概率P0由大到小，再由小到大，說明布谷鳥種群分布在解空間位置不斷變化。位置信息在尋優(yōu)過程中不斷在變化影響著概率P0的大小。在DECS 算法后期636 次迭代到1 000 次迭代，發(fā)現(xiàn)概率P0概率分布為一條規(guī)則且光滑的曲線。表明種群分布集中在某個解的子空間Ωj內(nèi)不斷尋優(yōu)。種群分布策略的引進有效提高了算法前期的種群多樣性，同時也加強了算法后期的局部搜索能力。

Fig.21 Probability curve of P distribution of CS algorithm圖21 CS 算法概率P 曲線分布圖

Fig.22 Probability curve of Pa distribution of ACS algorithm圖22 ACS 算法概率Pa 曲線分布圖

Fig.23 Probability curve of P0distribution of DECS algorithm圖23 DECS 算法概率P0曲線分布圖

3.5 三種萊維飛行模式比較分析

在布谷鳥搜索算法中，由Levy(λ)～μ=t-λ可知，布谷鳥連續(xù)的位置變化形成了一個帶有重尾分布的概率分布，使得布谷鳥飛行路徑表現(xiàn)出了Levy 飛行的本質(zhì)，即在尋優(yōu)路徑中頻繁的短步長偶爾會出現(xiàn)長步長，使得CS 算法擁有更大的全局搜索能力，但是仍然存在全局搜索能力不足的缺陷。

本文提出的自適應雙重萊維飛行機制主要分為兩個階段：搜索前中期和搜索中后期。由步長更新公式可知，該式描述萊維飛行是一個馬爾科夫鏈，即下代的位置僅取決于當前位置信息。下一次位置是由當前位置Levy 飛行步長及步長因子ω共同決定的。由圖1 步長因子ω變化曲線可知，DECS 算法前期擁有較小的步長因子，且Levy 飛行搜索偶爾出現(xiàn)的長步長，確保了算法前期每只布谷鳥在子空間Ω1,Ω2,…,Ωk中充分搜索。DECS 算法的中后期由子空間Ωk的搜索范圍，擴大到整個解空間Ω的搜索范圍，較大的步長因子確保了整個解空間Ω的充分搜索能力。隨著迭代次數(shù)的增加步長因子的減小，DECS 算法后期的局部搜索能力增強。

為了驗證自適應雙重搜索Levy 飛行在全局搜索能力等方面的優(yōu)勢，從表1 中選取了4 個函數(shù)進行測試，f1(x)、f5(x)為復雜的多峰函數(shù)，擁有無數(shù)局部極小值和局部極大值，常導致算法在求解時陷入局部最優(yōu)，可有效測試算法跳離局部極值的能力及全局收斂性能。f8(x)、f9(x)為單峰函數(shù)，由于它在全局最小值附近函數(shù)變化極為緩慢，因此被用來測試算法的收斂速度和尋優(yōu)能力。CS-Ⅱ算法（自適應雙重搜索Levy 飛行）是CS 算法僅采用引進新型步長因子策略；ASCSA-Ⅰ算法（自適應搜索Levy 飛行）是CS 算法僅采用自適應步長因子策略；CS 算法（標準的Levy 飛行）是標準的布谷鳥搜索算法。CS-Ⅱ算法、ASCSA-Ⅰ算法、CS 算法參數(shù)設置與表2 中DECS 算法參數(shù)設置相同。圖24～圖27 分別為f1(x)、f5(x)、f8(x)、f9(x) 在n=10 維測試情況下的函數(shù)收斂曲線圖。表22 為CS-Ⅱ算法、ASCSA-Ⅰ算法、CS 算法在n=10 維情況下，對f1(x)、f5(x)、f8(x)、f9(x)函數(shù)測試并記錄，平均值、最佳值、最差值及標準差測試結(jié)果的比較。

由表22 可知，CS-Ⅱ算法求解精度優(yōu)于CS 算法，相比CS 算法f1(x)、f5(x)、f8(x)、f9(x) 在求解精度上分別提高了11、5、13、18 個數(shù)量級。CS-Ⅱ算法比ASCSA-Ⅰ算法在f1(x)、f5(x)求解精度上分別提高了8、2 個數(shù)量級，雖然在f8(x)、f9(x)求解精度上相差不多，但是在收斂速度上CS-Ⅱ算法優(yōu)于ASCSA-Ⅰ算法。由圖26、圖27 可知CS-Ⅱ算法在100 次迭代收斂到全局最優(yōu)，而ASCSA-Ⅰ算法在200 次迭代收斂到全局最優(yōu)。由圖24、圖25 可知，CS 算法易陷入局部最優(yōu)，而CS-Ⅱ算法在求解復雜的多峰且擁有無數(shù)的全局極小值的函數(shù)時，表現(xiàn)出更好的全局尋優(yōu)性能，說明CS-Ⅱ算法比CS 算法更易跳出局部最優(yōu)。由圖24～圖27 可知，CS-Ⅱ算法收斂速度優(yōu)于ASCSA-Ⅰ算法、CS 算法。CS-Ⅱ算法在求解f1(x)、f5(x)多峰函數(shù)時，在300 次迭代內(nèi)可收斂到全局最優(yōu)，ASCSA-Ⅰ算法分別在500、650 次迭代收斂，CS 算法陷入局部最優(yōu)；CS-Ⅱ算法在求解f8(x)、f9(x)單峰函數(shù)時均在100 次迭代內(nèi)可收斂到全局最優(yōu)，ASCSA-Ⅰ算法均在200 次迭代收斂到全局最優(yōu)，CS 算法在求解f9(x)函數(shù)時400 次迭代收斂到全局最優(yōu)，在求解f8(x)函數(shù)時1 000 次迭代未收斂。

Fig.24 Convergence curves of three Levy modes Ackley function圖24 三種萊維模式Ackley 函數(shù)收斂曲線圖

Fig.25 Convergence curves of three Levy modes Alpine function圖25 三種萊維模式Alpine函數(shù)收斂曲線圖

Fig.26 Convergence curves of three Levy modes Sphere function圖26 三種萊維模式Sphere函數(shù)收斂曲線圖

Fig.27 Convergence curves of three Levy modes Schwefel 2.22 function圖27 三種萊維模式Schwefel 2.22 函數(shù)收斂曲線圖

Table 22 Performance test results of three Levy modes表22 三種萊維模式的性能測試結(jié)果

3.6 三種改進策略的有效性分析

為了分析3 種改進策略對算法的性能影響，選取表1 中16 個函數(shù)進行測試，表23 測試結(jié)果為f1(x)～f5(x)、f7(x)～f9(x)、f12(x)函數(shù)，維數(shù)n=50；f13(x)～f19(x)函數(shù)，維數(shù)n=2；記錄每次測試結(jié)果并計算平均值、最佳值、最差值、標準差；圖28、圖29 分別為5 種不同策略下，維數(shù)n=50 的f5(x)函數(shù)收斂圖和維數(shù)n=2的f15(x)函數(shù)收斂圖。將DECS 算法分別與CS-Ⅰ算法、CS-Ⅱ算法、CS-Ⅲ算法、CS 算法進行比較測試。這里CS 算法是基本的布谷鳥算法；CS-Ⅰ算法是CS算法僅采用在隨機偏好游走的更新公式引入非線性對數(shù)遞減的慣性權(quán)重策略；CS-Ⅱ算法是CS 算法僅采用引進新型步長因子策略；CS-Ⅲ算法是CS 算法僅采用在發(fā)現(xiàn)概率P中引進種群分布策略。CS-Ⅰ算法、CS-Ⅱ算法、CS-Ⅲ算法及CS 算法4 種算法參數(shù)設置與表2 中DECS 算法參數(shù)設置相同。

Fig.28 Convergence curve of Alpine function with different strategies圖28 不同策略Alpine函數(shù)收斂曲線圖

Fig.29 Convergence curve of Goldstein&Price function with different strategies圖29 不同策略Goldstein&Price函數(shù)收斂曲線圖

由表23 的比較結(jié)果可知，CS-Ⅰ算法在高維多峰函數(shù)、高維單峰函數(shù)上的尋優(yōu)性能優(yōu)于CS 算法、CS-Ⅱ算法、CS-Ⅲ算法。CS-Ⅰ算法求解f1(x)函數(shù)的精度相對于CS 算法提高了17 個數(shù)量級，f2(x)～f5(x)、f7(x)～f9(x)、f12(x)均可收斂到理論最優(yōu)解。CS-Ⅱ算法在低維多峰函數(shù)、低維單峰函數(shù)上尋優(yōu)性能優(yōu)于CS-Ⅰ算法、CS-Ⅲ算法、CS 算法。f13(x)～f19(x)均可收斂到理論最優(yōu)值。采用CS 算法在測試f13(x)、f16(x)～f17(x)函數(shù)時很容易陷入局部最優(yōu)解，而CS-Ⅱ算法均可收斂于理論最優(yōu)解。說明雙重Levy 飛行搜索CS-Ⅱ算法比標準Levy 飛行搜索CS 算法更容易跳出局部最優(yōu)解，有效克服了陷入局部最優(yōu)的缺陷。由圖28 可知，CS-Ⅰ算法在高維函數(shù)尋優(yōu)精度和收斂速度上性能優(yōu)于CS-Ⅱ算法、CS-Ⅲ算法、CS 算法。由圖29 可知，CS-Ⅱ算法在低維函數(shù)的收斂速度上優(yōu)于CS-Ⅰ算法、CS-Ⅲ算法、CS 算法。而CS-Ⅲ算法優(yōu)于CS 算法，CS-Ⅲ算法在350 次迭代收斂到全局最優(yōu)，CS 算法在600 次迭代收斂到全局最優(yōu)，表明在概率P上引進種群分布熵策略，提高了CS 算法的收斂速度。

Table 23 Test comparison of five algorithms表23 5 種算法的測試比較

表23 （續(xù)）

DECS 算法采用了CS-Ⅰ算法、CS-Ⅱ算法、CS-Ⅲ算法中的策略，表現(xiàn)出了良好的尋優(yōu)能力。f1(x)函數(shù)求解精度相對于CS 算法提高了17 個數(shù)量級，f2(x)～f5(x)、f7(x)～f9(x)、f12(x)～f19(x)函數(shù)均可收斂于理論最優(yōu)值。對于高維多峰函數(shù)、高維單峰函數(shù)、低維多峰函數(shù)、低維單峰函數(shù)DECS 都表現(xiàn)出了良好的普適性。組合改進策略可以更加有效地提高算法的尋優(yōu)性能。

3.7 DECS 算法跳出局部極值能力分析

基本的CS 算法的偏好游走中，下一代鳥窩位置更新是采用固定上一代位置為參考的更新方式，容易造成算法在迭代后期陷入局部最優(yōu)解。因此本文提出了在偏好游走環(huán)節(jié)引入對數(shù)遞減策略。DECS算法主要分為兩個尋優(yōu)階段：迭代前期、迭代后期。由圖1 可知，迭代前中期萊維飛行由于動態(tài)變化步長因子ω，已經(jīng)將搜索精度縮小一個或多個數(shù)量級，因此偏好游走在迭代前期以較大的慣性權(quán)重κ保留上一代的位置信息，可以有效跳出子空間Ωj局部極

為了更好地驗證DECS 算法的搜索效率及收斂性，本文設定了固定精度。從表1 中選取了9 個函數(shù)進行測試，對每個函數(shù)在固定精度下獨立運行30次。記錄每個函數(shù)在固定精度下的最小迭代次數(shù)、最大迭代次數(shù)、平均迭代次數(shù)、算法成功率、運行時間。測試結(jié)果如表24 所示。表24 中“最小迭代次數(shù)”為函數(shù)尋優(yōu)獨立運行30 次中達到預設精度值時的最小迭代次數(shù)；“最大迭代次數(shù)”為函數(shù)尋優(yōu)獨立運行30 次中達到預設精度值時的最大迭代次數(shù)；“平均迭代次數(shù)”為函數(shù)尋優(yōu)獨立運行30 次中達到固定精度值時所有運行次數(shù)的平均數(shù)，最大迭代次數(shù)設置為3 000 次，如果實驗過程中迭代次數(shù)超過3 000，就認為尋優(yōu)失敗，其中沒有達到預設精度的運行次數(shù)不算在內(nèi)?！啊北硎竞瘮?shù)重復尋優(yōu)過程中沒有一次達到預設精度，“運行時間”為30 次函數(shù)尋優(yōu)過程運行時間的平均數(shù)。算法成功率=達到精度的運行次數(shù)/總次數(shù)。

Table 24 Comparison of algorithm success rate and number of iterations表24 算法成功率和迭代次數(shù)比較

由表24 可知，本文提出的DECS 算法在9 個測試函數(shù)上進行的30 次獨立運行實驗，都達到了目標精度并且成功率均為100%。對于f3(x)、f4(x)、f5(x)、f7(x)復雜的多峰函數(shù)，在尋優(yōu)精度固定的情況下，DECS算法的平均迭代次數(shù)明顯小于ASCSA、CS、BA 和FPA 算法，且成功率都達到了100%，而對f3(x)函數(shù)FPA 算法的成功率只有83.3%，f5(x)函數(shù)CS 算法的成功率只有60%，充分說明了DECS 算法具有更好的搜索能力以及更高的收斂效率。f8(x)、f9(x)、f12(x)為單峰函數(shù)，測試函數(shù)的搜索效率和尋優(yōu)能力。DECS 算法在平均迭代次數(shù)50 次以內(nèi)，均達到了固定收斂精度，表現(xiàn)出了較優(yōu)的收斂效率。面對二維的f15(x)、f19(x)多峰且具有多個極值點的函數(shù)，DECS 算法在平均迭代次數(shù)上優(yōu)于ASCSA 算法，表明DECS算法有較強的跳出局部最優(yōu)能力。從表24 第8 列運行時間可以看出，DECS 算法在時間效率上均高于ASCSA、CS、BA 和FPA 算法。

4 結(jié)束語

針對布谷鳥收搜索算法存在易陷入局部最優(yōu)，后期收斂速度慢，求解精度不高等不足，分析基本布谷鳥的尋優(yōu)過程與特性，提出了動態(tài)調(diào)整概率的雙重布谷鳥搜索算法。該算法在發(fā)現(xiàn)概率P引入種群分布熵的概念，P不僅隨著迭代次數(shù)的增加而變化，同時還隨著布谷鳥分布的情況而變化，使得算法前期增加了種群的多樣性且增強了全局搜索能力。布谷鳥尋優(yōu)過程中引入了動態(tài)變化步長因子ω，使得算法前期在各自的子空間中進行Levy 飛行尋優(yōu)機制，中后期再由整個解空間到局部精細搜索。有效改善了基本布谷鳥算法易陷入局部最優(yōu)，收斂速度慢，求解精度低等缺點。通過19 個測試函數(shù)驗證，DECS 算法的尋優(yōu)能力、求解精度、收斂速度等方面均有較大幅度的提升。