李東升, 李萬(wàn)龍, 劉祥坤

(長(zhǎng)春工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院, 吉林 長(zhǎng)春 130102)

0 引 言

近年來(lái),研究人員對(duì)群體智能算法的優(yōu)化(SI)變得非常熱衷。因?yàn)槿后w智能優(yōu)化算法可以高效率解決許多實(shí)際問(wèn)題。元啟發(fā)式算法(Meta-heuristic)是基于計(jì)算智能的機(jī)制求解復(fù)雜優(yōu)化問(wèn)題最優(yōu)解或滿意解的方法,有時(shí)也被稱為智能優(yōu)化算法(Intelligent optimization algorithm)。元啟發(fā)式算法是通過(guò)對(duì)生物、物理、化學(xué)、社會(huì)、藝術(shù)等系統(tǒng),或領(lǐng)域中相關(guān)行為、功能、經(jīng)驗(yàn)、規(guī)則、作用機(jī)理的認(rèn)識(shí),而提出優(yōu)化算法的設(shè)計(jì)原理,并在特定問(wèn)題特征的引導(dǎo)下提煉相應(yīng)的特征模型,設(shè)計(jì)出智能化的迭代搜索型優(yōu)化算法。啟發(fā)式算法主要分為三類:基于進(jìn)化的算法、基于群體智能的算法和基于物理現(xiàn)象的算法。

鯨魚(yú)群優(yōu)化該算法的主要思想是通過(guò)模仿鯨魚(yú)的捕食行為實(shí)現(xiàn)對(duì)目標(biāo)問(wèn)題的求解。Mirjalili S等[1]提出一種群體智能算法,它具有原理簡(jiǎn)單、操作簡(jiǎn)單、易于實(shí)現(xiàn)的顯著優(yōu)點(diǎn)。因?yàn)樗蕾囉诤?jiǎn)單的概念,包含的算子較少,因此引起了許多學(xué)者的關(guān)注。但是,WOA在解決優(yōu)化問(wèn)題方面仍然存在缺陷。

1 相關(guān)研究

近年來(lái),WOA的研究主要分為工程應(yīng)用和理論創(chuàng)新兩個(gè)方面。在工程應(yīng)用中,WOA的實(shí)際應(yīng)用主要基于其操作方便、性能優(yōu)良的特點(diǎn)。鐘明輝等[2]提出一種隨機(jī)調(diào)整控制參數(shù)的鯨魚(yú)優(yōu)化算法;Rkennedy J等[3]提出粒子群算法;沙金霞[4]通過(guò)改進(jìn)鯨魚(yú)算法并應(yīng)用在多目標(biāo)水資源優(yōu)化配置中也取得了良好的效果;Rashedi E等[5]提出一種引力搜索算法,在目前的人工智能應(yīng)用中也有很好的效果;Mehne H H等[6]提出一種基于 Levy飛行的變體來(lái)增強(qiáng)WOA的性能;Mafarja M等[7]提出鯨魚(yú)優(yōu)化算法在數(shù)據(jù)集的特征選擇中具有更好的選擇效果,尤其是在搜索最優(yōu)特征子集時(shí);Abdel-Basset M等[8]提出一種將WOA(稱為HWOA)與本地搜索策略相結(jié)合的新算法;Sayed G I等[9]提出一種針對(duì)數(shù)據(jù)聚類問(wèn)題的多群鯨魚(yú)優(yōu)化算法(MsWOA);郭振洲等[10]提出一種基于自適應(yīng)權(quán)重和柯西變異的鯨魚(yú)優(yōu)化算法;龍文等[11]通過(guò)求解大規(guī)模優(yōu)化問(wèn)題而改進(jìn)鯨魚(yú)優(yōu)化算法;王堅(jiān)浩等[12]提出基于混沌搜索策略的鯨魚(yú)優(yōu)化算法;何慶等[13]提出一種混合策略改進(jìn)的鯨魚(yú)優(yōu)化算法。以上研究結(jié)果表明,鯨魚(yú)應(yīng)用優(yōu)化算法解決實(shí)際問(wèn)題,取得了好的結(jié)果,鯨魚(yú)優(yōu)化算法性能值得肯定,具有重要意義。

2 原始鯨魚(yú)算法的基本思想

