鯨魚優(yōu)化算法的全局收斂性分析及參數(shù)選擇研究

馮文濤,鄧 兵

(盲信號處理國家級重點(diǎn)實(shí)驗(yàn)室,四川成都 610041)

1 引言

在社會(huì)生活的各個(gè)領(lǐng)域,最優(yōu)化的需求一直存在.隨著科學(xué)的發(fā)展與技術(shù)的進(jìn)步,越來越多的最優(yōu)化問題呈現(xiàn)出大規(guī)模、不連續(xù)、非線性、目標(biāo)函數(shù)不可導(dǎo)甚至表達(dá)式未知等特點(diǎn),傳統(tǒng)的最速下降法、最小二乘法等優(yōu)化方法難以很好的解決此類優(yōu)化問題.隨之應(yīng)運(yùn)而生的智能優(yōu)化算法也被稱作啟發(fā)式算法,是一種依概率搜索的隨機(jī)優(yōu)化算法.群體智能算法屬于智能優(yōu)化算法的一個(gè)分支[1],它通過模仿自然界中生物群體組織表現(xiàn)出的智慧行為來形成相應(yīng)的智能計(jì)算方法,如蟻群算法[2]、蜂群算法[3]等.

鯨魚優(yōu)化算法[4](whale optimization algorithm,WOA)是2016年由Mirjalili等人提出的一種新型群體智能優(yōu)化算法,它模仿的是大海中鯨魚群的集體捕食方式.鯨魚優(yōu)化算法包含了3種獨(dú)立求解的種群更新機(jī)制,因此其尋優(yōu)階段的全局探索和局部開發(fā)過程得以分別運(yùn)行及控制.此外,鯨魚優(yōu)化算法不需要人為的設(shè)置各種控制參數(shù)值,提高了算法的使用效率并降低了應(yīng)用難度.而常見的粒子群算法[5]、差分進(jìn)化算法[6]等進(jìn)化算法一般只含有單一的種群更新方式,致使算法中探索能力和開發(fā)能力的平衡較為困難,而且這些算法控制參數(shù)值的設(shè)置成功與否直接決定了算法最終的求解性能高低.與其它群體智能優(yōu)化算法相比,WOA算法結(jié)構(gòu)新穎,參數(shù)設(shè)置簡單,自問世以來在函數(shù)優(yōu)化[7–9]和工程領(lǐng)域[10–12]均得到了廣泛的應(yīng)用.但是目前關(guān)于WOA算法的理論分析在國內(nèi)外很少有文獻(xiàn)報(bào)道,文獻(xiàn)[13]提出了一種量子鯨魚優(yōu)化算法QWOA并對其進(jìn)行了收斂性證明,但文中對WOA算法并沒有給出明確的理論分析.在WOA算法的參數(shù)選取研究方面,文獻(xiàn)[14]提出并仿真比較了WOA算法在各種控制策略下的性能差異,研究結(jié)果表明控制參數(shù)a的變化明顯影響算法的最終收斂精度.文獻(xiàn)[8]通過對WOA算法中A參數(shù)的變化情況進(jìn)行分析,提出了一種指數(shù)形式和隨機(jī)分布相混合的a參數(shù)非線性變化策略.總的來說,雖然大部分文獻(xiàn)對于改進(jìn)WOA算法的參數(shù)選擇方式做了一定的嘗試,但是均沒有從理論分析的角度明確算法合理的參數(shù)選擇范圍.常見的參數(shù)選取分析方法有閉環(huán)控制系統(tǒng)[15]、李雅普諾夫穩(wěn)定準(zhǔn)則[16–17]、馮諾依曼穩(wěn)定準(zhǔn)則[18]等,其主要研究對象也局限于粒子群算法等經(jīng)典優(yōu)化算法.由于近年來群體智能優(yōu)化算法大量涌現(xiàn),當(dāng)前該領(lǐng)域的理論研究工作仍顯薄弱.

