曹 慧,秦江濤

上海理工大學 管理學院,上海 200093

1 引 言

隨著科學技術的進步,需要解決的優(yōu)化問題越來越多,如函數(shù)極值、聚類問題等,大多都具有復雜、多維、非線性等特點,用常規(guī)的數(shù)學方法難以解決。因此一些學者根據(jù)大自然中種群活動或自然規(guī)律的啟發(fā)提出多種元啟發(fā)式優(yōu)化算法[1],這類算法通過模擬生物行為或物理現(xiàn)象,建立不同的數(shù)學模型以解決優(yōu)化問題。常見的元啟發(fā)式算法有粒子群優(yōu)化算法(PSO)[2],遺傳算法(GA)[3],灰狼優(yōu)化算法(GWO)[4],鯨魚優(yōu)化算法(WOA)[5],蟻獅優(yōu)化算法(ALO)[6],麻雀搜索算法(SSA)[7]等。這些元啟發(fā)式算法具備方法簡便,參數(shù)少,易于實現(xiàn)等優(yōu)勢,可以解決不同類型的優(yōu)化問題,目前多被用于特征選擇、路徑規(guī)劃等相關領域[8-12]。此外,一些學者對這類算法也進行了相應的改進,以進一步增強算法的性能。但按照NFL(No Free Lunch)[13]理論,不存在一種可以獨立處理全部優(yōu)化問題的元啟發(fā)式算法,因此應不斷探索新算法并對算法進行改進。

禿鷹搜索算法(Bald Eagle Search,BES)在2020年由Alsattar等[14]受禿鷹的搜索和狩獵行為的啟發(fā)而提出的元啟發(fā)式算法。目前,國內外一些學者已將禿鷹搜索算法應用于實際工程問題的優(yōu)化,如文獻[15]將BES用于支持向量機(SVM),構建了BES-SVM預測模型,BES算法可以對SVM算法進行有效的優(yōu)化,提高了SVM的預測精度。文獻[16]將其應用于光伏參數(shù)估計,結果證明所使用的BES算法能夠獲得更好的光伏參數(shù)結果,但學者忽略了BES算法本身所存在的易陷入局部最優(yōu)等問題。文獻[17]將其用來解決水下無線傳感器網(wǎng)絡(UWSN)的高能耗等問題,根據(jù)實驗結果,BES算法在UWSN中表現(xiàn)的性能具有極大的優(yōu)越性。大部分文獻將BES算法用于實際問題的優(yōu)化中,并取得了較好的結果,但是并未考慮BES算法本身所存在的問題。而BES作為新型元啟發(fā)式算法,類似于其他傳統(tǒng)算法,具有收斂速度慢,尋優(yōu)精度不高等問題,因此文獻[18]提出了基于萊維飛行和模擬退火策略的禿鷹搜索算法(IBES),使用萊維飛行擴大群體的搜索范圍,模擬退火策略增強原算法在局部鄰域內求解精度,算法的性能得到一定程度的改善,但該算法側重于跳出局部最優(yōu)解,收斂速度和精度還有一定的提高空間。

上述改進策略側重于算法跳出局部最優(yōu),在提升算法局部搜索上具有一定的改善,但是對于算法的收斂速度以及平衡局部和全局搜索方面還具有很大的改進空間。為了彌補這些不足,本文將提出一種混合策略改進型禿鷹搜索算法(HSIBES),此算法利用Logistic映射策略初始化種群,使其分布更加均勻,有助于算法在全局范圍內搜索?？紤]萊維飛行具有長短步長交替搜索的特點,使用萊維飛行進行搜索空間中步長的控制,擴大搜尋區(qū)域,提高算法跳出局部極值點的能力。最后使用自適應慣性權重,協(xié)調禿鷹搜索算法在局部以及全局范圍內的尋優(yōu)能力,提高算法尋優(yōu)的精度和速度。將HSIBES算法在9個基準測試函數(shù)上進行仿真實驗,并且進行Wilcoxon秩和檢驗。實驗結果說明本文提出的HSIBES算法具有更快的收斂速度和更高的收斂精度,可以更好地平衡全局和局部搜索能力。

2 禿鷹搜索算法

禿鷹種群主要分布于北美地區(qū), 它們具有視力敏銳,觀察能力優(yōu)秀的特點。在進行捕食食物時,禿鷹種群會先根據(jù)食物的濃度來確定搜尋空間,之后飛向所確定的區(qū)域;接著在所選擇的搜尋空間中搜尋食物;最終禿鷹根據(jù)食物所在的位置,慢慢改變飛行高度,加速向下飛行,直至成功獲取獵物。

