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

唐劍蘭,蔡茂國(guó),徐 翔

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

1 引言

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

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

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

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

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

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

圖1 HHO階段圖

2.1 探索階段

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

(1)

(2)

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

2.2 探索階段過(guò)渡到開(kāi)發(fā)階段

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

(3)

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

2.3 開(kāi)發(fā)階段

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

2.3.1 軟圍攻

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

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

2.3.2 硬圍攻

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

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

(7)

2.3.3 漸進(jìn)式快速俯沖的軟圍攻

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

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

(8)

Y=Y+S×LF(D)

(9)

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

(10)

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

(11)

2.3.4 漸進(jìn)式快速俯沖的硬圍攻

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

(12)

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

(13)

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

(14)

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

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

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

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

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

(15)

(16)

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

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

3.2 對(duì)數(shù)螺旋

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

圖2 飛蛾飛行路徑 圖3 座頭鯨進(jìn)食行為

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

(17)

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

受MFO和WOA算法中對(duì)數(shù)螺旋軌跡的啟發(fā),本文在1.3.1小節(jié)軟圍攻和1.3.2小節(jié)硬圍攻中加入一種對(duì)數(shù)螺旋因子,來(lái)增強(qiáng)算法的局部開(kāi)發(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)表示對(duì)數(shù)螺旋因子,m和n同WOA和MFO中的數(shù)據(jù)保持一致。

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

3.3 ELSHHO算法的流程圖

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

圖4 ELSHHO流程圖

4 實(shí)驗(yàn)與結(jié)果分析

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

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

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

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

4.2 測(cè)試函數(shù)

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

表2 基準(zhǔn)測(cè)試函數(shù)

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

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

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

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

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

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

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

4.4 ELSHHO與其它改進(jìn)HHO算法的比較分析

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

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

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

5 結(jié)論

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