改進鯨魚算法及其在路徑規劃的應用

楊 博, 李昌華,李智杰,張 頡

(西安建筑科技大學 信息與控制工程學院,西安 710055)

0 引言

近年來，元啟發式算法在解決工程、經濟、信息等多個領域的問題方面逐漸開始流行。群智能算法是元啟發式算法的主要門類之一，通過模擬生物的社會行為來搜索問題最優解，包括粒子群優化算法(PSO，particle swarm optimization)、布谷鳥搜索算法(CS，cuckoo search)、蜻蜓算法(DA，dragonfly algorithm)、灰狼優化算法(GWO，grey wolf optimizer)、蛾-火焰優化算法(MFO，moth-flame optimization algorithm)和鯨魚優化算法(WOA，whale optimization algorithm)。

鯨魚優化算法(WOA，whale optimization algorithm)是Mirjalili和Lewi[1]，參照鯨魚群體習性提出的一種新的群體智能優化搜索算法。通過測試函數集和實際應用驗證，表明WOA同其他智能優化算法有足夠的競爭力[1]，但WOA在迭代過程中仍存在收斂速度慢、收斂精度低和易陷入局部最優的問題。因此，采用了非線性收斂因子、協同a的慣性權重和時變獨立搜索概率以及免疫算法的免疫記憶機制對WOA進行改進，通過15個基準測試函數進行性能測試驗證其有效性，最終將其應用在機器人路徑規劃問題中。

1 相關工作

近年來，大量學者對WOA進行了研究，T.Xu[2]等引入慣性權重來調節最佳解對迭代的影響。龍文[3]等通過對立學習策略優化初始種群，并設計了隨迭代次數非線性變化的收斂因子，提出了改進的鯨魚優化算法(IWOA)。G.Kaur和S.Arora[4]提出了混沌鯨魚算法(CWOA)，將混沌理論引入了WOA優化過程，用混沌圖調整WOA的主要參數，提高了WOA的全局收斂速度并獲得了更好的性能。Y.Q.Zhou[5]等引入Lévy飛行軌跡來增加生物多樣性，提出了基于Lévy飛行軌跡的鯨魚優化算法(LWOA)。吳澤忠和宋菲[6]提出了基于改進螺旋更新位置模型的鯨魚優化算法(IMWOA)，提升了WOA的收斂精度和收斂速度。

此外，WOA已被廣泛應用于實際問題中。肖子雅和劉升[7]應用反向學習和黃金分割數優化WOA，提出EGolden-SWOA應用于壓力容器和蝶形彈簧設計優化問題。Elham和Farnaz[8]將WOA算法與鄰域搜索算法結合應用在城市固體廢物回收車輛路徑規劃。Hany和Hasanien[9]采用基于WOA的PI控制器分別對直流斬波器和電網側逆變器進行控制，以實現最大功率點跟蹤運行，改善了光伏系統的動態電壓響應。徐繼亞等[10]采用基于馮諾依曼拓撲結構鯨魚算法優化正交匹配追蹤算法和優化小波核極限學習機的參數，有效提高滾動軸承故障的診斷精度。謝建群[11]等提出了一種混合小波包變換和正余混沌雙弦鯨魚優化(CSCWOA)算法優化多層感知器神經網絡(MLP)的短期云計算資源負載預測方法，提高了負載序列高頻分量的預測精度和泛化能力。

2 鯨魚優化算法(WOA)

鯨魚優化算法(WOA)是Mirjalili和Lewi[1]，參照鯨魚群體的覓食習性(圖1)，提出的群體智能優化搜索算法。

圖1 鯨魚覓食行為

(1)

2.1 收縮包圍

WOA的第一種搜索方式模擬鯨魚的收縮包圍機制，即種群向最優位置的包圍，見圖2，根據式(2)更新種群位置：

X(t+1)=X*(t)+A|C*X*(t)-X(t)|

(2)

其中：t為當前迭代次數，X*(t)為目標位置，迭代過程中X*(t)為當前最優個體，A*|C*X*(t)-X(t)|為收斂幅度，A和C定義如式(3)、(4)所示：

A=2a*r-a

(3)

C=2r

(4)

r為[0,1]上的隨機向量，通過r種群個體更新在圖2所示的當前最優點周邊空間中的任何位置，來模擬對獵物的包圍。a為收斂因子，與t的關系見式(5)：

(5)

其中：tmax為最大迭代次數。

圖2 包圍機制

2.2 螺旋捕食

