動態調整概率的雙重布谷鳥搜索算法

陳 程，賀興時+，楊新社

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

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

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

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

1 基本的布谷鳥搜索算法

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

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

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

（3）可選擇的鳥窩數量N是固定的,宿主鳥發現外來卵的概率Pa∈[0,1]。

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

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

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

其中，υ和μ服從標準的正態分布，β=1.5，φ=

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

其中，α0為常數，一般取0.01，xbest為當前最優解。

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

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

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

2 動態調整概率的雙重布谷鳥搜索算法

2.1 動態權重下改變自適應概率P0

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 對數遞減慣性權重偏好游走

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

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

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

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

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

2.4 DECS 算法的流程

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

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

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

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

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

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

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

3 仿真實驗

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

3.1 測試環境及算法參數

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

3.2 算法求解精度比較分析

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

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

Table 1 Test functions表1 測試函數

Table 2 Algorithm parameter settings表2 算法參數設置

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 算法收斂曲線分析

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

Fig.2 Convergence curves of Ackley function圖2 Ackley 函數收斂曲線圖

Fig.3 Convergence curves of Rastrigin function圖3 Rastrigin 函數收斂曲線圖

Fig.4 Convergence curves of Griewank function圖4 Griewank 函數收斂曲線圖

Fig.5 Convergence curves of Zakharov function圖5 Zakharov 函數收斂曲線圖

Fig.6 Convergence curves of Alpine function圖6 Alpine函數收斂曲線圖

Fig.7 Convergence curves of Exponential function圖7 Exponential函數收斂曲線圖

Fig.8 Convergence curves of Schaffer function圖8 Schaffer函數收斂曲線圖

Fig.9 Convergence curves of Schwefel 2.22圖9 Schwefel 2.22 函數收斂曲線圖

Fig.10 Convergence curves of Sphere function圖10 Sphere函數收斂曲線圖

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

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

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

Fig.14 Convergence curves of Beale function圖14 Beale函數收斂曲線圖

Fig.15 Convergence curves of Booth function圖15 Booth 函數收斂曲線圖

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

Fig.17 Convergence curves of Bohachevsky function圖17 Bohachevsky 函數收斂曲線圖

Fig.18 Convergence curves of Easom function圖18 Easom 函數收斂曲線圖

Fig.19 Convergence curves of Branin function圖19 Branin 函數收斂曲線圖

Fig.20 Convergence curves of Shubert function圖20 Shubert函數收斂曲線圖

3.4 三種策略下發現概率P 的比較分析

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

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

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

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-λ可知，布谷鳥連續的位置變化形成了一個帶有重尾分布的概率分布，使得布谷鳥飛行路徑表現出了Levy 飛行的本質，即在尋優路徑中頻繁的短步長偶爾會出現長步長，使得CS 算法擁有更大的全局搜索能力，但是仍然存在全局搜索能力不足的缺陷。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表23 （續）

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

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

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

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

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

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

4 結束語

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