隨機(jī)過程中的馬爾科夫(Markov)鏈理論目前已經(jīng)成功應(yīng)用于粒子群算法[19]、人工蜂群算法[20]、文化算法[21]、雞群算法[22]等隨機(jī)優(yōu)化算法的收斂性分析.本文首先采用馬爾科夫鏈理論對WOA算法的收斂性進(jìn)行分析,證明了WOA算法的全局收斂性由算法中的收縮包圍機(jī)制所決定.在完成WOA算法收斂性分析的基礎(chǔ)上,建立了WOA算法收縮包圍機(jī)制的雙層有限差分模型,并基于馮諾依曼穩(wěn)定準(zhǔn)則給出了WOA算法收縮包圍機(jī)制由穩(wěn)定性決定的合理參數(shù)選擇區(qū)域.最后對不同參數(shù)選擇方式時(shí)算法在標(biāo)準(zhǔn)測試函數(shù)上的性能做了仿真和比較,實(shí)驗(yàn)結(jié)果也驗(yàn)證了本文分析的有效性.

2 WOA算法的模型

收縮包圍機(jī)制的數(shù)學(xué)模型定義如下:

在螺旋更新位置階段,其數(shù)學(xué)模型可表示為

算法1WOA算法偽代碼.

設(shè)置算法初始參數(shù).

生成初始種群P0.

選擇P0中目標(biāo)函數(shù)值最優(yōu)的個(gè)體作為當(dāng)前種群最優(yōu)解.

計(jì)算所有種群個(gè)體的目標(biāo)函數(shù)值.

選擇目標(biāo)函數(shù)值最優(yōu)的個(gè)體作為當(dāng)前種群最優(yōu)解.

算法結(jié)束,返回當(dāng)前所獲得的最優(yōu)解.

3 鯨魚優(yōu)化算法的收斂性分析

由于離散空間中WOA算法的種群數(shù)量和狀態(tài)個(gè)數(shù)有限,因此種群序列也是一個(gè)有限馬氏鏈.根據(jù)算法1描述的WOA算法偽代碼可知,每一次算法找到的當(dāng)前最優(yōu)目標(biāo)函數(shù)值均會(huì)被記錄下來而不會(huì)丟棄,因此WOA算法采用了精英保留策略,其對應(yīng)的馬爾科夫過程是一個(gè)吸收態(tài)馬爾科夫過程.

定理1只含有螺旋更新機(jī)制的WOA算法不能依概率全局收斂.

證假定WOA算法個(gè)體i在時(shí)刻t陷入局部最優(yōu)狀態(tài)g(t),對于螺旋更新機(jī)制而言,其離散空間上的迭代形式為

因此其一步轉(zhuǎn)移概率為

令B?為WOA算法的全局最優(yōu)解集,B為局部最優(yōu)解的擴(kuò)充集合,假設(shè)在t時(shí)刻所有個(gè)體均陷入局部最優(yōu)解g(t),根據(jù)其一步轉(zhuǎn)移概率可知

因此只含有螺旋更新機(jī)制的WOA算法將會(huì)以一定概率進(jìn)入局部最優(yōu)解集的吸收態(tài)而無法跳出.也就是說存在一個(gè)非空閉集B,使得迭代次數(shù)趨于無窮時(shí),種群序列收斂到全局最優(yōu)解集B?的概率小于1,因此只含有螺旋更新機(jī)制的WOA算法無法確保依概率全局收斂. 證畢.

定理2只含有收縮包圍機(jī)制的WOA算法依概率全局收斂.

由于參數(shù)A和C在每次迭代過程中隨機(jī)取值,因此只含有收縮包圍機(jī)制的WOA算法很難陷入局部最優(yōu).

令B?為WOA算法的全局最優(yōu)解集,假設(shè)只含有收縮包圍機(jī)制的WOA算法個(gè)體i在第t次迭代時(shí)仍未進(jìn)入全局最優(yōu)解集B?,則有

根據(jù)收縮包圍機(jī)制的一步轉(zhuǎn)移概率可知其不會(huì)陷入局部最優(yōu)狀態(tài),因此在迭代過程中個(gè)體i會(huì)以一定概率進(jìn)入全局最優(yōu)解集并保持下去,即

由此可知只含有收縮包圍機(jī)制的WOA算法在迭代次數(shù)趨于無窮大時(shí)依概率收斂于全局最優(yōu)值.

證畢.