WOA的第二種搜索方式模擬鯨魚螺旋覓食機制，螺旋行進更新位置，其數學模型如式(6)：

X(t+1)=X*(t)+D*ebr*cos(2πr)

(6)

其中：D=|X*(t)-X(t)|表示第i只鯨魚和目標之間的距離，b為用于限定對數螺旋形狀的常數,r為[-1，1]上的隨機數。

鯨魚捕獵時對獵物的包圍和螺旋上升的過程是同時的，因此假設兩種機制都有50%的可能性發生。因此給定ρ∈[0,1]，鯨魚的位置更新表達式為式(7)：

(7)

2.3 獨立搜索

除上述兩種搜索方式外，WOA中還存在著鯨魚個體根據自身位置隨機搜索獵物的行為，這種方式提高了算法的全局搜索能力，其數學模型表述為式(8)：

X(t+1)=Xrandom(t)-A*|C*Xrandom(t)-X(t)|

(8)

其中：Xrandom(t)為群體中隨機選取的鯨魚個體位置。

綜上所述，WOA算法流程如圖3所示。

圖3 WOA算法流程

3 改進的鯨魚優化算法

3.1 非線性收斂因子

WOA主要通過A的值確定算法進行全局搜索或是局部搜索，A的大小由收斂因子a決定，較大的a值算法全局搜索能力越強，越小的a值則局部搜索能力越強。在WOA算法中，收斂因子a的取值由2線性遞減至0，算法在迭代中后期易陷入局部最優的狀況。為此，設計了一種非線性收斂因子，函數模型如圖4所示，在初期保持在相對較高的數值一段時間，后迅速減少至低水平，并在迭代后期維持低數值，表達式如式(9)所示:

(9)

其中：ζ為調控因子，影響收斂因子a的變化速率，經實驗ζ取值定為20。

圖4 收斂因子

該非線性收斂因子在迭代初期保持在較高數值，提升算法的全局搜索能力和收斂速度；在迭代中期迅速由較高數值衰減至較低數值，實現由全局搜索向局部搜索的快速過度；在迭代后期保持維持較低數值，保障算法的局部搜索性能。

3.2 協同a的慣性權重

慣性權重w是粒子群算法(PSO)的重要參數，對算法收斂性起很大作用，在PSO中w值越大，全局搜索能力越強；反之，w值越小，則局部搜索能力越強，全局搜索能力越弱[12]。引入PSO算法的慣性權重w作為引導者權重，來提高收斂精度，同時更好地調節算法的全局搜索能力和局部搜索能力。協同a的慣性權重w值隨迭代次數的增加而減小，并受收斂因子a控制，使w值與a值正相關，定義見公式(10)：

(10)

其中：amax為收斂因子a的最大值，amin為收斂因子a的最小值；wmax為慣性權重的最大值，wmin為慣性權重的最小值；tmax為最大迭代次數。

引入慣性權重w對算法改進后,WOA的3種搜索方式分別由公式(7)、(8)變更為公式(11)、(12)：

(11)

X(t+1)=wXrandom(t)-A*|C*Xrandom(t)-X(t)|

(12)

總體上，w隨迭代次數的增加而減小，同時受a的控制w也具備非線性變化，具有更強的適應性。經過a的系數放大，使算法在迭代初期具備更強的全局搜索能力，提高收斂速度；迭代中期隨著a的急速下降，w同時大幅減小，使算法在迭代中后期局部搜索能力大幅提升，提高收斂精度。

3.3 免疫記憶

Jangir[13]等的研究指出，在元啟發式算法中，隨機選擇在勘探和開發過程中都具有非常重要的作用。但參數的隨機性無法保證每一次迭代效果都是有效的，隨機的搜索方式和移動步長很可能出現效果的衰退而停滯不前。因此，需要對隨機的搜索方式進行一定的干預。

免疫記憶是免疫算法(IS)[14]的重要控制策略，可以加速優化搜索過程，提高優化效率和效果。IS通過保存最優個體記憶信息，用于加速局部搜索或者抑制早熟收斂，從而使算法快速收斂到全局最優解。WOA中每一代都在隨機的迭代搜索，沒有記憶單元。因此將IS的免疫記憶機制引入WOA，為WOA添加記憶庫M，記憶各個體的適應度以及執行動作的各參數(w、A、C和r)。在下一次優化搜索中，比較當次迭代更新后的適應度和根據記憶庫中的參數更新的適應度，若據記憶庫中的參數更新效果好，則使用記憶庫中的參數進行位置更新，否則更新M。添加記憶單元后，改進WOA每次迭代都在與記憶單元操作比較的基礎上運行，確保了算法快速收斂至全局最優解。

