田 媛，梁永全

（山東科技大學 計算機科學與工程學院，山東 青島266590）

20世紀后期出現(xiàn)了越來越多受自然啟發(fā)的現(xiàn)代元啟發(fā)式算法，通過模擬自然現(xiàn)象和動物行為來解決函數(shù)優(yōu)化問題，如蟻群算法（ant colony optimization，ACO）［1］、粒子群算法（particle swarm optimization，PSO）［2］等，這類啟發(fā)式智能算法是計算智能領(lǐng)域的研究熱點方向之一，并在求解工程優(yōu)化等實際問題中獲得廣泛應用。

隨著計算智能技術(shù)的快速發(fā)展，各種新穎的仿生優(yōu)化算法相繼被提出，其中布谷鳥搜索（cuckoo search，CS）算法是劍橋大學的Yang等［3］于2009年在模擬布谷鳥尋巢產(chǎn)卵的行為中提出的一種全局搜索算法，用來解決函數(shù)目標優(yōu)化問題，具有選用參數(shù)少、容易實現(xiàn)、搜索路徑優(yōu)和尋優(yōu)能力強等特點［4-6］。已經(jīng)通過建立Markov鏈模型在理論上證明了布谷鳥搜索算法可收斂于全局最優(yōu)［7］，在收斂速度和穩(wěn)定性方面都超過了遺傳算法和粒子群優(yōu)化算法［3］。布谷鳥搜索算法需要的控制參數(shù)少，并且可以在隨機化和集約化上保持良好的平衡。但CS算法作為一種新興的仿生算法，其收斂速度和收斂結(jié)果精確度仍需進一步改善，針對函數(shù)優(yōu)化問題，大部分都是基于發(fā)現(xiàn)概率、自適應步長的改進和混合CS算法改進的。

基于發(fā)現(xiàn)概率的改進中，文獻［8］認為發(fā)現(xiàn)概率P 如果固定不變，將會使得不管是較好解還是較壞解都會以同樣的概率被替換掉，因此提出一種動態(tài)的方法，根據(jù)整體解的情況確定來調(diào)節(jié)發(fā)現(xiàn)概率P 從而提高算法的求精能力和收斂速度。文獻［9］通過改變發(fā)現(xiàn)概率，提出一種基于自適應機制的改進機制來控制縮放因子和發(fā)現(xiàn)概率，提高布谷鳥搜索算法求解函數(shù)優(yōu)化問題的求精能力和收斂速度。文獻［10］使用模糊控制系統(tǒng)來動態(tài)的調(diào)節(jié)布谷鳥搜索算法的發(fā)現(xiàn)概率P，提高了CS算法的收斂速度與計算精度。

在基于自適應步長的改進中，文獻［11］通過對標準布谷鳥搜索算法中參數(shù)偏度動態(tài)自適應取值來實現(xiàn)算法對步長的動態(tài)自適應，同時引入動態(tài)平衡因子以調(diào)節(jié)全局適應度和當前迭代次數(shù)所占的比重，實現(xiàn)了布谷鳥搜索算法收斂速度和搜索精度的平衡。文獻［12］利用一種基于種群排序的改進算法來指導隨機游動時的步長，提高步長的自適應性，在收斂速度和收斂精確度上都優(yōu)于標準的CS算法。

在混合CS算法改進中，文獻［13］采用簡單的2-opt算子作為局部優(yōu)化算子加快算法收斂速度，引入模擬退火機制防止算法陷入局部最優(yōu)，提高算法的通用性。文獻［14］優(yōu)化局部搜索，在算法中偏好隨機游動和萊維隨機游動之間融合PSO組件，利用PSO算法優(yōu)化種群，然后利用CS算法在最優(yōu)個體中繼續(xù)尋優(yōu)，提高了算法的性能。文獻［15］結(jié)合動態(tài)慣性改進策略改進鳥窩位置的更新方式，依據(jù)動態(tài)慣性權(quán)重值保留上代鳥窩的最優(yōu)位置并進行下一代位置更新，有效平衡了種群探索能力和開發(fā)能力。文獻［16］在布谷鳥算法的迭代過程中對鳥窩位置加入高斯擾動，增強了鳥窩位置變化的活力，提高了算法的收斂速度。

