基于布谷鳥迭代更新策略的多重優(yōu)化算法

丁希成，王紅軍

國防科技大學(xué) 電子對抗學(xué)院，合肥230000

群智能算法作為新興智能優(yōu)化算法之一，由于其穩(wěn)定性、并行性、魯棒性和自組織性等特點而被廣泛地應(yīng)用于計算機、農(nóng)業(yè)和商業(yè)等領(lǐng)域來實現(xiàn)求解最優(yōu)化。自1989年Beni等在元胞機器人系統(tǒng)中首次提出了群智能的概念[1]，目前被廣泛認(rèn)可的群智能算法有遺傳算法（genetic algorithm，GA）、蟻群算法（ant colony optimization algorithm，ACOA）、粒子群算法（particle swarm optimization algorithm，PSOA）、蛙跳算法（shuffled frog leading algorithm，SFLA）、布谷鳥算法（cuckoo search algorithm，CSA）和灰狼算法（grey wolf optimizationalgorithm，GWOA）等。

布谷鳥算法作為一種新型的群智能算法，自2009年Yang 等[2]提出以來，由于其參數(shù)少、全局搜索能力強等特點受到眾多學(xué)者的青睞，被應(yīng)用于各類最優(yōu)化問題的求解[3-6]，布谷鳥算法的核心優(yōu)勢就是采用萊維（Levy）飛行來產(chǎn)生運動軌跡，其高度隨機的飛行機制使得搜索可以快速地在迭代前期遍布解空間，種群具有更好的多樣性，但是也導(dǎo)致算法在后期針對局部的開發(fā)能力較差，收斂速度較慢。因此，近年來眾多學(xué)者依據(jù)其特性對布谷鳥原始算法進行了如下三個方面的改進：參數(shù)的自適應(yīng)調(diào)整，算子修改、增加和替換，以及融合其他算法。

文獻[7]根據(jù)種群每次迭代后適應(yīng)度的差別分為三個階層，每個階層采用不同的飛行步長，并引入隨機偏移算子動態(tài)調(diào)整迭代方程，但算法復(fù)雜度略高。文獻[8]將多種群粒子群算法結(jié)合布谷鳥算法，并采用中位數(shù)聚類的方法將相近層次的種群聚類以加快收斂速度，但對多峰函數(shù)的搜索精度仍有待加強。文獻[9]根據(jù)種群歷史最優(yōu)適應(yīng)度和自身最優(yōu)適應(yīng)度按比例減少種群數(shù)量，提出了一種參數(shù)自適應(yīng)的布谷鳥算法，但會導(dǎo)致后期搜索能力下降。文獻[10]通過改進布谷鳥搜索的步長和發(fā)現(xiàn)外來物種的概率，提高了粒子濾波算法中粒子的多樣性，保證了估計精度。文獻[11]將布谷鳥算法融合進粒子群算法，并改進了算法的拓撲結(jié)構(gòu)，平衡了算法的全局搜索能力和局部開發(fā)能力，但在后期小范圍內(nèi)的多峰情況難以收斂到最優(yōu)值。文獻[12]將混沌映射引入布谷鳥算法的種群初始化中，提高了尋優(yōu)的速度和精度。文獻[13]混合布谷鳥算法和遺傳算法，引入交叉變異策略，增強種群的多樣性，但收斂精度仍有待提高。文獻[14]將改進的自適應(yīng)布谷鳥算法應(yīng)用于分布式無人機部署上，取得良好的效果，但在搜索后期的局部開發(fā)能力都仍需進一步加強。文獻[15]將tent映射引入灰狼算法，并借鑒粒子群算法思想，提出了混合灰狼優(yōu)化算法，進一步提高了灰狼算法的收斂速度和精度，但跳出局部最小值的能力有待加強。文獻[16]通過自適應(yīng)策略調(diào)整動態(tài)步長和發(fā)現(xiàn)概率，提高了布谷鳥算法收斂速度和精度，但同樣存在陷入局部極值問題。文獻[17]利用多階段動態(tài)擾動策略增加了種群的多樣性和粒子位置的靈活性，但無法保證初始種群的合理性。

