發現概率參數自適應調節的布谷鳥改進算法

賈 涵，連曉峰

北京工商大學 計算機與信息工程學院，北京 100048

1 前言

迄今為止優化算法分為傳統優化算法和智能優化算法。智能優化算法的理論研究主要包括算法的穩定性分析、收斂性分析、收斂速度分析及算法的計算復雜性分析等，這些研究中包含了對算法參數設置的一些理論性指導。其中，關于穩定性的研究結果相對較多，但收斂速度、收斂性分析和計算復雜性的研究相對較少[1-2]。智能優化算法的應用研究覆蓋了計算機、航空、電力電子、電磁、地球物理、生物醫學等大部分科技領域。

大量學者對常用優化算法進行改進研究，主要是通過對參數的動態調節，參數的動態調節可分為適應性調節、自適應性調節和非自適應調節三種基本類型。探索與開發的權衡問題源于智能優化算法，主要是針對一些基于種群的進化算法。探索-開發的權衡關系控制著算法的計算代價和收斂質量，在保證算法的計算時間較短的前提下，提高算法的收斂速度和尋優能力。改進算法的主要思想是借助探索-開發的平衡關系來動態調節某些相關參數。為了實現模態復雜問題的高效全局優化，任何優化算法必須兼具“全局探索”和“局部開發”能力，并在二者之間做出適當的權衡，有效的權衡有助于減少計算代價和實現高效的優化。

元啟發式群體智能算法是受“集體智慧”啟發而提出的高效算法。集體智慧是通過環境中大量相同因子的合作而出現的，例如魚群、鳥群和螞蟻群。在自然界中，集體智慧通常被用于解決動物覓食，逃避追捕或生存環境重新定位等問題。

群體智能優化算法主要受兩個基本算法的啟發：（1）蟻群算法，是受螞蟻在尋找食物過程中發現路徑的行為啟發；（2）粒子群優化算法，是受鳥群和魚群的覓食行為啟發。群體智能“算法”或“策略”被認為是自適應策略，并且通常應用于搜索和優化領域。常用的群體智能優化算法有遺傳算法（Genetic Algorithm，GA）、螢火蟲算法（Glowworm Swarm Optimization，GSO）、蟻群算法（Ant Colony Optimization，ACO）、人工蜂群算法（Artificial Bee Colony algorithm，ABC）和粒子群優化算法（Particle Swarm Optimization，PSO）等。

布谷鳥搜索算法（Cuckoo Search algorithm，CS）是由英國牛津大學的Yang等學者提出的一種元啟發式群體智能算法[3-5]。該算法是在長期研究布谷鳥生活習性的基礎上提出的，主要利用了布谷鳥卵育寄生和萊維（Lévy）飛行的特性，其優點是具有良好的適應性，參數少，隨機搜索路徑優并且尋優能力強[6]。

該算法自提出以來得到了廣泛的研究。在文獻[7]中Yang和Rajabioun等人將CS算法應用于工程優化和多目標優化等實際問題中。文獻[8-9]中Walton等人在布谷鳥尋找鳥巢的時候引入了交換信息，但是由于對CS算法中的隨機步長進行了改進，導致算法極易陷入局部最優并且全局搜索能力過弱。在文獻[10]中Tuba等學者對鳥巢的發現概率Pa和步長進行了動態自適應的調整，提高了算法的收斂性能，但是由于算法完全依賴隨機游走，很難保證其搜索精度。在文獻[11]中王凡等學者在迭代過程中對鳥窩位置加入高斯擾動，提高了CS算法的收斂速度，但是由于引入了高斯算子，使算法在搜索后期穩定性下降。在文獻[12-13]中賀興時等學者通過分析鳥窩位置的群體狀態轉移過程，提高了算法的全局搜索能力，但是由于加入Markov鏈，導致算法在搜索后期收斂速度慢。文獻[14-15]通過對種群的再分組，并根據當前不同的搜索階段對步長進行預先設置，提高了CS算法的搜索性能，但是算法在轉換搜索階段時增加了算法的計算時間并且存在很大的隨機性。

從國內外的研究現狀可以看出，CS算法還有很大的發展空間。但是CS算法也存在一些缺陷，比如在搜索后期收斂速度慢，全局尋優能力弱，不穩定并且易陷入局部最優，因此本文在深入分析CS算法的基礎上，提出了發現概率參數自適應調節的布谷鳥搜索算法（Adaptive Probability of Cuckoo Search algorithm，APCS）。首先設置一個狀態判別參數Ps用來切換探索和開發的狀態，然后設置一個探索開發平衡參數Peb使探索和開發階段達到一個互補，最后實現了對發現概率Pa的動態調整。實驗結果表明了APCS算法較好地解決了CS算法后期存在的收斂速度慢、不穩定等缺點。

