聚類質(zhì)心與指數(shù)遞減方法改進的哈里斯鷹算法

白曉波，江夢茜，王鐵山，邵景峰，李 勃

（1.西安工程大學(xué)管理學(xué)院，陜西 西安 710048；2“.一帶一路”紡織發(fā)展創(chuàng)新研究院，陜西 西安 710048；3.福州大學(xué)先進制造學(xué)院，福建 福州 350003）

0 引 言

群體智能優(yōu)化算法（Swarm Intelligence Optimization Algorithm，SIOA）是模擬生物種群的群體或社會行為，求解問題的最優(yōu)值，在工程、醫(yī)學(xué)、軍事和生產(chǎn)車間調(diào)度等領(lǐng)域均有應(yīng)用。為了解決不同類型的優(yōu)化問題，如在參數(shù)取值范圍內(nèi)，參數(shù)多、維度高，優(yōu)化目標(biāo)為單峰或者多峰函數(shù)，產(chǎn)生了一些比較有代表性的群體智能優(yōu)化算法，如粒子群算法（Particle Swarm Optimization，PSO）［1］、灰狼算法（Grew Wolf Optimization，GWO）［2］、煙花算法（Fireworks Algorithm，F(xiàn)WA）［3］、蛙跳算法（Shuffled Frog Leaping Algorithm，SFLA）［4］、螢火蟲算法（Firefly Optimization Algorithm，F(xiàn)OA）［5］和果蠅優(yōu)化算法（Fruit Fly Optimization Algorithm，F(xiàn)FOA）［6］等。這些不同的優(yōu)化算法在不同的優(yōu)化目標(biāo)上的性能表現(xiàn)差異較大。這也比較符合無免費午餐（No Free Lunch，NFL）定理［7］，即一個算法很難在每個優(yōu)化目標(biāo)上表現(xiàn)出優(yōu)異性能。這也是很多學(xué)者一直在改進現(xiàn)有算法或者研究出更有效的優(yōu)化算法的原因。

2019 年，Heidari 等［8］提出了哈里斯鷹優(yōu)化（Harris Hawks Optimization，HHO）算法，該算法通過模擬獵物的逃逸能量來控制全局和局部搜索，但是算法存在前期全局搜尋能力較弱、且種群多樣性不足的問題。與GWO 相比，對部分多峰函數(shù)優(yōu)化性能較差。因此，國內(nèi)外學(xué)者對HHO 進行了研究，并改進其尋優(yōu)能力。如賈鶴鳴等［9］，將動態(tài)反向?qū)W習(xí)的阿奎拉鷹（Aquila Optimizer，AO）［10］與HHO 相融合，解決了HHO 全局尋優(yōu)能力不足的問題，在對部分多峰函數(shù)的求解中，取得了和AO 近乎接近的結(jié)果。湯安迪等［11］利用精英等級策略和非線性能量因子對算法進行改進。高建瓴等［12］主要利用混合差分與二次插值的方法對HHO 改進。朱誠等［13］提出趨化校正的HHO。劉小龍等［14］利用方形鄰域和隨機數(shù)組對HHO改進。Wang 等［15］提出了一種離散HHO 解決充電的共享電動汽車調(diào)度問題。Song 等［16］以Tent 混沌映射和隨機游走機制改進HHO。國外學(xué)者的研究，如Elgamal 等［17］利用混沌映射初始化種群，增加種群多樣性，再用模擬退火（SA）算法對當(dāng)前最佳解進行優(yōu)化，以提高HHO 的利用率。Nandi 等［18］將HHO 和GWO相結(jié)合，利用GWO 算法進一步改進了HHO 算法的探索和開發(fā)階段。Hussien 等［19］將反向?qū)W習(xí)、混沌局部搜索和自適應(yīng)技術(shù)相結(jié)合，提高了HHO 的性能。Kamboj 等［20］基于正余弦算法改進HHO 的探索階段，提出了混合Harris Hawks 正余弦算法。Kaveh 等［21］將帝國主義競爭算法（Imperialist Competition Algorithm，ICA）［22］與HHO 相結(jié)合，構(gòu)成混合優(yōu)化算法ICHO。Gupta 等［23］利用非線性能量參數(shù)、差分進化、貪婪選擇機制和反向?qū)W習(xí)等提高了算法的搜索效率。