Alsattar 等根據(jù)禿鷹捕獲食物的活動建立了禿鷹搜索算法(BES)數(shù)學模型,算法可以總結為3個階段,分別是選取搜尋空間、搜尋空間食物以及俯沖捕獲食物。

2.1 選取搜尋空間

禿鷹選取搜尋區(qū)域,根據(jù)區(qū)域內食物的數(shù)量選擇最優(yōu)搜索位置,易于搜尋食物,該行為用數(shù)學模型表示如下:

Pi,new=Pbest+α×r×(Pmean-Pi)

(1)

式(1)中:α是控制禿鷹位置改變的因子,取值在1.5和2之間;r是0和1之間的隨機數(shù);Pi,new為禿鷹的更新位置;Pbest是禿鷹種群搜尋選擇的最優(yōu)位置;Pmean是當前種群的平均位置;Pi表示種群中第i只個體的位置。

2.2 搜尋空間食物(探索)

在此搜索階段,禿鷹種群在確定的搜尋空間中搜尋食物,并在空間中以螺旋狀飛行,加速對獵物的追捕,尋求最優(yōu)向下飛行捕獲食物的位置。禿鷹種群以螺旋狀搜尋食物的飛行軌跡可用以下數(shù)學模型進行表示:

θ(i)=a×π×rand()

(2)

r(i)=θ(i)+R×rand()

(3)

xr(i)=r(i)×sin(θ(i))

(4)

yr(i)=r(i)×cos(θ(i))

(5)

x(i)=xr(i)/max(|xr|)

(6)

y(i)=yr(i)/max(|yr|)

(7)

其中:θ(i)表示螺旋方程的極角,r(i)表示螺旋方程的極徑;a表示控制螺旋軌跡的因子介于5至10之間,R用來確定搜索周期數(shù),取值在0.5至2之間,x(i)與y(i)為極坐標方程中個體所處的位置,取值范圍均在-1到1之間。禿鷹位置更新如下:

Pi,new=Pi+x(i)×(Pi-Pmean)+y(i)×(Pi-Pi+1)

(8)

2.3 俯沖捕獲獵物

禿鷹從所選擇的搜尋區(qū)域的最優(yōu)位置加速飛向目標食物,所有個體也會飛向最優(yōu)位置去捕獲食物,飛行軌跡仍然使用極坐標數(shù)學模型進行描述,公式如下:

θ(i)=a×π×rand()

(9)

r(i)=θ(i)

(10)

xr(i)=r(i)×sinh(θ(i))

(11)

yr(i)=r(i)×cosh(θ(i))

(12)

x1(i)=xr(i)/max(|xr|)

(13)

y1(i)=yr(i)/max(|yr|)

(14)

加速飛向目標過程中禿鷹的位置更新公式為

(15)

Pi,new=rand×Pbest+δx+δy

(16)

其中:c1和c2分別表示禿鷹向最佳位置與中心位置的運動強度,取值區(qū)間均為[1,2]。

3 混合策略改進型禿鷹搜索算法

標準的禿鷹搜索算法與其他標準元啟發(fā)算法相比有良好的收斂速度和收斂精度,但與其余基準元啟發(fā)式算法相同也存在尋優(yōu)精度低,易陷入局部最優(yōu)的缺陷,為了提升收斂速度和精度,提出了一種混合策略改進型禿鷹搜索算法,并設計了3種改進策略,分別是:Logistic混沌映射,進行種群初始化,增加種群多樣性;萊維飛行,控制步長,擴大搜索范圍,跳出局部最優(yōu)解;自適應慣性權重,改善群體之間的信息交流,平衡局部和全局搜索能力。

3.1 Logistic混沌映射

禿鷹搜索算法采用隨機法初始化種群,使得禿鷹個體在搜索空間內分布不均勻,從而導致算法在解空間的遍歷性低,降低收斂速度和求解精度。將Logistic混沌映射[19]引入BES算法,增加種群的多樣性,提高算法的收斂速度并提升算法在全局范圍內的尋優(yōu)能力,其數(shù)學模型如下所示:

yt+1=μyt(1-yt)

(17)

式(17)中,yt表示第t次迭代產生的混沌變量,取值范圍為[0,1],μ為控制參數(shù),取值范圍為[0,4]。當μ的取值為4時,變量會遍歷整個搜索空間。

將獲得的混沌序列yt通過下式逆映射到搜尋空間中,得到初始化種群Pt:

