布谷鳥算法的收斂性分析及性能比較*

劉曉東，孫麗君，陳天飛+

1.河南工業大學糧食信息處理與控制教育部重點實驗室，鄭州 450001

2.河南工業大學鄭州市機器感知與智能系統重點實驗室，鄭州 450001

3.河南工業大學電氣工程學院，鄭州 450001

4.河南工業大學信息科學與工程學院，鄭州 450001

1 引言

近年來，群體智能算法廣泛應用于各個領域，其通過團隊的協作和組織，將簡單的個體聯系起來產生群體智慧，并以此解決實際問題[1]。與傳統優化算法相比，群體智能算法有以下三種特點：靈活性、穩健性、自組織性[2]。這三種特點主要表現：若在可變系統或者環境下，群體適應能力強；當某個體出現狀況時，不會影響群體對問題的處理；群體智能算法是通過個體相互競爭或者作用產生的，不受任何中心控制和局部監管[3]。

群體智能算法經過多年的發展，取得了許多重要的研究成果。例如，Eberhart和Kennedy觀察鳥群、魚群的行為于1995年提出了粒子群算法[4]（particle swarm optimization，PSO）。該算法具有收斂速度快、效率高的特點，但任子暉等人[5]從轉移概率的角度證明了標準粒子群算法不是全局收斂的。同年，Storn和Price提出了差分進化算法（differential evolution，DE）[6]，它具有結構簡單，易于實現等優點，廣泛應用于模式識別、數據挖掘等領域。2005年，Karaboga小組通過觀察蜜蜂群體行為得到啟發，提出了人工蜂群算法（artificial bee colony，ABC）[7]，而孔翔宇等人[8]基于鞅論研究了人工蜂群算法的幾乎必然強收斂性，并且由于該算法結構簡單，易于實現，在電力、組合優化、系統工程等領域有著廣泛的應用。2010年，Yang提出了蝙蝠算法（bat algorithm，BA）[9]，并且尚俊娜等人[10]采用Markov鏈模型證明了該算法具備全局收斂性。同樣，該算法具備模型簡單、參數少等優點，常常應用于組合優化等問題。2009年，Yang和Deb觀察布谷鳥巢寄生育雛行為，結合萊維飛行特征，首次提出了布谷鳥搜索算法[11]（cuckoo search，CS）。該算法主要特點：參數少、操作簡單、尋優能力強等。目前，布谷鳥算法在圖像和信號處理、電力系統、醫學應用、數據挖掘等領域已經得到成功應用[12-15]。例如Garg等[16]提出了CS算法的最優掩模生成方法，用于抑制噪聲和語音信號的增強；Liu將CS算法應用于臨床疾病診斷中等[17-19]。

自CS算法提出以來，一些學者對CS算法的性能進行了改進。這些改進的方式可大體分為三方面：（1）發現概率P的改進，如文獻[20]認為被發現的概率P的選擇會影響最優解的搜索；（2）步長的改進，如文獻[21]針對優勢解交換信息步長進行改進；（3）混合CS算法改進，如文獻[22]介紹了一種和差分進化算法相結合的混合CS算法。除此之外，CS算法的變體及應用研究也有不錯的成果，如文獻[23]提出了一種離散二進制布谷鳥搜索算法來處理二進制優化問題；文獻[24]提出了離散CS算法，用于解決帶時間窗和同時取送貨的車輛路徑問題；文獻[25]提出了混合多目標布谷鳥搜索算法來解決多目標優化問題。另外，CS算法在性能分析方面也有進步，如文獻[26]使用模糊系統來動態調整CS算法的參數，分析了參數對CS算法性能的影響等。然而，這些改進算法僅僅在實驗的角度下對比了算法收斂性能的提高，而缺乏必要的理論分析。因此，CS算法在實驗和理論上的綜合分析是必要的，進而為后期的改進提供支持。