綜上，國內(nèi)外學(xué)者都針對HHO 搜尋能力不足的問題進行研究，并取得了較好的效果，主要方法為：1）將HHO 中線性能量參數(shù)改進為非線性，并加入精英選擇策略。2）將全局尋優(yōu)能力好的算法和HHO 結(jié)合，構(gòu)成混合優(yōu)化算法。3）引入混沌方法，改進種群多樣性。但是在改進中都忽略了HHO 在更新種群位置的時候，用了種群均值，這就存在部分偏離最優(yōu)值位置較遠的種群對均值產(chǎn)生較大影響，進而影響到迭代時下一代的種群分布，導(dǎo)致算法難以較快收斂于最優(yōu)值。因此，本文提出新的假設(shè)，即將所有種群看作一類，利用聚類簇心代替均值，能夠使算法較快地收斂于最優(yōu)值；再結(jié)合非線性能量參數(shù)改進全局搜尋能力，能夠取得更好的優(yōu)化效果。

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

哈里斯鷹優(yōu)化算法是模擬哈里斯鷹圍捕獵物的過程，利用獵物的逃逸能量來控制探索與開發(fā)階段的轉(zhuǎn)換。HHO詳細的數(shù)學(xué)表示如下。

1.1 探索階段

探索階段（|E| ≥1，E為獵物逃逸能量），使用等概率的2種方式更新種群位置，如公式（1）所示。

1.2 探索開發(fā)轉(zhuǎn)換

HHO是線性的逃逸能量計算方式，如公式（2）所示：

其中，T為最大迭代次數(shù)，E0為（-1，1）之間均勻分布的隨機數(shù)。

1.3 開發(fā)階段

開發(fā)階段（|E| < 1）是在發(fā)現(xiàn)獵物后采用的抓捕策略，HHO 利用獵物逃逸能量E和（0，1）之間均勻分布的隨機數(shù)來控制4 種抓捕策略，如下所示。其中，r是（0，1）之間均勻分布的隨機數(shù)。

1）軟包圍。

若|E| ≥0.5 且r≥0.5，則使用軟包圍策略。獵物有逃逸能力，但無法逃脫。公式如下：

其中，ΔX(t)表示當(dāng)前最優(yōu)值與種群X的差，其中r5∈（0，1）為隨機數(shù)，J為獵物逃脫時的隨機逃逸距離。

2）硬包圍。

若|E| < 0.5且r≥0.5，則使用硬包圍對策。即獵物沒有足夠能量逃逸，且無逃出機會。公式如下：

3）漸進式快速俯沖軟包圍。

若|E| ≥0.5 且r<0.5，表示獵物有足夠能量，且有機會逃逸。此時，需使用2 種策略，如公式（7）~公式（9）所示：

式中，d表示問題維度，S表示d維的隨機向量，Levy（·）表示Levy 飛行函數(shù)，詳見文獻［11］。Levy（d）表示由Levy 飛行函數(shù)返回的d維向量。由此，種群更新公式如下：

其中，f（·）為優(yōu)化問題的適應(yīng)度函數(shù)。

4）漸進式快速俯沖硬包圍。

若|E| < 0.5 且r<0.5，表示獵物逃逸能量不足，但有逃脫機會，因此，使用硬包圍，快速縮小種群和獵物之間的距離。公式如下：

2 種群質(zhì)心和非線性能量改進HHO

2.1 改進HHO的基本思想

1）聚類質(zhì)心改進HHO?；舅枷胧牵簩HO 的種群X視作需要分類運算的一個矩陣，只是劃分時K=1，即本質(zhì)上并未分類，但是，取得了種群的質(zhì)心，利用種群的質(zhì)心代替HHO 中的種群均值X（t），以減少部分遠離最優(yōu)值的種群在進行均值運算后，對均值產(chǎn)生放大效應(yīng)，使得算法不能快速收斂。

種群質(zhì)心的獲取，使用Matlab2017 中的Kmeans［24］算法。在輸入?yún)?shù)值的選擇上，必定會影響到最后的簇心，對HHO 的影響主要體現(xiàn)在算法尋優(yōu)性能上。具體的影響和選取方式在后續(xù)實現(xiàn)仿真中會詳細闡述。

2）非線性能量改進HHO。在HHO 中，通過能量逃逸公式（2）控制探索與開發(fā)階段，也就是該公式?jīng)Q定了HHO 的全局和局部尋優(yōu)次數(shù)。根據(jù)公式（2）繪制的能量變化過程如圖1所示。

圖1 線性遞減能量變化曲線圖

