融合單純形法和個體記憶的鯨魚算法及工程應用

趙筱斌，王未卿

(1.浙江建設職業技術學院 教育技術中心，浙江 杭州 311231；2.北京科技大學 東凌經濟管理學院，北京 100083)

0 引 言

鯨魚是自然界中最大的哺乳動物，擁有獨特的捕食方法-氣泡網螺旋捕食法。該方法分兩個階段：第一階段，鯨魚在水下較深位置圍繞獵物螺旋游動生成大量氣泡；第二階段，通過循環方式完成捕食。受此啟發，學者Mirjalili提出一種新型群體智能優化算法-鯨魚優化算法(whale optimization algorithm，WOA)[1]，該算法通過鯨魚群體搜索、包圍、螺旋氣泡圍捕等過程，實現優化目標搜索。WOA算法執行原理簡單易行，依賴關鍵參數少，擁有較強全局搜索性能，用于函數優化時，求解精度和收斂性能要優于粒子群、引力搜索及差分進化等算法。該算法已經在車間作業調度[2]、物流路徑優化[3]、圖像分割[4]、群智感知系統[5]、TSP問題[6]、特征選擇[7]等諸多領域得到了應用。

然而，基本WOA算法依然存在搜索與開發間難以協調、復雜高維問題求解精度低、收斂速度慢等不足。為此，文獻[8]利用Logistic混沌映射優化種群初始位置，并設計非線性自適應權重協調種群搜索能力，提升種群多樣性。文獻[9]通過非線性收斂因子提升種群多樣性，利用局部擾動避免陷入局部最優，提升尋優精度。文獻[10]同樣利用混沌和非線性收斂因子的組合方式分別提升種群多樣性和平衡搜索能力。文獻[11]設計自適應隨機策略的鯨魚對獵物的包圍方法，可以較好提升收斂速度和尋優精度。文獻[12]提出萊維飛行的改進鯨魚優化算法，通過不同步長飛行軌跡提升種群多樣性。文獻[13]引入粒子群的慣性權重思維對算法搜索能力進行改進，提升尋優精度。

然而，已有改進工作雖然可以從某些方面優化WOA的尋優性能，但在局部開發與全局搜索的自適應均衡、收斂速度、跳離局部最優上，仍有進一步研究空間。為此，本文將提出一種改進算法，分別引入非線性收斂因子調整、單純形法及個體記憶融合機制對傳統鯨魚算法的尋優能力進行改進。通過國際公認的若干基準函數的尋優測試驗證改進算法可以有效提升收斂速度和尋優精度，實現預期效果。并用一種典型工程設計問題對改進算法的可應用性進行了驗證。

1 鯨魚優化算法WOA的基本原理

WOA是一種新型的受自然界動物行為啟發的元啟式算法，其主要思想是模擬大海中座頭鯨的捕食行為。座頭鯨以螺旋形式逐步靠近獵物并生成氣泡限制獵物的行動。同其它元啟發式方法類似，WOA算法有兩個階段：開發階段和搜索階段。開發階段根據座頭鯨包圍獵物(代表目前為止的最優解)并逐步向其靠近的機制模擬，可以表示為以下兩式

D=|C·X*(t)-X(t)|

(1)

X(t+1)=X*(t)-A·D

(2)

其中，X(t) 為當前鯨魚個體的位置，X*(t) 為當前種群中最優解的位置(可理解為食物源的位置)，t為當前迭代，A、C為系數矢量，代表鯨魚向獵物的包圍步長，具體定義為

A=2a·r1-a

(3)

C=2·r2

(4)

其中，r1和r2是[0,1]間的隨機量，a為收斂因子，取值迭代式從2線性遞減至0(模擬向獵物的收縮包圍行為)，表示為

a=2-2×t/max_iter

(5)

式中：max_iter為算法的最大迭代數。

下式用于模擬鯨魚向獵物靠近的螺旋式路徑