目前，布谷鳥搜索算法以及其改進算法已經(jīng)廣泛應用于大量實際應用問題中。文獻［4］選用布谷鳥搜索算法解決調(diào)度置換流水車間問題，取得了良好的實驗結(jié)果，證實其可以作為解決流水線生產(chǎn)調(diào)度問題的一種有效方法。文獻［5］融入量子計算和混沌局部搜索策略，以IEEE 118節(jié)點系統(tǒng)的最優(yōu)潮流計算問題證明改進后的布谷鳥搜索算法的有效性。文獻［6］將改進后的布谷鳥搜索算法應用于橋式起重機主梁優(yōu)化設計中，算法符合主梁約束條件，改進算法具有較高的可行性并取得了顯著的優(yōu)化效果。

原始布谷鳥搜索算法是基于無約束的全局優(yōu)化方法，每一代都參考當前最優(yōu)鳥窩，使其具有高效的尋優(yōu)能力，但布谷鳥種群進化方向由Lévy flight隨機游走產(chǎn)生的隨機步長決定，過大的隨機性會使尋優(yōu)結(jié)果無法準確落在最優(yōu)解的位置，而是圍著最優(yōu)解進行小范圍波動，導致算法在進化過程中缺乏可控制性，存在后期收斂慢和搜索精度不穩(wěn)定的問題。目前提出的改進算法中，無論是動態(tài)改變發(fā)現(xiàn)概率還是結(jié)合其他框架，都增加了算法復雜度和運行內(nèi)存，破壞了原始布谷鳥搜索算法控制參數(shù)少、運算簡便等優(yōu)點。針對這個問題，本研究在隨機游走過程中引入小批量梯度下降（mini-batch gradient descent，MBGD），與CS算法結(jié)合得到基于隨機梯度下降的布谷鳥搜索算法（cuckoo search algorithm based on mini-batch gradient descent，MBGDCS）。

1 布谷鳥算法

在自然界中，布谷鳥采用寄生育雛的特殊繁殖后代策略，將自己的卵生在其他（義親）鳥的鳥巢里，由義親鳥來代替自己孵化與養(yǎng)育下一代，并且為了保證孵化率，將義親鳥的蛋扔出鳥巢。

布谷鳥搜索算法在尋優(yōu)的過程中采用Lévy flight模式，Lévy flight是一種隨機游走，每一步方向完全隨機而各向同性，步長較小的短距離行走與偶爾較大步長的長距離行走相互交替，且步長服從重尾分布（heavy-tailed）。Shlesinger［17］將該飛行方式植入到群智能搜索算法中，長距離行走用于探索發(fā)現(xiàn)，擴大搜索范圍，跳出局部最優(yōu)的情況，距離越大，越容易搜索全局最優(yōu)，但會降低搜索精度，有時會出現(xiàn)震蕩現(xiàn)象；短距離行走用于在小范圍內(nèi)收斂于全局最優(yōu)解，距離越小，求解精度越高，但會降低搜索速度。Lévy flight每步游走都由兩個因素控制：一是游走方向，一般選取一個服從均勻分布的數(shù)；二是步長，步長服從Lévy分布。Reynolds等［18］證明了當目標位置呈現(xiàn)隨機特征并且無規(guī)律地稀疏排布時，對于M 個相互獨立的尋優(yōu)者來說，Lévy flight是最有效、最理想的搜索策略。Lévy flight可以在不確定區(qū)域內(nèi)最大限度地進行有效的搜索，許多動物的覓食模式都是Lévy flight，很多人類行為也符合Lévy flight。圖1為一個二維1 000步Lévy flight實例圖，在原點［0，0］開始隨機游走，游走過程中可以看出較小的跳躍組成的聚集被較大的跳躍分隔開的現(xiàn)象。

圖1 二維1 000步Lévy flight實例圖Fig.1 2D Lévy flights in 1 000 steps

布谷鳥尋找適合自己產(chǎn)卵的鳥窩位置是隨機的或類似隨機的方式，通過模擬布谷鳥寄生育雛行為及鳥類Lévy flights行為，設定以下三個理想規(guī)則［3，17］：

