多策略融合的黃金正弦布谷鳥搜索算法

劉 青，賀興時，顧佳鑫

(西安工程大學 理學院，陜西 西安 710048)

0 引 言

布谷鳥搜索算法(cuckoo search algorithm，CS)是YANG等基于一些布谷鳥的產卵寄生行為的群智能算法[1],具有計算速度快、穩定性高、參數少、易實現的優點。

國內外學者對該算法的改進研究，可歸納為以下幾個方面：①改進算法參數：陳程等提出了動態調整概率的雙重布谷鳥搜索算法(DECS)[2]，相比傳統布谷鳥搜索算法尋優性能有所提升，但算法步驟復雜不易理解；黃閩茗等將逐維的反向學習策略添加到動態自適應布谷鳥搜索算法中[3]，但測試函數只考慮了單峰和多峰函數，算法測試效果不全面；宋慶慶等將混沌序列引入布谷鳥搜索算法，以優化鳥巢的初始位置，并在混沌序列的基礎上建立布谷鳥搜索算法[4]，但僅和傳統的布谷鳥搜索算法進行了對比，對比算法種類較少；JABALLAH等提出了適應布谷鳥搜索算法(SACS)的方案，根據優化過程的進展動態調整控制參數[5]，但算法精度有待提高。②和不同優秀算法融合：張珍珍等提出了融合正弦余弦和種群初始化策略的布谷鳥搜索算法[6]；ABDEL-BASET等提出了CS-GA和GA-CA 等2種算法[7]；ZHAO等將CS算法與ABC算法相結合[8]；李娜等將PSO算法引入布谷鳥搜索算法[9]。不過，上述不同算法融合使改進算法復雜度變高，運算時間花費較大。③算法的應用：謝永盛等提出了一種改進算法，解決了多機器人任務分配和路徑規劃問題[10]，但改進算法對多機器人任務分配及路徑規劃所需能量消耗還存在提升空間；方園園把改進的布谷鳥搜索算法應用于幫助機器人準確定位氣味源[11]，但固定步長的萊維飛行發現策略，得到最優解的質量有所下降。賈政方等引入離散布谷鳥算法對建筑能耗數據進行監測[12]；GARG等提出了一種基于CS算法的最佳掩模生成方法，用于噪聲抑制和語音信號增強[13];過文俊等采用CS算法對支持向量機進行優化，將其引入到財務數據的評估[14]。以上算法一定程度上存在通用性差，不能有效地解決各種實際問題。

可見，上述文獻對于布谷鳥搜索算法的改進策略比較單一，改進算法運行時間消耗、計算精度、整體性能上還存在提升空間。本文提出一種融合多策略改進布谷鳥搜索算法(GSACS),通過對算法參數改進并與其他優秀算法的思想結合，極大地保證改進布谷鳥搜索算法的優化性能。

1 布谷鳥搜索算法

1.1 原理及相關公式

布谷鳥無固定配偶且不會筑巢孵化卵，而是在各種雀形目鳥類的巢中產卵，由這些鳥孵化后代。如果被其他鳥類發現巢穴內不是自己的后代，它們會丟棄這些鳥蛋或者重新搭建新的巢穴。同時，布谷鳥善于模仿其他鳥類的習性，以保護自己及后代不被其他鳥類發現。2009年，文獻[1]基于布谷鳥的產卵寄生行為，提出了3種理想化的規則。

1)每個布谷鳥在特定的時間產了一枚蛋，并轉儲在一個隨機選擇的巢。

2)提供高品質蛋的鳥巢將孵化下一代雛鳥。

3)自然界中其他鳥類的巢穴是有限的，其他鳥類發現不是自己后代的概率為Pa(1≥Pa≥0)。在被發現后，其他鳥類將舍棄巢穴或者丟棄鳥蛋。

根據上述3種理想化規劃建立布谷鳥搜索算法，更新公式如下。

1)全局位置更新[15]

(1)

(2)

式中:μ和ν服從標準正態分布，β=1.5,

(3)

α=α0(Xti-Xb)

(4)

式中:α0=0.01;Xb表示當前最優解。

根據式(1)～(4)，全局搜索公式可以表示為

(5)

2)局部位置更新公式

