多策略改進的混沌哈里斯鷹優化算法

胡春安,熊昱然

(江西理工大學信息工程學院,江西 贛州 341000)

1 引言

以模擬自然界中動物種群行為為基礎設計的算法被稱為元啟發式算法[1,2]。這些行為包括繁殖、捕獵和遷徙等。通過對這些行為進行數學建模,來解決一些分布式問題[3]。近年來,群優化算法[4]逐漸被應用于諸如圖像處理、路徑規劃和數據挖掘等方面,并取得了相應的研究成果。目前,群智能算法發展現狀已經從簡單的粒子群演變到一些具有一定感知、預警和自主搜尋能力的種群。比較常見的群智能算法有粒子群優化算法[4]、蟻群算法[5]、麻雀搜索算法[6]和布谷鳥算法[7]等。群算法的基礎理論提出后主要的發展方向有2個:一個是在算法的基礎上進行改進,優化其中的種群行為策略;另一個是將算法應用在實際工程案例中,獲得更好的優化效果。

哈里斯鷹優化HHO(Harris Hawk Optimization)算法是由Heidari等人[8]在2019年提出的一種元啟發算法,源于觀察哈里斯鷹和它們的獵物(兔子)之間的追逐逃跑行為。哈里斯鷹捕捉獵物的主要策略是突襲。在這個智能策略里,鷹群從幾個不同的方向協同攻擊檢測到的正在逃跑的兔子。由于獵物存在一定的逃生能力,哈里斯鷹可能在幾分鐘內在獵物附近進行多次短距離的快速攻擊。鷹群能根據環境和獵物的逃跑狀態表現出幾種不同的追逐風格。當最強的鷹(領導者)俯身沖向獵物并且迷路時,就會發生策略的轉換,由鷹群中另一名成員繼續追擊。

與其他的元啟發式算法類似,傳統的哈里斯鷹優化算法本身也存在在開發階段搜索容易陷入局部最優、收斂精度低等問題[9]。為了使算法有所改善,郭雨鑫等人[10]提出了多策略優化的哈里斯鷹優化算法,在探索階段引入了柯西變異,局部搜索階段引入了自適應權重粒子來更新位置,解決原始哈里斯鷹優化算法易陷入局部最優和收斂精度低的問題。馬一鳴等人[11]提出了一種改進的哈里斯鷹優化定位算法,在提升原算法性能的基礎上保留其尋優機制,對基于最大似然估計的適應度函數進行改進,在優化過程中達到更優的適應度值,從而提高算法的尋優精度。王歸新等人[12,13]通過結合2種較新的群智能算法(改進灰狼優化算法與哈里斯鷹優化算法),從而獲得了二者易實現、收斂速度快和全局搜索能力強的優點。

目前的HHO改進策略雖然在一定程度上改進了算法的尋優能力,但只是針對其中的某一種更新策略進行更改或者改變逃逸能量的變化方式,并沒有有效解決尋優的盲目性。針對以上問題,本文提出了一種融合分布式估計策略、混沌局部搜索策略和精英池策略的多策略改進哈里斯鷹優化算法。

2 哈里斯鷹優化算法

哈里斯鷹優化算法通過構建數學模型來模擬現實中哈里斯鷹在不同情況下的捕獵策略,整個算法分為探索階段和開發階段。

2.1 探索階段

在HHO算法中,哈里斯鷹個體是候選解,每個迭代步驟中的目標獵物為所求問題的最優解,并根據2種策略來發現獵物,如式(1)所示:

(1)

其中,t表示為當前迭代次數,X(t+1)表示第t+1次迭代時鷹的位置;Xrabbit(t)表示第t次迭代時獵物的位置;X(t)表示第t次迭代時鷹的位置;r1,r2,r3,r4,q是(0,1)的隨機數;LB和UB分別表示搜索空間的下界和上界;Xrand(t)表示第t次迭代時種群中隨機選擇的鷹的位置;Xm(t)表示第t次迭代時鷹群位置的平均值,如式(2)所示:

(2)

其中,Xi(t)表示第t次迭代時第i只鷹的位置,N表示鷹的總數。

2.2 過渡階段

根據獵物的逃逸能量,HHO算法可以從探索階段轉移到開發階段。在獵物逃跑的過程中,獵物的能量是遞減的,本文把逃逸能量抽象成式(3):

(3)

其中,E表示當前獵物的逃逸能量;T表示最大迭代次數;E0表示初始能量,是(-1,1)的隨機數。

在每次迭代過程中,當逃逸能量|E|≥1時,進入探索階段;逃逸能量|E|<1時,進入局部開發階段。