規(guī)則1 每只布谷鳥一次只產(chǎn)一枚蛋，并隨機選擇一個鳥窩存放；

規(guī)則2 在上一代選取的鳥窩里，鳥窩里最好的鳥蛋會保留到下一代；

規(guī)則3 可利用的鳥窩數(shù)量n 是固定的，宿主鳥發(fā)現(xiàn)一個外來鳥蛋的概率pa∈［0，1］，被發(fā)現(xiàn)的情況下，宿主鳥將扔掉這些外來鳥的卵或直接放棄該窩，去隨機建立一個新窩。

在這三個理想規(guī)則的基礎上，布谷鳥尋窩的路徑和位置更新公式如下：

其中，α0是常數(shù)（α0=0.01），xbest表示當前最優(yōu)解；Levy（β）是Lévy隨機搜索路徑，服從Lévy概率分布：

通過Lévy flight生成的步長s是不重要的，CS算法的提出者Yang等［19-20］提出了一個簡單方案：

其中，u，v 服從標準正態(tài)分布，即

這里

綜合式（1）～（6），在Lévy flight隨機游動組件中，生成新的解x（t）i的公式可以歸納為：

經(jīng)過位置更新后，用隨機數(shù)r∈ ［0，1 ］與發(fā)現(xiàn)概率pa∈［0，1 ］進行比較，若r＞pa，則對進行隨機改變，舍棄小部分不好的鳥窩，根據(jù)隨機游走生成與舍棄鳥窩相同數(shù)目的鳥窩，與未舍棄的鳥窩混合得到一組新鳥窩，從而避免陷入局部最優(yōu)，反之不變。最后保留測試值較好的一組鳥窩位置仍記為

綜上所述，布谷鳥搜索算法中的隨機游走效果明顯，大步長的游走有效避免了算法陷入局部最優(yōu)，而小步長的移動可以有效地尋找最優(yōu)解，使算法在尋找最優(yōu)解時十分有效且高效；同時，算法中需要調(diào)整的參數(shù)數(shù)量少，使得CS算法更廣泛地適用于函數(shù)優(yōu)化問題中。算法迭代過程中的每一組鳥窩都可以看作一組解決方案，因此CS算法也可以擴展應用在集合種群算法中。

2 基于小批量梯度下降的布谷鳥搜索算法

梯度下降算法是目前機器學習領(lǐng)域最常用的優(yōu)化算法，被廣泛應用于各種優(yōu)化問題中。梯度下降算法大致可以分為三種：批量梯度下降（batch gradient descent，BGD），每次迭代利用整個訓練集進行優(yōu)化；小批量梯度下降（MBGD），每次迭代利用部分訓練集進行優(yōu)化；隨機梯度下降（stochastic gradient descent，SGD），每次迭代僅用一個隨機選擇的樣例進行優(yōu)化求解。小批量梯度下降結(jié)合了批量梯度下降和隨機梯度下降的優(yōu)點，比批量梯度下降更簡便，比隨機梯度下降的準確性高，因此，在原始布谷鳥搜索算法中加入小批量梯度下降法，只需要每一代的小部分鳥窩信息即可以得出梯度方向，不會破壞原始布谷鳥搜索算法每一代進化過程中的獨立性，不需要引進其他參數(shù)，利用小批量梯度下降法一定程度上限制原始算法進化過程中過大的隨機性，使算法在迭代過程中可以更準確地尋找最優(yōu)解，提高算法搜索速度和搜索精度。

在布谷鳥搜索算法迭代過程中，在每次迭代得到的一組解中選取適應值最優(yōu)的部分構(gòu)成一個小批量梯度下降的批，從而確定一個梯度方向，從當前解出發(fā)沿該方向確定一個梯度下降的點，再從這個點出發(fā)利用Lévy flight找到一個新的解與之前的解進行比較。若新的解優(yōu)于舊解，則用新的解代替舊的解；若不優(yōu)于舊解，則返回之前小批量梯度下降得到的點，繼續(xù)小批量梯度下降得到新的點，重復此過程直到迭代結(jié)束?；谛∨刻荻认陆档牟脊萨B搜索算法（MBGDCS）結(jié)合布谷鳥算法隨機飛行不容易陷入局部最優(yōu)和小批量梯度下降法尋找最優(yōu)解的優(yōu)勢，提高算法的自適應性以及算法的求解精度和求解效率。