Pt=Lt+(Ut-Lt)yt

(18)

其中,Ut和Lt分別為搜索空間的上界和下界。

3.2 萊維飛行

萊維飛行[20]是一個隨機漫步的過程,由法國數(shù)學家萊維提出,萊維飛行大步長與小步長隨機交替,可有效跳出局部最優(yōu)。由于禿鷹搜索算法在選擇搜索空間階段的搜索步長是一個定值,容易陷入局部最優(yōu)。而引入萊維飛行能夠控制步長,擴大搜索范圍,使算法有機會跳出局部最優(yōu)解。根據(jù)萊維飛行,改進后的選擇搜索空間階段位置更新函數(shù)如下:

Pi,new=Pbest+α*r(Pmean-Pi)×Levy

(19)

Levy符合萊維分布,滿足Levy(λ)～u=t-λ(1<λ≤3)。由于萊維飛行的復雜性,通常使用Mantegna算法對其進行模擬[21],步長S的計算式為

(20)

式(20)中,u、v均遵循正態(tài)分布:

(21)

(22)

其中,τ為Gamma函數(shù),參數(shù)β=1.5。

3.3 自適應慣性權重

在搜尋空間食物中只依照當前禿鷹種群的信息來更新所處位置,而未考慮其余迭代中出現(xiàn)的位置信息,會導致在搜索更新位置中,位置更新不準確,并在一定程度上限制了算法的搜索效率。因此,將引入自適應慣性權重,在權重值較大的情況下,算法的在全局范圍內的搜尋能力比較強,在權值較小的情況下,算法后期在局部范圍內的尋優(yōu)能力較強。因此,加入自適應慣性權重,可以有效改善群體之間的信息交流,平衡局部和全局搜索能力,提高算法尋優(yōu)的精度和速度[22]。

自適應權重公式如式(23)所示:

ω=sin((π×p)/(2×M)+π)+1

(23)

其中,p為當前迭代次數(shù),M為最大迭代次數(shù)。

將式(23)代入式(8),得到改進的禿鷹位置更新函數(shù):

Pi,new=Pi+ω×x(i)×(Pi-Pmean)+ω×y(i)×(Pi-Pi+1)

(24)

3.4 算法流程

step1：初始化禿鷹算法種群規(guī)模,空間維度等參數(shù),使用Logistic混沌映射進行禿鷹種群初始化;

step2：計算適應度值,獲得最優(yōu)個體;

step3：禿鷹選擇搜索空間,利用式(19)更新位置;

step4：禿鷹在搜索空間搜索獵物,利用式(24)更新位置;

step5：禿鷹俯沖利用式(16),更新位置;

step6：當符合結束條件時,輸出最優(yōu)結果,否則繼續(xù)進行從step2到step6的流程。

3.5 時間復雜度分析

假設種群規(guī)模為N,空間維度為D,則BES算法參數(shù)初始化的時間復雜度為O(1),計算函數(shù)適應度為O(N),迭代過程中種群復雜為O(ND),BES算法總的時間復雜度為

O(1)+O(N)+O(ND)=O(ND)

(25)

在HSIBES算法中,隨機初始化替換為Logistic混沌初始化時間復雜度為O(ND),計算適應度為O(N),引入萊維飛行和自適應慣性權重進行位置更新所對應的時間復雜度均為O(ND),則HSIBES算法總的時間復雜度為

O(ND)+O(N)+O(ND)+O(ND)=O(ND)

(26)

基于上述分析,HSIBES算法和BES算法相比,時間復雜度并未增加。

4 實驗結果分析

實驗測試結果均在Intel(R) Core(TM) i7-10750H CPU @ 2.60GHz,64位Windows10操作系統(tǒng)和MATLAB R2018b上實現(xiàn)。

為了驗證混合策略改進型禿鷹搜索算法的有效性,將從以下幾個部分進行實驗驗證:

(1) 將HSIBES與基本禿鷹搜索算法(BES)[14]、粒子群優(yōu)化算法(PSO)[2]、鯨魚優(yōu)化算法(WOA)[5]、蟻獅算法(ALO)[6]、灰狼優(yōu)化算法(GWO)[4]這5個基本元啟發(fā)式算法進行對比,驗證混合策略改進型禿鷹搜索算法的尋優(yōu)能力和魯棒性。

(2) 將HSIBES與文獻[18]中改進的禿鷹搜索算法進行對比,驗證本文改進算法具有一定的競爭力。

(3) 通過Wilcoxon秩和檢驗進行差異性檢驗,驗證HSIBES算法與其他對比算法的差異性。