2 CS算法的基本原理

布谷鳥搜索算法是模擬布谷鳥尋窩產卵的行為和萊維飛行特性實現的元啟發式群智能優化算法，其中布谷鳥的卵育寄生行為和萊維飛行機制是算法的核心內容。

2.1 布谷鳥的卵育寄生行為

根據生物學家長期觀察，布谷鳥的卵育寄生行為的繁殖步驟如下[3-5]：

步驟1布谷鳥會在繁殖期尋找合適的宿主（大多為雀形目鳥類）。

步驟2布谷鳥趁宿主外出時快速產蛋并將自己的蛋放在宿主鳥巢里。

步驟3同時為了提高幼雛的成活率會移走一枚宿主自己的蛋，使得巢中鳥蛋數量不變，在宿主不發現的情況下代為孵化。

步驟4布谷鳥的蛋孵化時間短，通常最先孵出。之后會將同巢的其余鳥蛋推出巢外，以至于得到更高的成活率。

布谷鳥算法示意圖如圖1。

圖1 布谷鳥算法示意圖

2.2 布谷鳥的萊維飛行

以法國數學家保羅·萊維（Paul Lévy）命名的萊維飛行機制具有較強的隨機性，其步長服從冪律分布。這是一種典型的隨機游走過程，布谷鳥搜索算法使用的就是這種飛行機制。當布谷鳥在尋找鳥巢時，其飛行就是一種方向隨機的運動，飛行軌跡和前一時刻的飛行軌跡存在一定的偏差。布谷鳥飛行的過程主要以小步長為主，但是偶爾有較大步長的位移，因此布谷鳥不會重復停留在一個地方進行搜索[16-17]。

2.3 CS算法的實現

在CS算法的具體實現中，首先提出以下三個理想化的條件：

（1）布谷鳥每次隨機選擇一個最優的鳥巢完成寄生；

（2）孵化效果最好的鳥巢將會繼續利用；

（3）每次選擇寄生的鳥巢數量是不變的，布谷鳥蛋在宿主巢中被發現的概率為Pa。在這種情況下，宿主可以拋出鳥蛋或者放棄當前鳥巢，并建一個新的巢。為了方便研究和計算，這個理想化規則可以近似為被新巢替換（新的隨機解決方案）的概率為Pa[18]。

在理想化的條件下，布谷鳥的位置更新公式如下：

式中，t表示隨機步長。

上述是布谷鳥卵育寄生行為、萊維飛行機制和布谷鳥搜索算法的具體實現步驟。通過上述內容可以看出，布谷鳥搜索算法具有參數少，對目標問題的初始狀態低，隨機搜索路徑優和尋優能力強等優點。

3 發現概率參數自適應調節的布谷鳥搜索算法

CS算法在計算時比較繁瑣，并且因為隨機游走的飛行機制導致相關性能會受到影響[19]。于是本文將基本CS算法中的Pa由固定值調整為動態值，固定值將會影響算法的全局搜索（探索）和局部搜索（開發）性能，并且會導致算法收斂性能弱。

為此，本文提出一種發現概率參數自適應調節的布谷鳥改進算法（APCS）。該算法的核心思想是通過協調探索（全局）和開發（局部）的平衡關系，使參數Pa由固定值變成自適應的動態參數，以提高算法的收斂性能和尋優能力。

3.1 狀態判別參數

若算法處在探索階段的時候，局部搜索能力較弱，容易陷入局部最優；若算法處在開發階段的時候，全局搜索能力較弱[20]。為了實現多目標問題的優化，任何優化算法必須兼具“全局探索”和“局部開發”能力，并在二者之間做出適當的權衡，才能使算法的性能達到最優。APCS算法將利用Pareto最優解，使探索和開發的性能在一定程度上達到最好的狀態，在全局搜索能力最優的同時局部搜索能力也保持較優狀態。從Pareto最優解集中選擇合適的解來作為探索-開發的判別標準[21-22]。

在可行性區域 Xf中，對于 x∈(0,1)，不存在 x′∈Xf，使 得 F(x′)=(f1(x′),f2(x′),…,fk(x′)) 占 優 于 F(x)=(f1(x),f2(x),…,fk(x))，則稱 x為Xf上的Pareto最優解。

