基于精英反向學習和對數螺旋的HHO算法

唐劍蘭,蔡茂國,徐 翔

(深圳大學電子與信息工程學院,廣東 深圳 518000)

1 引言

在計算機科學、工程設計、運籌學、能源、商業及其應用等眾多領域都有亟需解決的優化問題,然而,在當今時代和科技的發展背景下,優化問題變得錯綜復雜,梯度下降法和牛頓法等傳統的數學方法難以去解決這些繁雜問題[1]。元啟發式算法因其原理簡單、靈活性高、易于實現等優點,被廣泛的應用于處理優化問題。常見的元啟發式算法有:基于進化的遺傳算法和差分進化算法、基于物理的重力搜索算法和模擬退火算法、基于人類的腦風暴優化和基于教學學習的優化算法、基于種群的灰狼優化算法和鯨魚優化算法等。

哈里斯鷹優化(Harris Hawks Optimization,HHO)[2]是近些年來一種比較新穎的基于種群的元啟發式算法,因其具有修改參數少,擴展性好,尋優能力強的特點,故現在已在圖像去噪[3]、特征選擇[4]、資源調度[5]、深度學習[6]、軌道優化[7]等多個領域得到應用。

然而,HHO算法也會存在和其它群優化算法一樣的“通病”,如易陷入局部最優、求解精度低。國內外一些學者對其進行研究改進,Dhawale D等人[8]提出一種改進的混沌哈里斯鷹優化算法(CHHO),即將帳篷混沌策略與傳統HHO相結合來增強HHO的局部搜索能力。Al-Betar等人[9]結合進化算法的適者生存原則,在探索階段采用錦標賽、比例和線性排名三種策略對HHO進行改進,其中錦標賽哈里斯鷹優化算法(THHO)性能最佳。Hussain K等人[10]提出一種具有長期記憶的HHO算法(LMHHO),即將多個有希望的搜索區域記憶存檔,群體可以根據多種過去的經驗來決定下一步行動,使得算法在探索和開發之間保持平衡。胡等人[11]受粒子群優化算法的啟發,將速度加入到HHO的探索階段,再利用人工樹算法的交叉算子改進HHO中漸進式快速俯沖的軟圍攻和漸進式快速俯沖的硬圍攻,得到一種改進的哈里斯鷹優化算法(IHHO)。

上述研究在一定程度上提升了HHO的性能,同時表明對HHO性能進行改進和提高具有意義性和研究性,故本文提出一種基于精英反向學習和對數螺旋的哈里斯鷹優化算法(Elite Opposition-Based Learning and Logarithmic Spiral Harris Hawks Optimization,ELSHHO)。

2 哈里斯鷹優化算法

HHO算法是對哈里斯鷹尋找和捕捉獵物過程中的協作行為進行數學建模,主要包含探索階段及開發階段,各個階段的流程如圖1所示。

圖1 HHO階段圖

2.1 探索階段

哈里斯鷹隨機棲息在某些位置,并根據兩種策略探測獵物,策略選擇由隨機數q決定。當q<0.5時,哈里斯鷹會根據其它成員和獵物的位置進行棲息;當q≥0.5時,哈里斯鷹會隨機棲息在鷹群活動范圍內的大樹上,具體模型為

(1)

(2)

其中,X(t+1)表示哈里斯鷹在下一次迭代過程中的位置,X(t)表示哈里斯鷹在本次迭代過程中的位置,Xb(t)表示獵物的位置(即擁有最優適應度的個體位置),Xr(t)表示當前種群中隨機選擇的哈里斯鷹的位置,XAvg(t)表示當前種群的平均位置,ω=r3(LB+r4(UB-LB)),r和q表示介于0到1之間的隨機數,LB、UB分別是探索空間的上限和下限,N為種群的數量。

2.2 探索階段過渡到開發階段

HHO算法根據獵物的逃逸能量E來判斷HHO處于全局探索階段還是局部開發階段,其數學公式如下

(3)

其中,E0被設置為-1～1之間的一個隨機數,代表獵物能量的原始狀態;t表示當前迭代次數;T則表示最大迭代次數。若|E|≥1時,哈里斯鷹將繼續探索以確定獵物的位置;若|E|<1時,表示獵物位置已確定,執行開發階段,哈里斯鷹開始逮捕獵物。

2.3 開發階段

HHO根據E和獵物逃脫概率r制定了四種策略。當r<0.5時,表示成功逃脫,當r≥0.5時,表示逃脫失敗。

2.3.1 軟圍攻

當r≥0.5且|E|≥0.5時,表示獵物此時能量充沛,試圖擺脫哈里斯鷹的追捕,但最終未逃脫成功,哈里斯鷹發動突襲并進行軟圍攻,獵物被軟包圍,位置更新公式如下

X(t+1)=ΔX(t)-E|J×Xb(t)-X(t)|

(4)

J=2(1-r5)

(5)

