一種自適應鯨魚快速優化算法*

楊炳媛,袁 杰,郭園園

(新疆大學電氣工程學院，新疆 烏魯木齊 830047)

1 引言

鯨魚優化算法是Mirjalili等人[1]受到座頭鯨群體圍捕獵物行為的啟發，于2016年提出的一種智能仿生算法。標準鯨魚優化算法具有可調節參數少、魯棒性強、易于實現等優點。文獻[1]表明，相比于粒子群優化算法、遺傳算法等部分經典優化算法，鯨魚優化算法具有更好的全局探索能力。雖然鯨魚優化算法的全局搜索能力在一定程度上更具優勢，但其局部搜索能力和收斂速度仍有待提高。

針對上述問題，近年來許多研究人員做了大量研究，提出了多種改進方法，大致可以分為3類：(1)參數優化；(2)策略改進；(3)算法融合[2 - 6]。鯨魚優化算法的架構簡單，易于控制，其中收斂因子a是該算法中的一個重要參數。隨著收斂因子的線性遞減，算法實現由全局搜索到局部搜索的過程。因此,如何控制收斂因子a成為改進鯨魚優化算法的一個重要方向[7 - 9]。尋優策略的優化也是目前改進算法性能的一個重要手段。為了平衡算法的全局搜索與局部搜索能力，文獻[10]根據基本初等函數的圖像特征，提出了一種基于反正弦函數的非線性控制策略。文獻[11]在鯨魚優化算法的尋優策略中加入非線性自適應權值并提出黃金正弦算子的改進策略。文獻[12]利用Tent混沌映射來保證初始種群的多樣性，并加入了自適應慣性權重來提高算法的收斂速度和精度。文獻[13]針對鯨魚優化算法陷入局部極值中停滯不前的問題，提出了一種鯨魚優化算法和灰狼算法的混合模型，并將其應用于壓力容器設計等工程問題。文獻[14]利用改進的微分進化算子擴大種群的多樣性，對鯨魚優化算法進行了性能優化。

標準鯨魚優化算法的局部搜索能力不足和收斂速度較慢導致了算法在有限時間內的收斂精度較差，本文針對上述問題提出了一種自適應鯨魚快速優化算法AWOA(Adaptive fast Whale Optimization Algorithm)，該算法的自適應選擇策略在全局搜索與局部搜索之間實現了動態平衡；針對部分個體,采用Levy Flight以擴大種群多樣性。此外，路徑規劃[15，16]是無人車駕駛領域內的重要問題，眾多智能仿生算法在極大提高了路徑規劃效率的同時也存在著規劃精度欠缺等不足[17 - 19]。因此，本文還將所提改進算法應用于無人車路徑規劃問題，進一步驗證本文所提算法的尋優性能。

2 標準鯨魚優化算法

在尋優過程中，標準鯨魚優化算法有以下3種行為方式可供選擇。

2.1 包圍捕獵方式

(1)

(2)

A=2ar1-a

(3)

C=2r2

(4)

其中，r1、r2為[0,1]內的隨機數;a為收斂因子，且0≤a≤2。因此，0≤|A|≤2。此階段，|A|≤1。a的更新公式如式(5)所示：

(5)

其中，M為最大迭代次數。

2.2 隨機捕獵方式

鯨魚在捕獲獵物的過程中，會根據其他鯨魚的位置移動，隨機尋找獵物。鯨魚隨機狩獵時的數學模型如式(6)和式(7)所示：

(6)

(7)

2.3 螺旋捕獵方式

鯨魚圍捕獵物時，選擇螺旋方式的概率是P，選擇包圍或隨機方式的概率是1-P。式(8)和式(9)為鯨魚螺旋捕獵方式的運動模型：

(8)

(9)

其中，l為[0,1]內的隨機數，b為常數參數。

3 自適應鯨魚快速優化算法

標準鯨魚優化算法根據概率值P和|A|選擇狩獵方式，這種選擇策略具有一定隨機性，降低了算法的收斂速度且不能保證算法的穩定性。在迭代中后期，由于|A|≤1，鯨魚無法選擇隨機捕獵方式，使種群多樣性大大減少，導致收斂精度變差。

目前，大多數研究工作通過改進收斂因子a為非線性方式遞減，以提高算法在迭代前期的全局搜索能力和后期的局部搜索能力。但是，這樣的改進仍然具有隨機性，種群個體不能根據自身的特點去選擇狩獵方式，減緩了收斂速度，并且導致了收斂精度不足。

