基于趨化校正的哈里斯鷹優化算法

朱 誠，潘旭華，張 勇

（天津商業大學信息工程學院，天津 300134）

0 引言

群智能優化算法是一種模擬自然界中進化機制、行為模式、物理規律，并建立特定數學模型的元啟發式算法，被廣泛應用于模式識別、人工智能、系統控制、信號處理等領域。大量學者在受到不同生物行為和物理現象的啟發后，先后提出多種群智能優化算法，Rashedi 等提出基于萬有引力定律和牛頓第二定律，通過種群的粒子位置移動來尋找最優解的引力搜索算法（Gravitational Search Algorithm，GSA）；源于對鳥群捕食的行為，通過群體中個體之間的協作和信息共享來尋找最優解，Kennedy 等提出粒子群優化（Particle Swarm Optimization，PSO）算法；Passino受大腸桿菌的群體覓食行為所啟發而提出細菌覓食優化（Bacterial Foraging Optimization，BFO）算法；Mirjalili 等通過模仿鯨魚圍捕獵物時的行為方式，提出鯨優化算法（Whale Optimization Algorithm，WOA）；Dorigo 等受自然界中螞蟻覓食的群體行為啟發而提出蟻群（Ant Colony Optimization，ACO）算法。

哈里斯鷹優化（Harris Hawks Optimization，HHO）算法是Heidari 等于2019 年提出的一種新型群智能算法，該算法源于哈里斯鷹（又名栗翅鷹）捕食時的群體協作行為。整個尋優過程包括探索、探索與開發轉換和開發三個階段，具有原理簡單、控制參數少、全局搜索能力出色等特點；但也存在收斂速度慢、尋優精度低、易陷入局部最優等缺點。為了克服上述缺點，學者們提出了不同的優化方法，湯安迪等通過引入Tent 混沌映射和精英等級制度策略提升算法收斂速度和精度（Chaos Elite HHO，CEHHO）；趙世杰等提出獵物能量的周期性遞減調控機制，并與牛頓局部增強策略相融合實現改進HHO（Improved HHO，IHHO）；Qu 等利用信息交換機制和非線性逃逸能量因子提高種群的多樣性和算法性能；Zhang 等通過對仿真實驗結果進行評估，從6 種不同的能量更新策略中選出指數遞減策略作為優化方案；馬一鳴等對基于最大似然估計的適應度函數進行改進，有效解決針對室內到達時差定位的非線性方程求解問題；Turabieh等通過控制種群分布來改進HHO 算法，并用于預測學生潛力；Ismael 等使用基于對立學習的HHO 算法（HHO Algorithm based on Opposition-Based Learning，HHOA-OBL）用于超參數估計和特征選擇；Elsayed 等將HHO 與序列二次規劃相結合方法HHO-SQP（hybrid HHO with Sequential Quadratic Programming），實現電源的定向過流繼電器的優化協調；劉小龍等通過多子群方形鄰域拓撲結構和固定置換概率來平衡算法的探索、開發；郭雨鑫等利用精英反向學習機制和黃金正弦算法提高種群多樣性并減少算法收斂時間；Guo 等利用佳點集和非線性收斂方程對HHO 進行改進；Gupta 等通過引入優化的快速俯沖策略和對立學習機制提出了HHO 的改進優化算法m-HHO（modified HHO）。

本文針對HHO 算法存在的問題提出了一種基于趨化校正的哈里斯鷹優化（Chemotaxis Correction HHO，CC-HHO）算法，從5 個方面進行改進：通過識別收斂曲線的狀態，預測尋優的發展方向；引入基于生物能量消耗的逃逸能量因子

E

與跳躍距離

J

，使算法更符合生物的規律特性、更好地平衡算法的探索與開發；通過精英選擇拓展算法全局搜索的廣泛性；引入CC 機制提高局部搜索的精確性；當尋優陷入停滯時，對種群的逃逸能量施加擾動，強制進入探索階段，幫助算法跳出局部最優。

1 HHO算法的介紹

HHO 算法作為一種元啟發式算法，其靈感來自于哈里斯鷹的捕食過程。本章對其基本原理和數學模型進行簡要說明。

1.1 探索階段

哈里斯鷹是一種群體捕食動物，所有成員分工合作、協調行動。探索階段是一個全局搜索的過程，鷹從空中跟蹤和探測獵物。當確定目標獵物后，所有成員逐步向獵物位置靠近，圍繞獵物尋找合適的位置。完成包圍，為最后的攻擊做準備。

