基于PWLCM和禿鷹俯沖機制改進的野狗優化算法

歐基發，蔡茂國，洪廣杰，詹楷杰

（深圳大學電子與信息工程學院，廣東 深圳 518060）

0 引 言

優化問題是社會各個領域逃避不了的一個問題，例如自動化［1］、計算機科學［2］、電力［3］、交通運輸［4］等眾多領域。然而使用梯度下降法等舊式數學方法已經難以解決當今社會大規模的優化問題。元啟發式算法應運而生，其具備通俗易懂、易于實現等優點，逐漸成為人們解決優化問題的一種常規手段。元啟發式算法通過對決策空間的部分子集進行采樣來搜索優化解，成為解決黑箱優化問題的有效途徑［5］。目前，除了蟻群算法［6］、遺傳算法［7］和粒子群算法［8］等經典算法，麻雀搜索算法［9］、哈里斯鷹優化算法［10］、蝴蝶優化算法［11］和螢火蟲優化算法［12］等算法也是人們使用得比較多的元啟發式算法。在科技迅猛發展的時代里，舊的元啟發式算法不斷被改進優化，甚至被新的元啟發式算法取代更替。

野狗優化算法（Dingo Optimization Algorithm，DOA）的工作原理簡單明了，具有較強的全局開發探索能力，其尋優速度也有不俗表現［13］，已應用在網絡帶寬選擇［14］、光伏組件參數提?。?5］、特征選擇［16］和粒子濾波器導航［17］等領域中。

元啟發式算法普遍存在尋優速度偏慢、收斂精度偏低等現象，作為其子集的野狗優化算法也存在相同的情況。針對上述問題，學者從種群的初始化、野狗的群體攻擊策略、迫害策略和種群生存標準等方面著手對DOA 進行一系列改進。Almazán-covarrubias 等人［18］利用局部搜索，對生存標準進行修改，來實現更佳的種群更替。Chaabane 等人［16］通過正弦切混沌映射策略初始化種群和引進慣性權重來改進群體攻擊和迫害策略得到CDOA，并將該算法結合深度學習應用到光譜傳感特征選擇領域中。蔡新雷等人［19］將原來判斷野狗種群行為的固定概率值P和Q修改成動態概率值，形成的IDOA 應用到電車調峰領域中，取得了良好的效果。然而這些改進的算法在尋優的速度和精度上仍有很大的提升空間，全局搜索以及收斂精度等有待深究。

上述研究表明野狗優化算法存在應用價值和研究意義，并為改進野狗優化算法提供了一些研究方向，因此本文提出一種基于PWLCM 和禿鷹俯沖機制改進的野狗優化算法。

1 野狗優化算法

野狗優化算法模擬了澳洲野狗在自然界生存時的行為，主要由4 個部分組成：群體攻擊策略、迫害策略、食腐策略和種群更新。澳洲野狗種群補充生存發展的能量是通過狩獵活物（兔子、綿羊和爬行動物等）或者食用腐肉（動物的遺體）來進行的。本章描述DOA工作的基本步驟。

1.1 初始化種群

野狗個體隨機分布在大自然中各個位置，并根據3種策略尋找食物補充能量。具體初始化公式如下：

1.2 群體攻擊策略

當澳洲野狗種群在生存環境中發現大型活物時，它們便對該獵物進行包圍、追逐，并發動群體攻擊，共同分享食物。然而，包圍體型巨大的獵物時，并非每個野狗都會對獵物進行攻擊。澳洲野狗個體采用群體攻擊策略時，其位置更新公式如下：

1.3 迫害策略

當野狗個體在覓食過程中發現個體比較小的獵物（例如兔子、老鼠等）時，野狗個體便會單獨行動，并對小獵物進行追趕、迫害捕食。野狗個體在迫害小獵物過程中，其位置更新公式如下：

其中，β2是隨機數，取值范圍為［-2，2］；(t)是從野狗種群中隨機選擇出來的個體；r1為隨機數，取值范圍為1到最大野狗數，其中i≠r1。

1.4 食腐策略

野狗種群在尋找食物過程中如果沒有發現活的獵物，就會將找到的動物遺體等腐肉作為食物來攝取營養維持種群的生存和發展。野狗個體在尋找腐肉充饑過程中，其位置的更新公式如下：

其中，σ是隨機生成的二進制數，即σ∈ {0，1} 。

1.5 3種不同策略對應的條件

采用群體攻擊策略、迫害策略和食腐策略等3 種狩獵策略是通過生成2個隨機概率值（P1和P2）和2個預設概率值（P和Q）進行比較實現的。