該階段為偏好隨機游走階段，計算公式為

(6)

1.2 布谷鳥算法實現流程

1)布谷鳥算法各參數值設置并初始化,其中鳥巢個數為m，最大迭代次數為N。

2)計算每個鳥巢的適應度值，找出所對應適應度最優的位置，即當前最優解。

3)保留上次迭代所產生的最優位置，對剩下m-1個位置的鳥巢按照萊維飛行進行位置更新并計算適應度值。

5)按照布谷鳥巢卵發現的概率，對當前位置的布谷鳥蛋進行一輪“發現”。被發現的鳥巢則拋棄，并按照萊維飛行產生新解。

6)在新解中找出適應度最優的解并與當前最優解進行比較，有更優則替換。

7)判斷算法是否達到最大迭代次數N。若達到，輸出當前最優解；否則轉2)。

2 改進布谷鳥搜索算法

2.1 拉丁超立方體采樣初始化種群

經典的布谷鳥搜索算法一般以隨機方式產生初始化種群的位置，但這種采樣方法可能導致種群內個體分布不均勻，故采取拉丁超立方體抽樣方法[17]產生初始種群。拉丁超立方抽樣是基于空間填充技術，即在設計變量空間內的樣本點在每一維上的投影都是均勻分布的。根據拉丁超立方體采樣方法的初始種群位置可以保證整個空間填充和采樣的非重疊，并且可以使種群分布均勻[18]，同時可以在少量樣本點的情況下更加充分地探索整個設計變量空間。種群初始化的具體步驟如下：

1)確定布谷鳥搜索算法種群規模N和維數D；

2)確定變量x的區間為[Ub,Lb]，其中Lb和Ub分別是變量的下界和上界；

3)將變量x的區間[Ub,Lb]劃分為N個相等的子區間；

4)在每一維各個子區間中隨機選取一個點；

食管癌 吞咽食物有遲緩、滯留或輕微哽噎感，可自行消退，數日后又可出現，反復發作，逐漸加重?；蛟谕萄蕰r，總感覺胸骨有定位疼痛。平時感覺食管內有異物且與進食無關，持續存在，喝水及咽食物均不能使之消失。

5)將抽取的每一維的點組合形成布谷鳥搜索的初始種群。

2.2 發現概率改進

發現概率保證了將最優解帶到下一代以構造新的解的概率，同時發現概率用于均衡隨機搜索和局部搜索之間的關系[19]?；镜牟脊萨B搜索算法采用固定發現概率Pa=0.25。Pa為定值時，不能根據解的好壞進行動態調整。本文采取發現概率Pa的動態調整機制，Pa隨著迭代次數增長動態變化。由于雙曲正切函數具有良好的性能[20]，故將雙曲正切函數引入到發現概率中，對其進行動態調整。改進的發現概率公式為

Pa=tanh(0.75log(exp(-T/t)+

exp(T/t)))-0.25

(7)

發現概率隨著迭代次數變化如圖1所示。

圖1 改進的發現概率變化曲線

2.3 局部搜索公式改進

2017年,TANYILDIZI提出黃金正弦優化算法(golden sine algorithm,Golden-SA)[21]。由于該算法在收斂速度、求解精度方面表現優秀，被廣泛應用并結合到不同的算法中。本文將黃金正弦優化算法結合到局部搜索的偏好游走公式中，即在每次算法迭代的后期對更新位置進行黃金正弦操作；并將黃金分割數添加到位置更新公式中，使搜索范圍更加精準，同時有效地克服局部最優。算法中的參數r1和r2用于均衡位置迭代更新的距離和方向，合理地指引布谷鳥個體趨向于更好的個體，使布谷鳥之間的信息互通更有效。改進后的偏好游走位置更新公式為

(8)

3 仿真實驗

3.1 仿真實驗設計

選取適當的測試函數，通過將本文方法與布谷鳥搜索算法(CS)、自適應布谷鳥搜索算法(ASCSA)、蝙蝠算法(BAT)及螢火蟲算法(FPA)進行對比，可以全面有效地測試GSACS算法的優化性能。