ΔX(t)=Xb(t)-X(t)

(6)

其中,J是介于0～2之間的一個隨機數,表示獵物在逃跑過程中的跳躍強度。

2.3.2 硬圍攻

當r≥0.5且|E|<0.5時,獵物逃跑能量消耗殆盡,哈里斯鷹將在發起最后突襲時進行猛烈圍攻,獵物被直接捕獲,位置由以下公式更新

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

(7)

2.3.3 漸進式快速俯沖的軟圍攻

當r<0.5且|E|≥0.5時,獵物能量充沛并且成功逃脫哈里斯鷹的追捕,因此哈里斯鷹采用漸進式快速軟包圍圈來進行包圍,其數學描述如下:

Y=Xb(t)-E|J×Xb(t)-X(t)|

(8)

Y=Y+S×LF(D)

(9)

其中,D表示當前問題維度,S是大小為1×D的隨機向量,LF為萊維飛行函數,如等式(10)所示。

(10)

其中,μ和ν為0～1之間的隨機數,β=1.5,該位置由以下公式更新

(11)

2.3.4 漸進式快速俯沖的硬圍攻

當r<0.5且|E|<0.5時,模擬獵物逃逸能量不足但卻成功逃脫的情況,此時哈里斯鷹快速發起突襲并進行猛烈硬包圍,其數學模型為

(12)

Y′=Xb(t)-E|J×Xb(t)-XAvg(t)|

(13)

Z′=Y′+S×LF(D)

(14)

3 基于精英反向學習和對數螺旋的HHO算法

3.1 精英反向學習

算法的收斂速度和求解精度會受種群質量優劣的影響,若種群的值不在所求空間而在它相反空間,則會加大算法的尋優難度,甚至找不到最優解,因而種群的初始化和位置更新是種群優化算法中的重要一環。目前有許多學者采用反向學習和精英反向學習的方法來對其進行改進,如文獻[12-14]。

反向學習(Opposition-Based Learning,OBL)是Tizhoosh[15]提出的一種機器智能策略,將其應用在初始化種群中可以有效提高解的質量。精英反向學習(Elite Opposition-Based Learning,EOBL)是在反向學習的基礎上對其改進,它是通過種群中的精英個體來求解反向個體,再從候選方案內選取優秀個體(適應值更高的個體)來形成新的種群。

傳統HHO算法初始化種群時是一個隨機的過程,存在較大的偶然性和盲目性,因而會造成種群多樣性低和收斂速度慢等缺點,為此本文采用精英反向學習策略來對其改進,具體步驟如下:

(15)

(16)

3)合并當前種群和精英反向種群,并對其適應值進行排序,選取前N個優秀個體作為新的種群。

本文在初始種群和每次種群迭代時都引入精英反向學習機制,通過該方法可以擴大種群的探索范圍,使得算法在更廣的范圍內找到質量更優的解,提高種群的豐富性和算法的收斂速度。

3.2 對數螺旋

在元啟發式領域,對數螺旋(Logarithmic Spiral,LS)這一概念被Mirjalili等人在2015年和2016年分別應用于飛蛾火焰優化算法(MFO)[16]和鯨魚優化算法(WOA)[17]。MFO的靈感起源于飛蛾飛行這一行為,飛蛾實際上是通過與自然光源保持相對固定的角度來進行飛行,但由于人造光源會擾亂飛蛾的視線,通常觀察到的飛蛾在光源附近是呈螺旋狀飛行的,如圖2[15]。WOA是一種模仿鯨魚捕食行為的優化算法,它使用螺旋狀來模擬座頭鯨的泡沫網攻擊機制,如圖3[16]。將螺旋飛行運動的數學模型集成到MFO和WOA中可以有效的提高算法的空間搜索能力,具體公式如式(17)所示

圖2 飛蛾飛行路徑 圖3 座頭鯨進食行為

Xt+1=|Xbest-Xt|×emn×cos(2πn)+Xbest

(17)

其中,Xbest表示最優解的位置向量,m表示對數螺旋常數,n表示路徑系數,在WOA和MFO中m=1,n是(-1,1)之間的一個隨機數。

受MFO和WOA算法中對數螺旋軌跡的啟發,本文在1.3.1小節軟圍攻和1.3.2小節硬圍攻中加入一種對數螺旋因子,來增強算法的局部開發性能,位置更新公式如下

X(t+1)=δ×(ΔX(t)-E|J×Xb(t)-X(t)|)

(18)

X(t+1)=δ×(Xb(t)-E|ΔX(t)|)

(19)

其中,δ=emn×cos(2πn)表示對數螺旋因子,m和n同WOA和MFO中的數據保持一致。

引入對數螺旋因子后,哈里斯鷹群將以對數螺旋飛行的方式去逮捕獵物,不容易被局部最優值所困,擴展了算法的局部搜索技術,增強了ELSHHO算法的定位能力,有效提高收斂速度和尋優精度。