X(t+1)=X*(t)+D′·ebl·cos(2πl)

(6)

D′=|X*(t)-X(t)|

(7)

其中，D′為個體i與當前最優目標的距離，b為對數螺旋形狀常量，l∈[-1,1]。 算法以50%概率選擇位置更新方式

(8)

式中：p為[0,1]間的隨機量。

為了模擬WOA算法的搜索行為，隨機選取一個搜索個體更新當前個體位置，以替代根據目前最優解引領個體位置更新，此方法可以提升算法的隨機性。該過程可表示為

D=|C·Xrand(t)-X(t)|

(9)

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

(10)

其中，Xrand(t) 為當前種群中隨機選取的搜索個體。

WOA算法始于一個隨機初始化的種群結構，然后通過目標函數計算每個解的適應度。緊接著選取最優解，并更新相關系數因子。接下來，種群內的解根據式(2)或式(6)進行更新，這取決于隨機概率p。該過程重復直到滿足預定義的終止條件為止。最終，算法將返回種群內的全局最優解。

2 融合個體記憶和單純形法的非線性改進鯨魚優化算法IMSWOA

2.1 非線性收斂因子調整機制

WOA算法的搜索過程始于隨機解集合。每次迭代中，個體將根據隨機選取的搜索代理或當前最優個體作位置更新。收斂因子a線性從2遞減至0，提供全局搜索和局部開發的協調能力。 |A|>1時，選取隨機個體為向導作位置更新，即：個體將擴大搜索范圍，尋找更好的解，可視為全局搜索； |A|<1時，選取當前最優解為向導作位置更新，即：個體將在局部范圍作精細搜索，可視為局部開發。概率p決定是進行螺旋靠近或向目標包圍。可見，a決定算法的局部開發與全局搜索之間的協調。由式(5)可知，a值呈線性遞減。即：整個過程中，全局搜索和局部開發的遞減速率是相同的，這極大降低了鯨魚搜索個體的靈活性，使迭代早期的搜索和迭代后期的尋優收斂失去平衡。

為此，IMSWOA引入非線性收斂因子遞減調整策略，使a值在迭代中以不同的速率進行遞減。具體改進公式為

(11)

式中：ainitial、afinal分別為收斂因子的初值和終值，max_iter為最大迭代數，μ為調整系數，μ>0。根據式(11)，收斂因子將隨迭代次數呈非線性遞減，其曲線為遞減式的凸曲線形式。那么，迭代早期a較大，但遞減速率較小，可以更大步長實現充分全局搜索。迭代后期a變小，但遞減速率變大，這樣個體可以以較小的步長以更快的速度在局部范圍內進行精細的局部開發，可以加速算法收斂，得到最優解。這種以不同速率遞減的收斂因子調整策略將有助于算法的局部開發與全局搜索間的協調進行。

2.2 基于單純形法的局部搜索機制

單純形法(simplex method)是一種原理簡單、搜索速度較快、局部搜索能力較強的多面體搜索算法。IMSWOA算法進一步引入單純形法增強局部搜索能力，提升算法收斂速度。單純形法構建在由若干頂點組成的多面體多維空間上，通過評估各頂點(代表鯨魚個體位置目標)適應度，尋找最優點、次優點和最差點；然后通過反射、擴展、收縮和壓縮4種策略尋找較優點以替換較差點，以形成新多面體結構，通過若干次迭代接近全局最優點。點搜索模型如圖1所示。

圖1 單純形法的點搜索模型

基于單純形式法的局部搜索過程如下：

步驟1 根據選取的基準函數，計算所有頂點(對應種群中的鯨魚個體)的適應度(由于基準函數是最小值尋優，故適應度值越小，位置越優)，找到適應度最優點Xg、次優點Xb、最差點Xw，并計算中心點Xc為

Xc=(Xg+Xb)/2

(12)

