融合正弦余弦和種群初始化策略的布谷鳥算法

張珍珍，賀興時，于青林，楊新社

(1.西安工程大學(xué) 理學(xué)院,陜西 西安 710048；2.湯普森大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院,加拿大 甘露 V2C0C8；3.密德薩斯大學(xué) 科學(xué)與技術(shù)學(xué)院,英國 倫敦 NW4 4BT)

0 引 言

元啟發(fā)式算法包括花授粉算法[1](FPA)、蝙蝠算法[2](BA)、鯨魚優(yōu)化算法[3](WOA)、蟻群算法[4](ACO)、粒子群優(yōu)化算法[5](PSO)、螢火蟲算法[6](FA)等。這些生物算法仿照動物行為特征，靈活高效地解決了許多復(fù)雜優(yōu)化問題。

布谷鳥搜索算法[7](cuckoo search，CS)廣泛應(yīng)用于智能機器人[8]、水利工程[9]、物流配送[10]、電力設(shè)計[11]、優(yōu)化聚類[12]、神經(jīng)網(wǎng)絡(luò)[13]等領(lǐng)域，但布谷鳥算法仍存在尋優(yōu)解結(jié)果不夠精確，求解速度不夠快和容易取得當(dāng)前最優(yōu)解而無法繼續(xù)迭代尋找全局最優(yōu)解等方面的問題。為了改善布谷鳥算法存在的這些問題與不足，人們對布谷鳥算法做出了相應(yīng)的改進。2013年，OUYANG等提出了離散布谷鳥搜索算法(DCS)，并將其應(yīng)用到經(jīng)典問題旅行商中[14]；2018年,BOUSHAKI等提出了一種新的量子混沌CS算法(QCCS)，將混沌映射及量子技術(shù)與布谷鳥算法結(jié)合[15]；2019年，宋慶慶等將擬牛頓算法和布谷鳥算法結(jié)合，建立了一種擬牛頓布谷鳥混合算法[16]；2020年，王曉華等改進了布谷鳥算法的發(fā)現(xiàn)概率步長[17]。

針對布谷鳥優(yōu)化算法在處理復(fù)雜函數(shù)時，尋優(yōu)結(jié)果不精確、尋優(yōu)速度不高和容易陷入局部最優(yōu)解等問題，本文提出了融合正弦余弦和種群初始化策略的布谷鳥算法(DCCS)。首先，在布谷鳥初始種群產(chǎn)生環(huán)節(jié)引用一種結(jié)合均勻化與隨機化的策略，以半均勻、半隨機的方式產(chǎn)生初始種群，有效地減少隨機誤差，提高了算法尋優(yōu)效率。其次，分別在全局搜索和下一步局部搜索中引入了正弦余弦算子，充分靈活開發(fā)上一代鳥窩位置作用，克服算法易陷入局部最優(yōu)的缺陷，提高算法尋優(yōu)搜索能力。最后，引入了指數(shù)型動態(tài)概率p代替固定概率，用于自適應(yīng)平衡算法的2個階段。實驗結(jié)果表明，DCCS算法提高了結(jié)果精度和運算效率，在一定程度上具有更好的尋優(yōu)性能。

1 布谷鳥優(yōu)化算法

基本布谷鳥算法包括萊維飛行和隨機偏好游走過程，萊維飛行位置更新公式[18]為

(1)

(2)

2 改進的布谷鳥優(yōu)化算法

2.1 種群初始化策略

布谷鳥算法的初始種群是隨機分布產(chǎn)生的。這種隨機分布方式會致使尋優(yōu)結(jié)果含有隨機誤差，在一定程度上影響了布谷鳥算法的尋優(yōu)精度; 并且因為種群分布隨機混亂，沒有規(guī)律地分布在解區(qū)間，也在一定程度上影響了布谷鳥算法的尋優(yōu)速度。為了解決因為布谷鳥初始種群完全隨機分布而對布谷鳥算法性能的影響問題，在布谷鳥初始種群產(chǎn)生環(huán)節(jié)引用一種結(jié)合均勻化與隨機化[19]的策略。以半均勻、半隨機的方式產(chǎn)生初始種群：一方面保證均勻化，將布谷鳥算法的解變量分布區(qū)間平均分割，有規(guī)律地進行迭代搜索，幫助提高算法的尋優(yōu)速度和尋優(yōu)精度；另一方面保證隨機化，隨機地選取被劃分區(qū)間和在被劃分區(qū)間中選取隨機值，保證了算法的初始隨機性。種群初始化的具體方法[19]如下:

