朱 誠,潘旭華,張 勇
(天津商業(yè)大學(xué)信息工程學(xué)院,天津 300134)
群智能優(yōu)化算法是一種模擬自然界中進化機制、行為模式、物理規(guī)律,并建立特定數(shù)學(xué)模型的元啟發(fā)式算法,被廣泛應(yīng)用于模式識別、人工智能、系統(tǒng)控制、信號處理等領(lǐng)域。大量學(xué)者在受到不同生物行為和物理現(xiàn)象的啟發(fā)后,先后提出多種群智能優(yōu)化算法,Rashedi 等提出基于萬有引力定律和牛頓第二定律,通過種群的粒子位置移動來尋找最優(yōu)解的引力搜索算法(Gravitational Search Algorithm,GSA);源于對鳥群捕食的行為,通過群體中個體之間的協(xié)作和信息共享來尋找最優(yōu)解,Kennedy 等提出粒子群優(yōu)化(Particle Swarm Optimization,PSO)算法;Passino受大腸桿菌的群體覓食行為所啟發(fā)而提出細菌覓食優(yōu)化(Bacterial Foraging Optimization,BFO)算法;Mirjalili 等通過模仿鯨魚圍捕獵物時的行為方式,提出鯨優(yōu)化算法(Whale Optimization Algorithm,WOA);Dorigo 等受自然界中螞蟻覓食的群體行為啟發(fā)而提出蟻群(Ant Colony Optimization,ACO)算法。
哈里斯鷹優(yōu)化(Harris Hawks Optimization,HHO)算法是Heidari 等于2019 年提出的一種新型群智能算法,該算法源于哈里斯鷹(又名栗翅鷹)捕食時的群體協(xié)作行為。整個尋優(yōu)過程包括探索、探索與開發(fā)轉(zhuǎn)換和開發(fā)三個階段,具有原理簡單、控制參數(shù)少、全局搜索能力出色等特點;但也存在收斂速度慢、尋優(yōu)精度低、易陷入局部最優(yōu)等缺點。為了克服上述缺點,學(xué)者們提出了不同的優(yōu)化方法,湯安迪等通過引入Tent 混沌映射和精英等級制度策略提升算法收斂速度和精度(Chaos Elite HHO,CEHHO);趙世杰等提出獵物能量的周期性遞減調(diào)控機制,并與牛頓局部增強策略相融合實現(xiàn)改進HHO(Improved HHO,IHHO);Qu 等利用信息交換機制和非線性逃逸能量因子提高種群的多樣性和算法性能;Zhang 等通過對仿真實驗結(jié)果進行評估,從6 種不同的能量更新策略中選出指數(shù)遞減策略作為優(yōu)化方案;馬一鳴等對基于最大似然估計的適應(yīng)度函數(shù)進行改進,有效解決針對室內(nèi)到達時差定位的非線性方程求解問題;Turabieh等通過控制種群分布來改進HHO 算法,并用于預(yù)測學(xué)生潛力;Ismael 等使用基于對立學(xué)習(xí)的HHO 算法(HHO Algorithm based on Opposition-Based Learning,HHOA-OBL)用于超參數(shù)估計和特征選擇;Elsayed 等將HHO 與序列二次規(guī)劃相結(jié)合方法HHO-SQP(hybrid HHO with Sequential Quadratic Programming),實現(xiàn)電源的定向過流繼電器的優(yōu)化協(xié)調(diào);劉小龍等通過多子群方形鄰域拓?fù)浣Y(jié)構(gòu)和固定置換概率來平衡算法的探索、開發(fā);郭雨鑫等利用精英反向?qū)W習(xí)機制和黃金正弦算法提高種群多樣性并減少算法收斂時間;Guo 等利用佳點集和非線性收斂方程對HHO 進行改進;Gupta 等通過引入優(yōu)化的快速俯沖策略和對立學(xué)習(xí)機制提出了HHO 的改進優(yōu)化算法m-HHO(modified HHO)。
本文針對HHO 算法存在的問題提出了一種基于趨化校正的哈里斯鷹優(yōu)化(Chemotaxis Correction HHO,CC-HHO)算法,從5 個方面進行改進:通過識別收斂曲線的狀態(tài),預(yù)測尋優(yōu)的發(fā)展方向;引入基于生物能量消耗的逃逸能量因子E
與跳躍距離J
,使算法更符合生物的規(guī)律特性、更好地平衡算法的探索與開發(fā);通過精英選擇拓展算法全局搜索的廣泛性;引入CC 機制提高局部搜索的精確性;當(dāng)尋優(yōu)陷入停滯時,對種群的逃逸能量施加擾動,強制進入探索階段,幫助算法跳出局部最優(yōu)。HHO 算法作為一種元啟發(fā)式算法,其靈感來自于哈里斯鷹的捕食過程。本章對其基本原理和數(shù)學(xué)模型進行簡要說明。
哈里斯鷹是一種群體捕食動物,所有成員分工合作、協(xié)調(diào)行動。探索階段是一個全局搜索的過程,鷹從空中跟蹤和探測獵物。當(dāng)確定目標(biāo)獵物后,所有成員逐步向獵物位置靠近,圍繞獵物尋找合適的位置。完成包圍,為最后的攻擊做準(zhǔn)備。
所有哈里斯鷹在初始狀態(tài)下隨機出現(xiàn)在搜索空間的某一個位置,并根據(jù)兩種策略向最優(yōu)解移動。令q
為位于(0,1)的隨機數(shù),當(dāng)q
<0.5 時,每只鷹會根據(jù)種群其他成員和獵物的位置進行移動;當(dāng)q
≥0.5 時,哈里斯鷹會隨機棲息在種群活動范圍內(nèi)的某一棵樹上,其數(shù)學(xué)公式如下:N
為種群規(guī)模;X
為種群的平均位置;X
(t
+1)和X
(t
)分別表示第t
+1 次和第t
次迭代后種群所處的位置;X
為種群中隨機選擇的搜索代理的位置;X
為最優(yōu)個體的位置;r
、r
、r
、r
均為(0,1)的隨機數(shù);ub
和lb
分別為種群的上下界。E
來控制,其定義如下:E
為在(-1,1)的能量迭代初始值;T
表示最大迭代次數(shù)。當(dāng) |E
|≥1 時,HHO 算法將進行全局搜索,表示整個種群隨著獵物在整個搜索空間中移動;當(dāng)|E
|<1 時,HHO 算法則轉(zhuǎn)為代表局部搜索的開發(fā)階段。E
和隨機數(shù)r
∈(0,1)來決定使用的策略,r
是獵物的逃脫機會,r
<0.5 表示成功逃脫,r
≥0.5 則是未能成功逃脫。1.3.1 軟包圍
當(dāng) |E
|≥0.5 和r
≥0.5 時,獵物有足夠的體力,試圖通過跳躍逃脫,但最終被捕獲,公式如下:DX
(t
)為最優(yōu)個體和當(dāng)前個體的距離,表示第t
次迭代后鷹群與獵物的位置偏差;r
為(0,1)的隨機數(shù);J
為獵物逃跑過程中的跳躍距離。1.3.2 硬包圍
當(dāng) ||E
<0.5 和r
≥0.5 時,獵物沒有充足的能量,被鷹直接捕獲,公式如下:1.3.3 快速俯沖的軟包圍
當(dāng)|E
|≥0.5 和r
<0.5 時,獵物逃逸能量充沛有機會逃脫,因此鷹群形成一個更加智能的軟包圍圈,實施策略如下:D
為問題維度;S
是一個D
維的隨機向量;LF
為Levy 飛行函數(shù)。計算公式如式(11)所示:ru
和rv
為(0,1)的隨機數(shù),β
是值為1.5 的常量。1.3.4 快速俯沖的硬包圍
當(dāng) |E
|<0.5 和r
<0.5 時,獵物體能不足,但仍有機會逃脫。因此鷹群形成一個硬包圍圈,縮小與獵物的平均距離,采用以下策略進行狩獵:為了克服經(jīng)典HHO 算法存在的缺陷,并提高其尋優(yōu)性能,本章將從以下幾個方面闡述采用的優(yōu)化方法。
在尋優(yōu)過程中,收斂曲線能夠描述每次迭代的搜索結(jié)果及其變化軌跡,所以,分析曲線的變化趨勢并采取相應(yīng)的處理機制可以有效防止搜索陷入局部最優(yōu)。本節(jié)對收斂曲線的趨勢和分類進行說明,并對識別方法和分類規(guī)則進行闡述。
1)設(shè)相鄰兩次迭代之間搜索到最優(yōu)解的下降率為HuntStep
,其數(shù)學(xué)公式如下:t
為迭代計數(shù),Curve
(t
)為第t
次迭代搜索到的最優(yōu)解。2)設(shè)最優(yōu)解變化權(quán)重StepValue
,其值受迭代計數(shù)t
和最優(yōu)解下降率HuntStep
的影響,見表1。表1 最優(yōu)解變化權(quán)重Tab 1 Change weight of optimal solution
3)針對不同的尋優(yōu)階段統(tǒng)計不同數(shù)量的最優(yōu)解變化權(quán)重之和TreadStatus
,公式如下:TreadStatus
的值,識別收斂曲線變化趨勢ConvergenceState
,如表2 所示。表2 收斂曲線變化趨勢說明Tab 2 Explanation of change trend about convergence curve
使用u
個最優(yōu)解變化權(quán)重之和來分析收斂曲線的變化趨勢,是為了排除個別記錄偏離總體趨勢而導(dǎo)致的誤判。結(jié)果表明,該方法能夠較好地預(yù)判陷入局部最優(yōu)的可能性,有助于最終得到更優(yōu)解。ConvergenceState
處于“平緩下降”的前提下,才進行CC。設(shè)隨機方向向量δ
,其每個元素的取值范圍為(-1,1),定義如下:φ
定義如下:che
的定義如下:CC
(i
)為HHO 中第i
個搜索代理的游動步長;D
是每個搜索代理的維數(shù);v
是第v
個變量。反復(fù)游動,直到趨化計數(shù)器ss
達到最大游動步數(shù)Ns
。若f
(che
)<f
(X
(t
)),則與經(jīng)典的HHO 算法相比,此方法使搜索代理有更多的移動機會,因此更有可能獲得最佳結(jié)果。
E
反映對問題最優(yōu)解的搜索能力、決定著全局搜索和局部搜索的切換、影響著開發(fā)階段所采用的策略,其在尋優(yōu)過程中表現(xiàn)為線性遞減的狀態(tài)。Gupta 等提出的m-HHO 優(yōu)化算法為了使搜索獲得更多處于開發(fā)階段的機會,設(shè)置非線性能量因子E
如下:t
為當(dāng)前迭代計數(shù);T
為最大迭代次數(shù);mi
為非線性調(diào)制指數(shù);E
和E
分別為初始和最終能量參數(shù)值。m-HHO 雖然在探索階段將獲得較好的結(jié)果,但是因其放棄的隨機因子,使得算法在廣泛性和魯棒性上有所下降,且以上兩種算法均不符合獵物在逃跑過程中的能量消耗與恢復(fù),以及鷹群與獵物間的多輪博弈的實際情況。獵物在逃跑過程中隨著奔跑距離的增加體能迅速下降,在體能消耗到極限的條件下,通過短暫的休息或停留可以獲得一定程度的恢復(fù),將這個往復(fù)、循環(huán)的過程描述為如下公式:
E
的含義與式(3)相同;st
為(20,100)的隨機數(shù),決定著獵物在逃跑過程中進行體能恢復(fù)的次數(shù)。由圖1 可知,獵物在被追捕過程中的體能消耗的總體趨勢呈下降狀態(tài),而且隨著時間的推移,體力恢復(fù)的上限將會越來越低、恢復(fù)所需時間越來越長。
圖1 逃逸能量因子E的變化曲線Fig.1 Change curve of escape energy factor E
逃逸能量因子E
的變化必然導(dǎo)致其在逃跑過程中的跳躍距離J
產(chǎn)生相應(yīng)的變化,針對逃逸能量因子|E
|與0.5 的關(guān)系,設(shè)置J
如下:E
,上方曲線為跳躍距離J
??梢?,E
與J
的變化是一一對應(yīng)的,獵物在體能充沛時,跳躍距離較遠;體力耗盡時,幾乎跳不動;更加符合生物規(guī)律。圖2 逃逸能量因子E與跳躍距離J的關(guān)系Fig.2 Relationship between escape energy factor E and jump strength J
為了提高HHO 算法的收斂精度和全局搜索能力,本節(jié)在迭代過程中不僅僅記錄搜索到的最優(yōu)解,同時將次優(yōu)解引入尋優(yōu)過程,用于引導(dǎo)其他個體的移動方向。
設(shè)X
和X
分別為通過迭代得到的最優(yōu)解和次優(yōu)解所處的位置,根據(jù)精英選擇機制計算以X
(t
)、X
和X
兩兩組合作為參數(shù),生成的新位置集合LocationES
,計算公式如下:LocationES
中三個新位置的代價函數(shù)適應(yīng)度值,并取出最小值,如式(32)所示:FitnessES
<f
(X
(t
)),則同時更新X
(t
)、X
和X
。E
=1,強制使尋優(yōu)切換到全局探索階段。根據(jù)隨機數(shù)q
的值,搜索代理向上限或下限大范圍移動,公式如下:X
和X
分別為種群中距種群的平均位置X
最遠和最近的個體;r
是位于(0,1)的隨機數(shù);ub
和lb
分別為上下限。當(dāng)q
<0.5 時,搜索代理在X
和上限之間選擇一個位置;q
≥0.5 時,在X
和下限之間選擇一個位置。本節(jié)對上述改進方法在原始HHO 算法中的應(yīng)用以偽代碼形式進行說明。
輸入 種群規(guī)模N
、最大迭代次數(shù)T
。輸出 獵物的位置和其適應(yīng)度值。
N
,迭代T
次,按照算法的執(zhí)行步驟進行算法時間復(fù)雜度分析。1)鷹群初始化,需進行N
次操作,時間復(fù)雜度為O
(N
)。2)計算收斂趨勢,計算2 次,時間復(fù)雜度為O
(2)。3)計算函數(shù)適應(yīng)度,時間復(fù)雜度為O
(1)。4)進行精英選擇求得最優(yōu)解,需要6 次計算、2 次比較,時間復(fù)雜度為O
(8)。5)執(zhí)行群行為。
5.1)計算E
與J
,時間復(fù)雜度為O
(2)。5.2)根據(jù)收斂趨勢,判斷是否進入強制探索,比較1 次,計算1 次移動1 次,時間復(fù)雜度為O
(3)。5.3)確定進入探索或開發(fā),比較1 次,時間復(fù)雜度為O
(1)。5.4)在探索階段,比較1 次,移動1 次,時間復(fù)雜度為O
(2)。5.5)在開發(fā)階段,比較1 次,確定鷹群的攻擊策略,移動1 次,時間復(fù)雜度為O
(2)。5.6)趨化校正,計算3 次,比較1 次。趨化過程中需要試探MaxStep
次,時間復(fù)雜度為O
(4+MaxStep
)。步驟5)循環(huán)N
次,因此其時間復(fù)雜度為O
((14 +MaxStep
)*N
)。經(jīng)歷上述步驟后,改進算法在T
次迭代后的時間復(fù)雜度為:O
(T
*(14 +MaxStep
)*N
)。N
,迭代次數(shù)為T
,需要求解的函數(shù)的維數(shù)為D
,按照算法步驟進行空間復(fù)雜度分析。在改進算法中,X
[N
][D
]存儲種群初始化值,X
[1][D
]存儲優(yōu)化的自變量,Fitness
存儲優(yōu)化函數(shù)值,LocationES
[3][D
]存儲3 個精英自變量,FitnessES
[3][1]存儲3個精英函數(shù)值,HuntStep
[1][T
]存儲每兩次迭代之間的結(jié)果差,StepValue
[1][T
]存儲每次迭代結(jié)果評分,X
[1][D
]存儲種群中隨機選擇的搜索代理所在位置,X
[1][D
]存儲種群的平均位置,δ
[1][D
]存儲隨機方向向量,che
[N
][D
]存儲趨化修正值。因此,整個改進人工魚群算法的空間復(fù)雜度為:2*O
(N
*D
)+7*O
(D
)+2*O
(T
) +O
(3)。本節(jié)通過10 個基準(zhǔn)函數(shù),使用Intel i7-4790、8 GB 內(nèi)存的計算機在Matlab 2012b 仿真平臺上對CC-HHO 算法的尋優(yōu)性能進行測試,并給出實驗結(jié)果及分析?;鶞?zhǔn)函數(shù)分為3 類:F1~F4 為單峰函數(shù),用于評估元啟發(fā)式算法的開發(fā)能力;F5~F8 為多峰函數(shù),F(xiàn)9~F10 為定維多峰函數(shù);F5~F10 均具有一個以上的局部最優(yōu)解,變量數(shù)量以指數(shù)形式增加,用于對算法的探索能力和對局部最優(yōu)的規(guī)避能力進行評價。函數(shù)編號、函數(shù)名、變量數(shù)、變量邊界和理論最優(yōu)解如表3 所示。
表3 基準(zhǔn)函數(shù)信息Tab 3 Information of benchmark functions
Ns
為4。每組測試包含30輪,記錄均值、標(biāo)準(zhǔn)差、最優(yōu)值和最差值,測試結(jié)果見表4。表4 CC-HHO 與其他元啟發(fā)式算法的尋優(yōu)結(jié)果比較Tab 4 Optimization result comparison between CC-HHO and other meta heuristics algorithms
本文所提出CC-HHO 算法的尋優(yōu)能力與其他4 種算法相比都具有很強的競爭力。對于單峰測試函數(shù)F1~F4,CCHHO 的平均值和標(biāo)準(zhǔn)差都大幅優(yōu)于包含HHO 在內(nèi)的其他4種算法,不但最終結(jié)果更好,而且算法穩(wěn)定性更優(yōu)。在多峰函數(shù)和定維多峰函數(shù)方面,從F5~F6 來看,CC-HHO 的均值與HHO 持平,優(yōu)于GSA、PSO、WOA;從F7~F10 來看,CCHHO 獲得令人滿意的結(jié)果,相對于HHO 具有小幅優(yōu)勢。
本節(jié)將CC-HHO 算法與其他4 種改進的HHO 算法CEHHO、IHHO、HHOA-OBL、HHO-SQP進行性能對比分析,迭代次數(shù)為500,每種算法對每個函數(shù)進行30 次測試,收集均值、標(biāo)準(zhǔn)差、最優(yōu)值和最差值作為評價依據(jù),測試結(jié)果如表5 所示。
如表5 所示,CC-HHO 算法在函數(shù)F1~F4 的平均值和最優(yōu)值表現(xiàn)上完全壓制其他4 種改進的HHO 算法。對于F5~F6,因為5 種改進算法都是從HHO 算法的衍生而來,所以搜索性能指標(biāo)基本相同。從函數(shù)F7~F10 的結(jié)果來看,雖然CC-HHO 算法在數(shù)量級上沒有形成巨大優(yōu)勢,但與其他函數(shù)相比仍然更加優(yōu)秀。結(jié)果表明,CC-HHO 算法的準(zhǔn)確度和魯棒性都優(yōu)于其他改進算法。
表5 CC-HHO 與其他改進HHO算法的尋優(yōu)結(jié)果比較Tab 5 Optimization result comparison between CC-HHO and other improved HHO algorithms
圖3 是單峰基準(zhǔn)函數(shù)的收斂曲線,在5 種改進的HHO 算法中,CC-HHO 算法的最終尋優(yōu)結(jié)果最好。F1 和F4 的收斂速度最快,收斂精度最高。在F3,雖然CC-HHO 算法的收斂速度相對較慢,但是依然在尋優(yōu)后期通過CC 找到更優(yōu)解。在F4,能夠明顯看出CC-HHO 算法在迭代初始階段就快速收斂并經(jīng)歷至少兩次陷入局部最優(yōu),但通過“強制探索”跳出。
圖3 單峰函數(shù)的收斂曲線Fig.3 Convergence curves of unimodal functions
圖4 是多峰基準(zhǔn)函數(shù)的比較,對于F7,CC-HHO 算法比HHO-SQP 和HHOA-OBL 收斂速度稍慢;對于F5、F6、F8,CCHHO 算法收斂最快,收斂精度也很突出,當(dāng)其他改進的HHO算法陷入局部最優(yōu),沒有機會搜索到更好的解時,CC-HHO 算法通過分析收斂趨勢、精英選擇、趨化校正尋找到更優(yōu)解。
圖4 多峰函數(shù)的收斂曲線Fig.4 Convergence curves of multimodal functions
圖5 為5 種改進的HHO 算法在定維多峰函數(shù)F9~F10 的尋優(yōu)收斂曲線,最終尋優(yōu)結(jié)果處于同一數(shù)量級。F10 表明CC-HHO 算法具有最佳的收斂速度和最終解。
圖5 定維多峰函數(shù)的收斂曲線Fig.5 Convergence curves of fixed-dimensional multimodal functions
為了克服HHO 算法的缺點,提高算法的尋優(yōu)性能,通過識別收斂曲線狀態(tài)、趨化校正、引入基于生物能量消耗的逃逸能量因子、精英選擇、強制探索的途徑進行優(yōu)化和提出改進算法。并通過10 個基準(zhǔn)函數(shù)進行測試。對比其他元啟發(fā)式算法和改進的HHO 算法,仿真結(jié)果和收斂曲線表明,本文CC-HHO 算法在單峰函數(shù)上展現(xiàn)出超強的尋優(yōu)能力;在多峰函數(shù)和定維多峰函數(shù)上,除所有參與比較算法均能找到理論最優(yōu)解的情況,本文CC-HHO 算法在收斂精度上具有一定優(yōu)勢。綜上說明,本文算法在探索、開發(fā)和避免局部最優(yōu)方面具有競爭力,提高了原算法的搜索效率和魯棒性。但是多模態(tài)基準(zhǔn)函數(shù)的尋優(yōu)表現(xiàn)不如單峰基準(zhǔn)函數(shù),有待于進一步研究。