2.3 開發階段

HHO提出了4種可能的策略來模擬哈里斯鷹的攻擊手段。用r來表示獵物的逃跑概率。

Case 1:軟圍攻。當r≥0.5且|E|≥0.5時,在這種攻擊方式中,哈里斯鷹群將會對它進行軟包圍,使獵物更加疲憊,然后進行突襲。該行為的抽象數學模型如式(4)所示:

X(t+1)=ΔX(t)-E|JXrabbit(t)-X(t)|,

ΔX(t)=Xrabbit(t)-X(t)

(4)

其中,ΔX(t)表示第t次迭代時獵物位置與哈里斯鷹距離之差;J表示獵物在逃跑過程中的隨機跳躍強度,是一個(0,2)的隨機數,每次迭代中都會隨機變化。

Case 2:硬圍攻。當r≥0.5且|E|<0.5時,獵物此時逃逸能量低,哈里斯鷹直接進行最終突襲。在這種情況下用式(5)更新當前位置:

X(t+1)=Xrabbit(t)-E|ΔX(t)|

(5)

Case 3:累速俯沖式軟圍攻。當r<0.5且|E|≥0.5時,獵物仍然有足夠的能量成功逃脫,在突襲之前,哈里斯鷹建立了一個軟圍攻策略,將Levy飛行集成進了HHO中,這個階段的位置更新策略如式(6)～式(8)所示:

Z=Y+S·LF(D)

(6)

Y=Xrabbit(t)-E|JXrabbit(t)-X(t)|

(7)

(8)

其中,D表示當前問題的維度,S表示D的隨機行向量,Y表示累速俯沖式軟圍攻公式計算出的位置向量,Z表示經過Levy飛行擾動過的位置,F(·)表示求當前適應度值的函數,LF(·)表示Levy飛行生成的擾動值。

Case 4:累速俯沖式硬圍攻。當r<0.5且|E|<0.5時,獵物沒有足夠的能量逃跑,在突襲捕捉獵物之前哈里斯鷹會進行一次硬圍攻。在這次圍攻中,哈里斯鷹試圖縮小它與獵物的距離,因此按照式(9)～式(11)所示的策略更新:

Z=Y+S·LF(D)

(9)

Y=Xrabbit(t)-|EXrabbit(t)-Xm(t)|

(10)

(11)

3 改進的哈里斯鷹優化算法

通過分析HHO算法可知,HHO也存在開發能力不足、種群多樣性下降、容易陷入局部最優等缺點,這是由于算法對搜索空間開發和探索的不平衡造成的。為了提高算法的性能,平衡HHO算法的開發和探索能力,本文提出了一種具有3種改進策略的HHO算法變體,叫做多策略改進的哈里斯鷹優化算法MHHO(Harris Hawk Optimization algorithm using Multi-strategy)。首先,在HHO中引入混沌局部搜索策略,提高算法的開發能力。利用混沌映射的優點,圍繞當前個體進行局部搜索,從而找到更好的個體。其次,為了增強種群多樣性,提出了精英備選池策略。此外,為了修改進化方向,本文采用了分布估計策略,通過對優勢種群信息進行采樣,更好地引導種群方向,從而提高算法收斂速度。最后,采用貪婪策略充分保留優勢個體,加快收斂速度。

3.1 混沌局部搜索策略

混沌局部搜索策略通過搜索每一個解決方案的附近區域,從而找到更好的解決方案,因此該策略能夠有效提高算法的開發能力。另一方面,混沌映射具有隨機性和遍歷性的特點,所以利用混沌映射能夠進一步提高局部搜索策略的有效性。在MHHO中,混沌局部搜索策略只應用于種群的優勢種群。混沌局部搜索策略的公式如式(12)所示:

(12)

混沌映射的方法有很多種[14],最常見的有Logistic映射、Tent映射和Sin映射。但是,Logistic映射的遍歷性較差,對初始參數的設置較敏感,映射點在邊緣位置的密度大,在中間位置的密度相對較小,與本文想要達到的種群均衡性的預期不符合。而Tent映射值的分布比較平坦、均勻,映射的均勻性相比于Logistic映射的均勻性更好,能夠提高算法的尋優速度。考慮結合完全隨機化的特點,MHHO將Tent混沌映射生成Ct,同時在[0,1]產生分布較均勻的初始值。Tent混沌映射分布值如圖1所示,Tent映射表達式如式(13)所示:

Figure 1 Tent chaos mapping

(13)

3.2 精英備選池策略

