周欣榮, 王芳, 陰良魁, 單銳*

(1.燕山大學(xué)理學(xué)院, 秦皇島 066004; 2.中國科學(xué)院行政管理局, 北京 100086)

受座頭鯨狩獵行為的啟發(fā),Mirjalili等[1]提出了一種新的基于自然啟發(fā)的啟發(fā)式算法(whale optimization algorithm,WOA)。該算法模擬了座頭鯨對獵物的包圍、泡泡網(wǎng)攻擊模式和搜索獵物的使用。鯨魚優(yōu)化算法具有結(jié)構(gòu)簡單、調(diào)節(jié)參數(shù)少、操作簡單、全局尋優(yōu)能力強等特點。鯨魚優(yōu)化算法已經(jīng)在許多領(lǐng)域得到了應(yīng)用,并且在解決連續(xù)優(yōu)化和工程優(yōu)化問題方面具有良好的性能[2-4]。

中外研究者針對算法自身魯棒性和應(yīng)用性也提出了多種改進(jìn)策略。由于動態(tài)變形的參數(shù)受環(huán)境影響,Wang等[5]設(shè)計了一種基于邏輯映射的改進(jìn)鯨魚優(yōu)化算法(improved whale optimization algorithm,IWOA)來進(jìn)行參數(shù)識別。文獻(xiàn)[6]結(jié)合最優(yōu)最差反向?qū)W習(xí)思想提出了一種小孔成像反向?qū)W習(xí)策略,增加了尋優(yōu)位置的多樣性。文獻(xiàn)[7]采取卡方分布的逆累積分布函數(shù)更新收斂因子以實現(xiàn)全局搜索和局部開發(fā)的平衡。Jaafari等[8]提出了一種混合算法,將自組織深度學(xué)習(xí)組數(shù)據(jù)處理方法、布谷搜索算法和鯨魚優(yōu)化算法相結(jié)合,以增強算法模型在實際應(yīng)用中的魯棒性。為了優(yōu)化預(yù)測天氣變化,文獻(xiàn)[9]將鯨魚優(yōu)化算法與機器學(xué)習(xí)算法相結(jié)合。Zhang等[10]提出了一種改進(jìn)傳統(tǒng)鯨魚優(yōu)化算法算法的混合策略,提高了鯨魚優(yōu)化算法優(yōu)化能力,并將其應(yīng)用于洪災(zāi)預(yù)測。Chen等[11]提出了增強變異鯨魚優(yōu)化算法(reinforced whale optimization algorithm, RDWOA),該算法采用隨機備用或隨機替換策略來提高算法的收斂速度,并采用雙自適應(yīng)加權(quán)策略來改善早期探索搜索趨勢和后期行為利用率。改進(jìn)的鯨魚優(yōu)化算法不僅提高了算法的收斂性,還用于解決全球多維工程優(yōu)化、無線傳感器中的點覆蓋問題和物品運輸路徑優(yōu)化等問題[12-14]。

針對鯨魚優(yōu)化算法收斂速度慢、易陷入局部最優(yōu)的問題,擬采用動態(tài)因子策略對算法進(jìn)行改進(jìn)。首先,針對傳統(tǒng)隨機初始化種群容易產(chǎn)生質(zhì)量差種群的問題,約束上下界對種群進(jìn)行初始化,使搜索范圍在搜索空間中合理分布。其次,為了在每次迭代中保持種群的多樣性,設(shè)計了動態(tài)收斂因子,以提高后期局部搜索能力。此外,在更新搜索位置公式中引入動態(tài)權(quán)重因子,以確保在早期階段具有更好的全局搜索能力,并減少陷入局部優(yōu)化的可能性。改進(jìn)的鯨魚優(yōu)化算法不僅避免早熟收斂,避免陷入局部最優(yōu),實現(xiàn)了全局最優(yōu)解,而且提高了收斂速度和計算精度。最后,將改進(jìn)鯨魚優(yōu)化算法與其他智能優(yōu)化算法進(jìn)行仿真對比,驗證了動態(tài)因子鯨魚優(yōu)化算法的優(yōu)越性。為該算法在快遞配送、農(nóng)業(yè)等實際場景中的應(yīng)用打下了良好基礎(chǔ)。

1 傳統(tǒng)的鯨魚優(yōu)化算法

1.1 圍捕獵物