3.1 自適應選擇策略

本文設計了一種自適應選擇策略，根據樣本特性即樣本中個體的集散程度來選擇尋優策略，以實現全局搜索與局部搜索之間的動態平衡。由于標準差最能體現樣本的集散程度，因此結合標準差公式，用式(10)和式(11)衡量個體偏離整體樣本的程度[20]：

(10)

(11)

將單個樣本偏離整體樣本的程度進行歸一化處理[21]，如式(12)所示：

(12)

其中，Smin(k)和Smax(k)分別表示第k次迭代時Si(k)的最小值和最大值。

通過對所有樣本的每一維求均值得到樣本整體的平均位置，然后計算個體偏離樣本平均位置的程度并對其進行歸一化，以衡量該樣本的集散程度。對于集散程度較高的個體，令其向當前最優位置附近移動并進行局部搜索，設定閾值T，當0≤H≤T時，算法選擇包圍捕獵方式或螺旋捕獵方式，以提升局部搜索能力及收斂速度。對于集散程度較低的個體，令其向隨機個體所在位置附近移動，當T

3.2 基于Levy Flight的二次優化

鯨魚優化算法通過式(6)更新鯨魚位置進行隨機搜索，但信息交換范圍仍局限在現有種群空間，很大程度上受到初始化種群質量和隨機選擇的影響，導致搜索空間有限，且算法尋優能力的穩定性無法保證。針對上述問題，本文針對聚集程度較低的個體采用Levy Flight進行二次優化，通過步長的變化，進一步擴大搜索區域，以提高算法搜索全局極值的能力。進行Levy Flight迭代的數學模型如式(13)所示：

(13)

其中，x(k)表示需進行二次優化的個體在第k次迭代時的位置，α0為常數0.01，rand為[0,1]內的隨機數，s為Levy Flight的數學模型,如式(14)所示：

(14)

根據式(13)和式(14)，Levy Flight的二次優化數學模型可以寫為式(15)：

(15)

3.3 自適應鯨魚快速優化算法流程

不同于標準鯨魚優化算法根據|A|的取值選擇狩獵方式，AWOA主要根據個體特性自適應選擇捕獵方式，其流程如圖1所示。

Figure 1 Flow chart of AWOA圖1 AWOA流程圖

自適應快速鯨魚優化算法AWOA的具體步驟如下所示：

步驟1相關參數初始化。

步驟2在搜索區域內生成初始種群并記錄最優值。

步驟3更新相關參數，主要參數有A,C,l,P。

步驟4利用式(12)計算函數H的值，若0≤H≤T且P≤0.5，根據式(1)進行位置更新；若0≤H≤T且P>0.5，用式(8)進行位置更新；若T

步驟5針對T

步驟6計算適應度值，更新最優信息。

步驟7判斷是否達到最大迭代次數，若是則輸出最優信息，否則跳轉至步驟3。

4 算法性能測試及結果分析

4.1 算法性能測試函數

本文選取了7個常用的標準測試函數對算法性能進行驗證。f1(x)和f2(x)是單峰函數，用來檢驗算法的收斂速度;f3(x)～f7(x)是多峰函數，用來檢驗算法的全局搜索能力。測試函數的詳細信息見表1,函數表達式中D表示維度。

4.2 性能測試及結果分析

本文將所提出的改進算法AWOA與差分進化DE(Differential Evolution)算法、粒子群優化PSO(Particle Swarm Optimization)算法、灰狼GWO(Grey Wolf Optimizer)算法、鯨魚優化算法WOA(Whale Optimization Algorithm)進行測試對比。為保證實驗的客觀性，統一設置種群數量為30，最大迭代次數為1 000，每種算法在每個測試函數上分別進行50次獨立實驗。為檢驗算法的綜合能力，評價指標包括測試函數在迭代過程中的最小值(Min)、最大值(Max)、平均值(Mean)和標準差(Std)。此外，DE算法和PSO算法參數設置分別來源于參考文獻[22,23]，在DE算法中設置參數F=0.9,CR=0.5;在PSO算法中設置c1=1.5，c2=1.5，ω由0.9線性遞減至0.4。實驗硬件為Intel Core i7-6700,8 GB內存，2.6 GHz的計算機，軟件為Matlab R2019a，實驗結果如表2所示。

Table 1 Test functions