3.4 時變獨立搜索概率

WOA具有獨立搜索的機制，由|A|≥1控制，通過公式(3)以及公式(5)、(9)可知，無論是原始的a還是改進后的a，在迭代中后期都無法觸發獨立搜索機制，導致鯨魚算法更難跳出局部最優的情況。因此保持獨立搜索機制在迭代后期仍有一定的發生概率，可以在一定程度上提高鯨魚算法跳出局部最優的能力。定義一種時變獨立搜索機制發生概率為η，表達式見式(13):

(13)

時變獨立搜索概率η使得算法迭代中后期，仍具有一定的全局搜索能力，有效提高了算法后期跳出局部最優的能力，尤其是在密集多峰函數問題中具有較好的效果。

通過以上方式對鯨魚算法進行改進后，基于免疫記憶、協同a的慣性權重和時變獨立搜索概率的改進鯨魚優化算法(IWTWOA,Immune memory-α Weight-Time varying search factor Improved Whale Optimization Algorithm)的具體流程，見算法1。

算法1:IWTWOA

t=1，fbest=fop；

WHILE(t

FORi=1 TOn

FORj=1 TOd

更新a,A,C,r,ρ；

IF (ρ<0.5)

IF (η<1) THEN

包圍機制更新位置；

ELSE IF(η≥1) THEN

隨機個體機制更新位置；

END IF

ELSE IF(ρ≥0.5) THEN

螺旋機制更新位置；

END IF

END FOR

計算新的目標值fnew；

與記憶庫M中參數操作對比；

IFfnew

fnew=fM；

END IF

IFfnew

fbest=fnew；

更新引導者位置Xbest；

END IF

END FOR

更新記憶庫M；

t=t+1；

END WHILE

4 測試與對比

4.1 測試函數

為了驗證IWTWOA算法的性能，選取了15個基準函數進行對比實驗，基準函數詳見表1。這些函數分為具有少量局部最小值的單峰函數和具有大量局部最小值的多峰函數以及固定維函數。函數F1-F4、F14、F15是單峰函數，函數F5-F10是多峰函數，函數F11-F13是固定維函數。

表1 測試函數

4.2 實驗結果與分析

將IWTWOA算法與WOA算法和文獻[3]中所提到的IWOA算法進行對比試驗，各進行30次實驗，分別記錄每種算法實驗結果的最小值、平均值、最大值和標準差，實驗結果見表2。

表2 實驗結果

由表2的實驗數據可知，IWTWOA算法在對測試函數F2、F4、F6、F7、F10、F14、F15的測試中都收斂到了最小值0，標準誤差為0，其中F2、F4、F14、F15為單峰函數，F6、F7、F10為多峰函數，證明了算法的適應性和穩定性。對測試函數F6、F7、F10的測試中，WOA、IWOA、IWTWOA算法均得到了最優解，但在收斂速度上IWTWOA明顯領先，收斂代數詳見表3。

表3 平均迭代次數

F1-F4和F14、F15的結果表明，在單峰函數問題中，IWOA、IWTWOA算法相較于WOA算法優化效果和收斂精度均有明顯提升，相對IWOA而言IWTWOA算法改進效果更為顯著。F5-F10的多峰函數測試說明，鯨魚算法在多峰函數問題的求解上優勢巨大，除在F8函數的測試中IWTWOA算法的計算結果誤差相對較大以外，對其余函數的計算結果或達到最優，誤差為0或誤差十分接近0，對F9函數的測試中3種算法效果相同。F11-F13的固定維函數測試中，IWOA、IWTWOA算法較WOA算法在計算精度上均有所提升，F13函數測試中WOA算法所得的最優值更接近目標值，IWTWOA算法具有更好平均效果和穩定性，F11函數測試中3種算法都得到過最優解，但IWTWOA算法穩定性更高。

總體而言，IWTWOA算法對WOA算法在計算精度和收斂速度上均有所提高，尤其是在F1、F5的計算中，IWTWOA算法相較于改進的IWOA算法也有較大幅的性能提升。為更直觀展示優化效果，選擇測試函數中較典型的幾個進行繪圖展示，如圖5所示。

圖5 部分測試效果對比

5 IWTWOA在路徑規劃的應用

路徑規劃是機器人領域的熱門研究問題，在機器人、飛行器、導航、物流及通信等諸多高新科技領域都有廣泛應用。路徑規劃就是在具有障礙物的環境內按照一定的評價標準，尋找一條從起始位置到達目標位置的無碰路徑[15]。

近年來隨著群智能算法的發展，基于群智能優化的路徑規劃研究層出不窮。秦元慶[16]等采用鏈接圖進行環境建模，使用粒子群算法對Dijkstra算法求得的最短路徑進行優化,得到全局最優路徑。李珣[17]等結合三次樣條插值方法、選取罰函數作為適應度函數等對PSO進行了算法改進,提高了室內環境中路徑規劃的實時性和有效性。朱慶保[18]采用了概率搜索策略、最近鄰策略和目標引導函數改進蟻群算法，搜索過程極為迅速高效。吳坤[19]等將WOA算法引入無人機航路規劃研究，獲得了代價最優的、有效的航路結果。

5.1 環境建模

柵格法是路徑規劃環境建模公認最成熟的技術[20]。柵格法將規劃空間劃分為數個格網狀區塊，將空間環境轉化為一個由“0”，“1”信息表示的矩陣grid，grid中“0”表示可自由通行空間單元，“1”表示被障礙物占據的單元。柵格精度取g=10 cm，柵格法環境建模效果如圖6所示。

圖6 柵格法環境建模

5.2 代價函數

根據路徑規劃問題的描述，應滿足：1)路徑最短、2)和障礙物無碰撞，可以通過定義路徑的代價函數獲取最優路徑。代價函數定義為：