3.3 ELSHHO算法的流程圖

綜上所述,ELSHHO的流程圖如圖4所示。

圖4 ELSHHO流程圖

4 實驗與結果分析

實驗運行環境為Windows 10(64位)操作系統、Intel(R) Core(TM)i5-6200U CPU、2.40GHz主頻、4G 內存,算法在MATLABR2018b編程和運行。

4.1 參數設置

參數設置見表1。

表1 參數設置

4.2 測試函數

本文選用10個國際上通用的基準測試函數來測試ELSHHO的性能。如表2所示,其中f 1-f5為單峰函數,故常用來測試算法的開發能力,f6-f 10為多峰函數,故用來檢驗算法的探索能力和避免局部最優的能力,所有基準函數的維度為30,理論最優值為0。

表2 基準測試函數

4.3 ELSHHO與其它元啟發式算法的比較分析

為了驗證ELSHHO的有效性與優越性,本節選擇PSO[18]、GWO[19]、MFO[16]、WOA[17]、以及傳統 HHO[2]進行對比分析。為保證實驗的公平性,各算法的共有參數設置同4.1節一致,其它參數設置和原文獻一致,記錄最優值、平均值、標準差,測試結果見表3,其中尋優結果最好的值用粗體表示。

表3 ELSHHO與其它元啟發式算法的測試結果比較

由表3可知,本文所提出ELSHHO的尋優能力明顯優于PSO、GWO、MFO、WOA、HHO。對于函數F1-F4,ELSHHO可以直接搜索到最優值,尋優效果大幅度優于所有對比算法。對于函數F5、F9、F10,所有算法的均值相近,但ELSHHO的最優值略優于其它算法,這表明改進的算法對問題空間的探索和開發更加充分。對于函數F6,ELSHHO、HHO、WOA均能搜索到最優值,性能優于PSO、GWO、MFO。對于函數F7,ELSHHO與GWO、WOA、HHO的值相差不大,略優于PSO、MFO。對于函數F8,ELSHHO、HHO均能搜索到最優值,性能優于PSO、GWO、MFO 、WOA。10個基準測試函數中,除了函數F5、F9、F10,ELSHHO在其余7個函數上的標準差均為0,這表明ELSHHO具有較強的穩定性。以上實驗結果分析證明,所提出ELSHHO有較強的尋優性和穩定性。

為了進一步闡述ELSHHO的收斂性能,給出部分基準函數的收斂曲線圖,如圖5所示。

圖5 測試函數的收斂曲線圖

從函數F1-F3的收斂曲線圖可直觀的看到ELSHHO的收斂速度和收斂精度都明顯優于PSO、GWO、MFO、WOA、HHO。從函數F6可以看出,雖然ELSHHO、HHO、WOA的搜索精度一樣,但ELSHHO的收斂速度快于HHO、WOA。對于函數F7,雖然ELSHHO與GWO、WOA、HHO的尋優精度旗鼓相當,但是ELSHHO的收斂速度快于其它算法。對于函數F8,ELSHHO在迭代50次之前就已經收斂到最優值,HHO在迭代200次之后才收斂到最優值,雖然兩者的搜索精度一樣,但ELSHHO比HHO的收斂速度更快。

4.4 ELSHHO與其它改進HHO算法的比較分析

為了驗證ELSHHO與其它改進HHO算法的優劣性,本文選擇與CHHO[8]、THHO[9]、LMHHO[10]、IHHO[11]進行對比分析。各算法的共有參數同4.1節一致,其它參數設置和原文獻一致,對比結果見表4,其中“-”表示原文獻中沒有出現的。

表4 ELSHHO與其它改進的HHO算法的測試結果比較

如表4所示,ELSHHO在函數F2、F3、F4的最優值、平均值和標準差大幅度優于其它4種改進的算法。對于函數F1,ELSHHO、LMHHO的尋優精度相同,比CHHO、THHO、IHHO仍有巨大優勢。對于函數F6-F8,因為5種算法都是在HHO的基礎上改進而來,故性能指標一致。對于函數F5、F9、F10,所有改進算法相差不大,但ELSHHO的性能略優于其它改進算法。結果表明,ELSHHO算法的精確度和穩定性整體上優于其它4種改進的HHO算法。

5 結論

本文提出一種基于精英反向學習和對數螺旋的改進哈里斯鷹算法(ELSHHO)來克服傳統哈里斯鷹算法的不足并進一步提升HHO算法的性能。在初始種群和每次種群迭代時都引入精英反向學習機制,提高種群的多樣性和種群的質量。在開發階段,引入對數螺旋因子來幫助種群進行局部搜索,指引種群更新位置,提高尋優性能。并通過10 個基準函數進行測試,將ELSHHO算法與其它5種元啟發式算法和4種改進的HHO算法進行對比分析,實驗結果表明,ELSHHO算法的收斂速度和解的精度較原始算法有了較大提升且優于絕大部分對比算法。