在捕食過程中,座頭鯨首先確定獵物的位置,然后包圍并捕獲獵物。鯨魚優(yōu)化算法將目標(biāo)獵物或近似最優(yōu)解作為當(dāng)前最佳候選解。在確定領(lǐng)航鯨的位置后,其他鯨魚將游到目標(biāo)位置以更新其位置。以式(1)表示此行為。

(1)

式(1)中:D為待求解個體與領(lǐng)航鯨之間的距離;t為當(dāng)前迭代次數(shù);A和C為系數(shù)函數(shù);X*(t)為第t代領(lǐng)航鯨的位置函數(shù);X(t)為第一代領(lǐng)航鯨魚個體的位置函數(shù);|·|表示絕對值運算。

系數(shù)函數(shù)可分別表示為

(2)

式(2)中:a為收斂因子,在勘探和開發(fā)階段,a從2線性下降至0;r為取值在[0,1]之間的隨機數(shù)。

在WOA中,鯨魚的捕獵行為由系數(shù)函數(shù)A引導(dǎo),A取不同值鯨魚捕食方式不同。

1.2 氣泡網(wǎng)攻擊

根據(jù)概率選擇收縮環(huán)繞機制或螺旋模型選擇更新位置。圖1展示了座頭鯨使用氣泡網(wǎng)策略攻擊獵物。為了模擬這種同時發(fā)生的行為,假設(shè)有概率p=0.5的可以在縮小到包圍機制和螺旋模型中進(jìn)行選擇,以更新鯨魚的位置,當(dāng)p≥0.5時,鯨魚位置更新公式為

圖1 氣泡網(wǎng)攻擊獵物Fig.1 Bubble net attacks prey

X(t+1)=D′eblcos(2πl(wèi))+X*(t)

(3)

式(3)中:D′=|X*(t)-X(t)|,D′為目前得到的最優(yōu)解;b為對數(shù)螺旋常數(shù);l為[-1,1]中的隨機數(shù)。

1.3 搜索獵物

在這一階段根據(jù)彼此位置進(jìn)行隨機搜索,因此,使用|A|>1迫使搜索遠(yuǎn)離目標(biāo)鯨魚。相對于開發(fā)階段根據(jù)隨機選擇的搜索來更新搜索在探索階段的位置,而不是根據(jù)目前發(fā)現(xiàn)的最佳搜索執(zhí)行。搜索獵物的位置更新公式為

X(t+1)=Xrand(t)-A|CXrand(t)-X(t)|

(4)

式(4)中:Xrand(t)為第t代領(lǐng)航鯨隨機搜索位置。

2 動態(tài)因子鯨魚優(yōu)化算法

鯨魚優(yōu)化算法采用隨機或最佳搜索代理來模擬狩獵行為,并使用螺旋模擬座頭鯨的氣泡網(wǎng)攻擊機制。相比于其他優(yōu)化算法具有原理簡明,需要調(diào)整的參數(shù)少,易實現(xiàn)等優(yōu)點。但是算法容易陷入局部極值和收斂速度問題也阻礙著鯨魚優(yōu)化算法發(fā)展。針對上述問題,提出動態(tài)因子鯨魚優(yōu)化算法(dynamic factor whale optimization algorithm, DFWOA)。

2.1 種群初始化

初始種群的多樣性會極大地影響種群智能算法的收斂速度和精度,但基本的鯨魚優(yōu)化算法不能通過隨機初始化種群來保證種群的多樣。在該步驟中設(shè)置種群(N)的大小、最大迭代次數(shù)(tmax)、獵物i所在區(qū)域(Ti)、獵物i所在區(qū)域半徑(Ri)、獵物所在范圍距離上/下界的距離(Δd)。限制種群初始化范圍,使搜索過程更高效。如圖2所示,設(shè)置兩條虛線以限制下限(Pmin)和上限(Pmax)。這些邊界由開始邊界和目標(biāo)最大的威脅確定。因此,初始種群的位置限制在[Pmin,Pmax]中。并且計算初始群體中每個個體的適應(yīng)度,并且[Pmin,Pmax]計算公式為

Rj為獵物j所在區(qū)域半徑圖2 種群初始化范圍上下界Fig.2 Upper and low bounds of the population initialization range

(4)

2.2 動態(tài)收斂因子