鯨魚(yú)優(yōu)化算法的數(shù)學(xué)模型相對(duì)于其他比較流行的群智能算法的數(shù)學(xué)模型比較簡(jiǎn)單[14],參數(shù)也相對(duì)較少,對(duì)其參數(shù)優(yōu)化也容易,原始鯨魚(yú)優(yōu)化模型大致分為三個(gè)階段。

2.1 包圍獵物

因?yàn)樽^鯨能識(shí)別獵物的位置并包圍它們。但是算法的全局最優(yōu)位置沒(méi)有優(yōu)先級(jí),所以在鯨魚(yú)群算法(WOA)的最初設(shè)定中,假設(shè)最優(yōu)解位置是獵物的位置或是最接近獵物的鯨魚(yú)位置,然后,其他鯨魚(yú)向最優(yōu)解的位置通過(guò)變換位置來(lái)進(jìn)行靠攏[9],此行為表示為

(1)

式中:t----當(dāng)前迭代;

A,C----系數(shù)向量;

X*----迄今為止獲得最佳解的位置向量;

X----位置向量;

·----逐個(gè)元素的乘法。

A=2ar-a,

C=2r,

(2)

式中:a----在迭代過(guò)程中從2 線性減小到0(在探索和利用階段);

r----[0,1] 中的隨機(jī)向量。

搜索代理的位置(X,Y)可以根據(jù)當(dāng)前最佳記錄(X*,Y*)的位置更新。通過(guò)調(diào)整“A”和“C”向量的值,可以在當(dāng)前位置實(shí)現(xiàn)最佳代理周圍的不同位置。

(3)

式中:a----參數(shù);

i----當(dāng)前代數(shù);

M----總的迭代次數(shù)。

2.2 螺旋氣泡網(wǎng)攻擊

因?yàn)樽^鯨的捕食行為是通過(guò)泡泡網(wǎng)攻擊的方式來(lái)得到食物,所以對(duì)泡泡網(wǎng)攻擊行為進(jìn)行數(shù)學(xué)建模設(shè)計(jì)的兩種方法為收縮環(huán)繞機(jī)制和螺旋上升機(jī)制。

1)收縮環(huán)繞機(jī)制是由系數(shù)A控制,當(dāng)A≤1時(shí),當(dāng)前鯨魚(yú)開(kāi)始向最優(yōu)解靠攏,并且在這個(gè)過(guò)程中,當(dāng)前代理的位置可能是原始位置和當(dāng)前最佳代理位置之間的任意位置。但是系數(shù)A又是由其中的參數(shù)a來(lái)控制,a是一個(gè)[-A,A]區(qū)間內(nèi)的隨機(jī)值,過(guò)程中從2線性下降到0,當(dāng)達(dá)到0時(shí),表示當(dāng)前鯨魚(yú)的位置已經(jīng)是最優(yōu)解的位置。

2)螺旋上升機(jī)制(螺旋更新位置)的建立是通過(guò)先計(jì)算出當(dāng)前鯨魚(yú)搜索代理(X,Y)和最佳位置的鯨魚(yú)(X*,Y*)之間的距離。然后在兩者之間建立一個(gè)螺旋方程,并模擬座頭鯨的螺旋捕食行為,

X(t+1)=D·ebl·cos(2πl(wèi))+X(t),

(4)

式中:D----第i條鯨魚(yú)到獵物的距離(迄今為止獲得的最佳解);

b----用于定義對(duì)數(shù)螺旋形狀的常數(shù);

l---- [-1,1] 中的隨機(jī)數(shù)。

結(jié)合前面描述,座頭鯨在整個(gè)捕食過(guò)程中,會(huì)在縮小的圓圈內(nèi)圍繞獵物游動(dòng),同時(shí)沿著螺旋形路徑游動(dòng)。通過(guò)一個(gè)隨機(jī)數(shù)P[0,1]來(lái)假設(shè)有50%的概率在優(yōu)化過(guò)程中選擇收縮環(huán)繞機(jī)制或螺旋模型來(lái)更新鯨魚(yú)的位置[10]。 對(duì)應(yīng)的數(shù)學(xué)模型為

(5)

這是我們?cè)谔剿魅褐悄芩惴碧胶烷_(kāi)發(fā)過(guò)程中的開(kāi)發(fā)階段。

2.3 搜索階段