Table 2 Comparison of function test results of some algorithms

由表2可以看出，在f1(x)和f2(x)測試函數上，相較于其余4種經典算法，AWOA的各評價指標均有提升，表明在本文所提改進策略下，算法的收斂精度及穩定性得到了提高，且f1(x)和f2(x)是單峰函數，因而說明本文所提改進策略提升了算法的局部搜索能力。在f7(x)測試函數上，雖然GWO、WOA和AWOA都能收斂到最優值，但只有AWOA在每次測試實驗中都能穩定地得到最優值。f3(x)～f7(x)上的測試結果表明,AWOA具有跳出局部最優的能力，并且穩定性有所提升。

為了更直觀清晰地觀察算法的收斂情況，圖2給出了DE、PSO、GWO、WOA和AWOA的收斂曲線，橫坐標代表迭代次數，縱坐標代表目標函數值。從圖2a～圖2c、圖2f和圖2g可以看到，AWOA的收斂速度始終遠遠優于其余4種經典算法。圖2a和圖2b是在單峰函數上進行的實驗，說明在局部搜索中本文所提改進策略不僅使算法在收斂精度及穩定性方面得到了改善，同時在收斂速度上也得到了較大的提升。圖2c～圖2g是在多峰函數上進行的實驗，從中可以看出，AWOA在迅速收斂的同時也具有跳出局部最優的能力，保證了算法在多極值情況下的收斂精度。

Figure 2 Convergence characteristic curves for different test functions圖2 不同測試函數上的收斂特性曲線

5 路徑規劃實驗

本文將所提改進算法應用于路徑規劃仿真實驗，并與經典算法進行對比，以進一步驗證其有效性。

5.1 環境建模及適應度函數

本次實驗中場景1采用10*10含障礙物地圖，場景2和場景3采用100*100含障礙物地圖。以場景1為例，如圖3所示，方形物為起點，坐標(0，0)；五角星為終點，坐標(100，100)；圓狀物為障礙物，其數學模型如式(16)所示：

r2=(x-a)2+(y-b)2

(16)

其中，(a,b)表示障礙物圓心，r表示障礙物半徑,x和y分別表示障礙物邊緣的橫坐標和縱坐標。

Figure 3 Modeling of path planning map 圖3 路徑規劃地圖建模

將橫坐標等距離劃分為n份，即為種群中個體的維度，每個維度在[0,10]內取值，即為縱坐標數值。尋優目的為通過迭代規劃出一條不與障礙物發生碰撞且長度最短的路徑。路徑表示為：

{(x1,y1),(x2,y2),…,(xn+1,yn+1)}

其中，(x1,y1)為路徑起點，(xn+1,yn+1)為路徑終點。

評價函數L的第1部分表示路徑長度，第2部分表示路徑與所有障礙物的總碰撞程度,如式(17)所示：

(17)

其中，M為障礙物個數;ω為懲罰因子，本文設定ω為100;h(m)為第m個障礙物與路徑的碰撞程度，計算公式如式(18)所示：

h(m)=

(18)

其中，a(m),b(m)和R(m)分別表示第m個障礙物的圓心橫坐標、縱坐標和障礙物半徑。

5.2 路徑規劃仿真實驗

選取算法PSO、GWO、WOA與AWOA應用于路徑規劃實驗，每種算法分別進行30次獨立實驗，每次實驗進行500次迭代，種群規模設置為50。

5.2.1 場景1路徑規劃仿真實驗

場景1下的實驗結果如圖4所示?？梢钥闯?AWOA規劃出的路徑波動較小且路徑較優，表明其穩定性較高且局部搜索能力較強。

Figure 4 Path planning results of scene 1 圖4 場景1路徑規劃結果

30次實驗對比結果如表3所示，分析路徑長度的最小值、最大值、平均值及標準差對算法的優劣進行評價。其中，最小值能夠體現算法的收斂精度，最大值、平均值及標準差可以體現出規劃結果的穩定性。

Table 3 Experimental results of scene 1

從表3可以看到,AWOA及PSO算法規劃的最優路徑長度最短，但PSO算法規劃結果最不穩定，最長路徑可達17.925 4。相比于其余3種經典算法，本文算法AWOA規劃出的路徑無論在精度方面還是穩定性方面的表現都是最優的。