根據(jù)分析，MBGDCS算法的實施過程與步驟如下：

步驟1（初始化） 隨機生成n 個鳥窩，發(fā)現(xiàn)概率pa，搜索空間維數(shù)為nd，解的上下界分別為Ub與Lb，精度Tol，最大迭代次數(shù)iteration；生成初始鳥窩位置，i∈{1， 2，…，n}和當前的最優(yōu)解fmin。

步驟2（循環(huán)過程） 保留上代最優(yōu)的batch_size個鳥窩的位置，通過小批量梯度下降得到下降方向向量，利用Lévy flight在方向?qū)ζ渌B窩進行更新，得到一組解；對這組鳥窩位置進行測試，將這組解與上一代的解進行比較，用新解中較好的解替換上一代中較差的解，從而得到一組較優(yōu)的鳥窩位置，記為，i∈{1， 2，…，n}。

步驟3 用服從均勻分布的隨機數(shù)r ∈ ［0，1 ］作為鳥窩主人發(fā)現(xiàn)外來鳥蛋的可能性并與pa比較，若r＞pa，保留被發(fā)現(xiàn)概率較小的鳥窩位置，同時隨機改變發(fā)現(xiàn)概率較大的鳥窩位置，得到一組新的鳥窩位置，將這組鳥窩位置進行測試，與替換前的每個鳥窩位置的測試值進行對比，用測試值較好的鳥窩位置替換測試值較差的鳥窩位置，得到一組新的較優(yōu)鳥窩位置。

改進后的基于小批量梯度下降的布谷鳥搜索算法只需要初始化鳥窩數(shù)和發(fā)現(xiàn)概率兩個關(guān)鍵參數(shù)，設置好目標函數(shù)的相關(guān)信息，不需要額外的輸入信息。算法輸出包括算法迭代得到的最優(yōu)目標函數(shù)值、最優(yōu)鳥窩位置、得到最優(yōu)鳥窩的迭代次數(shù)、每次迭代的結(jié)果和迭代過程圖。

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

仿真實驗的運行環(huán)境為Intel（R）Core（TM）i5-4200U CPU，主頻1.60 GHz，內(nèi)存4 GB，Windows 10 64位操作系統(tǒng)，實驗仿真軟件采用Matlab R2013b。

為了觀察改進算法求解函數(shù)優(yōu)化問題的收斂速度和解的質(zhì)量，驗證所提出方法的有效性，實驗選擇3類測試函數(shù)，包括5組單峰基準測試函數(shù)、3組多峰基準測試函數(shù)和3組固定維度多峰基準測試函數(shù)［21-22］，見表1。實驗中用CS算法和改進后的MBGDCS算法對每個測試函數(shù)分別運行20次，進行200次迭代，取平均值表示搜索的結(jié)果精準性，實驗中參數(shù)默認設置為：鳥窩規(guī)模n 為25，發(fā)現(xiàn)概率pa為0.25，梯度下降的批量batch_size為5。實驗結(jié)果如表2～3和圖2～12所示。

表1 標準測試函數(shù)表Tab.1 Standard test functions

3.1 收斂速度和求精能力分析

對單峰基準測試函數(shù)而言，由表2可以看出，MBGDCS算法比CS算法在提高收斂速度上效果顯著，測試函數(shù)f1的MBGDCS算法平均迭代次數(shù)比CS算法平均減少16.25次，提高了77.57%；測試函數(shù)f2的MBGDCS算法平均迭代次數(shù)比CS算法平均減少43.3次，提高了95.58%；測試函數(shù)f3的MBGDCS算法平均迭代次數(shù)比CS算法平均減少15.45次，提高了79.23%；測試函數(shù)f4的MBGDCS算法平均迭代次數(shù)比CS算法平均減少59.5次，提高了96.75%；測試函數(shù)f5的MBGDCS算法平均迭代次數(shù)比CS算法平均減少95.5次，提高了63.83%。從表3可以看出，MBGDCS算法迭代得到的最優(yōu)解的精確度有了很大提高，測試函數(shù)f1到f4都收斂到了理論最小值，而CS算法都存在一定的誤差；測試函數(shù)f5在MBGDCS算法的迭代中雖然沒有收斂到理論最小值，但是收斂結(jié)果比CS算法提高了0.000 281 4，與理論最小值相差0.000 182 4。