選取6個基準測試函數，在Matlab上進行仿真實驗。其中f1(x)為Ackley函數,可有效檢測算法的全局收斂速度;f2(x)是Rastrign函數,用于檢測算法在求解規律中的實用性;f3(x)是Griewank函數,是檢測算法跳出局部最優性能的;f4(x)為Sum Squares函數,可以檢測算法的收斂性，但比Ackley函數更平滑;f5(x)為Schwefels 2.2函數,是連續的、平滑多峰函數，該函數有大量局部極值區域；f6(x)為Goldstein&Price函數，是常見的多模態基準測試函數，有多個局部極小值。6種測試函數如表1所示。

表 1 測試函數

實驗環境如下：處理器為AMD Ryzen 55500U with Radeon Graphics 2.10 GHzb; 系統版本為Windows 10家庭中文版;運行內存為16.0 GiB; 操作系統為64位操作系統, 基于x64的處理器;編程環境為MatlabR2020b。

CS算法、ASCSA、BAT算法、FPA算法種群數目為25，迭代次數1 000次，各算法的其他參數如表2所示。

表 2 算法參數設置

3.2 實驗結果及分析

算法的收斂曲線直觀地顯示了算法的收斂速度和收斂精度。圖2是上述5種算法在6個測試函數上的適應度值對比圖。

(a)Ackley函數

從圖2(a)可以看出，GSACS的全局收斂速度比其他同類算法更快;圖2(b)驗證了改進算法的適應性能優于其他4種算法;圖2(c)用的測試函數顯示了算法跳出局部搜索的能力，從收斂曲線可以看出GSACS算法能有效的跳出局部搜索;圖2(d)為測試收斂性能的函數，展示不同算法的收斂性能; 圖2(e)、(f)為多模態測試函數，顯示出GSACS算法跳出多個局部搜索范圍的能力。

比較算法求解精度，用5種算法分別以50維和100維對每個測試函數獨立分析，記錄其標準差、平均值、最大值、最小值，結果如表3～8所示。

表 3 Ackley函數仿真結果

表 4 Rastrign函數仿真結果

表 5 Griewank函數仿真結果

表 6 Sum Squares函數仿真結果

表 7 Schwefel′s Problem 2.2函數仿真結果

表 8 Goldstein&Price函數仿真結果

從表3～8可以看出，在50維、100維2種維數情況下，與其他4種算法比較，GSACS算法具有更優質的解，其他4種算法的求解精度和跳出局部搜索的能力略差于GSACS算法。

對于基準測試函數Ackley，各算法的性能表現優劣依次為：在50維下標準差評估指標的排序GASCS、CS、FPA、BAT、ASCSA。在100維下標準差評估指標的排序GSACS、FPA、BAT、CS、ASCSA。在基準測試函數Rastrign，50維情況下，GSACS、CS、ASCSA的標準差都相同；均值指標最好的為GSACS算法，最差的為BAT算法。100維情況下，各算法標準差指標的優劣排序為GASCS、ASCSA、CS、FPA、BAT。

對于不同維度Griewank函數各評估指標的表現，GSACS算法表現最好，BAT算法次之。在單模態基準測試函數Sum Squares和Schwefel′s Problem 2.2函數上，GSACS算法的求解結果標準差、最大值、平均值優于同類型算法；在多模態基準測試函數Goldstein&Price函數上，GSACS算法的求解精度和穩定性高于其他算法，GSACS的尋優能力強。

在不同維度下6個基準測試函數上的仿真結果表明，與CS算法、ASCSA算法、BAT算法、FPA算法相比，GSACS算法的性能更出色。在求解不同難度的優化問題上，該算法求解精度高、魯棒性強。

4 結 語

針對布谷鳥搜索算法收斂速度慢且易陷入局部缺陷的問題，用拉丁超立方體初始化策略更新初始種群位置，基于雙曲正切的動態發現概率，并結合黃金正弦算法的偏好隨機游走位置更新算法公式。數值模擬實驗結果表明，GSACS算法具有更好的性能，可以有效克服收斂速度遲緩和陷入局部最佳的缺點。同時，GSACS算法在理論上對基本的布谷鳥搜索算法進行改進和完善，并從其他高效能算法上獲得啟發，尋求不同算法之間的結合。GSACS算法可應用到醫學、電子商務、金融等多個領域。