步驟2 根據最差點Xw和中心點Xc的位置，進行反射操作，反射點Xr為

Xr=Xc+α×(Xc-Xw)

(13)

式中：α為反射因子，取值1。

步驟3 若f(Xr)

Xe=Xc+γ×(Xr-Xc)

(14)

式中：γ為擴展因子，取值2。若f(Xe)

步驟4 若f(Xr)>f(Xg)， 說明反射方向不對，進一步作壓縮操作，壓縮點Xt為

Xt=Xc+β×(Xw-Xc)

(15)

式中：β為壓縮因子，取值0.5。若f(Xt)

步驟5 若f(Xw)>f(Xr)>f(Xg)， 則進行收縮操作，收縮點Xs為

Xs=Xc-β×(Xw-Xc)

(16)

式中：β為收縮因子，取值同上。若f(Xs)

2.3 融入個體記憶的位置更新機制

由式(2)可知，鯨魚對獵物進行包圍時的位置迭代更新中僅考慮當前種群的歷史最優位置和個體的當前位置的結合來得到最優解，而沒有考慮與個體自身經驗的交流，即缺乏考慮個體歷史最優位置對其位置更新的影響，導致缺乏個體記憶性。為此，借用粒子群優化的思路，將個體的歷史最優解考慮在位置更新中，使個體位置更新具備記憶保存功能，促進自身位置進一步尋優。那么，個體包圍獵物時，融入個體記憶功能的位置更新方式為

X(t+1)=c1r3·(X*(t)-A·D)+c2r4·(Xibest-X(t))

(17)

式中：c1為社會學習因子，對應于當前種群最優解對個體搜索能力的影響，c2為認知學習因子，對應于個體本身所經歷的最優解對個體搜索能力的影響，r3、r4為[0,1]區間的隨機量，Xibest為個體經歷的最優解。

相應地，鯨魚的螺旋靠近也進一步添加記憶功能，則

X(t+1)=c1r5(D′·ebl·cos(2πl)+X*(t))+c2r6·(Xibest-X(t))

(18)

式中：r5、r6為[0,1]內的隨機量。融入個體記憶后，通過調整社會學習因子和認知學習因子，即可協調個體與種群間的信息交流和個體記憶對整體算法的搜索和尋優能力的影響。

2.4 IMSWOA算法具體過程

輸入：初始種群結構X={X1,X2,…,XN}， 收斂因子初值ainitial、終值afinal，算法最大迭代數max_iter，收斂因子調整系數μ，反射因子α，擴展因子γ，壓縮因子β，社會學習因子c1，認知學習因子c2，對數螺旋形狀常量b

輸出：全局最優解X*

(1) 初始化鯨魚種群，規模為N，表示為Xi,i=1,2,…,N

(2) 計算N個個體的適應度f(Xi)

(3) 選擇適應度最小(最優)的個體X*

(4)whilet

(5)foreachXi,i=1,2,…,N

(6) 根據式(11)更新收斂因子a

(7) 根據式(3)、式(4)更新參數A、C，并更新l、p

(8)if(p<0.5)

(9)if(|A|<1)

(10) 根據式(17)更新個體位置//位置包圍

(11)if(|A|≥1)

(12) 隨機選擇個體Xrand

(13) 根據式(10)更新個體位置//獵物搜索

(14)endif

(15)elseif(p≥0.5)

(16) 根據式(18)更新個體位置//螺旋位置更新

(17)endif

(18)endfor

(19) 調用2.2節執行單純形法優化種群中的較差解

(20) 越界檢查，并修正越界個體

(21) 計算種群個體適應度{f(Xi),i=1,2,…,N}

(22) 更新全局最優個體X*

(23)t=t+1

(24)endwhile

(25) 返回全局最優解X*

3 實驗分析

3.1 實驗環境

