劉 青，賀興時，顧佳鑫

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

0 引 言

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

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

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

1 布谷鳥搜索算法

1.1 原理及相關(guān)公式

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

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

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

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

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

1)全局位置更新[15]

(1)

(2)

式中:μ和ν服從標(biāo)準(zhǔn)正態(tài)分布，β=1.5,

(3)

α=α0(Xti-Xb)

(4)

式中:α0=0.01;Xb表示當(dāng)前最優(yōu)解。

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

(5)

2)局部位置更新公式

該階段為偏好隨機(jī)游走階段，計算公式為

(6)

1.2 布谷鳥算法實現(xiàn)流程

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

2)計算每個鳥巢的適應(yīng)度值，找出所對應(yīng)適應(yīng)度最優(yōu)的位置，即當(dāng)前最優(yōu)解。

3)保留上次迭代所產(chǎn)生的最優(yōu)位置，對剩下m-1個位置的鳥巢按照萊維飛行進(jìn)行位置更新并計算適應(yīng)度值。

5)按照布谷鳥巢卵發(fā)現(xiàn)的概率，對當(dāng)前位置的布谷鳥蛋進(jìn)行一輪“發(fā)現(xiàn)”。被發(fā)現(xiàn)的鳥巢則拋棄，并按照萊維飛行產(chǎn)生新解。

6)在新解中找出適應(yīng)度最優(yōu)的解并與當(dāng)前最優(yōu)解進(jìn)行比較，有更優(yōu)則替換。

7)判斷算法是否達(dá)到最大迭代次數(shù)N。若達(dá)到，輸出當(dāng)前最優(yōu)解；否則轉(zhuǎn)2)。

2 改進(jìn)布谷鳥搜索算法

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

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

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

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

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

4)在每一維各個子區(qū)間中隨機(jī)選取一個點；

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

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

2.2 發(fā)現(xiàn)概率改進(jìn)

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

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

exp(T/t)))-0.25

(7)

發(fā)現(xiàn)概率隨著迭代次數(shù)變化如圖1所示。

圖1 改進(jìn)的發(fā)現(xiàn)概率變化曲線

2.3 局部搜索公式改進(jìn)

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

(8)

3 仿真實驗

3.1 仿真實驗設(shè)計

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

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

表 1 測試函數(shù)

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

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

表 2 算法參數(shù)設(shè)置

3.2 實驗結(jié)果及分析

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

(a)Ackley函數(shù)

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

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

表 3 Ackley函數(shù)仿真結(jié)果

表 4 Rastrign函數(shù)仿真結(jié)果

表 5 Griewank函數(shù)仿真結(jié)果

表 6 Sum Squares函數(shù)仿真結(jié)果

表 7 Schwefel′s Problem 2.2函數(shù)仿真結(jié)果

表 8 Goldstein&Price函數(shù)仿真結(jié)果

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

對于基準(zhǔn)測試函數(shù)Ackley，各算法的性能表現(xiàn)優(yōu)劣依次為：在50維下標(biāo)準(zhǔn)差評估指標(biāo)的排序GASCS、CS、FPA、BAT、ASCSA。在100維下標(biāo)準(zhǔn)差評估指標(biāo)的排序GSACS、FPA、BAT、CS、ASCSA。在基準(zhǔn)測試函數(shù)Rastrign，50維情況下，GSACS、CS、ASCSA的標(biāo)準(zhǔn)差都相同；均值指標(biāo)最好的為GSACS算法，最差的為BAT算法。100維情況下，各算法標(biāo)準(zhǔn)差指標(biāo)的優(yōu)劣排序為GASCS、ASCSA、CS、FPA、BAT。

對于不同維度Griewank函數(shù)各評估指標(biāo)的表現(xiàn)，GSACS算法表現(xiàn)最好，BAT算法次之。在單模態(tài)基準(zhǔn)測試函數(shù)Sum Squares和Schwefel′s Problem 2.2函數(shù)上，GSACS算法的求解結(jié)果標(biāo)準(zhǔn)差、最大值、平均值優(yōu)于同類型算法；在多模態(tài)基準(zhǔn)測試函數(shù)Goldstein&Price函數(shù)上，GSACS算法的求解精度和穩(wěn)定性高于其他算法，GSACS的尋優(yōu)能力強。

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

4 結(jié) 語

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