座頭鯨除了捕食行為外,還有尋找獵物的過(guò)程,下面就是對(duì)座頭鯨尋找獵物行為的描述。在前面描述座頭鯨泡泡網(wǎng)攻擊行為的時(shí)候,已經(jīng)明確座頭鯨的捕食行為和尋找獵物行為之間的交替是基于系數(shù)A向量的變化而決定的。 因此,在搜索階段,我們使用大于1或小于-1的隨機(jī)值A(chǔ)來(lái)強(qiáng)制搜索代理遠(yuǎn)離參考鯨魚(yú)。與開(kāi)發(fā)階段相比,在探索階段根據(jù)隨機(jī)選擇的搜索代理,而不是迄今為止找到的最佳搜索代理來(lái)更新搜索代理的位置[11]。 這種機(jī)制和|A|>1 強(qiáng)調(diào)探索并允許WOA算法執(zhí)行全局搜索。數(shù)學(xué)模型為

D=|CXrand-X|,

X(t+1)=Xrand-A·D,

(6)

式中:Xrand----從當(dāng)前種群中選擇的隨機(jī)位置向量(隨機(jī)鯨魚(yú))。

事實(shí)上,座頭鯨是根據(jù)彼此位置隨機(jī)搜索的。

3 改進(jìn)的鯨魚(yú)優(yōu)化算法

WOA算法成功的因素之一是勘探能力和開(kāi)發(fā)能力較其他群智能算法較優(yōu),但是隨著時(shí)間的增長(zhǎng),在實(shí)際應(yīng)用中也暴露出較多缺點(diǎn),如精度低、收斂速度慢、易涉及局部最優(yōu)等。所以,近幾年有許多學(xué)者在優(yōu)化鯨魚(yú)群算法上繼續(xù)做著努力,文中對(duì)鯨魚(yú)算法優(yōu)化的幾個(gè)策略能夠很好地提高該算法的勘探能力和開(kāi)發(fā)能力。

在前人優(yōu)化策略中就有單獨(dú)對(duì)WOA算法的距離控制參數(shù)A進(jìn)行優(yōu)化,得到的效果也比較顯著。因?yàn)樗谡麄€(gè)算法中是在探索和開(kāi)發(fā)之間找到適當(dāng)平衡的主要因素。文中優(yōu)化策略不是繼續(xù)尋求勘探與開(kāi)發(fā)之間的平衡,而是單獨(dú)地對(duì)勘探和開(kāi)發(fā)階段進(jìn)行優(yōu)化,也就是整體全面的優(yōu)化[12]。

3.1 勘探階段優(yōu)化策略

在鯨魚(yú)群算法的勘探階段,就是當(dāng)前搜索代理發(fā)現(xiàn)獵物不是最優(yōu),會(huì)向外繼續(xù)搜索獵物。當(dāng)然這個(gè)行為通過(guò)學(xué)者們抽象用一個(gè)系數(shù)A的范圍來(lái)控制,當(dāng)|A|≥1時(shí),就會(huì)向外搜索,也就是該算法的勘探階段。

在實(shí)際的座頭鯨群搜索獵物過(guò)程中,參照隨機(jī)鯨魚(yú)更新自己的位置,肯定不是在原始的搜索獵物模型中,可以看出,當(dāng)前搜索代理在找參照搜索代理,更新自己的位置時(shí),參照的搜索代理目標(biāo)比較單一,因此也就在全局范圍內(nèi)搜索獵物存在缺陷,容易造成向單一方向?qū)ふ?造成局部最優(yōu)的結(jié)果。所以,文中通過(guò)優(yōu)化原始搜索獵物的數(shù)學(xué)模型,引入隨機(jī)因子X(jué)rand來(lái)擴(kuò)大當(dāng)前鯨魚(yú)的搜索范圍,使當(dāng)前鯨魚(yú)在整個(gè)范圍內(nèi)尋優(yōu),得到的值也能達(dá)到最優(yōu),優(yōu)化后的數(shù)學(xué)模型為

X(t+1)=kXrand 1(t)+(1-k)Xrand 2(t)-AD3,

D3=|kCXrand 1(t)+(1-k)CXrand 2(t)-X(t)|,

(7)

式中:k----(0,1]之間的一個(gè)隨機(jī)數(shù);

D3----當(dāng)前搜索代理到隨機(jī)代理之間的距離。

