多階段動態擾動和動態慣性權重的布谷鳥算法

張珍珍，賀興時，于青林，楊新社

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

2.湯普森大學數學與統計系，哥倫比亞 甘露 V2C0C8

3.密德薩斯大學科學與技術學院，倫敦 NW4 4BT

隨著科學與技術的發展，優化問題在人們生活中發揮了越來越重要的作用，對于優化問題的解決方法要求也逐漸提高。傳統的計算方法來解決這些復雜優化問題時，會出現求解精度低，收斂速度慢且耗時長、成本高等方面的缺點。針對傳統算法解決復雜問題時出現的局限性，為了復雜的優化問題能夠得到解決，找到更為合理和滿意的近似解。眾多學者開始設計了元啟發式算法，并在過去的二三十年中得到迅速發展，成為當前最活躍的算法研究領域之一。常用的元啟發式算法包括螢火蟲算法[1]（firefly algorithm，FA）、飛蛾撲火算法[2]（moth-flame optimization algorithm，MFO）、粒子群優化算法[3]（particle swarm optimization，PSO）、花粉算法[4]（flower pollination algorithm，FPA）、樽海鞘算法[5]（salp swarm algorithm，SSA）等算法。這些算法都具有簡單易行、參數少、運行時間短等特點，因此解決了眾多非線性和多模態的現實尋優問題。

劍橋大學的Yang 和Deb[6]于2009 年通過模擬布谷鳥尋窩產卵的行為提出了一種新的搜索算法，并命名為布谷鳥搜索算法（cuckoo search，CS）。布谷鳥搜索算法因其通用性強，單高效、控制參數少、易于實現，而被廣泛研究與應用于圖像處理[7]、臨床醫學[8]、旅行商問題[9]、PID控制器調整[10]、工程優化[11]、信號處理[12]等諸多領域，并表現出良好的尋優性能。但布谷鳥算法同其他生物啟發式算法一樣都存在易限于局部最優，后期收斂速度偏慢，求解精度不高等問題，在處理一些多維復雜函數時，難以找到最優解，因此，需要改進布谷鳥優化算法來克服它的這些不足，使其能更好地應用于更多問題。針對以上問題，Gherboudj 等[13]提出了一種離散二進制布谷鳥搜索（binary cuckoo search，BCS）算法來處理二進制優化問題。Kanagaraj 等[14]將遺傳算子嵌入到CS 算法中以平衡局部搜索和全局優，提出了CS-GA 算法。王凡等[15]通過分析鳥窩位的群體狀態轉移過程加入了Markov 鏈，提高算法全局搜索能力。宋慶慶等[16]將混沌序列引入到布谷鳥算法中初始化鳥窩位置。陳程等[17]提出了動態權重改變自適應概率的雙重搜索布谷鳥算法（DECS）。針對布谷鳥算法在處理復雜函數時，求解精度不高，易陷入局部最優等缺陷，本文提出了基于多階段動態擾動和動態慣性權重的布谷鳥算法（MACS），通過將多階段動態擾動策略引入到布谷鳥算法的全局位置，對最優鳥巢位置進行根據方差可調的正太隨機分布擾動，增加了種群的多樣性和鳥窩的靈活性，提高全局搜索能力。并在局部位置處引入動態慣性權重，更大程度提高了鳥窩的開發與探索能力，使得算法有效克服易陷入局部最優的缺陷，提高局部尋優搜索能力。最后，引入了動態切換概率p代替固定概率，可以動態平衡全局搜索和局部搜索。實驗結果表明，MACS 算法提高了求解精度，加快收斂速度，具有更好的優化性能。

1 基本布谷鳥算法

在大自然中，布谷鳥具有特殊的尋窩產卵行為，不自己筑巢，而將自己的卵悄悄的產在其他宿主鳥的巢穴中，由其他鳥幫它來卵化下一代。但是當宿主鳥一旦發現有外來鳥蛋，宿主鳥就會拋棄這些外來的鳥蛋或者重新筑巢，為了模擬布谷鳥特殊的尋窩和繁衍后代的行為。Yang和Deb假設了以下3個理想規則[18]：

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