本文對CS算法構建數學定義，并建立其Markov模型，在此基礎上利用算法收斂準則證明布谷鳥的全局收斂性。雖然文獻[27]同樣采用Markov模型對CS算法進行了收斂性分析，但本文的收斂性證明與文獻[27]存在著一定的差異。首先，在CS算法的數學定義方式上存在著顯著不同；其次，本文對CS算法收斂性分析證明中采用了Chapman-Kolmogorov方程的方式進行證明和分析。本文不僅對已有CS算法的理論分析加以補充，而且使CS算法的收斂分析更加全面。然后，從兩方面展開實驗分析：（1）根據數據規模的變化來繪畫出時間復雜度增長曲線，對比分析五種算法的復雜度。（2）五種典型群體智能算法在相同維度和不同維度情況下分別以數據統計的形式對同一個優化問題進行比較；并通過圖像對比的形式直觀地衡量算法的性能。

2 布谷鳥算法原理

在自然界中，布谷鳥的繁殖習性是比較獨特的，它是巢寄生鳥類，巢寄生是指利用其他鳥類的巢穴來孵化自己的蛋[28]。若要提高蛋的存活率，則將宿主的蛋破壞掉或者偽裝。若蛋被宿主發現，則宿主尋找新的鳥巢或者破壞蛋[29]。這個是自然選擇的過程，選擇鳥巢的好壞直接影響下一代的生存率。通過布谷鳥搜尋鳥巢的過程來模擬出布谷鳥算法，該算法基于三種理想規則：

規則1每只布谷鳥一次只能產一枚卵，并隨機選擇地放入一個鳥巢中。

規則2在隨機選擇的一組鳥巢中，最好的寄生巢將會被保留到下一代。

規則3鳥巢數量是固定的，被發現的概率Pa,Pa∈[0,1]，若宿主發現蛋，它會將蛋摧毀或者重新尋找新巢。

基于以上三種理想規則，布谷鳥尋找宿主鳥巢的位置和路徑更新公式如下：

當鳥巢位置更新后，將區間[0,1]的隨機數r與Pa比較，如果r＞Pa時，就隨機更新一次鳥巢的位置，否則鳥巢的位置不變。

根據上述分析過程，布谷鳥搜索算法流程圖如圖1所示。

Fig.1 Cuckoo search flow chart圖1 布谷鳥搜索算法流程圖

3 Markov鏈收斂性分析

3.1 算法的收斂準則

收斂準則是一種判斷算法收斂的理論分析方法，定理如下。

在Lebesgue測度空間定義搜索的下確界：

其中，v(x)表示在集合x上的Lebesgue測度?？梢远x最優區域：

其中，ε＞0,C為充分大的正數，如果算法找到Rε,M中的一個點，則認為算法找到了可接受的最優值。

假設1f(D(x,ζ))≤f(x),若ζ∈A，則有f(D(x,ζ))≤f(ζ)。

假設2對于?B∈A,s.t.v(B)＞0，有其中uk(B)為算法D第k次迭代搜索解在集合B上的概率測度。

定理1（算法全局收斂）設f是可測的，可測空間A是Rn上可測度的子集，算法D滿足兩個假設，是算法D產生的序列，則有，即算法全局收斂[30]。

3.2 CS算法的Markov鏈模型

定義1（鳥巢位置的狀態和鳥巢位置的狀態空間）鳥巢的位置構成布谷鳥的狀態，記作x,x∈A,A為可行解空間。鳥巢位置的所有可能狀態組成的集合構成鳥巢位置的狀態空間，記為X={x|x∈A}。

定義2（鳥巢位置的群狀態和鳥巢位置的群狀態空間）鳥巢位置群中所有布谷鳥的狀態構成布谷鳥巢位置群狀態，記作S=(x1,x2,…,xN),其中xi表示第i個布谷鳥位置的狀態。鳥巢位置群所有可能狀態組成的集合構成鳥巢位置群的狀態空間，記為S={s=(x1,x2,…,xN)|xi∈X,1 ≤i≤N}。