對多峰基準測試函數(shù)而言，從表2和表3可以看出，無論是收斂速度還是收斂結(jié)果，MBGDCS算法都比CS算法有了顯著提高，尤其是收斂速度上，多峰基準測試函數(shù)f6、f7、f8都以極快的速度收斂，僅需要1次迭代或者2次迭代即可收斂，相比原算法收斂速度分別提高了98.38%、98.97%和97.43%，同時在收斂結(jié)果上也穩(wěn)定收斂到理論最優(yōu)值，尤其對測試函數(shù)f7，收斂結(jié)果與理論最優(yōu)值的誤差減小了12.802 37，效果十分明顯。

表2 平均收斂次數(shù)表Tab.2 Average number of iterations to convergence

表3 平均收斂結(jié)果表Tab.3 Average convergence result

對固定維度基準測試函數(shù)而言，由表2和表3可知，CS算法和MBGDCS算法都收斂到了理論最優(yōu)值，但是MBGDCS算法在收斂速度上比CS算法有一定的提高，測試函數(shù)f9迭代到58.25次收斂，收斂速度提高了8.48%；測試函數(shù)f10迭代87.4次到達收斂，收斂速度提高了25.52%；測試函數(shù)f11迭代32.55次到達收斂，收斂速度提高了33.97%。

圖2到圖12是測試函數(shù)迭代過程中的函數(shù)值進化曲線，可以看出，改進后的MBGDCS算法比原始CS算法收斂速度更快，尋優(yōu)精確度更高，效果提升明顯。

圖2 測試函數(shù)f1 迭代過程圖Fig.2 Iterative process of f1

圖3 測試函數(shù)f2 迭代過程圖Fig.3 Iterative process of f2

圖4 測試函數(shù)f3 迭代過程圖Fig.4 Iterative process of f3

圖5 測試函數(shù)f4 迭代過程圖Fig.5 Iterative process of f4

圖6 測試函數(shù)f5 迭代過程圖Fig.6 Iterative process of f5

圖7 測試函數(shù)f6 迭代過程圖Fig.7 Iterative process of f6

圖8 測試函數(shù)f7 迭代過程圖Fig.8 Iterative process of f7

圖9 測試函數(shù)f8 迭代過程圖Fig.9 Iterative process of f8

圖10 測試函數(shù)f9 迭代過程圖Fig.10 Iterative process of f9

圖11 測試函數(shù)f10迭代過程圖Fig.11 Iterative process of f10

圖12 測試函數(shù)f11迭代過程圖Fig.12 Iterative process of f11

綜上所述，改進后的MBGDCS算法與原始CS算法相比，在收斂速度和收斂精度方面都有明顯提高。

3.2 同類算法性能比較

粒子群算法［2］與灰狼算法（grey wolf optimizer，GWO）［23］都是目前常見的啟發(fā)式智能優(yōu)化算法，處理函數(shù)目標優(yōu)化問題各有優(yōu)勢，將改進布谷鳥搜索算法與粒子群算法、灰狼算法進行性能對比，每組函數(shù)運行10次，取平均值進行對比，對所有測試函數(shù)測試結(jié)果如表4所示。

表4 算法對比結(jié)果Tab.4 Comparisons of algorithms

由表4可知，對單峰基準測試函數(shù)和多峰基準測試函數(shù)，MBGDCS算法的尋優(yōu)結(jié)果均比粒子群算法和灰狼算法優(yōu)秀，除測試函數(shù)f5外都準確找到理論最優(yōu)解，而粒子群算法和灰狼算法都有一定誤差，測試函數(shù)f5的尋優(yōu)結(jié)果也優(yōu)于其他兩種算法；對固定維度基準測試函數(shù)，測試函數(shù)f9僅在MBGDCS算法的尋優(yōu)過程中找到了理論最優(yōu)，測試函數(shù)f10和f11三種算法都尋找到了理論最優(yōu)。