第一個判斷是判斷野狗是否找到活的獵物，包括體型小的獵物和體型大的獵物：當第一個隨機概率值P1＜P時，野狗找到活的獵物；否則，野狗找不到活的獵物，只能通過清除生存環境中的腐肉來維持生存。

第二個判斷是判斷當野狗找到活的獵物時，根據獵物的體型大小采取的是群體攻擊策略還是迫害策略。即當P2＜P時，野狗種群覓食到體型較大的獵物時，采用群體攻擊策略；否則，野狗個體覓食到體型較小的獵物時，采用迫害策略?？偟呐袛嘁罁缦拢?/p>

1.6 種群更新

DOA 通過每只野狗的位置信息來確定其適應值，其中個體適應值越大對應的生存率越低。根據“適者生存”法則，當野狗個體生存率低于某個數值時，說明該個體不適應當前的生存環境，就會被大自然淘汰?；谝肮贩N群規模趨于穩定，其種群規模大小默認不會有變化，而那些被淘汰的野狗將會由新的個體替代。

1.6.1 適應值計算

野狗個體的適應值等于該只野狗各維度上對應的位置信息的平方和。

其中，fitness（i）是第i個野狗個體的適應值，positionk*（i）是第i個野狗第k個維度上的具體位置信息。

1.6.2 生存率計算

通過公式（7）對野狗個體的生存率在［0，1］區間內進行歸一化。

其中，survival（i）是第i個野狗個體的生存率，fitnessmax是野狗種群中最大的適應值，其生存率最小，對應的生存率值為0；fitnessmin是野狗種群中最小的適應值，其生存率最大，對應的生存率值為1。

1.6.3 野狗個體更替

2 融合多種策略改進的野狗算法

2.1 基于PWLCM 的種群初始化

DOA 在初始化種群個體時劃定邊界，在指定的空間內得到的野狗個體種群分布不均、質量參差不齊，種群多樣性得不到保證。使用質量欠佳的種群進行迭代不僅會讓算法求解精度下降，而且也會降低算法尋優效率。而混沌映射在解決偽隨機數序列存在的問題上表現不俗，能夠讓個體按照一定規則隨機并均勻分布在特定的空間里。通過文獻［20］可知，PWLCM 生成的隨機序列擁有良好的遍歷性、統計特性，能生成覆蓋率高、質量高的種群。

見名識義，PWLCM（分段線性混沌映射）是將混沌值映射分成4 段，每一段都具備線性混沌的性質。利用PWLCM生成的種群，避免了極端的種群初始化問題的出現，不僅能加快原始DOA尋優速度，而且使得算法的求解精度得到一定程度的提升。通過文獻［21］以及實驗得知，當K=0.4時，PWLCM的性能較好。

2.2 融合禿鷹搜索算法的迫害策略

澳洲野狗在采用迫害策略捕食過程中，通過追蹤獵物，直至獵物疲憊放棄掙扎。原始野狗優化算法在模擬這一過程時不經意間讓自身的尋優速度偏慢，因此對這一策略進行優化改進能讓野狗優化算法得到很大提升。而禿鷹搜索算法［22］具有極強的搜索能力，收斂速度快。通過引進禿鷹搜索算法中的俯沖捕獲獵物機制能讓野狗個體更快地靠近、捕獲小獵物，即引進禿鷹俯沖機制能極大地改善野狗優化算法迫害策略的局部搜索能力差的問題。

其中，C1和C2為野狗迫害策略時的運動強度參數，取值范圍均為［1，2］的隨機數；A=10，為控制螺旋軌跡的參數；Pmean為野狗種群的平均位置。

2.3 基于改進的螺旋搜索因子的食腐策略

螺旋搜索因子分別被應用到飛蛾火焰優化算法（MFO）［23］和鯨魚優化算法（WOA）［24］中。由文獻［25］可知，改進的螺旋搜索因子能有效地增強算法在指定區域的探索和開發能力。本文在1.4節食腐策略中引進改進的螺旋搜索因子，以增強算法局部開發和尋找更優質解的能力。野狗個體位置更新公式如下：

其中，a∈(0，1)，是隨機變量，U是控制對數螺旋曲線形狀的定值參數，I是服從正態分布的隨機變量。與原始的DOA 食腐策略相比，融合改進的螺旋搜索因子的食腐策略使得野狗個體呈螺旋狀的方式進行尋優求解，讓算法不會輕易地被局部最優所迷惑，從而使得算法的尋優精度在原基礎上得到突破。