綜合各個評價指標，選取實驗中表現較優的WOA和AWOA再進行實驗對比，對比結果如圖5所示?？梢钥闯?WOA的規劃結果波動較大，且路徑較長；而AWOA的規劃結果在精度和穩定性方面較WOA都有所提升，能較為穩定地接近最優值。

Figure 5 Comparison of WOA and AWOA experimental results in scene 1圖5 場景1中WOA與AWOA實驗結果對比圖

5.2.2 場景2路徑規劃仿真實驗

場景2較為復雜，用來檢驗算法在存在較多局部最優路徑的情況下的收斂精度，以及是否具有跳出局部極值的能力。

圖6為場景2下各算法的規劃結果。從圖6中可以看出，AWOA的實驗結果大體上只有3條路徑，且收斂精度較高，表明其在更復雜的場景下同樣具有較好的穩定性以及局部開發能力，即便在陷入某一區域無法收斂到全局最優的情況下，也能更徹底地進行局部搜索，提升收斂精度。

表4為場景2下各算法的實驗結果。對比表3和表4可以看出，隨著環境的復雜程度增加，算法之間的差異性也更加明顯，也更體現出了AWOA的優越性。從表4可以看出，AWOA和PSO算法規劃出的最優路徑長度最短，但PSO算法的規劃結果穩定性仍然較差；相比于PSO、GWO和WOA，AWOA規劃的路徑最大值分別降低了42.71%,45.09%和8.17%,平均值分別降低了13.78%,14.78%和2%,標準差分別降低了91.83%,90.87%和3.76%,這表明在較為復雜的場景下，AWOA的路徑規劃精度及穩定性仍然是最優的。

Table 4 Experimental results of scene 2

選取WOA和AWOA的30次實驗結果進行對比，如圖7所示。WOA的實驗結果中僅有3次接近最優路徑，并且路徑長度波動幅度較大。而AWOA雖然不能保證每次規劃出的路徑都接近全局最優，但可以看出其跳出局部極值的能力更優，且能穩定地收斂到極值。

Figure 7 Comparison of WOA and AWOA experimental results in scene 2圖7 場景2中WOA與AWOA實驗結果對比圖

5.2.3 場景3路徑規劃仿真實驗

為進一步驗證算法的尋優能力，設置場景3增加障礙物個數并添加凹形障礙物，以增加更多局部最優點，以此來檢驗算法跳出局部最優的能力。圖8表明，在增加了路徑尋優難度的情況下，AWOA的路徑規劃結果及穩定性仍優于其余3種算法，表明AWOA在提升了局部搜索能力的同時仍然具有較好的跳出局部最優值的能力。

Figure 8 Path planning results of scene 3 圖8 場景3路徑規劃結果

復雜環境中，算法進行路徑規劃通常需要跳出規劃過程中的數個局部極小值才能最終收斂到最優值附近。因此，在復雜環境中的路徑規劃結果更能體現算法跳出局部最優的能力。圖9為AWOA在場景3下的迭代過程，可以看出AWOA多次跳出了局部極小值，最終收斂到最優值附近。此外，為了更加直觀地體現出AWOA的優勢，仍選取WOA和AWOA的30次實驗結果進行對比，如圖10所示。可以看出，在整體測試下，AWOA更能穩定地收斂于最優值附近。以上分析皆表明,AWOA具有較好的脫離局部極小值的能力。

Figure 9 Path planning iteration diagram of AWOA圖9 AWOA路徑規劃迭代圖

Figure 10 Comparison of WOA and AWOA experimental results in scene 3圖10 場景3中WOA與AWOA實驗結果對比圖

6 結束語

標準鯨魚優化算法的局部搜索能力不足、收斂速度慢等問題導致了其收斂精度較低，因此本文提出了一種自適應鯨魚快速優化算法AWOA。首先，使個體依據樣本特性進行位置更新，實現算法的快速收斂，并在全局搜索與局部搜索之間達到動態平衡；其次，利用Levy Flight進行二次優化，進一步擴大種群的多樣性，保證算法的全局搜索能力。利用標準測試函數驗證算法的性能，實驗結果表明，本文所提改進策略使算法在收斂速度和收斂精度等方面均有所提升。最后將AWOA應用于路徑規劃，證實了算法具有較強的局部搜索能力和跳出局部最優的能力，也驗證了算法的可行性。后續研究將從2個方向入手：(1)將算法運用于機器人，檢驗其運用在真實環境中的性能。(2)考慮實驗環境中的動態因素，進一步提高算法的性能。