在鯨魚優(yōu)化算法中A用于調(diào)整算法的局部和全局搜索能力。當(dāng) |A|≥1時,該算法將擴大搜索范圍以找到更好的候選解,而當(dāng)|A|<1時,算法將縮小搜索范圍,并在區(qū)域內(nèi)進(jìn)行精細(xì)搜索。根據(jù)式(2)可知,A的值受收斂因子a的影響。當(dāng)a較大時算法具有更好的跳出局部優(yōu)化的能力。相反,較小的算法具有較強的局部搜索能力和較快的收斂速度。因此,自適應(yīng)調(diào)整a有助于平衡算法的全局和局部搜索能力。調(diào)整后的a的表達(dá)式為

(5)

式(5)中:as、af分別為收斂因子的初始值和停止值;t為當(dāng)前迭代次數(shù);tmax為最大迭代次數(shù);η和λ為非線性調(diào)整系數(shù)。

傳統(tǒng)鯨魚優(yōu)化算法中a的線性遞減策略不能完全反應(yīng)實際的優(yōu)化過程,調(diào)整后的動態(tài)收斂因子是非線性變化的,能更好的適應(yīng)非線性變化的搜索過程,有效地保證全局搜索和局部搜索能力的平衡。

2.3 動態(tài)慣性權(quán)重因子

慣性權(quán)重因子作為優(yōu)化算法中的一個重要參數(shù),在目標(biāo)函數(shù)的優(yōu)化中起著重要作用。當(dāng)慣性權(quán)重因子較大時,該算法具有良好的全局搜索能力,可以搜索范圍較廣的區(qū)域;當(dāng)慣性權(quán)重因子較小時,該算法具有較強的局部搜索能力,可以搜索最優(yōu)解周圍的區(qū)域。然而,在傳統(tǒng)的優(yōu)化算法中,慣性權(quán)重因子的值是恒定的,這在算法的早期和后期顯然不是一個更好的值。因此,適當(dāng)變化的權(quán)重因子有助于改進(jìn)算法的優(yōu)化。

在算法優(yōu)化過程中,如果線性慣性權(quán)重因子的調(diào)整策略不當(dāng),會影響算法的收斂速度。因此,提出動態(tài)慣性權(quán)重因子(ω)的表達(dá)式[式(6)],并根據(jù)迭代次數(shù)(t)改變動態(tài)慣性權(quán)重因子的值。

(6)

式(6)中:m為可選參數(shù)。

通過加入動態(tài)慣性權(quán)重因子,傳統(tǒng)鯨魚位置表達(dá)式,即式(1)、式(3)、式(4)分別變?yōu)?/p>

X(t+1)=ω(t)X*(t)-AD

(7)

X(t+1)=D′eblcos(2πl(wèi))+ω(t)X(t)

(8)

X(t+1)=ω(t)Xrand(t)-

A|CXrand(t)-X(t)|

(9)

2.4 DFWOA算法步驟

步驟1初始化一個特征個體Xi(i=1,2,…,k)。

步驟2選擇最佳適應(yīng)值從而確定最佳鯨魚個體。

步驟3當(dāng)t

步驟4如果p≥0.5,基于對數(shù)螺旋位置更新策略,使用式(8)更新當(dāng)前鯨魚的位置信息。

步驟5檢查是否有鯨魚超出搜索空間并對其進(jìn)行修改。

步驟6更新X*將其轉(zhuǎn)換為更好的解決方案,算法結(jié)束。

動態(tài)因子鯨魚優(yōu)化算法(dynamic factor whale optimization algorithm, DFWOA) 的算法流程圖如圖3所示。

圖3 算法執(zhí)行流程圖Fig.3 Algorithm execution flow chart

3 最新研究成果對比

雖然現(xiàn)在已經(jīng)有很多對鯨魚優(yōu)化算法的改進(jìn),但大多都是聚焦算法搜索能力和給定應(yīng)用場景。動態(tài)因子鯨魚優(yōu)化算法與最新研究成果對比分析如下。

(1)參考文獻(xiàn)[6-7]專注于對算法本身的改進(jìn),在算法中都更新了收斂因子,協(xié)調(diào)了算法的全局搜索和局部開發(fā)能力,但種群數(shù)量有限,算法實際應(yīng)用范圍有限。

(2)參考文獻(xiàn)[5,8-9]在船舶、滑坡預(yù)測和天氣預(yù)測的特定應(yīng)用場景下,對鯨魚優(yōu)化算法做了針對性的改進(jìn),分別引入邏輯映射進(jìn)行船舶變形測量,把其他優(yōu)化算法和鯨魚優(yōu)化算法相結(jié)合,算法之間優(yōu)勢互補,提高測量精度。在此基礎(chǔ)上改進(jìn)的鯨魚優(yōu)化算法針對性強,適用于指定任務(wù),缺乏算法應(yīng)用的普適性。