定義3（鳥巢位置的狀態轉移）對?xi∈s，?xj∈s，在CS算法迭代中，鳥巢位置的狀態從xi轉移到xj，記為T(xi)=xj。

定理2在CS算法中，鳥巢位置狀態從xi轉移到xj的轉移概率P(T(xi)=xj)。其表達式為P(T(xi)=xj)=,其中是通過CS算法中式（1）位置轉移的概率，表示被宿主發現概率所產生的位置轉移概率。

證明假設鳥巢位置的狀態從xi轉移到xj過程中，它們之間有一次的中間轉移狀態xi′，此時P(T(xi)=xj)的概率為：

由于x、g是多維數據，加減號表示矢量加減，式（6）中絕對值表示超空間立方體的體積。

由布谷鳥算法的理想規則3可知，隨機數r∈[0,1]與Pa對比。則鳥巢位置狀態由xi′→xj的概率為：

由此，定理得證。□

定義4（鳥巢位置的群狀態轉移）在布谷鳥算法迭代中，對于?si=(xi1,xi2,…,xiN)∈S，?sj=(xj1,xj2,…,xjN)∈S，鳥巢位置的群體狀態從si轉移到sj，記作T(si)=sj。

定理3在CS算法中，鳥巢位置的群狀態從si轉移到sj的轉移概率為：

證明鳥巢位置的群狀態中包含所有鳥巢位置的狀態。當鳥巢位置的群狀態從si轉移到sj時，表示群狀態的所有位置狀態都會同時轉移，即T(xi1)=xj1,T(xi2)=xj2,…,T(xiN)=xjN同時成立，則鳥巢位置群狀態轉移的概率為：

由此，定理得證?！?/p>

定理4CS算法中鳥巢的群體狀態序列{s(t):t≥0}，是有限齊次Markov鏈。

證明任何優化算法的搜索空間都是有限的，任一個鳥巢的位置狀態xi都是有限的，因此鳥巢位置的狀態空間X也是有限的。群狀態空間s=(x1,x2,…,xN)由N個鳥巢位置組成，N為有限正整數，則鳥巢位置群狀態空間S也是有限的。

由定理3得，群狀態序列{s(t):t≥0}中，對于?s(t-1)∈S,?s(t)∈S,其轉移概率P(T(s(t-1))=s(t))是由鳥巢群體中的所有鳥巢位置的轉移概率P(T(x(t-1))=x(t))決定，由定理2可知，轉移概率P(T(x(t-1))=x(t))僅與t-1時刻的狀態x、優化問題的最大值和最小值相關，因此P(T(s(t-1))=s(t))也僅與t-1時刻的狀態相關，而與時間t-1無關，即鳥巢的群體狀態{s(t):t≥0}有Markov性和齊次性，又因為狀態空間為可列集，所以其構成一個有限齊次Markov鏈?！?/p>

3.3 布谷鳥算法的收斂性分析

定義5設優化問題全局最優解g*，定義鳥巢位置的最優狀態集M={s*=(x)|f(x)=f(g*),s∈S}。

定理5CS算法中，對鳥巢位置的狀態序列{s(t):t≥0}而言，最優狀態集M是狀態空間S上一個閉集。

證明對?si∈M?sj?M，對于任意轉移步長l，l≥1，由Chapman-Kolmogorov方程可得：

由sr(c-1)∈M,src?M，有f(xc)＞f(xc-1)=f(g*)=inf(f(a))，a∈A，則至少存在，此時，因此M是S上的一個閉集。□

定理6鳥巢位置群體狀態空間S，不存在非空閉集B,使得B?M=?。