定理3WOA算法依概率全局收斂.

證由于WOA算法在迭代后期|A|<1恒成立,因此算法中只含有螺旋更新機(jī)制和收縮包圍機(jī)制且兩種機(jī)制的選擇概率相等.即使某一鯨魚個(gè)體在螺旋更新階段陷入局部最優(yōu)解,也可以很快在收縮包圍階段跳出局部最優(yōu).根據(jù)定理1和定理2,WOA算法在迭代次數(shù)趨于無窮大時(shí),最終可以依概率收斂于全局最優(yōu)值. 證畢.

4 鯨魚優(yōu)化算法的參數(shù)選擇研究

雖然WOA算法可以依概率全局收斂,但是在實(shí)際應(yīng)用中所有的智能優(yōu)化算法均不可能無限次迭代,因此在完成WOA算法收斂性分析的基礎(chǔ)上,必須對合理的參數(shù)選擇范圍進(jìn)行進(jìn)一步研究,以加快WOA算法收斂的速度.根據(jù)第3節(jié)中的定理1可知,WOA算法的螺旋更新機(jī)制由于易陷于局部最優(yōu)解集而無法依概率全局收斂,因此本節(jié)主要研究WOA算法收縮包圍機(jī)制穩(wěn)定收斂時(shí)的合理參數(shù)選擇范圍.

有限差分近似是解決線性偏微分方程初值問題的一種有效方法[24].WOA算法的連續(xù)解空間在離散化后,首先對求解區(qū)域作網(wǎng)格剖分,然后構(gòu)造其差分方程的雙層有限差分格式,最后使用馮諾依曼穩(wěn)定準(zhǔn)則[25]判斷該差分格式的穩(wěn)定性及方程穩(wěn)定時(shí)的參數(shù)取值.

WOA算法中收縮包圍機(jī)制的式(4)可以寫成如下格式:

式中:i∈{1,2,···,N},k∈{1,2,···,Dm},N為算法種群中的個(gè)體的總數(shù);Dm為所求解目標(biāo)函數(shù)的維度;t為當(dāng)前算法的迭代次數(shù);Xi,k(t)和Xi,k(t+1)分別表示第t次和第t+1次迭代時(shí),第i個(gè)候選解在第k維上的值;Xbest,k(t)表示第t次迭代時(shí),當(dāng)前鯨魚種群的最優(yōu)解在第k維上的值.

由于WOA算法中的鯨魚個(gè)體更新自身位置時(shí)均按照每一個(gè)維度單獨(dú)進(jìn)行,因此不失一般性的可以將高維的WOA算法降低到一維進(jìn)行分析.因此式(15)可以進(jìn)一步寫成

作為當(dāng)前最優(yōu)解的鯨魚個(gè)體Xbest(t),可以假定其為種群中的第r個(gè)鯨魚個(gè)體Xr(t),且r=i+a,a∈{1,2,···,N},r∈{1,2,···,N}.將其代入式(16)可得

式(17)的差分方程形式表示如下:

由于方程在i?t離散網(wǎng)格節(jié)點(diǎn)上的近似解可以表示為Xm,n=X(im,tn),因此(18)在網(wǎng)格點(diǎn)Xm,n上的雙層有限差分格式如下所示:

下面分3種情況對式(20)進(jìn)行考慮:

a) 當(dāng)Cvn(k)eik(m+a)?x?vn(k)eikm?x=0或A=0時(shí),式(20)化簡可得

此時(shí)|g(k)|=1恒成立,因此算法處于邊緣穩(wěn)定狀態(tài).

由于WOA算法中參數(shù)A和C隨機(jī)取值,由定理2可知收縮包圍機(jī)制不易陷入局部最優(yōu)狀態(tài),因此在WOA 算法迭代過程中A=0或

成立的概率很小,后續(xù)研究中可以忽略不計(jì).

b) 當(dāng)Cvn(k)eik(m+a)?x?vn(k)eikm?x >0時(shí),式(20)可寫成

對式(22)進(jìn)行簡化可得

令θ=ka?x,則eika?x=eiθ=cosθ+isinθ,代入式(23)并進(jìn)行整理可得