所有哈里斯鷹在初始狀態下隨機出現在搜索空間的某一個位置，并根據兩種策略向最優解移動。令

q

為位于（0，1）的隨機數，當

q

＜0.5 時，每只鷹會根據種群其他成員和獵物的位置進行移動；當

q

≥0.5 時，哈里斯鷹會隨機棲息在種群活動范圍內的某一棵樹上，其數學公式如下：

其中：

N

為種群規模；

X

為種群的平均位置；

X

（

t

+1）和

X

（

t

）分別表示第

t

+1 次和第

t

次迭代后種群所處的位置；

X

為種群中隨機選擇的搜索代理的位置；

X

為最優個體的位置；

r

、

r

、

r

、

r

均為（0，1）的隨機數；

ub

和

lb

分別為種群的上下界。

1.2 探索與開發轉換階段

哈里斯鷹優化算法從全局搜索與局部搜索的轉換主要依靠逃逸能量因子

E

來控制，其定義如下：

其中：

E

為在（-1，1）的能量迭代初始值；

T

表示最大迭代次數。當 |

E

|≥1 時，HHO 算法將進行全局搜索，表示整個種群隨著獵物在整個搜索空間中移動；當|

E

|＜1 時，HHO 算法則轉為代表局部搜索的開發階段。

1.3 開發階段

在對目標獵物完成包圍后，鷹群在開發階段將進行攻擊。根據獵物的逃逸行為和哈里斯鷹的追逐策略，HHO 算法使用四種不同的策略來模擬攻擊，并通過逃逸能量因子

E

和隨機數

r

∈(0，1)來決定使用的策略，

r

是獵物的逃脫機會，

r

＜0.5 表示成功逃脫，

r

≥0.5 則是未能成功逃脫。

1.3.1 軟包圍

當 |

E

|≥0.5 和

r

≥0.5 時，獵物有足夠的體力，試圖通過跳躍逃脫，但最終被捕獲，公式如下：

其中：

DX

（

t

）為最優個體和當前個體的距離，表示第

t

次迭代后鷹群與獵物的位置偏差；

r

為（0，1）的隨機數；

J

為獵物逃跑過程中的跳躍距離。

1.3.2 硬包圍

當 ||

E

＜0.5 和

r

≥0.5 時，獵物沒有充足的能量，被鷹直接捕獲，公式如下：

1.3.3 快速俯沖的軟包圍

當|

E

|≥0.5 和

r

＜0.5 時，獵物逃逸能量充沛有機會逃脫，因此鷹群形成一個更加智能的軟包圍圈，實施策略如下：

其中：

D

為問題維度；

S

是一個

D

維的隨機向量；

LF

為Levy 飛行函數。計算公式如式（11）所示：

其中：

ru

和

rv

為（0，1）的隨機數，

β

是值為1.5 的常量。

1.3.4 快速俯沖的硬包圍

當 |

E

|＜0.5 和

r

＜0.5 時，獵物體能不足，但仍有機會逃脫。因此鷹群形成一個硬包圍圈，縮小與獵物的平均距離，采用以下策略進行狩獵：

2 改進的HHO算法

為了克服經典HHO 算法存在的缺陷，并提高其尋優性能，本章將從以下幾個方面闡述采用的優化方法。

2.1 識別收斂趨勢

在尋優過程中，收斂曲線能夠描述每次迭代的搜索結果及其變化軌跡，所以，分析曲線的變化趨勢并采取相應的處理機制可以有效防止搜索陷入局部最優。本節對收斂曲線的趨勢和分類進行說明，并對識別方法和分類規則進行闡述。

1）設相鄰兩次迭代之間搜索到最優解的下降率為

HuntStep

，其數學公式如下：

其中：

t

為迭代計數，

Curve

（

t

）為第

t

次迭代搜索到的最優解。2）設最優解變化權重

StepValue

，其值受迭代計數

t

和最優解下降率

HuntStep

的影響，見表1。

表1 最優解變化權重Tab 1 Change weight of optimal solution

3）針對不同的尋優階段統計不同數量的最優解變化權重之和

TreadStatus

，公式如下：

4）根據

TreadStatus

的值，識別收斂曲線變化趨勢

ConvergenceState

，如表2 所示。

