基于改進動態因子的鯨魚優化算法

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

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

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

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

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

1 傳統的鯨魚優化算法

1.1 圍捕獵物

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

(1)

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

系數函數可分別表示為

(2)

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

在WOA中,鯨魚的捕獵行為由系數函數A引導,A取不同值鯨魚捕食方式不同。

1.2 氣泡網攻擊

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

圖1 氣泡網攻擊獵物Fig.1 Bubble net attacks prey

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

(3)

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

1.3 搜索獵物

在這一階段根據彼此位置進行隨機搜索,因此,使用|A|>1迫使搜索遠離目標鯨魚。相對于開發階段根據隨機選擇的搜索來更新搜索在探索階段的位置,而不是根據目前發現的最佳搜索執行。搜索獵物的位置更新公式為

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

(4)

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

2 動態因子鯨魚優化算法

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

2.1 種群初始化

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

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

(4)

2.2 動態收斂因子

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

(5)

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

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

2.3 動態慣性權重因子

慣性權重因子作為優化算法中的一個重要參數,在目標函數的優化中起著重要作用。當慣性權重因子較大時,該算法具有良好的全局搜索能力,可以搜索范圍較廣的區域;當慣性權重因子較小時,該算法具有較強的局部搜索能力,可以搜索最優解周圍的區域。然而,在傳統的優化算法中,慣性權重因子的值是恒定的,這在算法的早期和后期顯然不是一個更好的值。因此,適當變化的權重因子有助于改進算法的優化。

在算法優化過程中,如果線性慣性權重因子的調整策略不當,會影響算法的收斂速度。因此,提出動態慣性權重因子(ω)的表達式[式(6)],并根據迭代次數(t)改變動態慣性權重因子的值。

(6)

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

通過加入動態慣性權重因子,傳統鯨魚位置表達式,即式(1)、式(3)、式(4)分別變為

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

(7)

X(t+1)=D′eblcos(2πl)+ω(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選擇最佳適應值從而確定最佳鯨魚個體。

步驟3當t

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

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

步驟6更新X*將其轉換為更好的解決方案,算法結束。

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

圖3 算法執行流程圖Fig.3 Algorithm execution flow chart

3 最新研究成果對比

雖然現在已經有很多對鯨魚優化算法的改進,但大多都是聚焦算法搜索能力和給定應用場景。動態因子鯨魚優化算法與最新研究成果對比分析如下。

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

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

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

4 收斂性分析

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

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

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

(10)

式(10)中:f為函數。

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

(11)

定理1動態因子鯨魚優化算法的位置更新方程是一階線性時變差分方程。

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

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

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

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

(12)

令A(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],線性差分方程的穩定性等同于相應的齊次線性方程通解的穩定性。

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

(14)

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

定理2[15]當滿足t→tmax時,個體將收斂到局部或全局最優解。

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

=0

(15)

(16)

代入式(12)可得

=Xk

(17)

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

(18)

根據動態慣性權重因子性質可得

(19)

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

因此,式(16)可寫為

(20)

當滿足t→tmax時,所有個體都可以收斂到最優解并證明了定理2。

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

5 復雜度分析

復雜度分析包括時間復雜度和空間復雜度。動態因子鯨魚優化算法的計算和分析如下。

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

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

綜上所述,動態因子鯨優化算法具有高穩定性和良好的空間優化效率。

6 實驗與結果分析

6.1 算法比較

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

表1 收斂精度對比結果Table 1 Convergence precision comparison results

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

6.2 環境威脅下無人機協同路徑規劃

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

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

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

7 結論

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

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