(14)

其中：i為迭代次數；L(i)為每次迭代移動的直線距離，定義為：

L(i)=

(15)

xi，yi表示當前所在位置，xi-1，yi-1表示迭代前所在位置，g是柵格精度。

C(i)為障礙物碰撞代價，定義為：

C(i)=k∑grid(pi)

(16)

其中:pi為當次迭代途徑的點，grid(pi)為柵格環境下障礙物信息，k為一個較大的常數以保障路徑與障礙物無碰撞。

那么，路徑規劃問題就轉換成求解代價函數最小值問題，即：

minf

(17)

5.3 IWTWOA路徑規劃流程

綜上所述，IWTWOA對路徑規劃問題的具體求解過程如下：

Step1：環境建模，確定起點與終點；

Step2：初始化IWTWOA參數；

Step3：根據式(14)計算代價函數，將路徑規劃轉化為優化問題 ；

Step4：根據IWTWOA的式(11)、(12)進行位置更新，對路徑規劃問題進行優化求解；

Step5：與記憶庫M中的參數操作對比，判斷是否跟新記憶庫，迭代次數加1；

Step6：判斷是否滿足終止條件，滿足則輸出最優路徑，否則跳轉Step4。

5.4 實驗測試

基于上節算法流程描述，將IWTWOA算法與WOA算法和PSO算法進行仿真實驗。在上述20×20的柵格環境下進行仿真，起點S=(1，1)，終點D=(20，20)，黑色區域為障礙物。3種算法的初始種群數均為N=30，最大迭代次數均為500次，搜索范圍[-20,20]。PSO算法慣性權重ω=0.78，c1=1.5，c2=1.5。

路徑規劃結果如圖7所示，表4給出了3種算法的代價函數最大值、最小值和平均值。由表4可知，改進的IWTWOA算法較WOA算法在應對路徑規劃問題的整體性能上有較大的的提升，雖然PSO算法取得了最好的優化值結果，但IWTWOA算法在最大值和平均值方面都取得更好的結果，說明IWTWOA算法能夠找到相對較短的路徑，且具有較好的穩定性。

圖7 路徑規劃結果

表4 代價函數比較

經仿真實驗測試，提出的IWTWOA算法能夠規劃出一條有效的、較短的路徑，在穩定性和收斂精度上均有所提高。

6 結束語

本文采用非線性收斂因子、協同a的慣性權重和時變獨立搜索概率改進鯨魚算法迭代模型，并引入免疫算法的免疫記憶機制對WOA進行改進；經15個基準測試函數的測試驗證，IWTWOA算法較WOA算法在算法穩定性、計算精度和收斂速度上均有所提高；最后將IWTWOA算法應用在機器人路徑規劃問題中，經仿真實驗證明了IWTWOA算法的有效性和穩定性。另外，鯨魚優化算法還有諸多改進策略，下一步將進行深入的研究和比對；路徑規劃的實驗環境相對簡單，將對復雜環境下的路徑規劃進行深入的研究。