基于自適應步長的改進布谷鳥算法

孫 敏，房明磊，韋 慧

（安徽理工大學 數學與大數據學院，安徽 淮南 232001）

近年來，各種啟發式算法不斷涌現，如遺傳算法[1]，粒子群算法[2]等，它們都是通過模擬生物的行為或自然界的現象來解決最優化問題.隨著模擬生物行為的不斷發展，2009年，劍橋大學的Yang和Deb通過模擬布谷鳥尋窩產卵的行為提出了一種新的搜索算法，即布谷鳥搜索算法（Cuckoo Search，CS)[3].由于這種算法簡單高效、參數少、易于實現、隨機搜索路徑優等特點，已成功應用于工程設計優化[4]、多目標優化[5]、人臉識別[6]、神經網絡訓練[7]、整數規劃[8]和多閾值圖像分割[9]等實際問題中.

但CS算法與其他一些智能算法一樣，存在后期精度不高、搜索速度慢等缺點.針對這些不足，Valian等[10]引入自適應機制，提出了一種自適應步長和自適應發現概率的CS算法，提高了原始CS算法的性能.王凡等[11]重點探索了基于高斯擾動的CS算法，在迭代過程中對鳥窩加入高斯擾動，增強了鳥窩位置變化的活力.王李進等[12]提出了一種基于逐維改進的CS算法，改進的算法針對解采用逐維更新評價策略，有效地提高了CS算法的收斂速度并改善解的質量.李明等[13]介紹了一種和差分進化算法結合的混合CS算法，提高了算法的尋優精度.

本文針對CS算法的步長、發現概率和縮放因子引入動態自適應策略，提出了一種基于自適應步長的改進布谷鳥算法（improved Cuckoo Search,iCS），以提高算法的收斂速度和求解精度.

1 基本的布谷鳥搜索算法

自然界中，布谷鳥不僅有令人著迷的美妙聲音，而且有獨特的繁衍方式.它們是通過寄生育雛的方式來繁殖下一代，將自己產下的卵偷偷放入宿主鳥窩中，讓它們為其孵化下一代.為了避免被發現，一些布谷鳥將自己的卵模仿成宿主鳥的卵，由于布谷鳥的卵比宿主鳥孵化的時間早，孵化的雛鳥會本能地將宿主的幼雛或卵推出巢穴，這將會提高它們自己獲得宿主食物的可能性，從而增大存活概率.一旦被宿主鳥發現，宿主鳥就會將外來的卵直接丟棄或棄窩另筑新窩.

布谷鳥尋找適合自己產卵的鳥窩位置是隨機或類隨機的方式，為了模擬布谷鳥尋窩的行為，首先，設定以下3個理想化狀態[3]：

（1）每只布谷鳥1次只產1個蛋并隨機選擇鳥窩來放置它.

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

（3）可利用的鳥窩數量n是固定的,宿主鳥能發現外來鳥蛋的概率pa∈[0,1].

在這種情況下，宿主鳥可將該鳥蛋丟棄或放棄這個鳥窩，另尋地方再重新建1個新鳥窩.

在這3個理想狀態的基礎上，布谷鳥按萊維飛行（lêvy flight）方式搜索鳥窩的路徑和位置更新公式[3]如式（1）所示：

式中xit和xit+1分別表示第t代和第（t+1）代的位置；⊕為點對點乘法；α表示步長控制因子；lêvy（λ）為lêvy隨機搜索路徑，并且其與時間t的關系服從 lêvy 分布，即 lêvy（λ）~u=t-λ(1＜λ≤3).

通過位置更新后，用隨機數r∈[0,1]與pa對比，若r＞pa，則對xit+1采用偏好隨機游動方式進行改變，偏好隨機游動如式（2）所示：

式中，r是縮放因子，服從（0,1）區間上的均勻分布，xjt和xkt表示第t代的兩個隨機解.

2 改進的布谷鳥搜索算法

2.1 改進算法的內容

在基本的CS算法中，隨機步長是通過lêvy flight產生的，搜索時，步長時大時小，步長越大越有利于搜索全局最優，但降低了搜索精度，有時會出現震蕩現象.若步長越小，則結果相反.因此針對lêvy flight產生的步長雖具有隨機性但缺乏自適應性問題，鄭洪清等[14]根據不同階段的搜索結果提出了一種自適應步長布谷鳥搜索算法（Self-Adaptive Step Cuckoo Search algorithm,ASCS）.該算法自適應動態調整了步長的大小，增加了解的多樣性，使算法的搜索速度和精度都有較大的提高.其自適應策略如下：

式中，ni表示第i個鳥窩位置，nbest表示此時鳥窩位置的最佳狀態，dmax表示最優位置與其余所有鳥窩位置距離的最大值，stepmax和stepmin分別表示步長的上下限.

根據式（3）和式（4）實現自適應動態調整步長.當第i個鳥窩位置越接近最佳位置時，步長越小，當第i個鳥窩位置離最佳位置較遠時，步長越大.這樣，由上一代迭代的結果來動態更新本次迭代的移動步長，使算法具有更好的自適應性.

然而，自適應步長布谷鳥搜索算法[14]僅僅只對步長進行改進，其發現概率pa取固定值0.25，不利于保持算法的全局和局部隨機搜索之間的平衡；同時，該算法中的縮放因子r取[0,1]區間的均勻分布隨機數，對較差的個體沒有產生較大的變異，不利于新解的生成.所以，若能較好地控制縮放因子r和發現概率，使較差的個體產生較大變異，從而提高算法的求解精度.