APCS算法的探索-開發模式如式（3）所示：

式中，Ps主要用于判斷當前搜索過程處于探索階段還是開發階段；nupdate為更新的鳥巢數量；nall為全部的鳥巢數量。當Ps＜x時，APCS算法處于開發階段，正在進行局部搜索，此時算法極易陷入局部最優解，導致算法的種群多樣性下降，并且收斂性能不佳；當Ps＞x時，APCS算法處于探索階段，正在進行全局搜索，此時雖然算法保持了種群多樣性，但是全局性太強并且易陷入局部最優，使算法的性能不能達到最優狀態。

3.2 探索開發平衡參數

探索（Exploration）是指在搜索優化過程中從整個解空間范圍內獲取目標函數的信息，以便定位全局最優解所在的局部區域。開發（Exploitation）是指在搜索優化過程中對解空間中有希望包含最優解的局部區域進行搜索，以便找到局部最優解甚至全局最優解的搜索策略。通常將探索和開發分別視為全局搜索和局部搜索。

為了協調兩個階段的不足并發揮各階段的優勢，設置參數Peb使探索和開發階段達到一個互補狀態，使APCS算法的收斂性能和尋優能力在兼具“全局探索”和“局部開發”兩個階段下發揮出最好的性能，如式（4）所示：

當Ps較大時，算法處于探索階段，那么為了提高算法的開發能力，使得Peb為較小值；同理，當Ps較小時，算法處于開發階段，那么為了提高算法的全局搜索能力，此時需要Peb為較大值。

3.3 發現概率參數

APCS算法將發現概率Pa由一個固定值改成動態值，主要通過對參數Ps和Peb的動態調整而提出用式（5）實現算法參數Pa的自適應調整：

其中，i為當前迭代次數；imax為最大迭代次數；μ是在區間[0,1]內均勻分布隨機產生的實數；λ為隨機搜索軌跡(1＜λ≤3)；表示當Ps的狀態處于探索（開發）階段時，可以對開發（探索）的性能進行互補，達到一種平衡狀態。

當Ps＞x時，雖然計算時間短，但是收斂性能極差，算法的全局搜索性能過強，因此通過對算法進行改善。以全局搜索為主，局部搜索為輔，使探索階段和開發階段保持平衡，最后求出使算法收斂性能和尋優能力較好的動態Pa值。當Ps＜x時，算法的局部搜索性能過強，將會極易陷入局部最優。同理通過對算法進行改善，進行局部搜索的同時也在進行全局搜索，最終將會隨著迭代的增加而達到全局最優和局部最優的一種平衡。

APCS算法將參數Pa由固定值調整成動態值，實現了自適應的搜索策略，通過迭代次數的增加Pa的值也同時增大，使算法同時兼具探索性和開發性。算法的全局搜索能力往往會隨著迭代的進行而減弱，逐漸向局部搜索轉變，隨著算法的逐漸收斂，多數解將集中到較小的局部區域，最終使算法的各項性能得到提升。

3.4 算法實現

根據上述的條件，APCS算法的具體實現步驟如下：

步驟1定義目標函數 f(x)，并隨機生成nall個鳥巢的初始位置xi(i=1,2,…,nall)。

步驟2計算每個鳥巢對應的目標函數，得到最優值，并且利用位置更新公式對其余鳥巢的位置進行更新。

步驟3對比目前函數最優值，并作出相應改變。

步驟4計算參數Ps并與Pareto最優解求出的判別標準x進行對比，若Ps＜x時，處于開發階段，反之則處于探索階段。

步驟5計算參數Peb實現對當前階段性能的互補。

步驟6在位置更新后，用隨機數r∈[0,1]和更新后的Pa進行對比，若r＞Pa，則對x(t+1)i進行改變，相反則保持不變。最后保留最好的一組鳥巢位置y(t+1)i。

步驟7若未達到最大迭代次數或最小誤差要求，則返回步驟2，否則，繼續下一步。

APCS算法的流程圖如圖2所示。

圖2 APCS算法流程圖

4 數值仿真與分析

通過仿真實驗，測試上述改進算法的性能，并與CS算法的性能進行比較。仿真環境為Windows 7操作系統，Intel處理器，2.10 GHz，內存為4 GB，仿真軟件為MATLAB 2014a。

4.1 測試函數