2.4 IDOA的偽代碼

IDOA算法的偽代碼如下：

輸入：野狗種群數量SizePop。

1 初始化Iterations、Fn和Times等參數

2 PWLCM初始化野狗種群，計算個體適應值

3 參數設置：種群數量SizePop、P、Q

4 while Iteration＜Iterations do

5 if 隨機數P1＜Pthen

6 if 隨機數P2＜Qthen

7 使用式（2）更新群體攻擊的野狗位置

8 else

9 使用式（18）更新迫害策略的野狗位置

10 end if

11 else

12 使用式（21）更新食腐策略下的野狗位置

13 end if

14 根據式（7）計算野狗個體的生存率

15 根據式（8）對低生存率個體進行種群更替

16 ifPnew＜P*then

17P*=Pnew

18 end if

19 Iteration=Iteration+1

20 end while

21 輸出全局最優解

整個IDOA的算法流程圖如圖1所示。

圖1 IDOA流程圖

3 算法的性能測試

3.1 測試函數

為了驗證IDOA 的優良性能，選取8 個測試函數［26］進行仿真實驗。這8 個測試函數的理論最優值均為0，其中F1~F5 是單峰函數，F6~F8 是多峰函數。仿真實驗使用的函數信息如表1所示。

表1 測試函數

3.2 參數設置

參數設置如表2所示。

表2 參數設置

3.3 不同種類智能優化算法比較

為確保實驗的公平有效，6 種算法的對比仿真實驗均在同一環境下進行。即使用CPU 參數為11th Gen Intel（R）Core（TM）i7-11700、主頻參數為2.5 GHz、內存大小為16 GB 的64 位Windows 10 操作系統的電腦設備上的R2021a版本的MATLAB 進行算法對比。將基于PWLCM和禿鷹俯沖機制改進的野狗優化算法（IDOA）同粒子群優化算法（PSO）［8］、灰狼優化算法（GWO）［27］、北方蒼鷹優化算法（NGO）［28］、鵜鶘優化算法（POA）［29］、野狗優化算法（DOA）在8 個測試函數上進行實驗對比。種群數量和迭代次數分別設置為30 和500 ，嚴格遵循8 種測試函數的維度、搜索上下界范圍。通過仿真實驗，可以得到6 種算法在8 種不同函數上的測試結果（見表3）：最優值、平均值以及標準差。其中表現最好的數據用粗體來表示。

表3 IDOA與其它元啟發式算法比較結果

3.4 IDOA與其它元啟發式算法的比較

8種測試函數的收斂曲線圖如圖2所示。

圖2 8種函數的收斂曲線圖

結合表3 和圖2，從函數F1~F4 的收斂曲線圖（圖2（a）~圖2（d））可直觀地看到IDOA 的尋優速度和精度遙遙領先于PSO、GWO、NGO、POA、和DOA，并且只有IDOA 求解到最優解。對于函數F5 和F7（圖2（e）和圖2（g）），雖然所有算法均沒有尋找到最優值，但是IDOA 的收斂速度和尋優精度明顯優于其他算法。對于函數F6 和F8（圖2（f）和圖2（h）），與PSO 和GWO相比，IDOA 與NGO、POA、DOA的尋優精度表現更佳且它們之間平分秋色，但是IDOA 的收斂速度遠快于其他算法，在迭代20次之前就收斂到最優值。

3.5 IDOA與其它改進的DOA的比較

為了驗證 IDOA 與其他改進DOA 算法的優劣性，將本文的IDOA 與CDOA［16］、IDOA［19］進行對比分析。各算法的共有參數與3.2 節中保持一致，其他參數設置跟原文獻保持一致，對比結果見表4，其中原文獻中沒有出現的數據用“-”表示。算法尋找到測試函數的最優值，表明該算法在該測試函數里達到最優，則記錄該算法達到一次最優，該項數據則用粗體來表示。

表4 IDOA與其他改進的DOA的比較分析

如表4 所示，對于函數F1~F3，本文的算法與CDOA 的尋優精度相同，與IDOA 相比，擁有巨大優勢。對于函數F4，本文的IDOA 的平均值和標準差大幅度優于其他2種改進的算法。對于函數F5，因為本文的IDOA和CDOA這2種算法都是在DOA的基礎上改進而來，故性能指標接近，但本文的IDOA 的尋優精度劣于CDOA。在函數F6~F8 中，本文的算法和CDOA 的平均值和標準差的表現不分上下。本文的IDOA 在8 種測準測試函數實驗的24 項數據中，有20項占優；而CDOA 次之，有15 項占優；IDOA 表現最差，0 項占優。結果表明，兼顧精確度和穩定性，本文提出的IDOA的整體性能優于其他2種改進的DOA。