1) 輸入種群規(guī)模n，決策向量維度k，各決策變量xj(j∈{1，2，…，n})的區(qū)間[aj,bj]。

2) forj=1,2,…,k。

3) Δj={[aj,aj+Δj],(aj+Δj,aj+2Δj],…,(aj+(n-2)Δj,aj+(n-1)Δj],(aj+(n-1)Δj,bj]}。

4) fori=1,2,…,n。

6) 更新集合Δj，從集合Δj中刪除在5)中已選中的子區(qū)間。

7) end for。

8) end for。

9) 輸出多樣性的初始種群。

通過對布谷鳥算法采取基于均勻化和隨機化相結(jié)合的種群初始化方式，在保證算法初始種群隨機性的前提下，獲得了一組在決策區(qū)間均勻分布的初始解，減少了算法因為初始解分布完全隨機而降低的運算速度和產(chǎn)生的隨機誤差，提高了算法的運算效率和尋優(yōu)速度。

2.2 融合正余弦算子

在布谷鳥算法中，上一代鳥窩位置發(fā)揮重要作用，不斷引導(dǎo)算法向最優(yōu)解靠近。但在布谷鳥算法的萊維飛行階段和偏好隨機游動階段的更新公式中，都將該位置固定，這種更新方式容易造成算法在迭代過程中取得局部最優(yōu)而非全局最優(yōu)，致使種群出現(xiàn)停止搜索的現(xiàn)象，無法獲得全局最優(yōu)解。為了克服這一缺陷，平衡布谷鳥算法的全局搜索和局部搜索，在布谷鳥算法的全局搜索和局部搜索階段的上一代鳥窩位置處引入正弦和余弦算子[20]。通過正余弦算子隨迭代次數(shù)的變化，靈活調(diào)整布谷鳥鳥窩的位置：使其前期保持靈活性，進行全局搜索；后期布谷鳥個體趨于局部開發(fā)，進行精細(xì)搜索，使算法取得全局最優(yōu)解。融合正余弦算子后的全局搜索公式和局部搜索公式分別更新為：

(3)

(4)

r1sinr2、r1cosr2共同控制算法進行全局搜索和局部搜索。當(dāng)r1sinr2、r1cosr2的值>1或<-1時，上一代鳥窩位置的慣性權(quán)重較大，有利于擴大搜索范圍，開發(fā)不同區(qū)域，提高布谷鳥算法的全局開發(fā)能力，避免算法只取得當(dāng)前最優(yōu)解而無法繼續(xù)迭代尋找全局最優(yōu)解; 當(dāng)r1sinr2、r1cosr2的值在1和-1之間時，上一代鳥窩位置的慣性權(quán)重系數(shù)取值較小，不再進行大范圍搜索，以免跳出最優(yōu)范圍，而是在最優(yōu)解附近進行精細(xì)搜索，直至尋找到全局最優(yōu)解。將正余弦算子引入到布谷鳥算法中，使上一代鳥窩位置具有靈活性，提高算法性能。

2.3 指數(shù)型動態(tài)發(fā)現(xiàn)概率

在布谷鳥算法中，用來控制全局搜索和偏好隨機游走過程的概率為固定數(shù)值P=0.25。概率P是布谷鳥算法轉(zhuǎn)換萊維飛行階段和偏好游走階段的重要參數(shù)，固定概率值不利于靈活轉(zhuǎn)換算法的2個階段，無法隨迭代進程及時調(diào)整算法的全局探索和局部開發(fā)進程。本文引入了指數(shù)型動態(tài)切換概率P代替固定概率，使概率P隨著迭代次數(shù)的變化自適應(yīng)調(diào)整算法的2個階段，改善因固定概率P而影響的算法性能。動態(tài)概率公式如下：

(5)

式中:Pmin是當(dāng)前概率的最小獲得值;Pmax是當(dāng)前概率的最大獲得值;t是當(dāng)前迭代的次數(shù);tmax是迭代的次數(shù)最大值;β(0,1)是定義在(0，1)的貝塔分布;φ是極小的數(shù)，用于調(diào)整發(fā)現(xiàn)概率和期望值之間的偏差程度。指數(shù)型動態(tài)概率變化圖如圖1所示。