(3)相比于現(xiàn)在對鯨魚優(yōu)化算法的最新研究成果,在種群多樣性、算法性能和算法普適性等方面對鯨魚優(yōu)化算法做了全面的升級,在收斂速度得到滿足的基礎(chǔ)上,算法收斂精度也滿足要求,對于實際問題的應(yīng)用也得到了進(jìn)一步驗證。在提高算法性能的基礎(chǔ)上增強了算法的實用性。

4 收斂性分析

定義1[15]線性微分方程。

定義A(·):J+→Rn是一個平方非奇異矩陣,J+是一個非負(fù)整數(shù)的集合,f*(·):J+→Rn,X(t)∈Rn,對于每個t∈J+,線性差分方程和相應(yīng)的變系數(shù)齊次線性方程可表示為

X(t+1)=A(t)X(t)+f(t)

(10)

式(10)中:f為函數(shù)。

X(t+1)=A(t)X(t)

(11)

定理1動態(tài)因子鯨魚優(yōu)化算法的位置更新方程是一階線性時變差分方程。

證明根據(jù)式(1)、式(2)和式(5)～式(7),動態(tài)因子鯨魚優(yōu)化算法算法的整體位置更新方程為

X(t+1)=ω(t)X*(t)-AD

=ω(t)X*(t)-ACX*(t)+AX(t)

=AX(t)+ω(t)X*(t)-ACX*(t)

(12)

令A(yù)(t)=A,f(t)=ω(t)X*(t)-ACX*(t),因此式(7)可寫為

X(t+1)=A(t)X(t)+f(t)

(13)

引理1[15]對?f(t)∈[J+,Rn],線性差分方程的穩(wěn)定性等同于相應(yīng)的齊次線性方程通解的穩(wěn)定性。

引理2[15]對?t0∈R,若矩陣范數(shù)‖A(t)‖X滿足

(14)

那么可以保證X(t+1)=A(t)X(t)+f(t)一致漸近穩(wěn)定。

定理2[15]當(dāng)滿足t→tmax時,個體將收斂到局部或全局最優(yōu)解。

證明根據(jù)式(2)、式(5)～式(7)可得

=0

(15)

(16)

代入式(12)可得

=Xk

(17)

代入式(15),式(17)可變形為

(18)

根據(jù)動態(tài)慣性權(quán)重因子性質(zhì)可得

(19)

式(19)中:m為實數(shù)范圍內(nèi)可選參數(shù),一般取值是4或5。

因此,式(16)可寫為

(20)

當(dāng)滿足t→tmax時,所有個體都可以收斂到最優(yōu)解并證明了定理2。

綜上所述,當(dāng)滿足一定條件時,可以保證DFWOA算法的收斂性。

5 復(fù)雜度分析

復(fù)雜度分析包括時間復(fù)雜度和空間復(fù)雜度。動態(tài)因子鯨魚優(yōu)化算法的計算和分析如下。

(1)時間復(fù)雜度。動態(tài)因子鯨魚優(yōu)化算法包括5個步驟:初始化,包括獵物、氣泡網(wǎng)攻擊獵物、更新位置信息和停止評估。在動態(tài)因子鯨魚優(yōu)化算法中,N為鯨魚的數(shù)量,tmax為最大迭代次數(shù),Dw為鯨魚捕捉獵物的維度。初始化的時間復(fù)雜度為O(N*Dw)。在包含獵物、用氣泡網(wǎng)攻擊獵物和更新位置信息的過程中,每個步驟的時間復(fù)雜度為O(N*Dw*tmax)。停止評估的時間復(fù)雜度為O(1)。因此,動態(tài)因子鯨魚優(yōu)化算法的總體時間復(fù)雜度為O(N*Dw*tmax)。

(2)空間復(fù)雜性。在動態(tài)因子鯨魚優(yōu)化算法中,N為鯨魚的數(shù)量,Dw為鯨魚捕捉獵物的維度。動態(tài)因子優(yōu)化算法隨機選擇勘探或開發(fā)以評估空間復(fù)雜性。整個空間的復(fù)雜度為O(N*Dw)。

綜上所述,動態(tài)因子鯨優(yōu)化算法具有高穩(wěn)定性和良好的空間優(yōu)化效率。