圖1 是一個種群數(shù)為20、迭代次數(shù)也為20，生成400個點構(gòu)成的能量變化曲線。|E|≥1，HHO進行全局尋優(yōu)。從圖1 可以明顯看出，其整個尋優(yōu)過程中，|E|≥1的次數(shù)很少，必然影響到HHO全局尋優(yōu)能力。這就導(dǎo)致在面對多峰函數(shù)時，尋優(yōu)效果較差，易陷入局部極值。為了增加其全局搜尋能力，需要改進能量計算方法，使用指數(shù)遞減的計算方法［25］，公式如下：

其中，Emin為能量最小值，Emax為能量最大值，c為一常數(shù)，在本文中c=0.1。其能量變化曲線如圖2所示。

圖2 指數(shù)遞減能量變化曲線

在圖2 中，可以明顯看出 |E|≥1 的次數(shù)明顯增加，即使到了中間階段，也存在 |E|≥1 的情況。迭代后期，進入局部尋優(yōu)階段，所采用的種群更新策略也較線性遞減更為全面。在圖1 中，進入迭代后期主要是 |E|≤0.5 的情況，而在圖2 中，|E|≤0.5 和 |E|> 0.5的情況比較均衡，這就更有利于搜尋到最優(yōu)值。

2.2 KmHHO算法

基于2.1 節(jié)中的改進思想和方法，得出改進的HHO算法（記作：KmHHO）流程如圖3所示。

圖3 KmHHO算法流程圖

KmHHO算法的詳細過程如下。

步驟1種群初始化。根據(jù)參數(shù)取值范圍［lb，ub］和維度d，隨機生成N個d維種群，并設(shè)置主要參數(shù)Emax=2、Emin=0.0001及最大迭代次數(shù)T。

步驟2進入迭代。

步驟3若t=T，程序結(jié)束，否則返回步驟2。

2.3 KmHHO算法時間復(fù)雜度

在KmHHO 中增加了Kmeans 算法計算簇類質(zhì)心，其時間復(fù)雜度為O（RNDK）（R：迭代次數(shù)，N：數(shù)據(jù)個數(shù)，D：數(shù)據(jù)特征維度，K：類簇數(shù)），會較大程度地影響KmHHO 的效率，非線性遞減能量計算公式并不影響。在本文中，加入了Kmeans，但是K=1，R待定，N和D由具體問題決定。則KmHHO 的算法時間復(fù)雜度表示為O（2TN+TNRD）。根據(jù)NFL 定理，算法性能提高，增加了一定時間開銷，這也是可以接受的。

3 實驗仿真

實驗仿真選擇了23個benckmark 基準(zhǔn)函數(shù)，詳見文獻［2］。整體分為3 個部分：1）分析Kmeans 算法優(yōu)化后的HHO 性能，并分析Kmeans 不同取參對尋優(yōu)結(jié)果的影響。2）將KmHHO與GWO［2］、HHO［8］、DAHHO［9］和AO［10］在相同種群數(shù)N、最大迭代次數(shù)T和運行次數(shù)runs下的均值、標(biāo)準(zhǔn)差進行對比分析，均值越小，尋優(yōu)性能越好，標(biāo)準(zhǔn)差越小，算法越穩(wěn)定。3）Wilcoxon秩和檢驗［26］，以檢驗KmHHO算法與其他算法的差異性。

所有實驗運行環(huán)境為：Windows 10 操作系統(tǒng)（64位）， Matlab2017a， Anoconda3。 Intel（R） Core（TM）i5-7400 CPU@3.00 GHz，4 GB 內(nèi)存。為了與主要參考文獻的實驗數(shù)據(jù)公平對比，將迭代次數(shù)T、種群數(shù)N和每個算法獨立運行次數(shù)runs 設(shè)置為與文獻［9］相同，即T=500、N=30、runs=30。

3.1 聚類質(zhì)心優(yōu)化HHO后的尋優(yōu)結(jié)果

用Kmeans 聚類質(zhì)心代替HHO 均值后，是否能夠提升算法尋優(yōu)性能，若能提升，又能提升多少。這里需要進一步說明。對此，本文將加入Kmeans 的HHO與原HHO 在23 個基準(zhǔn)函數(shù)上進行效果對比。為了統(tǒng)計方便，在23 個基準(zhǔn)函數(shù)中，只要獲得最優(yōu)值，即使和其他算法相同，也算作勝出。實驗結(jié)果如表1 所示。其中，粗體表示最優(yōu)值。

表1 使用Matlab的Kmeans聚類質(zhì)心改進HHO與原HHO的對比