本文基于CS算法和GWO算法的優(yōu)勢，從布谷鳥算法的迭代更新策略出發(fā)，引入粒子群思想，并利用灰狼算法的狩獵思想，在搜索后期進行小范圍擾動式搜索，提高算法后期小范圍擾動，促使算法在保證搜索廣度的前提下，利用粒子間學(xué)習(xí)增加其種群內(nèi)自我認(rèn)知和種群間社會交流的能力。同時引入tent 映射方法使初始種群更均勻地遍布解空間，防止搜索過程陷入局部最優(yōu)，提高種群收斂速度。同時，針對布谷鳥參數(shù)固定的弊端，對步長控制參數(shù)提出對數(shù)自適應(yīng)改進策略，提高算法的全局搜索能力和局部開發(fā)能力。

1 經(jīng)典布谷鳥算法描述

布谷鳥算法是一種啟發(fā)式群智能優(yōu)化算法，通過模擬自然界布谷鳥尋找鳥巢繁殖后代的行為，總結(jié)其規(guī)律運用到最優(yōu)化問題解決上來。布谷鳥算法在模擬尋找鳥巢的過程需要遵循以下三條假設(shè)規(guī)則：

（1）每只布谷鳥每次只孵化一枚鳥蛋，并選擇一個隨機鳥巢進行孵化。

（2）在所有寄生巢中選擇最好的寄生巢保留至下一代。

（3）在布谷鳥飛行過程中，可利用的鳥巢總數(shù)n固定，一個鳥巢中布谷鳥鳥蛋被主人發(fā)現(xiàn)并拋棄的概率為Pa∈[0,1]。

在布谷鳥原始算法中，布谷鳥的種群規(guī)模代表解決方法的數(shù)量，通過Levy 飛行共同尋找搜索空間內(nèi)的最優(yōu)鳥巢。鳥巢的位置更新方程為：

其中，α為步長縮放因子，通常取固定常數(shù)0.01；⊕為點對點的乘法；萊維飛行通常采用Mantegna算法實現(xiàn)，其步長s表示為：

其中，s為萊維飛行的步長，β取1.5，u、v為服從正態(tài)分布的隨機數(shù)：

鳥巢位置通過萊維飛行更新后，判斷隨機數(shù)r∈[0,1]和Pa的大小，取Pa=0.25,則有：若r＞Pa，則按照式（4）更新，否則不更新鳥巢位置。

2 算法改進

2.1 參數(shù)α 的對數(shù)自適應(yīng)改進

布谷鳥算法主要由萊維飛行隨機搜索和拋棄原有鳥巢隨機替代兩部分組成，并結(jié)合擇優(yōu)選擇的原則迭代更新。根據(jù)式（2），參數(shù)α對于萊維飛行的步長控制具有重大的影響。

在尋優(yōu)算法中，通常希望在搜索前期，通過較大的步長以擴大搜索范圍，增加種群多樣性和全局探索能力，在搜索后期，將步長穩(wěn)定在較小值以提高局部搜索能力。但在原始布谷鳥算法中，參數(shù)α通常被設(shè)置為常數(shù)0.01，無法滿足在不同搜索階段的搜索需求，為此，本文提出了一種針對參數(shù)α的對數(shù)自適應(yīng)改進，其計算公式為：

其中，maxgen為最大迭代次數(shù)，t為當(dāng)前迭代次數(shù)。使參數(shù)α隨著算法搜素進程動態(tài)從0.5下降到0.001，相比于固定常數(shù)，前期更大的搜索步長和后期更小的搜索步長，有利于提高收斂速度和搜索精度。

2.2 Skew tent映射初始化種群

布谷鳥算法在求解函數(shù)優(yōu)化的問題時，通常采用隨機初始化種群的方法，這種方法難以確保初始參數(shù)均勻遍布解空間，會導(dǎo)致算法的收斂速度減慢，同時也容易陷入局部最優(yōu)解。而混沌運動因為具有隨機性、遍歷性和規(guī)律性等特點，可以使初始種群更均勻地遍布解空間，目前已廣泛地在粒子群、灰狼、人工蜂群等群智能算法中以提高算法的搜索效率。

本文采用Skew tent 混沌映射，相對于目前普遍使用的logistic映射，減少了在邊緣區(qū)域分布率高的問題，其均勻性更好。

Skew tent算法公式為：

其中，φ∈[0,1]，取φ=0.5，x∈[0,1]。

2.3 迭代方程更新