6 實驗與結(jié)果分析

6.1 算法比較

為了研究該算法的性能,將粒子群優(yōu)化算法(particle swarm optimization,PSO)、改進(jìn)粒子群優(yōu)化算法[16](modified particle swarm optimization,MPSO)、鴿群優(yōu)化算法[17](pigeon inspired optimization,PIO)、鯨魚優(yōu)化算法[1](whale optimization algorithm,WOA)與動態(tài)因子鯨魚優(yōu)化算法(dynamic factor whale optimization algorithm, DFWOA)進(jìn)行了比較。每種算法在運行過程中執(zhí)行30次,其他參數(shù)如下:af=0,as=2,η=2,λ=1,m=2,ω=0.5。結(jié)果如表1所示,PSO、MPSO、PIO和WOA的最優(yōu)搜索得分分別為3.364、3.289、3.356和3.068。動態(tài)因子鯨魚優(yōu)化算法具有所有比較算法中最好的穩(wěn)定性。圖4給出了實驗中5種算法的收斂曲線,可以看出,動態(tài)因子鯨魚優(yōu)化算法(dynamic factor whale optimization algorithm, DFWOA)收斂速度比其他4種算法快,收斂精度比其他對比算法精度高。

表1 收斂精度對比結(jié)果Table 1 Convergence precision comparison results

圖4 收斂速度對比結(jié)果Fig.4 Convergence speed comparison results

6.2 環(huán)境威脅下無人機協(xié)同路徑規(guī)劃

無人機任務(wù)分配是航空優(yōu)化的研究熱點之一,也逐漸成為檢測各種優(yōu)化算法性能的典型問題。為了更好體現(xiàn)所提出動態(tài)因子鯨魚優(yōu)化算法中的應(yīng)用問題,驗證動態(tài)因子鯨魚優(yōu)化算法(dynamic factor whale optimization algorithm, DFWOA)算法的實踐性,整個搜索空間被設(shè)置為1 000 m×800 m×400 m,在這個空間中有4個環(huán)境威脅源:2個環(huán)境威脅,2個外部干擾威脅。使用了兩架相同的無人機,這2架無人機的起始坐標(biāo)是[240 m,600 m,150 m],[500 m,500 m,150 m]。目標(biāo)點的坐標(biāo)是[700 m,800 m,280 m],[950 m,700 m,280 m]。無人機的速度范圍為[100 m/s,200 m/s]。搜索節(jié)點為5 000,迭代次數(shù)為200,其他參數(shù)設(shè)置與仿真1相同。實驗結(jié)果如圖5、圖6所示,其中,圖5顯示了路徑規(guī)劃結(jié)果的三維視圖,圖6顯示了二維視圖?？梢钥闯?該算法能夠有效地為無人機生成一條滿足空間約束的可行路徑。

圖5 無人機路徑規(guī)劃的三維視圖Fig.5 3D View of UAV path planning

圖6 無人機路徑規(guī)劃的二維視圖Fig.6 2D View of UAV path planning

7 結(jié)論

(1)提出了一種動態(tài)因子鯨魚優(yōu)化算法,在該算法中,使用動態(tài)收斂因子來平衡收斂速度和搜索能力,并使用動態(tài)慣性權(quán)重因子來提高算法的穩(wěn)定性。原始的鯨魚優(yōu)化算法通常具有局部最優(yōu)停滯,但動態(tài)因子的引入可以通過改變鯨魚在搜索空間中的位置來幫助動態(tài)因子鯨魚優(yōu)化算法避免這一缺陷。這些改進(jìn)策略使得動態(tài)因子鯨魚優(yōu)化算法在算法收斂性、計算精度和計算復(fù)雜度等方面的性能更好。為了驗證算法可行性,對不同優(yōu)化算法在相同的目標(biāo)函數(shù)下進(jìn)行了仿真對比。實驗結(jié)果表明,DFWOA是一種有效可行的方法具有更好的收斂性。

(2)今后的工作面臨許多挑戰(zhàn),如可以將DFWOA引入其他多無人機領(lǐng)域應(yīng)用,解決多無人機在不同環(huán)境下任務(wù)分配問題。此外,將DFWOA加入更多應(yīng)用于無人機領(lǐng)域的其他優(yōu)化問題,如不同目標(biāo)函數(shù)、約束環(huán)境場景下任務(wù)分配和編隊控制,也具有重要意義。