為了充分測試算法的性能和特點，選擇8個標準函數進行測試，其中涵蓋了單模態和多模態函數，包括Sphere、Shelter、Griewank和Rastrigin等。各基準函數的參數設置如表2所示，CS算法和APCS算法分別進行30次獨立實驗，鳥巢n=30，最大迭代次數imax為600，發現概率Pa按式（10）進行動態調整，若收斂精度小于1.00E-15視為0。

4.2 實驗結果與分析

表2和表3分別記錄了APCS算法和CS算法在10維和30維的情況下，通過表1的8種測試函數得到的全局最優值、最差值和平均值的相關實驗數據，來對比兩種算法的收斂性能和全局尋優能力。

在10維的狀態下實驗結果如表2所示，最佳適應度值隨迭代次數變化的曲線如圖3所示。

f1和 f2是一類簡單的單峰且可分函數，這類函數在整個搜索空間內只有一個峰值，APCS算法分別比CS算法的最優值提高了43個和28個數量級，并且APCS基本接近了理論最優值。從圖3（a）和圖3（b）可以看出APCS算法的收斂性能優于CS算法，就穩定性而言，也比CS算法更加穩定；f3也是簡單的單峰且可分函數，APCS算法的最優值提高了54個數量級，在該基準函數下，APCS算法具有更強的收斂性；f4和 f6是一類復雜的多峰、可分且高維的函數，并且這兩個函數都是典型的多模態非線性全局優化函數，整個搜索空間中存在多個局部最優值，適用于衡量算法的尋優能力，并且使算法的全局尋優能力和局部尋優能力保持平衡。隨著迭代次數的增加，APCS算法可以更快地收斂，并且減少了計算代價。在這兩個基準函數的測試下，APCS算法的最優值、最差值和平均值均為0，說明該算法的穩定性較好；f5和 f7是一類復雜的多峰、不可分且高維的函數，通過圖3（e）和圖3（g）可以看出，APCS算法的收斂速度明顯優于CS算法，并且從表2的實驗數據中可以看出APCS算法的最優值分別提高了50個和65個數量級，因此較CS算法而言，其收斂精度和全局搜索能力得到了較大的改善；f8是一類復雜的多峰、不可分且低維的函數，如圖3（h）所示，APCS算法和CS算法皆避免了過早收斂，但是APCS算法較CS算法在尋優能力上更能兼顧全局搜索和局部搜索，使算法不易陷入局部最優又能在較短時間內尋找到局部最優。

在30維的狀態下實驗結果如表3所示，最佳適應度值隨迭代次數變化的曲線如圖4所示。

表1 基準測試函數

圖3 10維測試結果

表2 10維實驗結果分析

表3 30維實驗結果分析

圖4 30維測試結果

表3列出了在30維情況下的測試結果，通過對比分析全局最優值、最差值和平均值的實驗數據驗證了APCS算法的各項性能指標優于CS算法。對于 f1、f2和 f3函數，APCS算法的優化程度較CS算法的優化程度雖然不是十分明顯，但是收斂速度還是得到了改善，并且通過表3的實驗數據可以看出，APCS算法具有更好的全局搜索能力，同時又增強了局部搜索能力；f5函數是高維且多峰函數，不易找到全局最優解，但是通過對概率的自適應調整以后，尋優能力得到了提高，并且APCS算法的收斂速度較快，同時節省了計算時間；f6和 f8在30維的情況下，APCS算法的收斂速度遠遠高于CS算法的收斂速度，并且迭代次數減少。

通過8個基準函數，對APCS算法和CS算法的各項性能指標在10維和30維的狀態下進行了對比分析。實驗數據和曲線圖表明，APCS算法的收斂速度、尋優能力、穩定性和計算時間都優于CS算法，驗證了算法的有效性和改進后的優勢。

5 結束語

本文在原始的CS算法基礎上，著重研究了發現概率參數自適應調節的布谷鳥改進算法。由于基本的CS算法在搜索后期存在收斂速度慢，尋優能力低，易陷入局部最優并且不穩定等問題，通過對概率的自適應調整加快了算法的收斂速度，提升了算法在兼顧全局搜索和局部搜索時的尋優能力，并且在多峰函數下都不易陷入局部最優。實驗結果更一步驗證了，APCS算法的收斂性能優并且相對穩定。從本文參考的文獻中觀察到，CS算法及相關改進算法在醫療、圖像處理、經濟負荷調度、工程設計和數據聚類等各個領域均有涉及，具有十分廣闊的研究前景。與其他算法相比，CS算法的相關參數少，并且易于與其他算法相融合，若能針對上述問題展開深入研究，將會極大地促進該算法的發展，未來將在理論分析方面對CS算法做進一步的研究。