在早期迭代階段,HHO通過跟隨最優個體更新其余個體位置信息,雖然這有利于算法加快收斂,但會減弱種群的多樣性,容易導致算法陷入局部最優[15]。此外,在迭代后期,使用Levy捕食策略時,同樣僅跟隨最優個體。為了保證算法開發和探索的平衡,本文提出了一種精英備選池策略,將當前最好的3個個體放入一個集合,如式(14)所示:

Xesp={Xesp1,Xesp2,Xesp3}

(14)

其中,Xesp1、Xesp2和Xesp3是種群中最好的3個個體。

食物源每次都從這3個個體中隨機選擇。通過使用精英備選池策略,食物源的位置從最優個體變為最好的3個個體中的一個,這在一定程度上避免了因最優個體陷入局部最優而導致算法早熟收斂。為了平衡算法的開發和探索,本文算法還將全局最優個體放入精英備選池,以確保每一個個體有機會向最優個體靠近,確保算法的收斂效率。因此,精英備選池策略的最終數學模型描述如式(15)所示:

Xesp={Xesp1,Xesp2,Xesp3,Xbest}

(15)

避免局部最優一直是群智能算法的一個重大難題。本文通過精英池策略能夠有效地避免個體陷入局部最優。最終的精英池由幾個最好的個體隨機組成,這保留了選擇優勢個體的可能性,也給當前種群提供了更大的選擇范圍。由于精英池內的個體是隨著每次迭代進行更新的,所以不必擔心精英池內的個體陷入局部最優導致整個算法陷入局部最優的情況發生。

為了更直觀地比較原始HHO算法與使用精英池策略改進后HHO算法的區別,本文選取CEC2017中F3、F4、F9和F10作為測試函數。

Table 1 Test functions

從圖2中可以很明顯地看出,在4個測試函數上,精英池HHO算法比原始HHO算法有更好的收斂性和收斂速度。

3.3 分布估計策略

在原始的HHO中,迭代過程中種群的更新主要由迄今為止得到的最佳解引導,因此種群的多樣性在算法過程的后期迅速減少,導致HHO很容易陷入局部最優。分布估計策略的核心是加權協方差矩陣,具有較強的局部最優規避能力。因此,本文采用加權極大似然估計法對分布模型進行估計,選取表現較好的前一半作為優勢總體,以充分利用有希望的種群信息來估計更好的進化方向。該策略的數學模型描述如下:

(16)

(17)

Cov=

(18)

(19)

(20)

在每一次迭代完成之后,使用貪婪策略保留父代群體和子代群體中的最優NP個個體形成新的群體,這樣進一步提高了MHHO算法的全局收斂能力。

3.4 改進算法流程圖

MHHO的流程圖如圖3所示。

Figure 3 Flow chart of MHHO algorithm

3.5 時間復雜度分析

本節對HHO算法和MHHO算法的時間復雜度進行分析。對于原始的HHO算法而言,種群規模為NP,搜索空間維度為D,最大迭代次數為T,需要優化的目標函數為f(x),由此可知HHO算法的時間復雜度為:O(NP)+O(T·NP·D)+O(T·NP)。

MHHO算法每次只對優秀種群使用分布估計策略產生出M個變異新解。MHHO會計算M+NP/2個個體的適應度值,從得到的適應度值中挑選出前NP/2個個體進入下一輪更新。計算M+NP/2個個體的適應度值的時間復雜度為O(T·(M+(NP/2)))。將這些得到適應度值的個體進行排序的時間復雜度為:O(T·(M+(NP/2))log(M+(NP/2))),所以MHHO算法的總時間復雜度為:O(NP)+O(T·(M+(NP/2)))+O(T·(M+(NP/2))log(M+(NP/2)))+O(T·NP·D)。

4 仿真實驗和結果分析

4.1 測試函數和初始化參數

為了充分驗證MHHO算法的優越性,本文使用IEEE CEC2017單目標測試函數對算法進行測試。CEC2017測試集由16個測試函數組成。F1是一個只有一個全局最優解的單峰函數,用來驗證算法的局部搜索能力。F2～F4是多峰函數,主要用于測試算法跳出局部最優的能力。F9～F12、F17和F18是混合函數,F19、F20、F25～F28是復合函數,可以用來測試算法在現實世界中解決復雜優化問題的潛力。表2給出了函數及其全局最優點。

Table 2 CEC2017 test functions