3.6 消融實驗

為了驗證IDOA 每一處改進的有效性，本文的IDOA 在3.1 節和3.3 節的實驗環境下進行消融實驗。其中DOA 利用2.1節的PWLCM 初始化種群改進得到IDOA1；DOA 利用2.1 節的PWLCM 初始化種群和基于禿鷹俯沖機制的迫害策略，改進得到IDOA2。各算法的共有參數與3.2 節中保持一致，其他參數設置跟原文獻保持一致。即使用F1~F8 共8 個30 維的測試函數來進行仿真實驗，進行30 次獨立重復實驗，每次獨立實驗中，算法迭代500次。對比結果見表5，其中較上一個算法在尋優精度上有提升，則用“↑”表示；無提升則用“→”表示；尋優精度有所下降則用“↓”表示。每項最優數據用粗體來表示。

表5 3個改進策略的消融實驗

通過表5 可以看出，IDOA1 在F1~F5 和F7 這6 個測試函數上提升了DOA 的尋優精度，但算法的平均值仍未達到最優；在F6 和F8 中，IDOA1 的尋優精度和DOA 的保持一致。IDOA2 在F1~F4 這4 個測試函數上提升了IDOA1 的尋優精度；在F5~F8 中，IDOA2的尋優精度和IDOA1 的不分上下。IDOA 在F5 這1個測試函數上提升了IDOA2 的尋優精度；在剩下7個測試函數中，IDOA 的尋優精度和IDOA2 的旗鼓相當。

圖3 中的算法收斂曲線圖表明，在收斂速度方面，DOA＜IDOA1＜IDOA2＜IDOA，充分表明3處改進均提升了算法的收斂速度。綜合表5 和圖3，充分表明基于PWLCM 初始化種群、基于禿鷹俯沖機制的迫害策略和螺旋搜索因子的食腐策略都能提高算法的尋優精度和尋優速度。即充分表明了2.1 節、2.2 節和2.3節等3種改進方法的有效性。

圖3 消融實驗算法收斂曲線圖

3.7 Wilcoxon秩和檢驗

為全面地評估IDOA 的性能，本節將使用Wilcoxon 秩和檢驗［30］進行統計分析，以此來驗證IDOA和SSA、NGO、POA、BWO算法之間是否存在顯著性差異。設定顯著性水平為5%，并與Wilcoxon 秩和檢驗計算得到的P進行比較。當P≥0.05 時，表示比較的2種算法之間不存在顯著性差異，實驗結果中用“-”表示；當P＜0.05 時，則表示比較的2 種算法之間存在顯著性差異，實驗結果中用“+”表示；NaN 表示比較的2種算法性能旗鼓相當，不能進行顯著性分析，實驗結果統計中用“=”表示。

實驗結果如表6 所示，可以看出大部分P值是遠小于0.05 的。IDOA 跟PSO 和GWO 在8 個測試函數中存在顯著性差異。此外，IDOA 跟NGO 和POA 在6個測試函數中存在顯著性差異；在剩下的2 個測試函數里，不能進行顯著性分析。而IDOA 跟DOA 在5 個測試函數中存在顯著性差異；在1 個測試函數中不存在顯著性差異；在剩下的2 個測試函數里，不能進行顯著性分析。Wilcoxon 秩和檢驗的結果說明，IDOA的優化性能比其他5 種算法要好，具備更強大的尋優能力。

表6 Wilcoxon秩和檢驗結果

4 結束語

針對野狗算法尋優速度偏慢、求解精度偏低的問題，本文提出了一種基于PWLCM 和禿鷹俯沖機制改進的野狗優化算法。首先利用分段線性混沌映射初始化得到更均勻、高質量的種群；其次引進融合禿鷹搜索機制的迫害策略，有效地加速野狗個體捕獲小獵物，即加快算法尋找最優解的過程；最后通過引入改進的螺旋搜索因子的食腐策略，增強了算法的局部探索開發能力，提高了算法尋優效率以及求解精度。而消融實驗充分表明了3 種改進策略均能提高了野狗優化算法的收斂速度以及尋優精度。6 種算法在8個測試函數仿真實驗結果以及Wilcoxon 秩和檢驗的結果都表明提出的IDOA 具有更快的尋優速度和更強的尋優能力。與最近改進的野狗優化算法相比，本文的IDOA 兼顧精確度和穩定性，呈現出更強的整體性能。