一種自適應(yīng)鯨魚快速優(yōu)化算法*

楊炳媛,袁 杰,郭園園

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

1 引言

鯨魚優(yōu)化算法是Mirjalili等人[1]受到座頭鯨群體圍捕獵物行為的啟發(fā)，于2016年提出的一種智能仿生算法。標(biāo)準(zhǔn)鯨魚優(yōu)化算法具有可調(diào)節(jié)參數(shù)少、魯棒性強(qiáng)、易于實(shí)現(xiàn)等優(yōu)點(diǎn)。文獻(xiàn)[1]表明，相比于粒子群優(yōu)化算法、遺傳算法等部分經(jīng)典優(yōu)化算法，鯨魚優(yōu)化算法具有更好的全局探索能力。雖然鯨魚優(yōu)化算法的全局搜索能力在一定程度上更具優(yōu)勢，但其局部搜索能力和收斂速度仍有待提高。

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

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

2 標(biāo)準(zhǔn)鯨魚優(yōu)化算法

在尋優(yōu)過程中，標(biāo)準(zhǔn)鯨魚優(yōu)化算法有以下3種行為方式可供選擇。

2.1 包圍捕獵方式

(1)

(2)

A=2ar1-a

(3)

C=2r2

(4)

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

(5)

其中，M為最大迭代次數(shù)。

2.2 隨機(jī)捕獵方式

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

(6)

(7)

2.3 螺旋捕獵方式

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

(8)

(9)

其中，l為[0,1]內(nèi)的隨機(jī)數(shù)，b為常數(shù)參數(shù)。

3 自適應(yīng)鯨魚快速優(yōu)化算法

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

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

3.1 自適應(yīng)選擇策略

本文設(shè)計(jì)了一種自適應(yīng)選擇策略，根據(jù)樣本特性即樣本中個(gè)體的集散程度來選擇尋優(yōu)策略，以實(shí)現(xiàn)全局搜索與局部搜索之間的動態(tài)平衡。由于標(biāo)準(zhǔn)差最能體現(xiàn)樣本的集散程度，因此結(jié)合標(biāo)準(zhǔn)差公式，用式(10)和式(11)衡量個(gè)體偏離整體樣本的程度[20]：

(10)

(11)

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

(12)

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

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

3.2 基于Levy Flight的二次優(yōu)化

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

(13)

其中，x(k)表示需進(jìn)行二次優(yōu)化的個(gè)體在第k次迭代時(shí)的位置，α0為常數(shù)0.01，rand為[0,1]內(nèi)的隨機(jī)數(shù)，s為Levy Flight的數(shù)學(xué)模型,如式(14)所示：

(14)

根據(jù)式(13)和式(14)，Levy Flight的二次優(yōu)化數(shù)學(xué)模型可以寫為式(15)：

(15)

3.3 自適應(yīng)鯨魚快速優(yōu)化算法流程

不同于標(biāo)準(zhǔn)鯨魚優(yōu)化算法根據(jù)|A|的取值選擇狩獵方式，AWOA主要根據(jù)個(gè)體特性自適應(yīng)選擇捕獵方式，其流程如圖1所示。

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

自適應(yīng)快速鯨魚優(yōu)化算法AWOA的具體步驟如下所示：

步驟1相關(guān)參數(shù)初始化。

步驟2在搜索區(qū)域內(nèi)生成初始種群并記錄最優(yōu)值。

步驟3更新相關(guān)參數(shù)，主要參數(shù)有A,C,l,P。

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

步驟5針對T

步驟6計(jì)算適應(yīng)度值，更新最優(yōu)信息。

步驟7判斷是否達(dá)到最大迭代次數(shù)，若是則輸出最優(yōu)信息，否則跳轉(zhuǎn)至步驟3。

4 算法性能測試及結(jié)果分析

4.1 算法性能測試函數(shù)

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

4.2 性能測試及結(jié)果分析

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

Table 1 Test functions

Table 2 Comparison of function test results of some algorithms

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

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

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

5 路徑規(guī)劃實(shí)驗(yàn)

本文將所提改進(jìn)算法應(yīng)用于路徑規(guī)劃仿真實(shí)驗(yàn)，并與經(jīng)典算法進(jìn)行對比，以進(jìn)一步驗(yàn)證其有效性。

5.1 環(huán)境建模及適應(yīng)度函數(shù)

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

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

(16)

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

Figure 3 Modeling of path planning map 圖3 路徑規(guī)劃地圖建模

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

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

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

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

(17)

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

h(m)=

(18)

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

5.2 路徑規(guī)劃仿真實(shí)驗(yàn)