圖 1 指數(shù)型動態(tài)概率變化

由圖1可以看出，提出的概率P是隨著迭代過程自適應(yīng)指數(shù)型增大的動態(tài)發(fā)現(xiàn)概率。在布谷鳥算法搜索前期，概率P的取值在0.2左右，較小的概率取值在控制全局搜索和局部搜索的切換過程中，控制算法在搜索前期多進行大范圍的全局搜索，不斷使算法結(jié)果跳出當(dāng)前局部最優(yōu)解，避免算法在一開始就陷入局部最優(yōu)而停止搜索。隨著搜索過程的不斷進行，概率P的取值也在不斷增大，直至在算法搜索后期，概率P的取值超過了0.5，較大的概率取值將控制算法在搜索進程后期時不再進行大范圍搜索，而是在靠近全局最優(yōu)解的小范圍內(nèi)進行細(xì)致搜索，直至尋找到最終全局最優(yōu)解。通過在布谷鳥算法中引入指數(shù)型動態(tài)發(fā)現(xiàn)概率，概率P與搜索過程動態(tài)聯(lián)系在一起，自適應(yīng)平衡算法的2個階段進程，提高了算法的整體尋優(yōu)性能

2.4 DCCS算法執(zhí)行步驟

DCCS算法執(zhí)行步驟如下：

1) 設(shè)置布谷鳥算法各個參數(shù)值：m為鳥窩個數(shù)，n為維數(shù)，N為迭代次數(shù)最大取值。依照式(5)設(shè)置發(fā)現(xiàn)概率P，計算m個鳥窩的適應(yīng)度值。

2) 初始化種群，生成均勻化與隨機化相結(jié)合的初始種群。

3) 按照式(3)更新布谷鳥鳥窩位置，并計算每個更新解的適應(yīng)度值。當(dāng)更新解的適應(yīng)度值更高時，用適應(yīng)度更高的解替換舊的解；否則，仍使用舊的解。

4) 按照式(5)的動態(tài)發(fā)現(xiàn)概率P剔除部分解，并用改進后的式(4)產(chǎn)生新解。新解數(shù)量與剔除的部分解相同，進行局部搜索。

5) 計算m個鳥窩的適應(yīng)度值，得當(dāng)前最優(yōu)解。

6) 判斷算法是否達(dá)到迭代次數(shù)N。若達(dá)到，輸出當(dāng)前最優(yōu)解; 若沒達(dá)到，重復(fù)2)～6)。

3 仿真實驗

為了驗證融合正弦余弦和種群初始化策略的布谷鳥算法(DCCS)的尋優(yōu)性能，選取了6個不同難度的函數(shù)，分別測試DCCS算法的收斂速度、收斂精度，同時與ASCSA、CS、BA、FPA等4種算法進行對比分析。6種測試函數(shù)如表1所示。

表 1 測試函數(shù)

3.1 測試環(huán)境及算法參數(shù)

實驗環(huán)境如下：CPU為i5-4288U 2.60 GHz，運行內(nèi)存4 GiB;操作系統(tǒng)Windows10;編程環(huán)境Matlab r2020a。DCCS算法及ASCSA、CS、BA、FPA算法參數(shù)設(shè)置如表2所示。

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

3.2 算法求解精度比較

表3～8分別給出了5種算法對測試函數(shù)f1(x)～f6(x)，在維數(shù)n為10、100條件下的方差、最優(yōu)值、平均值及最差值等4個指標(biāo)的測試結(jié)果。其中，f1(x)函數(shù)是典型的非線性多模態(tài)函數(shù)，極小值個數(shù)與維數(shù)成正比且起伏不定。從表3中可以看出：DCCS 已經(jīng)展現(xiàn)出良好的全局性能,取得了一個全局最優(yōu)的值,而其他4種算法后期都已經(jīng)陷入局部最優(yōu)。f2(x)～f3(x)為復(fù)雜多峰函數(shù)，在整個解空間內(nèi)存在多個極值點，可以考察該算法是否具備優(yōu)秀的尋優(yōu)能力，能否在取得當(dāng)前最優(yōu)值后繼續(xù)迭代得到全局最優(yōu)值。由表4～5可以看出：ASCSA等4種算法都陷入了不同程度的局部最優(yōu)，并未繼續(xù)尋找到全局最優(yōu)解0，而DCCS算法在各個維度條件下都取得了相對應(yīng)函數(shù)的最優(yōu)求解，通過對比優(yōu)勢突出。f4(x)～f6(x)為單峰函數(shù)，在整個解空間內(nèi)只有一個極值點。由表6～8可以看出：DCCS在處理單峰函數(shù)時仍能取得全局最優(yōu)解，表現(xiàn)出良好的穩(wěn)定性。綜上所述，與其他4種算法相比，DCCS算法尋找全局最優(yōu)解優(yōu)勢更明顯，不易陷入局部最優(yōu)，并且在高維條件下結(jié)果也未改變，尋優(yōu)性能穩(wěn)定。

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

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

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