為了驗證IMSWOA算法在解決高維復雜函數優化問題的有效性，利用表1中比較常用的8種基準函數測試算法的尋優性能(基準函數很多，在此無法列舉太多作數值測試分析，但表1中已經涵蓋常用單峰函數和多峰函數)。表中包括函數表達式、搜索區間、理論最優值和收斂精度。仿真實驗中，改進鯨魚優化算法的相關參數：最大迭代次數max_iter=400，種群規模為N=30，收斂因子初值ainitial=2，終值afinal=0，收斂因子調整系數μ=10，社會學習因子c1=0.5，認知學習因子c2=0.5。對于每個基準函數，實驗均獨立運行30次。實驗硬件環境為Intel Core CPU 2.5 GHz主頻，4 G內存。軟件環境為Windows 10操作系統和Matlab 2017a。

表1 基準函數

3.2 IMSWOA算法與同類改進WOA算法的對比

對比算法選擇Logistic混沌映射和非線性自適應權重策略的改進鯨魚優化算法MWOA[8]、非線性收斂因子和局部擾動的改進鯨魚進化算法NPWOA[9]、慣性權重思維的改進鯨魚優化算法IWWOA[13]進行性能比較。公有參數中，種群規模和最大迭代次數配置相同。表2是與同類改進WOA算法的對比結果，利用目標函數的平均精度和標準差進行性能對比。依據表2所示結果，IMSWOA算法在所有測試的8個基準函數上基本可以得到最優解，同時標準差也基本為0，表明本文的改進算法不僅擁有較強的尋優能力，而且在不同類型的基準函數上(單峰或多峰)具有較好的穩定性和魯棒性。NPWOA算法引入非收斂因子和局部擾動機制，確保了WOA具有較強的搜索能力，但其復雜的過程會導致收斂速度變慢。但該算法在部分函數上還是取得了很好的尋優效果。IWWOA算法僅引入慣性權重思維，種群多樣性缺乏，尋優精度性能依然不足，改進比較片面。MWOA算法同步在初始種群和收斂系數做了改進，提升了種群多樣性，也增強了算法的搜索與開采能力的均衡，性能有所提升。總體上本文的IMSWOA算法的綜合性能是4種算法中最佳的。

表2 與同類改進WOA算法的對比結果

圖2是4種算法的收斂曲線。篇幅原因，僅羅列5個基準函數。總體觀察400次迭代過程中算法的收斂情況，曲線的墜落程度可以反映算法的尋優速度和收斂速度，而曲線的端點值則對應于算法的尋優精度。可以看到，IMSWOA算法的收斂速度是最快的，其下降趨勢是所有算法中最明顯的，同時具有更高的尋優精度，最為接近理論最優值。IWWOA算法和MWOA算法所表現出的較為平緩的曲線說明算法的尋優速度較慢、收斂速度較慢、尋優精度也較低。

圖2 收斂曲線

3.3 IMSWOA算法中不同改進策略的影響

本節測試分析利用IMSWOA算法中的3種改進策略對傳統WOA算法進行單獨改進時算法的性能表現。將僅利用非線性收斂因子調整機制的改進鯨魚優化算法命名為NC-WOA算法，將僅利用單純形法的改進鯨魚優化算法命名為SM-WOA算法，將僅融合個體記憶的改進鯨魚優化算法命名為IM-WOA算法。相關參數配置和實驗環境配置同上。實驗結果見表3。從比較結果可以看出，僅融合個體記憶的改進鯨魚優化算法IM-WOA對于傳統WOA的尋優性能的改進還是比較有限的，而非線性收斂因子調整的NC-WOA算法和單純形法的SM-WOA算法可以更好提升算法的尋優精度，穩定性也較好，在部分基準函數中甚至可以求解得到最優解。由此可見，對于WOA算法的改進問題而言，均衡個體的搜索與開采能力，提升整體種群質量，避免局部最優顯得尤為重要。

3.4 收斂因子不同變化下的性能表現