表2 收斂曲線變化趨勢說明Tab 2 Explanation of change trend about convergence curve

使用

u

個最優解變化權重之和來分析收斂曲線的變化趨勢，是為了排除個別記錄偏離總體趨勢而導致的誤判。結果表明，該方法能夠較好地預判陷入局部最優的可能性，有助于最終得到更優解。

2.2 趨化校正

在HHO 算法中，一個搜索代理每次迭代中只能移動一次位置。本節利用BFO 算法的CC 機制，提高HHO 局部搜索能力。由于CC 會增加算法尋優的時間消耗，為了平衡尋優精度和效率，只在軟包圍和硬包圍兩種策略中，且收斂曲線狀態

ConvergenceState

處于“平緩下降”的前提下，才進行CC。設隨機方向向量

δ

，其每個元素的取值范圍為（-1，1），定義如下：

設隨機游動方向

φ

定義如下：

通過趨化機制對搜索代理的位置進行校正，設

che

的定義如下：

其中：

CC

（

i

）為HHO 中第

i

個搜索代理的游動步長；

D

是每個搜索代理的維數；

v

是第

v

個變量。反復游動，直到趨化計數器

ss

達到最大游動步數

Ns

。若

f

（

che

）＜

f

（

X

（

t

）），則

與經典的HHO 算法相比，此方法使搜索代理有更多的移動機會，因此更有可能獲得最佳結果。

2.3 基于生物能量消耗的逃逸能量因子E與跳躍距離J

在HHO 算法中，逃逸能量因子

E

反映對問題最優解的搜索能力、決定著全局搜索和局部搜索的切換、影響著開發階段所采用的策略，其在尋優過程中表現為線性遞減的狀態。Gupta 等提出的m-HHO 優化算法為了使搜索獲得更多處于開發階段的機會，設置非線性能量因子

E

如下：

其中：

t

為當前迭代計數；

T

為最大迭代次數；

mi

為非線性調制指數；

E

和

E

分別為初始和最終能量參數值。

m-HHO 雖然在探索階段將獲得較好的結果，但是因其放棄的隨機因子，使得算法在廣泛性和魯棒性上有所下降，且以上兩種算法均不符合獵物在逃跑過程中的能量消耗與恢復，以及鷹群與獵物間的多輪博弈的實際情況。獵物在逃跑過程中隨著奔跑距離的增加體能迅速下降，在體能消耗到極限的條件下，通過短暫的休息或停留可以獲得一定程度的恢復，將這個往復、循環的過程描述為如下公式：

其中：

E

的含義與式（3）相同；

st

為（20，100）的隨機數，決定著獵物在逃跑過程中進行體能恢復的次數。

由圖1 可知，獵物在被追捕過程中的體能消耗的總體趨勢呈下降狀態，而且隨著時間的推移，體力恢復的上限將會越來越低、恢復所需時間越來越長。

圖1 逃逸能量因子E的變化曲線Fig.1 Change curve of escape energy factor E

逃逸能量因子

E

的變化必然導致其在逃跑過程中的跳躍距離

J

產生相應的變化，針對逃逸能量因子|

E

|與0.5 的關系，設置

J

如下：

如圖2 所示，下方曲線為逃逸能量因子

E

，上方曲線為跳躍距離

J

?？梢?，

E

與

J

的變化是一一對應的，獵物在體能充沛時，跳躍距離較遠；體力耗盡時，幾乎跳不動；更加符合生物規律。

圖2 逃逸能量因子E與跳躍距離J的關系Fig.2 Relationship between escape energy factor E and jump strength J

2.4 精英選擇

為了提高HHO 算法的收斂精度和全局搜索能力，本節在迭代過程中不僅僅記錄搜索到的最優解，同時將次優解引入尋優過程，用于引導其他個體的移動方向。

設

X

和

X

分別為通過迭代得到的最優解和次優解所處的位置，根據精英選擇機制計算以

X

（

t

）、

X

和

X

兩兩組合作為參數，生成的新位置集合

LocationES

，計算公式如下：

分別計算集合

LocationES

中三個新位置的代價函數適應度值，并取出最小值，如式（32）所示：

若

FitnessES

＜

f

（

X

（

t

）），則同時更新

X

（

t

）、

X

和

X

。

2.5 強制進入探索階段