表 6 f4(x)函數(shù)仿真結(jié)果

表 7 f5(x)函數(shù)仿真結(jié)果

表 8 f6(x)函數(shù)仿真結(jié)果

3.3 算法收斂性

圖2～7分別是改進后的布谷鳥算法與其他4種算法在6種函數(shù)下的收斂曲線圖。其中f1(x)～f3(x)為多峰函數(shù)，在整個解空間存在不止一個極值點，可以考察算法的尋優(yōu)能力，能否在取得當(dāng)前最優(yōu)值后繼續(xù)迭代得到全局最優(yōu)值。由圖2、4可以看出：在其他4個算法迭代后期都未能取得全局最優(yōu)時， DCCS算法在50次迭代左右就取得最優(yōu)值。由圖3可以看出：BA算法陷入了局部最優(yōu)，其他算法分別在200至800次后才取得最優(yōu)值，而DCCS算法在一開始就達(dá)到了全局收斂，取得了最優(yōu)值。f4(x)～f6(x)為簡單單峰函數(shù)，在整個解空間只有唯一一個極值點，可以考察比較算法的尋優(yōu)速度。由圖5～7可以看出：ASCSA等4種算法有時在100次迭代以后搜索到最優(yōu)求解，或者在1 000次迭代結(jié)束后都未搜索到最優(yōu)求解，而DCCS算法在搜索前期卻快速搜索得到各個函數(shù)的最優(yōu)求解，收斂速度優(yōu)勢明顯。綜上所述，與ASCSA等4種算法對6種函數(shù)的搜索結(jié)果相比較，DCCS算法具有相對較高的尋優(yōu)速度，有效地改善了布谷鳥算法收斂速度慢的不足。

圖 2 Rastrigin函數(shù)收斂曲線Fig.2 Convergence curve of Rastrigin function

圖 3 Griewank函數(shù)收斂曲線Fig.3 Convergence curve of Griewank function

圖 4 Alpine函數(shù)收斂曲線Fig.4 Convergence curve of Alpine function

圖 5 Sphere函數(shù)收斂曲線Fig.5 Convergence curve of Sphere function

圖 6 Sum square函數(shù)收斂曲線Fig.6 Convergence curve of Sum square function

圖 7 Schwefel函數(shù)收斂曲線Fig.7 Convergence curve of Schwefel function

4 結(jié) 語

本文提出了融合正弦余弦和種群初始化策略的布谷鳥算法。著眼于對布谷鳥算法進行整體優(yōu)化，充分協(xié)調(diào)利用種群初始化策略，正余弦算子和指數(shù)型動態(tài)概率P三者之間的關(guān)系。在算法初始階段，對布谷鳥初始種群利用結(jié)合均勻化與隨機化的策略，在保證種群隨機性的前提下，使初始種群隨機分布在解區(qū)間; 在算法的萊維飛行階段和偏好游走階段，引入變化范圍在[-1,1]的正余弦算子，靈活調(diào)整上一代鳥窩位置;通過引入指數(shù)型動態(tài)概率P，確保P在整個迭代階段保持在[0.15,0.55]區(qū)間的動態(tài)變化狀態(tài)，動態(tài)平衡算法的2個階段。3個策略之間相互作用、相互聯(lián)系，共同作用于布谷鳥算法。與另外4種算法相比較并通過6個測試函數(shù)的仿真結(jié)果表明：融合正弦余弦和種群初始化策略的布谷鳥算法，在一定程度上提高了算法性能，加快了尋優(yōu)速度，提高了尋優(yōu)解的數(shù)量級精度。