（2）在隨機選擇的鳥窩中，最好的鳥窩將被保留到下一代；

（3）可選擇的鳥窩數量N是固定的，宿主鳥發現外來布谷鳥蛋的概率為pa∈[0,1] 。

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

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

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

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

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

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

2 多階段動態擾動和動態慣性權重的布谷鳥優化算法

2.1 多階段動態擾動策略

在布谷鳥算法的全局搜索階段，所有鳥窩位置都朝著同一全局最優位置靠近，致使布谷鳥算法很容易陷入局部最優，導致算法在處理復雜多峰函數時，收斂精度低，收斂過早等缺點表現得尤為明顯。針對這個問題，本文提出了一種多階段動態擾動策略，對布谷鳥算法的最優鳥窩位置進行分階段的動態擾動，更新最優鳥窩位置。即對全局最優鳥窩位置根據方差可調的正態隨機分布進行擾動，從而得到新的全局最優鳥窩位置XNewbest，更新公式如（7）所示：

其中，σ表示相對于Xbest的不確定度，是關于迭代次數t的非增函數，其更新公式如下：

其中，σ表示對原最優鳥窩位置正態擾動的半徑參數且σ1<σ2，本文取σ1=0.9，σ2.=0.000 001，α1、α2是半徑變化的控制參數，且α1<α2，本文取α1=0.4，α2=0.7，t是當前迭代次數，T是最大迭代次數。其擾動半徑變化圖如圖1所示。

圖1 擾動半徑σ 變化圖Fig.1 Variation diagram of perturbation radius σ

由圖1可以看出，擾動半徑σ是一個分為三階段的動態變化數值。本文在算法的迭代前期以固定較大的半徑對布谷鳥算法的全局最優鳥窩位置進行擾動，得到新的變化較大的最優鳥窩位置，使全體鳥窩在朝著新的最優鳥窩位置靠近時，更具有廣泛性和多樣性，幫助算法在迭代前期更大范圍內的去尋找全局最優，避免算法朝著固定最優鳥窩位置靠近，而在迭代前期就陷入局部最優的情況。當在迭代中期，算法在逐步縮小范圍尋找全局最優時，本文也以線性遞減的方式逐步降低對最優鳥窩位置的擾動半徑，使全體鳥窩位置逐步穩定的向全局最優靠近。而在最后迭代后期，算法已經非常靠近尋求出全局最優解時，本文以固定非常微小的擾動半徑對當前最優鳥窩位置進行擾動，不再大范圍波動當前最優位置，使算法小范圍內精細搜索出全局最優解。本文基于上述根據迭代過程而變化的多階段擾動策略，充分靈活發揮了當前最優鳥窩位置的作用，有效避免算法易陷入局部最優的缺點，提高了算法的全局搜索能力和尋優性能。

2.2 動態慣性權重

在布谷鳥算法的偏好隨機游動環節中，如式（6）所示，采用的是固定上一代鳥窩位置的更新方式，容易造成算法在迭代后期陷入局部最優值。而慣性權重因子是布谷鳥算法中的重要影響參數，當慣性權重較大時，有利于擴大搜索范圍，增加全局搜索能力提高搜索速度。當慣性權重較小時，有利于幫助布谷鳥算法進行后期的精細搜索，提高搜索精度。所以動態慣性權重改進策略是一種能夠動態平衡全局搜索和局部搜索的改進機制，能夠提高算法的搜索速度和收斂精度。本文在上一代鳥窩位置處引入自適應動態慣性權重[19]對布谷鳥算法的偏好隨機游動環節進行改進。

改進后的布谷鳥偏好隨機游動環節式（6）如式（9）所示：

其中動態慣性權重?公式如（10）所示：

式中，t是當前迭代次數，tmax是最大迭代次數，?變化如圖2所示。

圖2 動態慣性權重? 變化圖Fig.2 Variation diagram of dynamic inertial weight ?