在迭代后期，如果收斂曲線的狀態為“平緩下降”或“水平線”，則說明搜索即將陷入局部最優或已經陷入局部最優，通過令逃逸能量因子

E

=1，強制使尋優切換到全局探索階段。根據隨機數

q

的值，搜索代理向上限或下限大范圍移動，公式如下：

其中：

X

和

X

分別為種群中距種群的平均位置

X

最遠和最近的個體；

r

是位于（0，1）的隨機數；

ub

和

lb

分別為上下限。當

q

＜0.5 時，搜索代理在

X

和上限之間選擇一個位置；

q

≥0.5 時，在

X

和下限之間選擇一個位置。

3 算法偽代碼與時空復雜度分析

3.1 算法偽代碼

本節對上述改進方法在原始HHO 算法中的應用以偽代碼形式進行說明。

輸入 種群規模

N

、最大迭代次數

T

。

輸出 獵物的位置和其適應度值。

3.2 時間復雜度分析

設改進算法的種群規模為

N

，迭代

T

次，按照算法的執行步驟進行算法時間復雜度分析。1）鷹群初始化，需進行

N

次操作，時間復雜度為

O

（

N

）。2）計算收斂趨勢，計算2 次，時間復雜度為

O

（2）。3）計算函數適應度，時間復雜度為

O

（1）。4）進行精英選擇求得最優解，需要6 次計算、2 次比較，時間復雜度為

O

（8）。

5）執行群行為。

5.1）計算

E

與

J

，時間復雜度為

O

（2）。5.2）根據收斂趨勢，判斷是否進入強制探索，比較1 次，計算1 次移動1 次，時間復雜度為

O

（3）。5.3）確定進入探索或開發，比較1 次，時間復雜度為

O

（1）。5.4）在探索階段，比較1 次，移動1 次，時間復雜度為

O

（2）。5.5）在開發階段，比較1 次，確定鷹群的攻擊策略，移動1 次，時間復雜度為

O

（2）。5.6）趨化校正，計算3 次，比較1 次。趨化過程中需要試探

MaxStep

次，時間復雜度為

O

(4+

MaxStep

)。步驟5）循環

N

次，因此其時間復雜度為

O

((14 +

MaxStep

)*

N

)。經歷上述步驟后，改進算法在

T

次迭代后的時間復雜度為：

O

(

T

*(14 +

MaxStep

)*

N

)。

3.3 改進算法空間復雜度分析

空間復雜度是用算法執行時占用存儲空間來衡量的，設鷹群的規模為

N

，迭代次數為

T

，需要求解的函數的維數為

D

，按照算法步驟進行空間復雜度分析。在改進算法中，

X

［

N

］［

D

］存儲種群初始化值，

X

［1］［

D

］存儲優化的自變量，

Fitness

存儲優化函數值，

LocationES

［3］［

D

］存儲3 個精英自變量，

FitnessES

［3］［1］存儲3個精英函數值，

HuntStep

［1］［

T

］存儲每兩次迭代之間的結果差，

StepValue

［1］［

T

］存儲每次迭代結果評分，

X

［1］［

D

］存儲種群中隨機選擇的搜索代理所在位置，

X

［1］［

D

］存儲種群的平均位置，

δ

［1］［

D

］存儲隨機方向向量，

che

［

N

］［

D

］存儲趨化修正值。因此，整個改進人工魚群算法的空間復雜度為：2*

O

(

N

*

D

)+7*

O

(

D

)+2*

O

(

T

) +

O

(3)。

4 實驗與結果分析

本節通過10 個基準函數，使用Intel i7-4790、8 GB 內存的計算機在Matlab 2012b 仿真平臺上對CC-HHO 算法的尋優性能進行測試，并給出實驗結果及分析?；鶞屎瘮捣譃? 類：F1～F4 為單峰函數，用于評估元啟發式算法的開發能力；F5～F8 為多峰函數，F9～F10 為定維多峰函數；F5～F10 均具有一個以上的局部最優解，變量數量以指數形式增加，用于對算法的探索能力和對局部最優的規避能力進行評價。函數編號、函數名、變量數、變量邊界和理論最優解如表3 所示。

表3 基準函數信息Tab 3 Information of benchmark functions

4.1 CC-HHO算法與其他元啟發式優化算法比較