經(jīng)典布谷鳥算法由于其飛行軌跡的高度隨機性，在迭代后期收斂的速度和精度效果均不夠理想，由式（2）～（4）可知，布谷鳥算法每次迭代采用的是隨機遷移和貪婪策略，種群中始終只保持全局最優(yōu)個體作為引導(dǎo)者，這容易導(dǎo)致算法對其他優(yōu)異解的區(qū)域探索能力下降。為了增強搜索的活力和效率，借鑒粒子群算法思想，加入“社會學(xué)習(xí)部分”和“自我學(xué)習(xí)部分”，其改進的位置更新公式為：

其中，stepi為萊維飛行的軌跡，ezbest為個體歷史最優(yōu)解，可以增強位置更新的自我學(xué)習(xí)的能力。egbest為全局歷史最優(yōu)解，egsecond為全局歷史次優(yōu)解，可以增強位置更新的社會學(xué)習(xí)能力。r1、r2、r3為學(xué)習(xí)因子。其中r1為針對個體歷史最優(yōu)解的學(xué)習(xí)因子，表示粒子的自我學(xué)習(xí)能力；r2和r3分別為針對全局歷史最優(yōu)解和全局歷史次優(yōu)解的學(xué)習(xí)因子，表示粒子的社會學(xué)習(xí)能力。三者均取[0,1]區(qū)間的隨機數(shù)。

2.4 灰狼算法變異種群

為了進一步提高算法的收斂速度和局部搜索能力，本文借鑒灰狼算法中的α、β、δ狼狩獵機制，即領(lǐng)袖狼號召群體盡快靠近其周圍達到快速種群快速收斂的目的?；依侨后w中的最優(yōu)解為α，次最優(yōu)解為β，第三最優(yōu)解為δ，其他解均稱為w，每次搜索過程中通過α、β、δ狼作為領(lǐng)袖狼包圍獵物，其中獵物標(biāo)記為頭狼∝所在的位置，本文選用每次布谷鳥算法尋優(yōu)后的全局歷史最優(yōu)解，全局歷史次優(yōu)解，個體歷史最優(yōu)解分別作為α、β、δ狼，依據(jù)灰狼算法對種群內(nèi)其他解進行變異，灰狼算法的數(shù)學(xué)模型為：

其中，Xi(t+1) 為第i個種群的w灰狼個體在t+1 次迭代時的位置，Xi,p(t)為第i個種群的領(lǐng)袖狼的位置，A×D為w狼包圍獵物所移動的步長，A和C分別定義為：

其中，r4和r5分別為0到1之間的隨機數(shù)，A為距離收斂參數(shù)，隨著迭代次數(shù)控制步長線性遞減至0，C為0到2之間的隨機數(shù)。

綜合領(lǐng)袖α、β、δ狼，分別得到Xi,α、Xi,β和Xi,δ，并代入本文的算法：

由式可以分別計算出三頭領(lǐng)袖狼與ω狼位置距離參數(shù)，并通過式綜合判斷w狼的變異方向，確定變異后的位置。變異按照個體選取率確定種群的變異概率pc。

由灰狼算法原理可知，變異后的個體比變異前更接近領(lǐng)袖狼位置，可以使種群快速向領(lǐng)袖狼位置，即全局歷史最優(yōu)解，全局歷史次優(yōu)解和個體歷史最優(yōu)解逼近，達到快速收斂的目的。同時三頭領(lǐng)袖狼也依然可以以ω狼的身份參與狼群的尋優(yōu)，這是由于布谷鳥算法的貪婪策略，并不會使優(yōu)異解退化，同時可以增加最優(yōu)解附近的擾動，有利于提高布谷鳥算法的局部開發(fā)能力和加快其收斂速度。

2.5 混合優(yōu)化算法架構(gòu)

混合布谷鳥優(yōu)化算法步驟如下：

步驟1算法參數(shù)設(shè)置：設(shè)置布谷鳥鳥巢數(shù)量N、搜索空間維數(shù)D、最大迭代次數(shù)maxgen和變異概率pc。

步驟2初始化種群：利用tent映射生成均勻分布搜索空間的初始種群。

步驟3計算各個鳥巢適應(yīng)度值，并記錄全局歷史最優(yōu)解，全局歷史次優(yōu)解，個體歷史最優(yōu)解的位置。