為了克服以上問題，本文提出了一種基于自適應步長的改進布谷鳥搜索算法（iCS），即在自適應步長布谷鳥搜索算法（ASCS）的基礎上，引入了發現概率和縮放因子自適應動態調整策略[15]，其縮放因子、發現概率分別調整為：

其中，

rit：第t代種群中，第i個個體的縮放因子；

fit、和分別為第 t代種群中第 i個個體、最優個體以及最差個體的適應度；

pat：第t代種群中第i個個體被發現并重新生成新解的概率；

pamax和 pamin：pat的上下限；rmax和 rmin：分別為縮放因子的上下限.

圖1 改進算法的流程圖

由式（5）和式（6）實現自適應動態調整發現概率和縮放因子，從而使更多的個體參與演化，以提高種群的多樣性，避免早熟，達到提高收斂速度和求解精度的目的.

2.2 改進算法的步驟

步驟1 初始化解，隨機生成n個鳥窩，搜索空間維數為D,最大迭代次數為itermax，步長step的上下限，發現概率pa和縮放因子r的上下限，并計算所有鳥窩的適應度.

步驟2 保留上代最優鳥窩位置，將其他鳥窩按式（3）和式（4）進行更新，計算更新會后鳥窩的適應度，若新的鳥窩適應度更高，則替換舊的解.

步驟3 通過動態縮放因子（式（5））和動態發現概率（式（6））淘汰部分解，并采用偏好隨機游動（式（2））產生與淘汰解數量相同的新解.

步驟4 計算更新的鳥窩適應度，輸出當前最優解.

步驟5 判斷算法終止條件，若滿足則獲得結果，否則返回步驟2.

基于以上步驟，改進算法的流程圖如圖1所示.

3 仿真實驗

3.1 實驗設計

為驗證改進算法的性能，選取如表1所示的4個典型的benchmark函數[12]進行測試.實驗中算法參數設置如表2所示，ASCS算法和iCS算法中步長step上下限分別為0.5和0.01.

表1 測試函數

表2 實驗參數設置

3.2 實驗結果及分析

固定收斂精度tol=1.0e-9，針對不同的標準測試函數，各算法獨立運行20次，實驗結果如表3所示，表中的最小值、平均值和最大值分別為所運行20次中相應的求得的最小適應值、平均適應值和最大適應值.

表3 三種優化算法的性能比較

從表3可以看出，對于測試函數f1，iCS算法比CS和ASCS算法的最小值分別提高了7個、1個數量級，平均值也分別提高了7個、1個數量級.對于測試函數f2，iCS算法的最小值比CS算法提高了4個數量級，比ASCS算法提高了1.1679，平均值比CS算法提高了4個數量級，比ASCS算法提高了1個數量級.對于測試函數f3，iCS算法比CS和ASCS算法的最小值分別提高了0.4330、0.0057，平均值分別提高了0.5987、0.0446.對于測試函數f4，iCS算法比CS和ASCS算法的最小值分別提高了9.8904、6.0140，平均值分別提高了6.3512、4.8826.就穩定性而言，iCS算法的穩定性也高于ASCS和CS算法.因此可以得出iCS算法的性能最優，其次是ASCS算法，CS算法最差.

為了反映算法的收斂速度，固定迭代次數為300，每種測試函數獨立運行20次.比較三種算法的收斂速度和求解精度.圖2—5分別為4個測試函數 f1、f2、f3、f4采用 3 種算法尋優時適應值隨迭代次數變化的曲線.

從圖2可以看出，對于函數f1，iCS算法迭代150次時最小適應值就已經達到10-2而ASCS算法的適應值較之較大，此時CS算法適應值為102.因此，由圖中適應值的變化曲線，可以明顯看出iCS收斂速度最快，ASCS次之，CS最慢.當迭代次數都為300次時，iCS算法的精度比ASCS和CS算法好.

從圖3可以看出，對于函數f2，iCS算法迭代150次時最小適應值達到10-1，而ASCS算法為100，此時CS算法的最小適應值為101.因此，由迭代過程適應值的變化曲線可知，iCS收斂速度最快，ASCS次之，CS尋優過程適應值下降十分緩慢.當迭代300次后，iCS算法的精度明顯比ASCS和CS算法的精度高.

從圖4可以看出，對于測試函數f3，iCS算法、ASCS算法尋優時適應值的下降速度也明顯比CS快，而iCS的收斂速度略優于ASCS.當迭代300次時，iCS算法的適應值為10-3，比ASCS和CS算法的精度高.

圖2 函數f1的收斂曲線

圖3 函數f2的收斂曲線

圖4 函數f3的收斂曲線

圖5 函數f4的收斂曲線

對于測試函數f4，由圖5可知，此時，三種算法的收斂速度快慢區別不是很明顯，改進的算法略優于ASCS和CS算法.該測試函數是多波谷函數，因此迭代時容易達到局部最優，收斂速度容易受到影響，較前面三種測試函數適應值的下降速度明顯變慢.

綜上分析可知，引入自適應縮放因子、發現概率的自適應策略，并結合自適應步長的優勢，能有效提高CS算法的收斂速度和尋優精度.

4 結語

論文主要引入了針對發現概率和收縮因子的自適應策略對自適應步長布谷鳥算法進行改進.由所給的標準測試函數，討論了基本CS算法，自適應步長算法和改進算法的收斂速度快慢和精度高低問題.仿真實驗結果表明，iCS算法比ASCS算法和CS算法有更佳的尋優性能，能夠提高收斂速度和求解精度.然而對于測試函數f4，雖然iCS算法能改善CS算法的性能，但迭代后期易陷入局部最優，這個問題仍然需要進一步研究.