由于式(24)只含有一個(gè)獨(dú)立變量,根據(jù)馮諾依曼穩(wěn)定性準(zhǔn)則,其穩(wěn)定的充要條件是|g(k)|1,等價(jià)于下式成立:

對式(25)進(jìn)行簡化可得

此時(shí)參數(shù)A和C的取值范圍為

而式(27)成立的必要條件是

此時(shí)僅部分θ的取值能滿足式(27),對應(yīng)的參數(shù)A和C的取值范圍為

c) 當(dāng)Cvn(k)eik(m+a)?x?vn(k)eikm?x <0時(shí),方程穩(wěn)定的條件如下:

同理,式(32)對?θ成立的充分條件為

此時(shí)參數(shù)A和C的取值范圍為

僅部分θ的取值滿足式(32)成立時(shí)的必要條件為

此時(shí)參數(shù)A和C的取值范圍為

綜上所述,式(29)(31)所示的參數(shù)A和C取值范圍為WOA算法收縮包圍機(jī)制CXbest(t)?Xi(t)>0時(shí)確定穩(wěn)定及不確定穩(wěn)定的合理參數(shù)選擇區(qū)域,如圖1–2所示.

圖1 WOA算法收縮包圍機(jī)制確定穩(wěn)定的參數(shù)選擇區(qū)域Fig.1 The stable range of control parameters in shrinking encircling mechanism of WOA

圖2 WOA算法收縮包圍機(jī)制不確定穩(wěn)定的參數(shù)選擇區(qū)域Fig.2 The uncertain range of control parameters in shrinking encircling mechanism of WOA

式(34)(36)所示的參數(shù)A和C取值范圍為WOA算法收縮包圍機(jī)制CXbest(t)?Xi(t)<0時(shí)確定穩(wěn)定及不確定穩(wěn)定的合理參數(shù)選擇區(qū)域,如圖3–4所示.從圖1–4可以看出,不確定穩(wěn)定區(qū)域顯然大于確定穩(wěn)定區(qū)域.另外對于不確定穩(wěn)定區(qū)域以外的參數(shù)A和C取值而言,WOA算法的差分格式是一定發(fā)散而不穩(wěn)定的,因此A和C參數(shù)取值在該區(qū)域內(nèi)的WOA算法是不收斂的.

圖3 WOA算法收縮包圍機(jī)制確定穩(wěn)定的參數(shù)選擇區(qū)域Fig.3 The stable range of control parameters in shrinking encircling mechanism of WOA

圖4 WOA算法收縮包圍機(jī)制不確定穩(wěn)定的參數(shù)選擇區(qū)域Fig.4 The uncertain range of control parameters in shrinking encircling mechanism of WOA

對于依概率搜索的鯨魚優(yōu)化算法而言,即使在收縮包圍機(jī)制確定穩(wěn)定的參數(shù)A和C選擇區(qū)域內(nèi)取值,使得收縮包圍機(jī)制能確定收斂,但是由于螺旋更新機(jī)制也容易陷入局部最優(yōu)解集而使得鯨魚優(yōu)化算法后期的全局探索能力嚴(yán)重匱乏,因此不能確保算法在該條件下收斂到全局最優(yōu).

5 仿真實(shí)驗(yàn)分析

為了驗(yàn)證WOA算法全局收斂性分析和收縮包圍機(jī)制參數(shù)選擇范圍分析的正確性,本文選取了文獻(xiàn)[4]中表2–3所示的f1(x)～f13(x)共13組可變維度的標(biāo)準(zhǔn)測試函數(shù)來對算法進(jìn)行仿真研究,如表1所示.其中f1(x)～f7(x)為高維的單峰函數(shù),f8(x)～f13(x)為高維的多峰函數(shù),所有測試函數(shù)的維度均為30維.標(biāo)準(zhǔn)函數(shù)f8(x)的理論最小值為?418.9829×30,其余標(biāo)準(zhǔn)函數(shù)的理論最小值均為0.表1中f12(x)有

表1 標(biāo)準(zhǔn)測試函數(shù)f1(x)～f13(x)Table 1 Benchmark functions f1(x)～f13(x)