步驟4利用萊維飛行一組隨機更新鳥巢位置，并重復(fù)步驟3。

步驟5根據(jù)式（7）保留或替換鳥巢位置，并重復(fù)步驟3。

步驟6利用灰狼算法思想變異種群，并重復(fù)步驟3。

步驟7循環(huán)迭代，并判斷是否滿足迭代終止條件。

步驟8輸出最終的全局歷史最優(yōu)解egbest和對應(yīng)鳥巢位置。

綜上所述，可得混合布谷鳥優(yōu)化算法架構(gòu)如圖1所示。

圖1 算法流程圖Fig.1 Algorithm flow chart

3 仿真實驗分析

3.1 測試函數(shù)

為了驗證本文所提出算法的先進性，選取了8個典型的beachmark測試函數(shù)，具體參數(shù)如表1所示。

表1 Beachmark s測試函數(shù)參數(shù)Table 1 Parameters of beachmarks test function

其中測試函數(shù)F1、F2為典型的單峰測試函數(shù)，函數(shù)F1圖像曲面較規(guī)則，函數(shù)F2圖像為波浪狀的倒沙漏型，具有非常多的局部極小值點和一個全局最小值點。函數(shù)F2、F3、F4 引入了三角函數(shù)項，因此函數(shù)圖像存在規(guī)律性波動，使得算法尋優(yōu)過程中會經(jīng)歷大量局部極小值。同時函數(shù)F4 在引入三角函數(shù)項基礎(chǔ)上，在變量間引入乘項，使其互相影響，使得函數(shù)圖像極其復(fù)雜，尋優(yōu)難度極大。函數(shù)F5為冪和函數(shù)，函數(shù)F6為平方和函數(shù)，也稱軸平行超橢球函數(shù)，均為典型的連續(xù)單峰的凸型函數(shù)，只存在一個全局極小值。函數(shù)F7 為較平緩的谷狀函數(shù)，前期尋優(yōu)速度快，但難以收斂到全局最小值。函數(shù)F8為波浪形的谷狀函數(shù)，較函數(shù)F7更加復(fù)雜，更加考驗算法的尋優(yōu)能力。

3.2 算法參數(shù)

為了驗證本文算法的性能，將布谷鳥算法、粒子群算法、灰狼算法與本文算法的尋優(yōu)結(jié)果進行比較驗證，其中各個對比算法的參數(shù)設(shè)置如表2。

表2 算法參數(shù)設(shè)置Table 2 Algorithm parameters setting

最大迭代次數(shù)設(shè)置為5 000 次，分別經(jīng)歷200 次獨立實驗，減少隨機誤差對實驗結(jié)果的影響。

3.3 測試環(huán)境

本實驗的測試環(huán)境為：硬件運行環(huán)境為CPUi7-9750H，內(nèi)為16 GB，顯卡RTX2060，軟件運行環(huán)境為Windows10系統(tǒng)，運行軟件Matlab2019b。

3.4 實驗結(jié)果分析

經(jīng)過8 個測試函數(shù)的檢驗，實驗結(jié)果如表3 和表4所示。

表3 各個算法對應(yīng)不同測試函數(shù)上的優(yōu)化結(jié)果比較Table 3 Comparison of optimization results on different test functions

表4 各個算法運行速度比較Table 4 Comparison on running speed of each algorithm

表3通過統(tǒng)計算法最終適應(yīng)度的平均值（Mean）、標(biāo)準(zhǔn)差（Std）、最優(yōu)適應(yīng)度（Best）、最劣適應(yīng)度（Wrost）來對比各個算法的性能優(yōu)劣，其中加粗部分代表各算法比較后平均性能最優(yōu)的性能，表4 通過對算法運行100 000次的總運行的時間（Time）和每次尋優(yōu)的平均時間（Mean FEs）代表各個算法的運行速度。