通過圖2 可以看出，?為（0，1）之間隨迭代次數非線性遞減的動態慣性權重，隨著迭代過程的進行，慣性權重?逐步減小。在標準布谷鳥偏好隨機游動環節中，新的鳥窩位置的更新是采用固定上一代鳥窩位置的方式，而本文通過在上一代鳥窩位置處引入如圖所示的動態慣性權重系數，靈活地將上一代鳥窩位置與迭代過程動態聯系起來。在迭代前期，給上一代鳥窩位置賦予相對大的系數，使上一代鳥窩具有更大的作用能力與范圍，幫助布谷鳥算法在前期擴大搜索空間，廣泛尋找全局最優解。隨著算法迭代過程的進行，慣性權重系數逐漸減小，直至到迭代后期，算法接近最優解時，對上一代鳥窩位置采用相對較小的慣性權重系數，有效的削弱了上一代鳥窩的保留信息，幫助布谷鳥算法有效跳出局部最優，使布谷鳥個體具有更好的局部尋優能力。本文通過動態慣性權重系數的引入，靈活處理上一代鳥窩的位置信息，提高了算法的局部尋優能力。

2.3 自適應切換概率

在基本布谷鳥算法中，用固定的切換概率p=0.25來控制全局搜索和偏好隨機游走，不利于動態平衡算法的全局探索和局部開發能力。自適應概率p是布谷鳥算法的重要參數，當p較小時，增加了全局的多樣性，提高全局搜索能力，當p較大時，增加局部搜索能力，提高了算法精度和效率。所以動態概率p是一種綜合提高算法性能的優化改進策略。本文引入了動態切換概率p來隨著迭代次數自適應地平衡全局和局部搜索能力，來更好地實現尋優能力，本文提出的動態概率公式如式（11）所示：

式中，t是當前迭代次數，tmax是最大迭代次數，p的變化如圖3所示。

圖3 自適應切換概率變化圖Fig.3 Adaptive switching probability graph

由圖3可以看出，本文提出的概率p是一個隨迭代過程進行而自適應增大的動態切換概率。在算法迭代前期，以較小的概率p來控制全局搜索和局部搜索的切換，在這個階段由于概率p較小，所以幫助算法在迭代前期多進行全局搜索，大范圍尋找全局最優解，增加了算法的全局多樣性，提高了算法的全局搜索能力。隨著迭代過程的進行，概率p不斷增大，直至在迭代后期，概率p相對較大，幫助算法在迭代后期已經靠近全局最優解時，多進行局部精細搜索，提高算法的運算精度和搜索效率。通過將布谷鳥算法的固定概率替換成自適應切換概率，將概率p與迭代過程動態聯系在一起，幫助算法靈活平衡了全局搜索能力和局部搜索能力，提高算法性能。

2.4 MACS算法分析

2.4.1 MACS算法的理論客觀分析

多階段動態擾動和動態慣性權重的布谷鳥算法（MACS）著眼于對布谷鳥算法的整體優化，充分協調利用多階段動態擾動策略、動態慣性權重?和自適應切換概率p三者之間的關系。MACS 算法前期全局搜索階段利用三階段的動態可調方差σ靈活控制最優鳥窩位置的擾動半徑范圍，擾動半徑變化范圍從0.000 001到0.9，在保證算法穩定性的前提下，最大程度上增加了前期鳥窩的多樣性，保證算法充分勘探搜索種群。與此同時，對偏好隨機游動環節結合變化范圍在[0，1]的非線性遞減動態慣性權重?進行補充，幫助進行算法后期精細搜索，提高算法尋找最優解的效率，并通過引入自適應切換概率p，確保p在整個算法迭代階段保持一個在[0.15，0.25]間動態變化的狀態，來動態平衡MACS算法的全局搜索和局部搜索階段，使算法更具有靈活性。通過3個策略間的相互作用、相互聯系，MACS算法對布谷鳥算法進行了整體優化，充分開發算法搜索性能。

2.4.2 MACS算法流程

MACS具體執行步驟如下：

