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

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

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

0 引言

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

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

1 相關工作

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

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

2 鯨魚優(yōu)化算法(WOA)

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

圖1 鯨魚覓食行為

(1)

2.1 收縮包圍

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

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

(2)

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

A=2a*r-a

(3)

C=2r

(4)

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

(5)

其中：tmax為最大迭代次數(shù)。

圖2 包圍機制

2.2 螺旋捕食

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

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

(6)

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

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

(7)

2.3 獨立搜索

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

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

(8)

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

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

圖3 WOA算法流程

3 改進的鯨魚優(yōu)化算法

3.1 非線性收斂因子

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

(9)

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

圖4 收斂因子

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

3.2 協(xié)同a的慣性權重

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

(10)

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

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

(11)

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

(12)

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

3.3 免疫記憶

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

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

3.4 時變獨立搜索概率

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

(13)

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

通過以上方式對鯨魚算法進行改進后，基于免疫記憶、協(xié)同a的慣性權重和時變獨立搜索概率的改進鯨魚優(yōu)化算法(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中參數(shù)操作對比；

IFfnew

fnew=fM；

END IF

IFfnew

fbest=fnew；

更新引導者位置Xbest；

END IF

END FOR

更新記憶庫M；

t=t+1；

END WHILE

4 測試與對比

4.1 測試函數(shù)

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

表1 測試函數(shù)

4.2 實驗結果與分析

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

表2 實驗結果

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

表3 平均迭代次數(shù)

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

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

圖5 部分測試效果對比

5 IWTWOA在路徑規(guī)劃的應用

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

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

5.1 環(huán)境建模

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

圖6 柵格法環(huán)境建模

5.2 代價函數(shù)

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

(14)

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

L(i)=

(15)

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

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

C(i)=k∑grid(pi)

(16)

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

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

minf

(17)

5.3 IWTWOA路徑規(guī)劃流程

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

Step1：環(huán)境建模，確定起點與終點；

Step2：初始化IWTWOA參數(shù)；

Step3：根據(jù)式(14)計算代價函數(shù)，將路徑規(guī)劃轉化為優(yōu)化問題 ；

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

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

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

5.4 實驗測試

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

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

圖7 路徑規(guī)劃結果

表4 代價函數(shù)比較

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

6 結束語

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