本節將CC-HHO 算法與包括經典HHO 算法在內的其他4 種元啟發式優化算法GSA、PSO、WOA和HHO進行比較。為了便于不同算法進行橫向比較，所有實驗參數均采用和原始HHO 算法相同的設置，即：種群數為30，迭代次數為500。為了平衡算法時間復雜度和局部搜索的細致性，趨化操作中單向運動的最大步數

Ns

為4。每組測試包含30輪，記錄均值、標準差、最優值和最差值，測試結果見表4。

表4 CC-HHO 與其他元啟發式算法的尋優結果比較Tab 4 Optimization result comparison between CC-HHO and other meta heuristics algorithms

本文所提出CC-HHO 算法的尋優能力與其他4 種算法相比都具有很強的競爭力。對于單峰測試函數F1～F4，CCHHO 的平均值和標準差都大幅優于包含HHO 在內的其他4種算法，不但最終結果更好，而且算法穩定性更優。在多峰函數和定維多峰函數方面，從F5～F6 來看，CC-HHO 的均值與HHO 持平，優于GSA、PSO、WOA；從F7～F10 來看，CCHHO 獲得令人滿意的結果，相對于HHO 具有小幅優勢。

4.2 CC-HHO算法與其他改進HHO算法比較

本節將CC-HHO 算法與其他4 種改進的HHO 算法CEHHO、IHHO、HHOA-OBL、HHO-SQP進行性能對比分析，迭代次數為500，每種算法對每個函數進行30 次測試，收集均值、標準差、最優值和最差值作為評價依據，測試結果如表5 所示。

如表5 所示，CC-HHO 算法在函數F1～F4 的平均值和最優值表現上完全壓制其他4 種改進的HHO 算法。對于F5～F6，因為5 種改進算法都是從HHO 算法的衍生而來，所以搜索性能指標基本相同。從函數F7～F10 的結果來看，雖然CC-HHO 算法在數量級上沒有形成巨大優勢，但與其他函數相比仍然更加優秀。結果表明，CC-HHO 算法的準確度和魯棒性都優于其他改進算法。

表5 CC-HHO 與其他改進HHO算法的尋優結果比較Tab 5 Optimization result comparison between CC-HHO and other improved HHO algorithms

圖3 是單峰基準函數的收斂曲線，在5 種改進的HHO 算法中，CC-HHO 算法的最終尋優結果最好。F1 和F4 的收斂速度最快，收斂精度最高。在F3，雖然CC-HHO 算法的收斂速度相對較慢，但是依然在尋優后期通過CC 找到更優解。在F4，能夠明顯看出CC-HHO 算法在迭代初始階段就快速收斂并經歷至少兩次陷入局部最優，但通過“強制探索”跳出。

圖3 單峰函數的收斂曲線Fig.3 Convergence curves of unimodal functions

圖4 是多峰基準函數的比較，對于F7，CC-HHO 算法比HHO-SQP 和HHOA-OBL 收斂速度稍慢；對于F5、F6、F8，CCHHO 算法收斂最快，收斂精度也很突出，當其他改進的HHO算法陷入局部最優，沒有機會搜索到更好的解時，CC-HHO 算法通過分析收斂趨勢、精英選擇、趨化校正尋找到更優解。

圖4 多峰函數的收斂曲線Fig.4 Convergence curves of multimodal functions

圖5 為5 種改進的HHO 算法在定維多峰函數F9～F10 的尋優收斂曲線，最終尋優結果處于同一數量級。F10 表明CC-HHO 算法具有最佳的收斂速度和最終解。

圖5 定維多峰函數的收斂曲線Fig.5 Convergence curves of fixed-dimensional multimodal functions

5 結語

為了克服HHO 算法的缺點，提高算法的尋優性能，通過識別收斂曲線狀態、趨化校正、引入基于生物能量消耗的逃逸能量因子、精英選擇、強制探索的途徑進行優化和提出改進算法。并通過10 個基準函數進行測試。對比其他元啟發式算法和改進的HHO 算法，仿真結果和收斂曲線表明，本文CC-HHO 算法在單峰函數上展現出超強的尋優能力；在多峰函數和定維多峰函數上，除所有參與比較算法均能找到理論最優解的情況，本文CC-HHO 算法在收斂精度上具有一定優勢。綜上說明，本文算法在探索、開發和避免局部最優方面具有競爭力，提高了原算法的搜索效率和魯棒性。但是多模態基準函數的尋優表現不如單峰基準函數，有待于進一步研究。