擬牛頓布谷鳥混合算法?

宋慶慶 賀興時 郭 旭

（西安工程大學理學院 西安 710048）

1 引言

布谷鳥算法是2009年YANG模擬布谷鳥的尋窩產卵行為，提出了一種新的智能優化算法，該算法依賴于布谷鳥的巢寄生性和萊維飛行（Lévy flight）搜索原理［1］。布谷鳥算法（CS）有很好的全局搜索能力，但由于它的隨機性強造成CS的局部搜索能力相對較弱，在后期優化效率地，因此需要進一步完善［2～4］。擬牛頓法是一種解決優化問題的有效方法，局部尋優能力強，但是擬牛頓算法對初值依賴性大，如果初始選的不合理，很可能造成算法不收斂［5］。目前擬牛頓法已經很好地與粒子群算法［6～7］、蝙蝠算法［8］遺傳算法［9～10］、蟻群算法［11］結合。本文結合兩算法的優點，在布谷鳥搜索后期可以加入擬牛頓法來優化布谷鳥算法的搜索性能，同時兩算法又能相互克服缺陷。

2 擬牛頓布谷鳥算法

2.1 布谷鳥算法

在布谷鳥算法中的三點理想化條件：1）每只布谷鳥一次只產一個蛋，并且隨機選擇一個鳥窩來存放它；2）最好的鳥窩（解）將會被保留到下一代；3）可用鳥窩的數量n是固定的，鳥窩主人發現外來鳥蛋的概率是 Pα，其中 Pα∈[0，1]。在這種情況下，鳥窩主人可以將該鳥蛋丟棄，或者干脆放棄這個鳥窩，在新的地方重新建立一個鳥窩。在上邊三個理想化條件下，布谷鳥根據Levy飛行進行搜索，步長更新公式為

式（1）中⊕表示點對點乘法；式（2）s0表示初始步長。CS的具體操作步驟詳見文獻［2］。

2.2 擬牛頓法的步驟［12-13］

已知目標函數 f（X）及梯度g（X），終止準則ε。

2）計算搜索方向 dk。做直線搜索 f（X（k）+αkdk）=minf（X（k）+αkdk），求出步長因子 αk，并令xk+1=xk+αkdk。

3）判斷是否滿足終止條件，若滿足則停止，否則轉5）。

4）修正Bk產生Bk+1，使得擬牛頓條件成立。5）k=k+1，轉至2）。

2.3 擬牛頓布谷鳥算法步驟

2）保留上一代最好鳥窩位置 fmin，利用式（1）、（2）對其他鳥窩進行位置更新，然后得到一組新的鳥窩位置Pt對這組鳥窩位置進行測試，與上一代鳥窩位置Pt-1=比較，讓測試值較好的鳥窩位置替代測試值較差的鳥窩位置，從而得到一組較優的鳥窩位置

3）產生服從均勻分布的隨機數 r∈（0，1），與布谷鳥的鳥蛋被鳥窩主人發現的概率Pα對比，保留P中發現概率較小的鳥窩位置，對概率較大的鳥窩位置進行隨機改變，從而得到一組新的鳥窩位置。將這組鳥窩位置進行測試，與P=的每個鳥窩位置的測試值進行比較，用測試值較好的鳥窩位置替代測試值較差的鳥窩位置，從而得到當代全局最優鳥窩位置

4）以P′為初始位置，采用擬牛頓算法精確搜索目標位置，若達到終止條件，算法結束，并輸出最優個體所在的位置，否則返回第2）步。

3 數值模擬

本文比較NQCS和CS對測試函數庫中的8個測試函數［14～15］的優化性能。除了 Sphere是單峰函數以外，其他都為多峰函數，測試函數的最優值都為0，如表1所示。種群規模n=25，Pα=0.25，參數β=1.5?，控制步長α取1，其他參數根據具體情況設定。

表1 測試函數

表2是NQCS和CS的測試結果表，表中的數據是在不同維度下計算函數的平均最優值、標準差、最大值、最小值。首先對與Cube函數、Himmelblau函數、Sphere函數來說NQCS的平均最優值遠遠小于CS并且計算精度上至少高出2個數量級，Zakharov函數和Zakharov函數甚至高出20個數量級，對于其他三個函數雖然不是很明顯但也可看出NQCS的平均最優值結果優于CS的。其次在標準差方面，對于8個函數來說NQCS的標準差也都低于CS可以得出NQCS是比CS穩定的。接著是最大值最小值，發現仍然對于Cube函數、Himmelblau函數、Zakharov函數、Sphere函數、Schwefel 2.4函數NQCS的最值明顯小于CS的最值，Cosine Mixture函數、Quintic函數、Ackley函數的最值也是NQCS較小。因此可以初步得出在計算精度上NQCS是優于CS的。

表2 兩種算法的測試結果

兩個算法在8個測試函數上均獨立運行20次，因而在每個測試函數上，每種算法都有20個樣本。采用T檢驗比較分析NQCS和CS的性能。本實驗的T檢驗的自由度為38，顯著水平為0.05。P值代表顯著性水平，當P小于0.05時，表示NQCS顯著優于CS，反之則不顯著。

表3 兩算法的T檢驗結果

從表3中NQCS和CS的T檢驗結果可以看出Cube函數、Zakharov函數、Sphere函數、Quintic函數、Ackley函數、Schwefel 2.4函數P值小于0.01，表明NQCS非常顯著的優于CS。Himmelblau函數的P值大于0.01小于0.05，表明NQCS顯著優于CS。Cosine Mixture函數的P值大于0.05表明在統計學角度上NQCS是不顯著優于CS的。

因此綜上所述，NQCS在大部分測試函數上顯著優于CS。

4 結語

本文擬牛頓算法和布谷鳥算法相結合，建立了一種混合算法NQCS。先采用CS為BFGS提供一個較好的初始點，然后再用BFGS更進一步搜尋局部精確解。這樣既可以避免CS局部精細搜索能力差，又能彌補擬牛頓算法對初值敏感的不足。通過8個基準函數測試其性能，實驗結果表明NQCS明顯比CS具有更高的收斂精度和更好的全局最優值。