步驟6 判斷算法的終止條件，若滿足，就輸出當前最優值fmin；若不滿足，就重復步驟2～6。

詳細算法流程圖，如圖4所示。

圖4 MACS算法流程圖Fig.4 MACS algorithm flow chart

2.4.3 MACS算法的計算復雜度分析

在標準布谷鳥算法CS 中，假設種群大小為N，解空間維數為n，最大迭代次數為tmax，那么原布谷鳥算法CS的計算復雜度可以用Ο(N×n×tmax)表示。

該方程的推導基于算法初始化大小為N的種群，維數因子n決定了算法的復雜性，對于每個布谷鳥種群中的個體，都需要執行Ο(n)次操作，導致復雜度為Ο(N×n)。這是針對單次迭代的復雜性，但是一般來說，布谷鳥算法運行需要許多次迭代，所以算法總計算復雜度取決于算法的最大迭代次數，這個過程給出了原布谷鳥算法的總復雜度為Ο(N×n×tmax)。

與原布谷鳥算法CS 相比，MACS 算法在原算法的基礎上添加了多階段動態擾動策略更新最優鳥窩位置，動態慣性權重和自適應切換概率的改進。原則上，所提出的新改進都沒有額外的計算負擔，從第3章的比較實驗結果也可以明顯看出，對于變化的種群大小，MACS算法的結果隨著CS 算法的變化而變化，維數大小的影響也保持一致，因此MACS算法的計算復雜度相較于原CS算法并沒有提升，仍為Ο(N×n×tmax)。

3 仿真實驗

3.1 測試函數

為了證明MACS 算法的尋優性能，本文選取了11個不同難度的函數，其中涵蓋簡單低峰函數和復雜多峰函數，高維函數和低維函數，函數設置見表1。分別對MACS 算法的收斂速度，收斂精度進行測試。同時與ASCSA算法、CS算法、FPA算法、BA算法，進行對比分析。

表1 測試函數Table 1 Test functions

3.2 測試環境及算法參數

實驗環境如下：CPU為i5-4288U 2.60 GHz，運行內存4 GB，操作系統Windows10，編程環境Matlabr2020a。CS算法、FPA算法、BA算法、ASCSA算法設置參數如表2所示。

表2 算法參數設置Table 2 Algorithm parameters setting

3.3 算法求解精度比較分析

表3～11 分別給出了5 種算法對測試函數f1～f9，在維數n=10、n=50、n=100 下的方差、最優值、平均值、最差值結果。表12 和表13 分別給出了5 種算法對低維測試函數f10、f11在維數n=2 下的方差、最優值、平均值、最差值結果。

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

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

表5 f3( x )Zakharov函數仿真結果Table 5 Simulation resutls of f3( x )Zakharow function

表中，f1(x)函數是典型的非線性多模態函數，局部最小值個數與維數成正比且起伏不定，從表3中可以看出，MACS表現出良好的性能，取到全局最優值，而其他4 種算法后期都陷入了局部最優。f2～f5為復雜多峰函數，MACS 算法在不同維度下均表現出良好的尋優能力，而其他算法都無法獲得全局最優解。

f6～f8為單峰函數，在定義域內只有一個極值點，MACS 也仍能取到全局最優解，表現出良好的尋優性能。從表格中可以看出，對測試函數f1～f8中的不管是單峰函數還是復雜多峰函數，MACS算法均取到了全局最優值。并且隨著維度的增加，仍能保持取到最優結果，表現出良好的尋優能力和穩定性，而其他4 個算法在迭代后期都陷入了局部最優，并隨著維度的提高，求解精度逐漸下降。對測試函數f9，MACS 算法雖然也陷入了局部最優8.881 8E-16，但相較于其他4個算法仍不同程度上的提高了收斂精度，并隨著維度的提高，當其他4個算法求解精度都在明顯下降時，MACS仍能表現出良好的穩定性。

對于低維函數f10～f11，由表12 和表13 可以看出，MACS 算法仍能收斂到全局最優，證明了MACS 算法在低維測試函數條件下也仍具有良好性能，具有普適性。

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