為了驗(yàn)證WOA算法中不同種群更新機(jī)制對全局收斂性的影響,對以下3種算法進(jìn)行了仿真分析和比較:只含有螺旋更新機(jī)制的WOASU算法、只含有收縮包圍機(jī)制的WOAEP算法和經(jīng)典WOA算法.所有算法的種群大小設(shè)置為30,迭代次數(shù)為500,算法的獨(dú)立運(yùn)行次數(shù)為30,算法內(nèi)部其它基本參數(shù)設(shè)置完全相同.記錄30次試驗(yàn)中每種算法在標(biāo)準(zhǔn)測試函數(shù)上所得最佳適應(yīng)度的最優(yōu)值和平均值,結(jié)果如表2所示.

從表2的結(jié)果可以看出,WOASU算法在所有標(biāo)準(zhǔn)測試函數(shù)上性能最差且無法收斂到全局最優(yōu)解,WOAEP算法在大部分標(biāo)準(zhǔn)測試函數(shù)上的收斂精度均優(yōu)于收縮包圍和螺旋更新機(jī)制同時(shí)存在的經(jīng)典WOA算法.而WOA算法在復(fù)雜的高維多峰函數(shù)f12(x)上的收斂平均值略優(yōu)于WOAEP算法,其原因是WOA算法的搜索覓食機(jī)制增強(qiáng)了迭代過程中種群的多樣性.對于標(biāo)準(zhǔn)測試函數(shù)f3(x),由于3種算法在500次迭代次數(shù)內(nèi)均無法收斂到令人滿意的精度,圖5示出了迭代次數(shù)為50000時(shí)3種算法最佳適應(yīng)度的平均值收斂曲線.

表2 WOASU算法、WOAEP算法和WOA算法的性能比較Table 2 The comparison results of WOASU,WOAEP and WOA algorithms

從圖5中可以看出隨著迭代次數(shù)的增加,WOA算法和WOAEP算法均能穩(wěn)定收斂,而WOASU算法仍然陷入局部最優(yōu)無法跳出,因此第3節(jié)中對于WOA算法全局收斂性的分析結(jié)論是正確和有效的.

圖5 WOAEP,WOASU和WOA算法在標(biāo)準(zhǔn)測試函數(shù)f3(x)上收斂曲線圖Fig.5 Convergence plots of WOAEP,WOASU and WOA algorithms on benchamrk function f3(x)

對于只含有收縮包圍種群更新機(jī)制的WOA算法,根據(jù)參數(shù)A和C取值范圍的不同,對以下4種算法進(jìn)行仿真分析和比較:參數(shù)取值位于確定穩(wěn)定區(qū)域的WOAEP–Stable算法,參數(shù)取值位于不確定穩(wěn)定區(qū)域且不包含確定穩(wěn)定區(qū)域的WOAEP–Uncertain算法,參數(shù)取值位于不確定穩(wěn)定區(qū)域以外的WOAEP–Unstable算法和經(jīng)典的WOA算法.

仿真實(shí)驗(yàn)過程中參數(shù)A和C的取值方法是:首先確定當(dāng)前迭代次數(shù)下參數(shù)A的取值,然后根據(jù)不同算法的要求隨機(jī)生成能滿足CXbest(t)?Xi(t)取值范圍限制的參數(shù)C,若無法找到滿足條件的參數(shù)C,則返回算法初始階段改變參數(shù)A的取值,重復(fù)進(jìn)行上述操作直至找到一組滿足約束條件的參數(shù)A和C取值為止.

4種算法在標(biāo)準(zhǔn)測試函數(shù)上所得最佳適應(yīng)度的最優(yōu)值和平均值結(jié)果如表3所示.

表3 WOAEP–Unstable算法、WOAEP–Stable算法、WOAEP–Uncertain算法和WOA算法的性能比較Table 3 The comparison results of WOAEP–Unstable,WOAEP–Stable,WOAEP–Uncertain and WOA algorithms