在表1 中，除了′Distance′=′sqEuclidean′時的avg的勝出數(shù)分別為9 和10，其他2 種情況的勝出數(shù)均高于原HHO，說明通過Kmeans聚類質(zhì)心改進HHO的可行性。后續(xù)實驗選擇勝出最多，且穩(wěn)定性較高的參數(shù)配置′Distance′=′cityblock′、′start′=′Uniform′。

3.2 KmHHO與其他算法性能對比

這里主要分析在HHO 加上Kmeans 和指數(shù)遞減的能量計算方式后對算法性能的影響。主要與GWO［2］、HHO［8］、DAHHO［9］、AO［10］這4 種算法作對比。實驗結(jié)果如表2所示。其中，粗體表示最優(yōu)值。

表2 KmHHO與其他4個優(yōu)化算法性能的對比

表2中的KmHHO 這一項，是在Kmeans聚類質(zhì)心優(yōu)化HHO 后，再加上指數(shù)遞減逃逸能量的改進效果，與表1 中的數(shù)據(jù)相比，尋優(yōu)精度有了進一步提升。如在函數(shù)F1~F4、F20~F22等，這也說明了使用指數(shù)遞減的逃逸能量比原HHO中線性遞減的逃逸能量更好。

從表2 的統(tǒng)計數(shù)據(jù)可以看出KmHHO 在23 個benckmark 函數(shù)中，共在14 個函數(shù)上取得了最優(yōu)值，比HHO 提高了6 個函數(shù)，整體效果明顯優(yōu)于GWO、HHO 和AO，從而說明Kmeans、指數(shù)遞減的逃逸能量對HHO 的改進有著良好的效果，比DAHHO 的勝出少1 個。但是，KmHHO 在單峰和多峰的高維函數(shù)上有很好的尋優(yōu)效果，如F1~F4、F8~F11、F14~F17、F19和F20，而在F21~F23 的尋優(yōu)效果上明顯低于GWO、DAHHO 和AO。這也符合NFL 理論，一個尋優(yōu)算法，很難在所有優(yōu)化目標(biāo)上都有良好性能。

3.3 Wilcoxon秩和檢驗

Wilcoxon 秩和檢驗［26］，用來檢查2 個算法之間的差異性。設(shè)顯著性水平為5%，若p<5%，則零假設(shè)被拒絕，表明2 個算法之間存在顯著性差異；否則，表明2 個算法性能相當(dāng)。KmHHO 與其他4 個算法的Wilcoxon 秩和檢驗的結(jié)果如表3 所示。針對每個算法、每個函數(shù)的30 次尋優(yōu)結(jié)果，使用Python 的scipy.stats.ranksums（）方法計算可得。

表3 KmHHO與4個算法Wilcoxon秩和檢驗結(jié)果

在表3 中，粗體是p>5%的，表明KmHHO 與相應(yīng)算法在對應(yīng)函數(shù)上性能相當(dāng)，其他表示有顯著差異。如HHO列，在函數(shù)F5~F13上與KmHHO性能相當(dāng)，其他函數(shù)上具有顯著差異。這也比較符合表2的測試數(shù)據(jù)。

由上述算法精度測試和統(tǒng)計檢驗，說明通過Kmeans和非線性遞減能量改進的KmHHO，在全局探索和局部開發(fā)能力上比GWO、HHO 和AO 都有了較大幅度的改善，存在的不足之處是略微弱于DAHHO。

4 結(jié)束語

本文通過Kmeans 簇類中心代替HHO 中的均值、指數(shù)遞減能量代替線性遞減能量這2種方法，將HHO算法的性能進一步提升，使其全局和局部尋優(yōu)能力都得到增強，并與4 個算法的性能進行了對比，綜合與GWO、HHO 和AO 比較，在尋優(yōu)精度和穩(wěn)定性上，都取得了絕對優(yōu)勢，并通過Wilcoxon 秩和檢驗，得出KmHHO與GWO、HHO、DAHHO和AO在23個函數(shù)上的差異性。差異性檢驗的結(jié)果，也與性能對比相吻合。但是，算法在部分多峰函數(shù)上的尋優(yōu)結(jié)果雖有提高，依然不是非常理想，這也是后續(xù)繼續(xù)開展研究的方向，以更進一步提升KmHHO 的綜合性能。另外，需要緊密結(jié)合工程設(shè)計問題，進一步對算法的性能進行驗證，以體現(xiàn)其工程適用性。