由表3可以發(fā)現(xiàn)，布谷鳥算法、粒子群算法、灰狼算法在8種測試函數(shù)的檢驗下，有部分測試函數(shù)尋優(yōu)結(jié)構(gòu)并不理想，其中粒子群算法因為其參數(shù)少，收斂快的優(yōu)勢被廣泛應(yīng)用于各個領(lǐng)域，但是由于其收斂方式單一，跳出局部最優(yōu)能力弱，會導(dǎo)致在復(fù)雜函數(shù)的尋優(yōu)問題上極易陷于局部極小值，在實驗結(jié)果上表現(xiàn)為在Quadric函數(shù)、Girewank函數(shù)、Sumsqu函數(shù)、Dixonpr函數(shù)上均明顯弱于其他三種算法，特別在Sumsqu函數(shù)和Dixonpr函數(shù)在尋優(yōu)結(jié)果上，其最優(yōu)適應(yīng)度表現(xiàn)較好，但是適應(yīng)度的平均值卻并不理想，這是由于粒子群算法在尋優(yōu)過程中陷入局部最優(yōu)值，且在較大迭代次數(shù)的條件下仍然無法跳出，導(dǎo)致出現(xiàn)壞解影響總體的尋優(yōu)結(jié)果。

布谷鳥算法作為2009 年較新提出的算法，在粒子飛行方式上采用更為隨機的萊維飛行模式，有更大的幾率跳出函數(shù)局部極小值，在全局范圍內(nèi)搜索最優(yōu)解，在4種測試函數(shù)上表現(xiàn)出的性能要略優(yōu)于粒子群算法，且在其他函數(shù)的尋優(yōu)表現(xiàn)上也較為平均，在對同一函數(shù)的多次尋優(yōu)結(jié)果統(tǒng)計中可以看出，布谷鳥算法穩(wěn)定性較粒子群算法更好，但是在最優(yōu)值附近收斂精度較差，表現(xiàn)在最優(yōu)適應(yīng)度（Best）的總體要劣于粒子群算法，另外布谷鳥算法在Schwefel problem 2.22 函數(shù)在尋優(yōu)上結(jié)果非常不理想，這是由于當(dāng)自變量趨近無窮大時，該函數(shù)會形成大量局部極值區(qū)域，且選取的維度較高，尋優(yōu)難度大引起尋優(yōu)效果的不理想。

灰狼算法作為2014 年提出的一個新興群智能算法，在5種測試函數(shù)的尋優(yōu)結(jié)果上要優(yōu)于布谷鳥算法和粒子群算法，且均有概率直接找到最優(yōu)解，表現(xiàn)出良好的全局搜索能力和局部開發(fā)能力，但是在Ackley、Rotated rastrigin等測試函數(shù)的尋優(yōu)表現(xiàn)中仍然可以看出有較大的進步空間。

由表4可以發(fā)現(xiàn)，在算法的運行效率上，GWO算法與PSO算法各有優(yōu)劣，但相較于CS算法都更加快速，但CS 算法由于其貪婪策略的存在，需要反復(fù)比較計算適應(yīng)度函數(shù)，犧牲了部分的運行時間換來更好的全局搜索能力和進化能力。本文算法在經(jīng)過改進后，融合的各個算法的優(yōu)勢，并簡化了部分流程，雖然復(fù)雜性相對三種算法較高，但容易更快收斂到最優(yōu)值。

綜上所述，本文提出的改進布谷鳥灰狼混合算法（improved cuckoo search grey wolf，ICSGWO）在8 種測試函數(shù)的尋優(yōu)結(jié)果均要優(yōu)于其他三種算法，其中在Girewank 函數(shù)、Rotated rastrigin 函數(shù)、Sumpow 函數(shù)、Sumsqu 函數(shù)上可以直接收斂到最優(yōu)解，且表現(xiàn)出優(yōu)異的穩(wěn)定性，在其他四種測試函數(shù)上也略優(yōu)于布谷鳥算法、粒子群算法和灰狼算法。

4 結(jié)束語

本文通過研究和分析布谷鳥算法和灰狼算法的優(yōu)勢和弊端，針對布谷鳥算法局部搜索能力弱的缺陷，引入粒子群算法的社會學(xué)習(xí)算子和自我學(xué)習(xí)算子，并結(jié)合灰狼算法的領(lǐng)袖狼機制，提出了一種改進混合布谷鳥灰狼算法。通過比較實驗發(fā)現(xiàn)，改進算法在保證算法收斂速度和搜索廣度的基礎(chǔ)上，提高后期的搜索精度，滿足算法的收斂性，在各個性能指標(biāo)上均優(yōu)于布谷鳥算法、粒子群算法和灰狼算法。