選取算法PSO、GWO、WOA與AWOA應(yīng)用于路徑規(guī)劃實(shí)驗(yàn)，每種算法分別進(jìn)行30次獨(dú)立實(shí)驗(yàn)，每次實(shí)驗(yàn)進(jìn)行500次迭代，種群規(guī)模設(shè)置為50。

5.2.1 場景1路徑規(guī)劃仿真實(shí)驗(yàn)

場景1下的實(shí)驗(yàn)結(jié)果如圖4所示。可以看出,AWOA規(guī)劃出的路徑波動較小且路徑較優(yōu)，表明其穩(wěn)定性較高且局部搜索能力較強(qiáng)。

Figure 4 Path planning results of scene 1 圖4 場景1路徑規(guī)劃結(jié)果

30次實(shí)驗(yàn)對比結(jié)果如表3所示，分析路徑長度的最小值、最大值、平均值及標(biāo)準(zhǔn)差對算法的優(yōu)劣進(jìn)行評價(jià)。其中，最小值能夠體現(xiàn)算法的收斂精度，最大值、平均值及標(biāo)準(zhǔn)差可以體現(xiàn)出規(guī)劃結(jié)果的穩(wěn)定性。

Table 3 Experimental results of scene 1

從表3可以看到,AWOA及PSO算法規(guī)劃的最優(yōu)路徑長度最短，但PSO算法規(guī)劃結(jié)果最不穩(wěn)定，最長路徑可達(dá)17.925 4。相比于其余3種經(jīng)典算法，本文算法AWOA規(guī)劃出的路徑無論在精度方面還是穩(wěn)定性方面的表現(xiàn)都是最優(yōu)的。

綜合各個(gè)評價(jià)指標(biāo)，選取實(shí)驗(yàn)中表現(xiàn)較優(yōu)的WOA和AWOA再進(jìn)行實(shí)驗(yàn)對比，對比結(jié)果如圖5所示?？梢钥闯?WOA的規(guī)劃結(jié)果波動較大，且路徑較長；而AWOA的規(guī)劃結(jié)果在精度和穩(wěn)定性方面較WOA都有所提升，能較為穩(wěn)定地接近最優(yōu)值。

Figure 5 Comparison of WOA and AWOA experimental results in scene 1圖5 場景1中WOA與AWOA實(shí)驗(yàn)結(jié)果對比圖

5.2.2 場景2路徑規(guī)劃仿真實(shí)驗(yàn)

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

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

表4為場景2下各算法的實(shí)驗(yàn)結(jié)果。對比表3和表4可以看出，隨著環(huán)境的復(fù)雜程度增加，算法之間的差異性也更加明顯，也更體現(xiàn)出了AWOA的優(yōu)越性。從表4可以看出，AWOA和PSO算法規(guī)劃出的最優(yōu)路徑長度最短，但PSO算法的規(guī)劃結(jié)果穩(wěn)定性仍然較差；相比于PSO、GWO和WOA，AWOA規(guī)劃的路徑最大值分別降低了42.71%,45.09%和8.17%,平均值分別降低了13.78%,14.78%和2%,標(biāo)準(zhǔn)差分別降低了91.83%,90.87%和3.76%,這表明在較為復(fù)雜的場景下，AWOA的路徑規(guī)劃精度及穩(wěn)定性仍然是最優(yōu)的。

Table 4 Experimental results of scene 2

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

Figure 7 Comparison of WOA and AWOA experimental results in scene 2圖7 場景2中WOA與AWOA實(shí)驗(yàn)結(jié)果對比圖

5.2.3 場景3路徑規(guī)劃仿真實(shí)驗(yàn)

為進(jìn)一步驗(yàn)證算法的尋優(yōu)能力，設(shè)置場景3增加障礙物個(gè)數(shù)并添加凹形障礙物，以增加更多局部最優(yōu)點(diǎn)，以此來檢驗(yàn)算法跳出局部最優(yōu)的能力。圖8表明，在增加了路徑尋優(yōu)難度的情況下，AWOA的路徑規(guī)劃結(jié)果及穩(wěn)定性仍優(yōu)于其余3種算法，表明AWOA在提升了局部搜索能力的同時(shí)仍然具有較好的跳出局部最優(yōu)值的能力。

Figure 8 Path planning results of scene 3 圖8 場景3路徑規(guī)劃結(jié)果

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

Figure 9 Path planning iteration diagram of AWOA圖9 AWOA路徑規(guī)劃迭代圖

Figure 10 Comparison of WOA and AWOA experimental results in scene 3圖10 場景3中WOA與AWOA實(shí)驗(yàn)結(jié)果對比圖

6 結(jié)束語

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