3.2 開(kāi)發(fā)階段優(yōu)化策略

群智能優(yōu)化算法中的開(kāi)發(fā)階段是當(dāng)前收縮代理,開(kāi)始根據(jù)周圍的搜索代理逐漸向獵物(最優(yōu)解)的位置靠攏,直到在代數(shù)的迭代下達(dá)到最優(yōu)值的一個(gè)過(guò)程。這就是常在群智能算法中看到的開(kāi)發(fā)階段。

3.2.1 在包圍獵物階段引入隨機(jī)因子

在鯨魚(yú)群算法的開(kāi)發(fā)階段,也就是該算法的經(jīng)典捕獵行為:泡泡網(wǎng)攻擊機(jī)制是由兩個(gè)不同機(jī)制共同構(gòu)成鯨魚(yú)的捕獵行為,如環(huán)繞機(jī)制和螺旋上升機(jī)制;在實(shí)際捕獵中,鯨魚(yú)進(jìn)行環(huán)繞機(jī)制時(shí),并不是所有鯨魚(yú)單一地向立體空間中規(guī)定的某一處(獵物)靠近,而是會(huì)在這個(gè)捕獵空間中,隨機(jī)地對(duì)比是否還有較優(yōu)的值存在,如果存在,則會(huì)向最優(yōu)值靠攏,這也會(huì)跳出群智能算法中常有的造成局部最優(yōu)的弊病[13]。

在優(yōu)化的包圍獵物階段策略引入空間隨機(jī)因子,在迭代過(guò)程中,當(dāng)前搜索代理會(huì)比較空間內(nèi)是否還有其他搜索代理的位置是最優(yōu)的。數(shù)學(xué)模型為

(8)

式中:t----(0,1]之間的一個(gè)隨機(jī)數(shù);

Xrand----空間中的隨機(jī)因子。

3.2.2 在螺旋上升階段引入增強(qiáng)開(kāi)采能力因子Q

在鯨魚(yú)群智能算法的開(kāi)發(fā)階段,另一個(gè)機(jī)制就是螺旋上升機(jī)制。在原始的螺旋上升機(jī)制中,迭代過(guò)程時(shí),當(dāng)前搜索代理通過(guò)不斷地參照搜索空間中其他搜索代理的位置來(lái)更新自己的位置,最終達(dá)到最優(yōu)解的目的[14]。因此,文中優(yōu)化螺旋機(jī)制的策略中,引入的因子Q可以提高算法的收斂速度,能夠?qū)ふ业降慕飧颖平顑?yōu)解,并能夠很好地跳出局部最優(yōu),最終提高了算法的開(kāi)發(fā)階段。因子數(shù)學(xué)模型為

Q=2e-5k,

(9)

優(yōu)化后的螺旋機(jī)制數(shù)學(xué)模型為

(10)

式中:k----當(dāng)前迭代次數(shù)和總迭代次數(shù)的比;

b----一個(gè)常數(shù)1。

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

算法仿真測(cè)試均在Intel Core i5-6500 CPU、3.2 GHz主頻8 GB內(nèi)存,以及 Windows 764 為操作系統(tǒng)的計(jì)算機(jī)上實(shí)現(xiàn),編程軟件為Annocoda中的Spyder,引入6個(gè)典型基準(zhǔn)測(cè)試函數(shù)進(jìn)行測(cè)試,見(jiàn)表1。

表1 基準(zhǔn)函數(shù)

其中:F1～F5為連續(xù)單模函數(shù); F6為復(fù)雜非線性多模函數(shù)。

文中對(duì)算法的測(cè)試主要包括以下三個(gè)部分:

1)在相同的種群大小和迭代次數(shù)條件下,比較改進(jìn)算法和傳統(tǒng)的WOA算法、傳統(tǒng)的GWO算法在基準(zhǔn)測(cè)試函數(shù)上算法的收斂速度和尋優(yōu)精度,并證明改進(jìn)的WOA算法各項(xiàng)性能的提升;

2)對(duì)改進(jìn)的WOA算法在不同策略下進(jìn)行獨(dú)立測(cè)試,根據(jù)測(cè)試結(jié)果分析各種策略對(duì)WOA性能的影響;

3)與其他研究人員對(duì)鯨魚(yú)算法的改進(jìn)對(duì)比,證明其具有較強(qiáng)的競(jìng)爭(zhēng)力。