證明（反證法）假設群體狀態空間S中存在非空閉集B，且B?M=?，則設si=(g*,g*,…,g*)∈M，?sj=(xj1,xj2,…,xjN)∈B,有f(xjc)＞f(g*)，由定理2和定理3可得，每個P(T(sj)=si)都有由于，則P(T(xj)=xi)≠0，因此B不是閉集，這與假設矛盾。因此鳥巢位置群狀態空間S中不存在M之外的非空閉集。□

定理7假定Markov鏈有一個非空閉集E，且不存在另一個非空閉集D，使得E?D=?，則當j∈E時，有且當j?E時，有=0[31]。

定理8當群體內部迭代趨于無窮時，群體狀態序列必將進入最優狀態集M。

證明由定理5、定理6和定理7可證?！?/p>

定理9CS算法收斂到全局最優。

證明由于CS算法的適應度函數是非遞增的，因此CS算法滿足隨機算法假設1。由定理8可知，CS算法滿足假設2，故CS算法收斂于全局最優?！?/p>

4 CS算法的仿真實驗分析

4.1 硬件設備和算法參數設置

實驗是在操作系統為Windows 10，處理器是英特爾i5-8 400，固態硬盤256 GB和GTX1050的顯卡的硬件環境下，采用Matlab2013運行算法，然后收集數據和圖像。為了保障算法的正常運行，分別對5種不同的算法進行參數的調整，如表1所示，可以看出布谷鳥算法與其他算法相比，參數明顯較少。

4.2 算法性能分析

4.2.1 復雜度分析

圖2是5種典型智能算法運行時間對比圖。根據復雜度的定義和算法偽代碼可知，智能算法的計算規模均與種群的數目N、維度D和迭代次數有關，當維度和迭代的次數一樣時，改變種群的數量即改變了計算的規模。本實驗對表2中F1函數進行求解，繪制出5種典型群體智能算法的運行時間。從整體變化中可以看出5種群體智能算法的復雜度由高到低依次為ABC ＞DE ＞CS ＞PSO ＞BA 。總體來說，CS算法與其他算法相比復雜度較低。

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

Fig.2 Time complexity comparison圖2 時間復雜度對比

4.2.2 收斂性分析

收斂性分析包含了對算法的收斂速度、收斂精度及其局部搜索和全局搜索的分析。本部分實驗是在Matlab2013軟件平臺上，對表2中18個測試函數進行求解，統計收斂數據并比較5種典型群體智能算法的性能，結果如表3和表4所示。

當判斷條件（精度或迭代次數）不變時，將表2中測試函數獨立運行50次，統計出均值、標準差和排名。其中，平均值和標準差分別代表著算法的搜索精度和穩定性。

CS算法在搜索精度上的比較分析，從表3中可以看出，當維度為10時，CS算法的平均排名在1.88，最終排名為第二位。在大部分測試函數上，CS算法的性能都優于其他算法，例如在F3、F4、F5等函數上，CS算法性能處于優勢；并在F1、F2、F6等測試函數上算法性能相當；只有在F13函數上性能處于劣勢。由表4看出，當維度為50時，CS算法的平均排名在1.61，最終排名處于第一。在所有測試函數中，除了F9、F10、F15函數CS算法性能處于中等，在其他函數上，CS算法的搜索性能都優于其他算法。此外，相同算法處理相同的問題時，當維度升高時，算法的搜索性能逐漸變差。根據表3和表4觀察到CS算法在平均排名和最終排名都發生了變化，高維度時，CS算法性能表現得更為優秀。

Table 2 Test functions表2 測試函數

Table 3 Comparison of standard test functions(D=10)表3 標準測試函數的比較(D=10)

Table 4 Comparison of standard test functions(D=50)表4 標準測試函數的比較(D=50)

為了更加直觀地評價5種算法的性能，首先選取18種標準測試函數分別對5種算法獨立運行50次，并畫出平均進化過程的結果圖像，如圖3～圖20所示。其次將測試函數分為單峰測試函數和多峰測試函數。單峰測試有F1、F2、F4、F8、F10、F11、F12、F14、F16、F17。單峰測試函數檢測出算法的尋優的精度、尋優的速度。多峰測試函數有F3、F5、F6、F7、F9、F13、F15、F18，由于多峰測試函數存在許多極值，因此多峰測試函數的作用為測試出算法是否會陷入局部最優以及全局最優的搜索能力。