綜上，MBGDCS算法較粒子群算法和灰狼算法有更高的尋優(yōu)準確度，在實際應用的優(yōu)化設計中較易取得更好的結(jié)果。

3.3 參數(shù)敏感性分析

參數(shù)敏感性分析是確定模型關(guān)鍵參數(shù)以及發(fā)現(xiàn)目標變量對某參數(shù)變化的響應敏感程度的重要方法。布谷鳥算法具有初始化參數(shù)少的優(yōu)點，改進后的MBGDCS算法與原始CS算法相同，只需要初始化n 和pa，使用單參數(shù)分析方法對MBGDCS算法進行參數(shù)敏感性分析，分別單獨改變各所選參數(shù)的取值，然后對改變參數(shù)后的MBGDCS算法進行10次運算，每次運算迭代200次，取10次運算的平均值表示結(jié)果的準確性，10次結(jié)果的標準差表示結(jié)果的穩(wěn)定性。

首先對初始化鳥窩數(shù)n 進行敏感性分析。MBGDCS算法默認n 取25，固定其他參數(shù)不變，將初始化鳥窩數(shù)n 的數(shù)值分別取10、15、20、30、35、40，進行10次運算的平均收斂次數(shù)、平均收斂結(jié)果和對應標準差如表5、表6所示。從表5可知，n 取10～40時，測試函數(shù)f1、f3、f5、f9、f10和f11的平均收斂次數(shù)有很小的遞減趨勢，整體保持穩(wěn)定，其他測試函數(shù)平均收斂次數(shù)穩(wěn)定沒有變化，說明MBGDCS算法對初始化鳥窩數(shù)n的變化不敏感。從表6可知，n 取10～40時，僅測試函數(shù)f5存在極小的誤差，其他均收斂到理論最優(yōu)，說明MBGDCS算法的收斂結(jié)果對初始化鳥窩數(shù)n 的變化不敏感。綜上所述，說明MBGDCS算法的收斂結(jié)果對初始化鳥窩數(shù)n 的變化不敏感。

表5 參數(shù)n 敏感性測試平均收斂次數(shù)表Tab.5 The average convergence times of test functions on n

表6 參數(shù)n 敏感性測試平均收斂結(jié)果表Tab.6 The average convergence results of test functions on n

然后對初始化發(fā)現(xiàn)概率pa進行敏感性分析，MBGDCS算法默認pa取0.25，固定其他參數(shù)不變，將初始化發(fā)現(xiàn)概率pa的數(shù)值分別取0.10、0.15、0.20、0.30、0.35、0.40，進行10次運算的平均收斂次數(shù)、平均收斂結(jié)果和對應標準差如表7、表8所示。從表7可知，MBGDCS算法的收斂過程對初始化發(fā)現(xiàn)概率pa的變化不敏感。從表8可知，MBGDCS算法的收斂結(jié)果對初始化發(fā)現(xiàn)概率pa的變化不敏感。綜上，說明MBGDCS算法對初始化發(fā)現(xiàn)概率pa的變化不敏感。

因此，通過單參數(shù)分析法對MBGDCS算法進行參數(shù)敏感性測試可知，算法具有較高穩(wěn)定性。

4 結(jié)束語

針對布谷鳥搜索算法存在的后期搜索速度慢、易早熟收斂和局部搜索能力弱等缺點，提出了基于小批量梯度下降的布谷鳥搜索算法，利用小批量梯度下降優(yōu)化局部搜索，提高算法自適應性，通過11個標準測試函數(shù)測試結(jié)果表明，改進后的布谷鳥算法具有更快收斂速度和更高的尋優(yōu)精度，尤其是對多峰基準測試函數(shù)的尋優(yōu)問題上提升十分顯著，相比其他啟發(fā)式智能優(yōu)化算法在性能上有一定的優(yōu)勢。

表7 參數(shù)pa 敏感性測試平均收斂次數(shù)表Tab.7 The average convergence times of test functions on pa

表8 參數(shù)pa 敏感性測試平均收斂結(jié)果表Tab.8 The average convergence results of test functions on pa