為了檢驗提出的改進的禿鷹搜索算法的魯棒性以及有效性,從文獻[23]中選擇了9個具備不同特征的基準測試函數(shù)進行實驗測試,具體函數(shù)表達式如表1所示。這9個用于實驗的測試函數(shù)主要分為單峰函數(shù)以及多峰函數(shù),其中f1(x)—f6(x)是單峰函數(shù),f7(x)—f9(x)是多峰函數(shù),算法的局部搜索能力與收斂速度可用f1(x)-f6(x)測試,算法在全局范圍內的尋優(yōu)能力以及跳出局部極值點的能力可用f7(x)—f9(x)測試。

表1 基本測試函數(shù)Table 1 Basic test functions

4.1 與其他基準算法進行對比

將提出的HSIBES算法與BES[14]、PSO[2]、WOA[5]、ALO[6]、GWO[4]算法在9個基準測試函數(shù)上進行對比實驗,為保證實驗的公平性,種群規(guī)模均設為30,最大迭代次數(shù)為500,維度設為30維,各個算法其他參數(shù)設置與相應參考文獻一致,實驗將記錄每種算法在測試函數(shù)上獨立運行30次的平均值、方差和平均耗時以便進行對比,結果如表2所示。

表2 函數(shù)測試實驗結果Table 2 Results of function test experiment

從均值來看,提出的HSIBES算法在測試函數(shù)f7(x)和f9(x)的均值達到了理論最優(yōu)值,說明30次獨立運行中得到的結果精度較高,穩(wěn)定性較好。HSIBES算法在測試函數(shù)f5(x)的均值結果不是算法結果里最優(yōu)的,劣于其他算法,但是差異不是非常顯著,求解精度在1個數(shù)量級以內,在可以接受的范圍內。在測試函數(shù)f1(x)—f4(x),f6(x),f8(x)上HSIBES算法明顯優(yōu)于其他對比算法,尤其在函數(shù)f1(x)、f3(x)和f4(x)上,HSIBES算法相較于BES、GWO、ALO、PSO、WOA均提升了100～200個數(shù)量級左右。在f2(x)、f6(x)和f8(x)函數(shù)上也提升了多個數(shù)量級,說明混合策略改進型禿鷹搜索算法求解精度較好。從標準差來看HSIBES算法測試函數(shù)上的標準差均是所有結果里最優(yōu)的,說明提出的算法的魯棒性較好。從平均耗時來看,PSO算法整體耗時最短,HSIBES算法相對于標準BES的平均耗時要小,說明引進的改進策略并未降低原算法的執(zhí)行效率。經(jīng)過上述分析,HSIBES算法在平均值標準差以及耗時方面整體來說要優(yōu)于對比算法,具有較好的收斂速度和收斂精度,穩(wěn)定性也較好。

4.2 與其他改進算法的對比

為了突出提出的混合策略改進型禿鷹搜索算法相比于其他學者改進的禿鷹搜索算法的競爭優(yōu)勢,選取文獻[18]改進的禿鷹搜索算法IBES進行對比,和上文設置統(tǒng)一的參數(shù)條件:c1=c2=α=2,a=10,R=1.5,種群規(guī)模均設為30,最大迭代次數(shù)為500,維度設為30維,在上文的測試函數(shù)及運行環(huán)境上進行測試,獨立運行30次,對所得結果求平均值與標準差,與本文提出的HSIBES進行對比分析,結果如表3所示。

對于函數(shù)f1(x)和f3(x),HSIBES算法的平均尋優(yōu)精度高于IBES算法,高出20個數(shù)量級左右,兩者的標準差相同,說明兩種算法在函數(shù)f1(x)和f3(x)的穩(wěn)定性相當,在測試函數(shù)f2(x)、f4(x)和f6(x)上,HSIBES算法的均值和標準差均高于IBES算法,在測試函數(shù)f5(x)上,HSIBES算法的尋優(yōu)精度和穩(wěn)定性不及IBES,在函數(shù)f7(x)—f9(x)上,二者的均值和標準差的求解結果相同。從平均值和標準差來看,HSIBES算法在55%以上的測試函數(shù)上優(yōu)于IBES算法,33%測試函數(shù)和IBES算法結果相同。從平均耗時的結果來看,HSIBES算法在9個函數(shù)上的耗時都比IBES算法的耗時短。綜上,和對比算法IBES相比,HSIBES算法具有一定的競爭優(yōu)勢。

4.3 算法收斂曲線對比分析