為了保證公平性,對于經典測試函數,所有算法都采用相同的維度,最大迭代次數設置為300,種群數量設置為50,分別對每個函數獨立求解30次。對于CEC 2017測試集,維度(Dim),最大迭代次數tmax和種群數(NP)分別被統一設置為30,600和500。所有測試函數獨立運行51次。本文實驗在一臺裝有Intel i5-8500U處理器和8 GB內存的計算機上進行,并使用Matlab R2020a進行編程。

4.2 實驗結果與分析

本節將最近提出的5種算法與MHHO進行比較。這些最先進的算法包括蝴蝶優化算法BOA(Butterfly Optimization Algorithm)、樽海鞘群算法SSA(Salp Swarm Algorithm)、算術優化算法AOA(Arithmetic Optimization Algorithm)、尋路者算法PFA(PathFinder Algorithm)和被囊群算法TSA(Tunicate Swarm Algorithm)[16-20]。所有算法的參數設置與原文獻的一致,如表3所示。

Table 3 Algorithm parameters setting

本文通過數值分析、收斂分析、穩定性分析、Wilcoxon符號秩檢驗、Friedman檢驗對MHHO的性能進行全面評估,結果如表4所示。

Table 4 Statistical results of seven algorithms on CEC2017 test functions

從表4可知,對于單峰測試函數F1,MHHO性能優于所有對比算法的,雖然MHHO無法取得最優解,但在所有對比算法中表現最好,表明了MHHO具有最強的開發能力;對于多峰測試函數,MHHO在2個測試函數(F2和F3)上表現最好,在F4上PFA取得了最好的結果,MHHO均排在第2位,MHHO在多峰函數上的表現說明改進算法能夠保持足夠好的種群多樣性,避免了陷入局部最優;對于混合函數和復合函數,每個算法各有優劣:MHHO在F9～F12、F17、F20、F26～F28上獲得了最優解,PFA則在F18和F25上求得了更好的解,BOA在F19上表現優于其他對比算法的。總的來說,MHHO在復合函數和混合函數上取得的結果均排在前兩位,很好地表明了MHHO解決現實世界中復雜優化問題的潛力。值得注意的是,MHHO在所有測試函數上的表現都優于HHO,表明本文提出的改進算法性能更好。

為了分析改進算法所求解的分布特性,根據各算法51次獨立求解的結果繪制了箱式圖,如圖4所示。對于每種算法,每個框的中心標記表示51次求解函數結果的中位數,框的底部和頂部邊緣表示一等分點和三等分點,符號“+”表示不在箱子內的壞值。從圖4可以得知,在求解其中5個測試函數(F3、F12、F20、F27和F28)時,MHHO沒有異常值,這表明MHHO所求解的分布非常集中;同時,對于其它在箱式圖中存在異常值的測試函數(F1、F2、F9～F11、F17、F26),MHHO有著最小的中位數,表明MHHO的解的質量相對更優。因此,本文提出的改進算法具有很強的魯棒性。

Figure 4 Box diagrams of CEC2017 test functions

為進一步說明算法的收斂性能,將適應度值為以10為底的對數計量的適應值(Fitness)作為每個算法收斂精度的評判標準。圖5展示了7種算法求解CEC2017測試集的平均誤差收斂曲線圖(迭代曲線圖),橫坐標表示算法的迭代次數,縱坐標表示算法的收斂精度,也就是最終得到的適應度值。結合以上7種算法在每個測試函數所展現出的進化曲線和收斂精度,實驗結果分析如下:

Figure 5 Convergence diagrams of CEC2017 test functions

對于單峰函數F1,MHHO有更好的收斂精度和更快的收斂速度。對于多峰函數F2～F4,MHHO在F2和F3上有更好的收斂精度和更快的收斂速度,PFA則在F4上具有更好的收斂精度。對于復合函數和混合函數,MHHO在求解其中的9個函數(F9～F12、F17、F20、F26～F28)時,收斂速度更快,收斂精度更高。值得注意的是,MHHO在所有測試函數上的尋優精度和收斂速度都比HHO的更好。綜上所述,MHHO在收斂精度和收斂速度方面優于對比算法。

為了測試函數的時間消耗(單位為s),本文挑選了CEC2017中幾個有代表性的單峰、多峰以及混合函數來對改進策略進行評估。

從表5可以發現,無論是單峰函數、多峰函數還是最復雜的混合函數,MHHO的時間消耗都控制在7 s左右;HHO的時間消耗極度不穩定,且遠高于MHHO的,這說明改進算法具有更好的性能。

Table 5 Time consumption of two algorithms on test functions