Fig.3 Logarithm F1 curve圖3 F1對數曲線

Fig.4 Logarithm F2 curve圖4 F2對數曲線

Fig.5 Logarithm F3 curve圖5 F3對數曲線

Fig.6 Logarithm F4 curve圖6 F4對數曲線

Fig.7 Logarithm F5 curve圖7 F5對數曲線

Fig.8 Logarithm F6 curve圖8 F6對數曲線

Fig.9 Logarithm F7 curve圖9 F7對數曲線

Fig.10 Logarithm F8 curve圖10 F8對數曲線

Fig.11 Logarithm F9 curve圖11 F9對數曲線

Fig.12 Logarithm F10 curve圖12 F10對數曲線

Fig.13 Logarithm F11 curve圖13 F11對數曲線

Fig.14 Logarithm F12 curve圖14 F12對數曲線

Fig.15 Logarithm F13 curve圖15 F13對數曲線

Fig.16 Logarithm F14 curve圖16 F14對數曲線

Fig.17 Logarithm F15 curve圖17 F15對數曲線

Fig.18 Logarithm F16 curve圖18 F16對數曲線

Fig.19 Logarithm F17 curve圖19 F17對數曲線

Fig.20 Logarithm F18 curve圖20 F18對數曲線

觀察單峰函數曲線圖3、圖4、圖10、圖12、圖14、圖18、圖19可知5種算法在搜索精度上CS算法始終處于優勢。如圖6觀察出CS、DE、ABC都達到了函數理論值，如圖13、圖16觀察出CS算法的計算精確度最高。

觀察多峰曲線圖5、圖7、圖8、圖9、圖15可以看出，ABC算法出現幾次陷入局部最優值的變化，人工蜂群算法是通過蜜蜂之間的正反饋機制，加快了全局尋優，但在接近全局最優時，尋優的速度變慢，種群的種類變少。CS算法曲線近似光滑的曲線，CS算法在處理這一類問題時，很好地跳出了局部最優值，使其盡可能快地搜尋全局最優值。如圖11、圖17、圖20中5種算法曲線都出現了局部最優值，由于CS算法在個體和群體之間的平衡，使得CS算法更好地跳出局部最優值。從圖11可以看出，CS算法和ABC算法的曲線極為相似，它們的局部搜索能力比較強，并能夠更好地跳出局部最優值，PSO算法對數曲線收斂速度最快，但從整體看精度不如其他算法，也容易陷入局部極值，粒子群是以全局最優粒子進行搜索，粒子缺乏多樣性。如圖17、圖20中CS算法曲線出現了幾次局部最優值的變化，最終停留到局部最優值。總體來說，無論是處理單峰函數問題還是處理多峰函數問題時，CS算法的性能都優于其他算法，CS算法的局部搜索和全局搜索能力較強，但在處理某些問題時，也會陷入局部最優的情況。

5 結束語

本文對布谷鳥算法從兩方面展開分析：（1）理論分析，先對CS算法構建數學定義，再利用數學定義構建Markov模型。然后，利用算法收斂準則證明布谷鳥的全局收斂性。（2）實驗分析，統計5種算法分別在不同維度下解決單峰問題和多峰問題的平均值、標準差。觀察得出當維度升高時，優化算法性能逐漸變差。再通過圖表的形式，分析出布谷鳥算法復雜度和性能。CS算法與其他算法相比，其精度較高、復雜度較低、穩定性較好，但在收斂速度方面明顯弱于粒子群算法和蝙蝠算法。若能夠對CS算法的性能進行深入的探究，將會使CS算法的發展更進一步。