為了更加直觀地反映HSIBES算法的性能,給出了算法在函數(shù)上運行30次中其中一次的收斂圖,如圖1所示。和其他基本算法相比,HSIBES算法在單峰函數(shù)f1(x)—f4(x),f6(x)的收斂速度和收斂精度明顯高于其他對比算法,雖然在f5(x)函數(shù)上的精度略低于其他算法,但是其收斂速度明顯優(yōu)于其他對比算法,在多峰函數(shù)f7(x)—f9(x)上,HSIBES算法可以快速地收斂并且跳出局部最優(yōu),說明混合策略改進型禿鷹搜索算法HSIBES可以提高基本算法的收斂速度,跳出局部極值點,進行全局范圍的尋優(yōu)。

和IBES對比算法相比,HSIBES算法除了在函數(shù)f5(x)上表現(xiàn)不佳,在其他函數(shù)上都有較好的尋優(yōu)精度和收斂速度。在函數(shù)f1(x)—f4(x)上,HSIBES算法和IBES算法相比精度顯著提升,在函數(shù)f6(x)上HSIBES算法出現(xiàn)了多次拐點,但停滯次數(shù)相對較少,并且在后期跳出局部最優(yōu)解,在函數(shù)f7(x)—f9(x)上,HSIBES算法可在較短的時間內和其他改進算法達到相同的尋優(yōu)值,綜上所述本文提出的HSIBES算法具有較好的收斂速度和尋優(yōu)精度,能更好地平衡算法局部和全局搜索能力。

(a) f1(x)收斂曲線

(b) f2(x)收斂曲線

(c) f3(x)收斂曲線

(d) f4(x)收斂曲線

(e) f5(x)收斂曲線

(f) f6(x)收斂曲線

(g) f7(x)收斂曲線

(h) f8(x)收斂曲線

(i) f9(x)收斂曲線圖1 各測試函數(shù)下的收斂曲線Fig.1 Convergence curves under each test function

4.4 Wilcoxon秩和檢驗

運用Wilcoxon秩和檢驗[24]的方法來檢驗提出的HSIBES算法與其他算法的顯著性差別。將獲得的實驗結果在5%的顯著性水平下進行統(tǒng)計檢驗,在p大于0.05的情況下,說明兩種算法性能相差不大,否則兩種比較算法的性能具有顯著性差異。為了判斷HSIBES算法與其他算法的顯著性區(qū)別,將以上算法在函數(shù)上獨立運行30次的結果作為樣本,進行實驗驗證。得到的Wilcoxon秩和檢驗的p值結果如表4所示,由于HSIBES算法不能和本身進行比較,所以在這里不再列出HSIBES算法的p值,當實驗樣本數(shù)據(jù)一樣時,說明兩個對比算法性能相當,此時數(shù)據(jù)無效,在下表中使用NaN表示。

表4 Wilcoxon秩和檢驗p值Table 4 Wilcoxon rank and test p-value

由表4可知,根據(jù)對比算法在測試函數(shù)f7(x)—f9(x)的檢驗結果來看,HSIBES算法與IBES算法性能相當,在函數(shù)f4(x)上,二者性能顯著性差異不明顯,在函數(shù)f7(x)上,HSIBES算法與WOA算法顯著性差異不明顯,除此之外,其余p值均小于5%,說明HSIBES算法和其他對比算法之間具有顯著性差異,總體看來,本文提出的HSIBES算法的優(yōu)越性在統(tǒng)計上是顯著的,與其他對比算法具有顯著性差異。

5 結束語

根據(jù)BES算法存在易陷入局部最優(yōu),收斂精度低的問題,提出了混合策略改進的禿鷹搜索算法(HSIBES),利用Logistic映射策略初始化種群,使種群分布更加均勻,其次引入萊維飛行,其長短步長交替搜索,控制搜索步長,有利于提高解的質量。最后在探索階段使用自適應慣性權重,提高了算法尋優(yōu)的精度和速度,平衡了局部和全局探索能力。最后在9個基準測試函數(shù)上進行了仿真實驗,并與BES、PSO、WOA、ALO、GWO以及其他學者改進的IBES算法進行對比實驗,分析得出了提出的HSIBES算法收斂速度、收斂精度以及魯棒性都表現(xiàn)較好,并通過Wilcoxon秩和檢驗驗證了HSIBES算法與其他算法的顯著性差異。在后續(xù)的研究中,將會把HSIBES算法用于實際工程問題中,如神經(jīng)網(wǎng)絡的優(yōu)化,圖像分割等。