從表3的結(jié)果可以看出,WOAEP–Unstable算法在所有的標(biāo)準(zhǔn)測試函數(shù)上均無法收斂到全局最優(yōu)解,表明WOAEP–Unstable算法是發(fā)散而不穩(wěn)定收斂的.WOAEP–Stable算法在單模函數(shù)f1(x),f3(x),f4(x),f7(x)和多模函數(shù)f9(x)～f11(x)上的收斂精度明顯優(yōu)于WOAEP–Uncertain算法,在其他測試函數(shù)上WOAEP–Stable算法的性能則稍弱于WOAEP–Uncertain算法.

為了進(jìn)一步比較不同算法在標(biāo)準(zhǔn)測試函數(shù)上的收斂速度,繪出4種算法在標(biāo)準(zhǔn)測試函數(shù)上最佳目標(biāo)函數(shù)值的平均值收斂曲線,如圖6–7所示.從圖中可以看出除函數(shù)f8(x)以外,WOAEP–Stable算法的收斂速度最快,且在函數(shù)f9(x)和f11(x)上WOAEP–Stable算法能快速穩(wěn)定收斂到理論最優(yōu)值0.這表明確定穩(wěn)定的A和C參數(shù)選擇方法能保證算法差分方程求解時(shí)的誤差影響不會(huì)隨著迭代次數(shù)的增加而上升,也就保證了算法在該參數(shù)選擇域內(nèi)取值是一定確保收斂的.WOAEP–Unstable算法在所有測試函數(shù)上很早就陷入局部最優(yōu),而WOAEP–Uncertain算法的收斂速度在各測試函數(shù)上并不穩(wěn)定.比如WOAEP–Uncertain算法在函數(shù)f3(x)和f4(x)上收斂性極弱,在函數(shù)f1(x),f7(x),f9(x),f10(x)和f11(x)上收斂速度明顯比WOAEP–Stable算法慢,而在函數(shù)f2(x),f5(x),f6(x),f12(x)和f13(x)上雖然其收斂速度稍慢,但是在算法的迭代后期可以達(dá)到優(yōu)于WOAEP–Stable算法的收斂精度.這是由于WOAEP–Uncertain算法每次迭代過程中其差分方程不確定穩(wěn)定,也就意味著算法迭代時(shí)可能收斂也可能發(fā)散,從而使得該算法可以保持一定的全局開發(fā)能力.而確定收斂的WOAEP–Stable算法在迭代后期的全局開發(fā)能力較弱,因此WOAEP–Uncertain算法可以在部分測試函數(shù)上取得優(yōu)于WOAEP–Stable算法的收斂精度.由于經(jīng)典的鯨魚優(yōu)化算法WOA同時(shí)具有收斂性迥異的螺旋更新機(jī)制和收縮包圍機(jī)制,其在大部分標(biāo)準(zhǔn)測試函數(shù)上也顯示出了與WOAEP–Uncertain算法相類似的性能.

圖6 WOAEP–Uncertain算法、WOAEP–Unstable算法、WOAEP–Stable算法和WOA算法在函數(shù)f1(x)～f8(x)上的收斂曲線圖Fig.6 Convergence plots of WOAEP–Uncertain,WOAEP–Unstable,WOAEP–Stable and WOA algorithms on benchmark functions f1(x)～f8(x)

圖7 WOAEP–Uncertain算法、WOAEP–Unstable算法、WOAEP–Stable算法和WOA算法在函數(shù)f9(x)～f13(x)上的收斂曲線圖Fig.7 Convergence plots of WOAEP–Uncertain,WOAEP–Unstable,WOAEP–Stable and WOA algorithms on benchmark functions f9(x)～f13(x)

6 結(jié)論

本文采用隨機(jī)過程中的馬爾科夫鏈理論對WOA算法的收斂性進(jìn)行了分析,論證了WOA算法的依概率全局收斂性,證明了WOA算法的全局收斂性由算法中的收縮包圍機(jī)制所決定.在此基礎(chǔ)上基于馮諾依曼穩(wěn)定準(zhǔn)則給出了收縮包圍機(jī)制中參數(shù)A和C的合理取值范圍.在標(biāo)準(zhǔn)測試函數(shù)上的仿真實(shí)驗(yàn)結(jié)果也證明了參數(shù)A和C的不同選擇方法對于WOA算法收縮包圍機(jī)制的收斂或發(fā)散有著重要影響.