僅根據平均值比較算法性能還不充分,為了避免測試中的偶然性,本文使用Wilcoxon符號秩檢驗來驗證改進算法與對比算法是否在統計上存在顯著差異。表6列出了每種算法和MHHO的Wilcoxon符號秩檢驗的結果。在表6 中,“+”表示MHHO的優化結果優于對比算法的,“-”表示結果較差,“=”表示結果相似;符號“R+”是一個正等級值,表示MHHO比對比算法更好的程度,“R-”表示相反的結果。從表6可以看出,MHHO至少在12個測試函數上優于所有對比算法,并且在所有測試函數(15個)上均優于原始HHO,在統計學上驗證了改進算法的出色性能。

Table 6 Results of Wilcoxon signed rank test

通過CEC2017測試集對MHHO的性能進行驗證,實驗結果表明:改進策略均能有效提高算法性能;和BOA、AOA、TSA、SSA和PFA相比,MHHO無論是在收斂精度和收斂速度,還是在算法穩定性上,均有顯著優勢,證明了本文改進算法的優越性。

5 工程約束問題

工程設計問題是一個幾何形狀復雜、設計變量多、實際工程約束多的非線性優化問題。本文通過求解實際工程問題對MHHO的性能進行評估。考慮到這些工程設計問題都是包含不等式和等式的約束優化問題,利用罰函數將約束優化問題轉化為無約束優化問題。這些問題包括壓力容器設計問題和拉壓彈簧設計問題,均使用相同的迭代次數(500)和種群(200)來解決這些優化設計問題。每個問題獨立運行30次,并將統計結果與文獻中的其他算法進行比較。

5.1 壓力容器設計問題

圖6所示的壓力容器設計問題是一個典型的混合優化問題,其目標是降低包括成形成本、材料成本和焊接成本在內的總成本。有4個不同的變量:容器厚度Ts(x1)、封頭厚度Th(x2)、內徑R(x3)和容器圓柱截面長度L(x4)。這個問題的數學描述如式(21)～式(24)所示:

Figure 6 Schematic diagram of pressure vessel design

(21)

g2(X)=-x2+0.00954x3≤0

(22)

(23)

g4(X)=x4-240≤0

(24)

約束條件如式(25)所示:

變量范圍:1×0.0625≤x1,

x2≤99×0.0625,10≤x3,x4≤200

(25)

各算法運行結果如表7所示。分析表7中數據可知,MHHO在求解壓力容器設計問題時的尋優精度和穩定性是最好的。MHHO得到的最佳方案是[0.778 2,0.384 7,40.321 0,199.981 2],說明MHHO在處理該工程問題時能獲得最佳結果。

Table 7 Comparison of optimal solutions for pressure vessel design problem

5.2 拉壓彈簧設計問題

拉伸/壓縮彈簧設計問題是一個機械工程設計優化問題,可以用來評價算法的優越性。如圖7所示,此問題的目標是減輕彈簧的重量。它包括4個非線性不等式和3個連續變量:導線直徑w(x1)、線圈平均直徑d(x2)、線圈長度或數量L(x3)。

Figure 7 Schematic design of tension spring design

該問題的數學模型可以用式(26)～式(31)所示來描述:

(26)

(27)

(28)

(29)

(30)

約束條件如式(31)所示:

變量范圍:0.05≤x1≤2,

0.25≤x2≤1.3,2.0≤x3≤15.0

(31)

各算法運行結果如表8所示。分析可知,MHHO在4項統計數據中均表現最好,說明MHHO具有最好的尋優精度和穩定性,MHHO的最佳方案為[0.051 600,0.354 400,11.424 800]。

Table 8 Best solution for tension spring design problem

6 結束語

哈里斯鷹優化算法是近幾年提出的一種新穎的元啟發式算法,其原理簡單易懂,算法本身參數較少,易實現,適合與其他的元啟發式算法進行結合,也適合解決各種高維問題和多極值問題。本文為了能使算法的性能進一步提升,提出了融合多策略改進的哈里斯鷹優化算法。引入了混沌局部搜索策略,提高了算法的開發效率,圍繞單個個體進行擾動,從而找到更好的個體。為了增加種群多樣性,提出了精英備選池策略。最后為了修改種群的進化方向,加入了分布式估計策略,能更好地對優質種群進行采樣獲得其權重值,把種群向更好的方向引導。通過CEC2017測試函數與其他5種新型群智能算法進行比較,實驗結果表明,融合了多策略的哈里斯鷹優化算法的性能得到大幅度提高。今后準備把改進后的HHO算法運用到更多的實際工程問題,為解決各種問題提供另一種可行的思路。