表12 f 10( x )Bohachevsky函數仿真結果Table 12 Simulation results of f10( x )Bohachevsky function

表13 f11( x )Mytyas函數仿真結果Table 13 Simulation results of f11( x )Mytyas function

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

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

表9 f7( x )Sum square函數仿真結果Table 9 Simulation resutls of f7( x )Sum square function

表10 f8( x )Schwefel’s 2.2函數仿真結果Table 10 Simulation resutls of f8( x )Schwefel’s 2.2 function

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

3.4 算法收斂曲線分析

圖5～15 分別是11 種函數的收斂曲線圖，直觀地反映出了5 種算法的收斂速度和收斂精度。f1～f5為多峰函數，在定義域內存在多個極值點，可以考察算法的尋優能力，是否能跳出局部最優。

由圖5、圖6、圖9 可以看出，其他4 個算法都在迭代后期都陷入了局部最優，而MACS 成功跳出局部最優，取得全局最優值。由圖7 和圖8 可以看出，CS 算法和BA 算法都陷入了局部最優，FPA 算法和ASCSA 算法在300 次后取得最優值，而MACS 算法在50 次迭代后就達到了全局收斂，取得最優值。f6～f8為單峰函數，在定義域內只有一個極值點，可以測試算法的收斂速度。

圖5 Rastrigin函數收斂曲線圖Fig.5 Convergence curve of Rastrigin function

圖6 Schaffer函數收斂曲線圖Fig.6 Convergence curve of Schaffer function

圖7 Zakharov函數收斂曲線圖Fig.7 Convergence curve of Zakharov function

圖8 Griewank函數收斂曲線圖Fig.8 Convergence curve of Griewank function

圖9 Alpine函數收斂曲線圖Fig.9 Convergence curve of Alpine function

由圖10～12 可以看出，MACS 算法均在50 次迭代就取得全局最優解，相較于其他4 個算法明顯有更高的收斂速度。f10～f11為低維函數，由圖14 和圖15 可以看出，MACS 算法也都在50 次迭代左右就達到全局最優。

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

圖11 Sum square函數收斂曲線圖Fig.11 Convergence curve of Sum square function

圖12 Schwefel’s 2.2函數收斂曲線圖Fig.12 Convergence curve of Schwefel’s 2.2 function

圖13 Ackley函數收斂曲線圖Fig.13 Convergence curve of Ackley function

圖14 Bohachevsky函數收斂曲線圖Fig.14 Convergence curve of Bohachevsky function

圖15 Mytyas函數收斂曲線圖Fig.15 Convergence curve of Mytyas function

綜上所述，經過對這5種算法的收斂曲線進行比較分析，可以看出，無論是單峰函數還是復雜多峰函數，無論是高維函數還是低維函數，無論是尋優能力還是尋優精度上，MACS 算法的尋優表現都優于其他四個算法，表現出良好的性能。

4 結束語

針對布谷鳥仿生智能優化算法存在著的易陷入局部最優、求解精度低以及收斂速度慢等問題，本文提出了基于多階段動態擾動策略和動態慣性權重的布谷鳥搜索算法（MACS）。在布谷鳥全局搜索階段，引入多階段動態擾動策略對布谷鳥算法的全局位置的最優鳥巢位置根據方差可調的正態隨機分布進行擾動；引入動態方差概念，根據迭代次數，靈活調整擾動半徑，增加種群的多樣性和鳥窩位置的靈活性，提高算法的全局搜索能力。在布谷鳥局部搜索階段，在上一代鳥窩位置處引入動態慣性權重?，使得算法有效克服易陷入局部最優的缺陷，提高算法局部尋優搜索能力。最后，引入了動態切換概率p代替原有的固定概率，可以動態平衡全局搜索和局部搜索。通過與4 種算法相比和11 個測試函數的仿真結果表明：改進布谷鳥算法（MACS）的尋優性能明顯提高，收斂速度更快，求解精度更高，具有更強的全局搜索能力和跳出局部最優能力。