唐劍蘭,蔡茂國,徐 翔

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

1 引言

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

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

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

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

2 哈里斯鷹優(yōu)化算法

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

圖1 HHO階段圖

2.1 探索階段

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

(1)

(2)

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

2.2 探索階段過渡到開發(fā)階段

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

(3)

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

2.3 開發(fā)階段

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

2.3.1 軟圍攻

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

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之間的一個隨機數(shù),表示獵物在逃跑過程中的跳躍強度。

2.3.2 硬圍攻

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

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

(7)

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

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

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

(8)

Y=Y+S×LF(D)

(9)

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

(10)

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

(11)

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

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

(12)

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

(13)

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

(14)

3 基于精英反向?qū)W習(xí)和對數(shù)螺旋的HHO算法

3.1 精英反向?qū)W習(xí)

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

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

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

(15)

(16)

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

本文在初始種群和每次種群迭代時都引入精英反向?qū)W習(xí)機制,通過該方法可以擴大種群的探索范圍,使得算法在更廣的范圍內(nèi)找到質(zhì)量更優(yōu)的解,提高種群的豐富性和算法的收斂速度。

3.2 對數(shù)螺旋

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

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

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

(17)

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

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

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)表示對數(shù)螺旋因子,m和n同WOA和MFO中的數(shù)據(jù)保持一致。

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

3.3 ELSHHO算法的流程圖

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

圖4 ELSHHO流程圖

4 實驗與結(jié)果分析

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

4.1 參數(shù)設(shè)置

參數(shù)設(shè)置見表1。

表1 參數(shù)設(shè)置

4.2 測試函數(shù)

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

表2 基準測試函數(shù)

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

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

表3 ELSHHO與其它元啟發(fā)式算法的測試結(jié)果比較

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

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

圖5 測試函數(shù)的收斂曲線圖

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

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

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

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

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

5 結(jié)論

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