本節測試收斂因子的變化對IMSWOA算法的性能影響。由收斂因子定義式(11)可知，收斂因子a隨迭代次數的遞增，主要受其初值ainitial、終值afinal、調整系數μ的影響。收斂因子決定搜索與開采能力的平衡。表4是4組收斂因子初值和終值對得到的實驗結果，其它參數配置同上，調整系數為10。表5是4組調整系數取值的實驗結果，收斂因子初/終值為2/0。根據表4的結果可以看到，不同的初/終值對尋優效果有一些影響，但影響很有限，在大多數基準函數上，改進算法的尋優精度表現比較穩定，尋優成功率未受到較大影響，說明算法對該因素的依賴性較小。同時，4組取值中，2/0這組取值相對尋優成功率是最高的(其它實驗中應用該組取值)。表5的結果表明，調整系數對IMSWOA算法的尋優性能具有一定影響，但不是單純的提升或者降低算法的性能。初期會隨調整系數的增加而提升，到達一定高度后，又會出現下降。總體來看，4組取值中，μ=10得到平均精度和標準差是最好的(在5組基準函數上得到了理論最優解，其它實驗中應用該取值)。

表3 不同改進策略下的WOA算法性能對比

表4 收斂因子初/終值的影響(維度=50維)

表5 調整系數取值的影響(維度=50維)

4 基于IMSWOA算法的工程設計優化應用

為了驗證IMSWOA算法解決實際問題的可行性，本節進一步將IMSWOA算法用于求解一種標準的工程設計優化問題。因為篇幅原因，僅利用在求解拉伸彈簧設計問題上。拉伸彈簧設計問題的目標是最小化拉伸彈簧的設計重量，該最小化過程同時受到以下4個因素的約束：切變壓力、波動頻率、外徑和繞度。問題的3個變量為：線材直徑d、平均繞線直徑D、活性線圈數量P。拉伸彈簧設計如圖3所示。

圖3 拉伸彈簧設計

具體的數學模型如下：

問題變量

x={x1,x2,x3}=[d,D,P]

最小化目標

f(x)=(x3+2)x2x12

約束條件

變量范圍

0.05≤x1≤2.00, 0.25≤x2≤1.30, 2.00≤x3≤15.0

表6是20次算法運行中IMSWOA算法與其它已經應用在拉伸彈簧設計問題上的幾種智能算法的尋優對比結果，表中同時給出了問題中的3個因變量和最優重量的取值，即優化變量的最優設計值。可以看到，前4種算法的最優解已經非常接近，其最優重量值的差別僅在10-7數量級上，但依然可以看到，IMSWOA算法得到了最小的拉伸彈簧重量。圖4中4種算法對于拉伸彈簧設計問題求解的收斂曲線也驗證IMSWOA算法可以更快的收斂，這說明算法在處理拉伸彈簧設計優化這類實際工程優化問題上是有效可行的。進一步可以將IMSWOA算法求解焊接梁設計、壓力容器設計、三桿桁架設計等不同規模和復雜程度的工程設計問題上，因篇幅受限，在此不作數據列舉。

表6 拉伸彈簧設計問題的求解

圖4 拉伸彈簧設計求解結果

5 結束語

提出了一種基于單純形法和融入個體記憶的改進非線性鯨魚優化算法IMSWOA。算法通過非線性調整使收斂因子在迭代過程中呈現不同遞減速率，以此協調搜索與開發間的平滑轉換；通過單純形法增強了算法的局部搜索能力，并利用融合個體記憶和種群最優改善位置更新機制，協調個體與種群間的交流和個體記憶對整體算法的搜索和尋優能力。基準函數測試驗證算法可以有效提升收斂速度和尋優精度，避免局部最優解。求解拉伸彈簧設計問題也驗證了算法的可行性。進一步研究可嘗試將改進算法在其它工程設計或神經網絡訓練領域的應用驗證，以此發現算法存在的可改進點。