傳統(tǒng)WOA參數(shù)見(jiàn)表2。

4.1 改進(jìn)策略對(duì)算法性能影響

為了對(duì)比不同改進(jìn)策略對(duì)GLOBAL_WOA算法性能的影響,參數(shù)用上述實(shí)驗(yàn)的參數(shù),策略一是對(duì)WOA中勘探階段的數(shù)學(xué)模型進(jìn)行改進(jìn),并用WOA_1來(lái)標(biāo)記;策略二是通過(guò)對(duì)WOA算法開(kāi)發(fā)階段的搜索獵物數(shù)學(xué)模型進(jìn)行改進(jìn),并用WOA_2來(lái)標(biāo)記;策略三是對(duì)WOA中開(kāi)發(fā)階段的螺旋上升氣泡網(wǎng)攻擊獵物階段的數(shù)學(xué)模型進(jìn)行改進(jìn),并用WOA_3來(lái)標(biāo)記。

不同策略下的改進(jìn)算法對(duì)比見(jiàn)表3。

表3 不同策略下的改進(jìn)算法對(duì)比(最優(yōu)適應(yīng)度值)

實(shí)驗(yàn)結(jié)果表明,在策略一(WOA_1)和策略二(WOA_2)的改進(jìn)下,可以增強(qiáng)初始WOA的尋優(yōu)進(jìn)度這個(gè)性能指標(biāo),而策略三(WOA_3)的引入主要提供了算法的收斂速度。

算法收斂曲線對(duì)比如圖1所示。

(a) fitness1 (b) fitness2

4.2 與其他改進(jìn)WOA性能對(duì)比

將改進(jìn)的WOA和其他研究人員對(duì)傳統(tǒng)WOA的改進(jìn)算法作對(duì)比實(shí)驗(yàn),對(duì)比改進(jìn)算法性能優(yōu)劣。參數(shù)設(shè)置最大迭代次數(shù)為1 000,種群規(guī)模為20,維數(shù)為30,基準(zhǔn)測(cè)試函數(shù)用上述實(shí)驗(yàn)用的函數(shù),比較最優(yōu)解的均值和標(biāo)準(zhǔn)差,測(cè)試結(jié)果見(jiàn)表4。

表4 不同改進(jìn)算法的基準(zhǔn)函數(shù)的對(duì)比

實(shí)驗(yàn)結(jié)果表明,改進(jìn)的WOA算法相較于其他改進(jìn)算法在尋優(yōu)精度和收斂速度等方面有較強(qiáng)的競(jìng)爭(zhēng)力[15]。

5 結(jié) 語(yǔ)

WOA 作為一種新型啟發(fā)式優(yōu)化算法,它與其他元啟發(fā)式優(yōu)化算法類似,在求解復(fù)雜函數(shù)優(yōu)化問(wèn)題時(shí),存在收斂速度慢、易陷入局部最優(yōu)的問(wèn)題。考慮在算法迭代過(guò)程中,鯨魚(yú)捕食策略的選擇,以及位置更新對(duì)算法尋優(yōu)性能的影響,在勘探階段引入隨機(jī)因子來(lái)擴(kuò)大搜索范圍,從而得到較優(yōu)結(jié)果,在開(kāi)發(fā)階段的螺旋上升階段引入隨機(jī)因子來(lái)找到范圍內(nèi)的最優(yōu)值,在氣泡網(wǎng)攻擊階段引入收斂因子Q,三種改進(jìn)策略對(duì) WOA 進(jìn)行改進(jìn),提高其初始算法的收斂速度和尋優(yōu)精度。通過(guò)對(duì) 6 個(gè)基準(zhǔn)測(cè)試函數(shù)仿真結(jié)果表明,改進(jìn)算法的尋優(yōu)精度及收斂速度均有大幅提升,并且相較于其他改進(jìn)算法仍具有明顯優(yōu)勢(shì),證明了提出的改進(jìn)策略能夠使算法在求解復(fù)雜函數(shù)優(yōu)化問(wèn)題時(shí)具有更好的優(yōu)化性能。而如何將改進(jìn)算法應(yīng)用于約束優(yōu)化問(wèn)題以及復(fù)雜的實(shí)際工程問(wèn)題將是下一步主要研究的內(nèi)容。