基于混合擾動的非線性灰狼優化算法

李征南,秦江濤

(上海理工大學管理學院,上海 200093)

0 引言(Introduction)

灰狼優化算法(GWO)是2014年由MIRJALILI等[1]提出的一種群智能優化算法。該算法因模型簡單、參數少、性能好而受到一些學者的追捧,被廣泛應用于函數優化、參數尋優和故障診斷等領域[2-4]。盡管傳統的灰狼優化算法在應用中表現出較佳的性能,但在面對多峰函數優化時,仍然存在依賴初始種群分布、容易陷入局部最優、難以有效協調開發和探索能力的缺點。目前,國內外學者從不同角度對灰狼優化算法進行了改進。王正通等[5]引入新型動態擾動因子策略,以確保算法的尋優精度,并將翻筋斗覓食策略融入GWO 算法中,提高灰狼種群的多樣性,使算法不易陷入局部最優。徐明等[6]結合非線性調整策略、個體記憶策略及小孔成像學習策略,提出一種多策略GWO算法,并對特征選擇問題進行求解。為了平衡探索和開發階段的能力,MA 等[7]提出了一種基于天鷹優化器(Aquila Optimizer,AO)的改進GWO算法。

為有效改進GWO 求解精度低、易陷入局部最優的不足,本文探索了4種不同的策略改進傳統GWO 算法。改進后的非線性控制參數和基于余弦變換的慣性權重,用于GWO 從探索到開發的和諧過渡。在每次的尋優過程中對灰狼個體采取t-分布概率擾動策略和最優個體擾動策略,增加灰狼的探索能力和提高灰狼個體跳出局部最優的能力,并采用貪婪策略決定是否更新最優灰狼。將所有策略都合并到GWO中,提出一種新的算法,稱作改進的灰狼優化算法(Improved Grey Wolf Optimization Algorithm,IGWO)。仿真結果表明,IGWO在10個基準函數上具有更快的收斂速度和更高的收斂精度。

1 灰狼優化算法(Grey Wolf Optimization algorithm)

在自然界中,灰狼是一種群居犬科動物,在生物圈食物鏈的頂端有著嚴格的等級制度。如圖1所示,灰狼等級按照金字塔從上往下依次劃分,即α、β、δ和ω。α對其他灰狼有絕對的控制權,主要管理其他等級的狼。β對除α外的其他灰狼具有絕對優勢,并輔助α進行決策。狼δ服從α和β的命令,對ω有絕對的控制權。灰狼ω是服從其他級別命令的狼。在GWO算法中,一般通過計算灰狼的目標函數值,將適應度最好(即函數值最低)的3只灰狼分別記為α、β和δ,灰狼ω在它們的引導下向獵物位置前進。

圖1 灰狼等級制度Fig.1 The gray wolf hierarchy

1.1 包圍獵物

灰狼包圍獵物的數學模型如下所示:

其中,D表示灰狼與獵物之間的距離;X p(t)為獵物的位置;灰狼當前位置是X(t);A和C是系數向量;a是控制參數,隨著迭代次數的不斷增加,從2線性減少到0。r1和r2是[0,1]中的隨機向量。

1.2 狩獵

在狩獵階段,灰狼ω會根據其他三只領導狼的位置更新其位置,其數學模型如下所示:

公式(5)至公式(7)中,灰狼α、β和δ的位置分別為Xα、Xβ、Xδ,Dα、Dβ和Dδ分別代表當前候選灰狼與灰狼α、β、δ之間的距離。X1、X2和X3分別代表灰狼ω分別朝灰狼α、β和δ前進的方向和步長,X(t+1)是灰狼ω的最終位置。

1.3 攻擊獵物

當獵物停止移動時,灰狼會根據α、β和δ的位置來攻擊獵物。由上文可知,a的值從2開始逐漸線性減小到0,所以a的取值范圍也不斷縮小,其對應的A值也會在區間[-a,a]內發生變化。當A的取值在[-1,1]范圍內時,灰狼發動攻擊,對應于局部搜索;反之,灰狼就會擴大搜索范圍,轉向探索。

2 改進的灰狼優化算法(Improved Grey Wolf Optimization algorithm)

2.1 非線性控制參數和余弦變換的權值因子

在群智能優化算法中,整個進化過程可分為探索(全局搜索)和開發(局部搜索)兩個階段。較強的局部搜索能力,會加快算法收斂的速度;而較強的全局搜索能力,會增強算法跳出局部最優的能力。因此,如何有效協調探索和開發能力,是算法獲得高搜索性能的關鍵。從上文可知,A值的大小決定了GWO是進行全局搜索還是局部搜索,而A值和控制參數a呈線性正相關。但是,GWO 算法是非線性搜索,控制參數a的線性遞減策略不能完全反映實際的優化搜索過程。

從文獻[8]得知,進行全局搜索與局部搜索的比例為7∶3時,算法搜索性能更佳。文獻[9]比較了多種不同函數形式的控制參數,發現余弦函數和二次函數的控制參數更有助于算法性能的提升。因此,本文提出一種搜索比例為7∶3的二次函數形式的非線性控制參數:

公式(8)中,t為當前迭代次數;T為最大迭代次數,其值設為500。由圖2可知,控制參數a隨著迭代次數的不斷增加而呈非線性動態變化,在算法迭代初期衰減較為緩慢,搜索步長相對較大,利于算法進行全局搜索;迭代后期衰減加快,步長減小,有利于提升算法的搜索精度,能夠有效協調算法的全局搜索能力和局部搜索能力。

圖2 控制參數對比Fig.2 Comparison of control parameter

雖然非線性控制參數對GWO的性能提升有一定的作用,但是效果有限,在算法的全局搜索和局部搜索之間難以平衡。考慮到粒子群優化算法(Particle Swarm Optimization,PSO)中慣性權重對算法的有效改進,為了更好地協調算法的全局搜索和局部搜索能力,本文提出一種基于余弦變換的自適應權值策略,如公式(9)所示。權值因子w和迭代次數t具有正相關的關系,即隨著t的增加而呈非線性增加的趨勢。算法初期,慣性權重較小,局部尋優能力得到了增強,從而提高了算法的尋優精度;算法中后期,灰狼種群聚集度較高,此時慣性權重隨迭代次數的增加而變大,有利于灰狼種群發揮全局尋優能力,提高算法的尋優速度。公式(10)是改進后的灰狼位置更新公式。

2.2 t-分布概率擾動

t-分布又稱作學生分布,含有自由度參數n,其概率密度函數如下:

其中,Γ是Gamma函數。

本文提出一種基于最優個體的t-分布概率擾動策略,利用最優灰狼個體對其他個體進行擾動后,產生了新的隨機種群,幫助算法擺脫局部最優。擾動后的個體就會分布在最優灰狼附近,幫助最優灰狼個體尋找到最佳位置,不僅增強了算法的開采能力,還幫助最優個體跳出局部最優點。設置t-分布概率擾動策略中變異概率p=0.01×(2-a),其中a是非線性控制參數。針對每只灰狼,都生成一個[0,1]的隨機數,隨機數小于變異概率的灰狼為滿足變異條件的灰狼,t-分布擾動公式如下:

其中,為第i只經過t-分布概率擾動策略擾動后灰狼個體的位置,Xbest為最優灰狼個體的位置,X i是第i只灰狼個體的位置,trnd(t)是自由度參數為迭代次數的t-分布隨機數。u是取值[0,1]范圍內的系數,隨著迭代次數的增加,u不斷變小,最優灰狼對灰狼個體的影響不斷減小且變異概率p不斷變大,以此增加算法變異的概率,在迭代后期,會幫助算法跳出局部最優。

如圖3所示,t-分布把柯西分布和高斯分布二者的特點結合。迭代初期,會呈現出柯西分布的特點,豐富了種群的多樣性;迭代中后期,自由度參數的取值較大,t-分布近似于高斯分布,增強了算法的局部開發能力。

2.3 最優位置擾動策略

GWO算法在迭代后期,灰狼種群多樣性大大降低,易于陷入局部最優的情況,因此要對最優位置進行擾動,增加對周圍空間的搜索。本文結合t-分布對最優灰狼個體進行擾動,增強算法擺脫局部最優解的能力,保證算法的精度,具體公式如下:

為了保證經過t-分布擾動后的灰狼位置優于原目標位置,在更新操作后引入貪婪策略,通過比較新、舊目標位置的適應度值后再決定是否更新目標位置。貪婪策略如下:

2.4 算法流程

改進灰狼優化算法的偽代碼如下:

3 實驗仿真與結果分析(Experimental simulation and result analysis)

本實驗使用MATLAB R2019b進行仿真實驗。操作環境為64 位Windows 10 操作系統,Intel(R) Core(TM) I5-6300 HQ CPU@3.0 GHz。為了驗證本文改進的灰狼優化算法具有更好的搜索性能和求解精度,實驗選用了文獻[1]中10個標準測試函數進行驗證。測試函數信息如表1所示,其中函數F1～F7為單峰函數,只有一個最小值,所以用來測試算法的開發性能。多峰函數F8～F10,具有一個全局最優值和多個局部極值,可以用來評估算法的探索能力。

表1 基準測試函數Tab.1 Benchmark function

3.1 與原始GWO及其他幾種算法對比

將IGWO與灰狼優化算法(GWO)[1]、粒子群優化算法(PSO)[10]、鯨魚優化算法(WOA)[11]和海鷗優化算法(SOA)[12]進行對比,算法參數設置相同:種群大小為30個,空間維度dim=30,最大迭代次數設置為500次。同時,為客觀評價算法尋優性能的好壞,在上述參數設置條件下,各算法獨立運行30次,記錄各算法的平均值和標準差。其中,平均值越小,表明算法尋優精度越高;標準差越小,算法越穩定。測試結果如表2所示,其中加粗字體為最優測試結果。

表2 各優化算法在30維下的尋優對比基準測試函數Tab.2 Comparison of optimization results of each optimization algorithm in 30 dimensions

表2展示了IGWO和各種基本算法在函數F1～F10上的運行結果。由表2得知,在維度dim=30時,IGWO 算法在5個測試函數F1、F2、F3、F8、F10上能找到最優值。而對于函數F4～F7、F9,IGWO算法雖然未能達到理論最優值,但是尋優結果非常逼近最優值。同時,對比函數F1～F10的標準差(std),發現IGWO 的標準差(除F8外)均小于其他4種基本算法的標準差,僅在函數F8上測試所得標準差與WOA 算法相同,并小于其他3種算法,這表明IGWO 算法收斂穩定性更強,算法的魯棒性更好。綜合來看,IGWO 算法的尋優能力優于其他4種算法。

3.2 與不同改進策略的對比

將IGWO與僅改進控制參數的灰狼優化算法(GWO1)、僅采用自適應慣性權重的灰狼優化算法(GWO2)、僅采用t-分布擾動策略改進的灰狼優化算法(GWO3)和僅實行最優位置擾動策略的灰狼優化算法(GWO4)進行比較,參數設置與本文“3.1”相同,以驗證IGWO 的優越性。表3展示了各種改進GWO算法在測試函數上的均值與標準差,其中加粗字體為最優的測試結果。此外,為更清晰地展示各單一策略對GWO 算法的影響,圖4給出了各種算法在函數F3～F6、F8～F9上的收斂曲線圖。

表3 各改進GWO算法尋優結果對比Tab.3 Comparison of optimization results of each improved GWO algorithm

圖4 各改進GWO算法的收斂曲線圖Fig.4 Convergence curves of each improved GWO algorithm

從表3可以看出,對于函數F1、F3、F8～F10,GWO2、GWO4和IGWO的平均值比采用其他改進策略的算法更接近理論最優值,甚至在函數F1、F3、F8、F10上達到理論最優值。對于函數F2、F4、F5、F7,IGWO 的平均值比其他所有改進算法都要更接近理論最優值。對于函數F6,可以看出GWO3算法的尋優能力最強、IGWO次之。從表3中所有基準測試函數的標準差可以看出,IGWO算法的標準差大多數要低于其他算法,說明改進后的灰狼優化算法進行的30次實驗的平均數據更集中,改進后算法的結果更準確、更穩定。

從圖4可以看出,IGWO算法的性能與其他改進算法相比有明顯的提升。與GWO相比,GWO1在收斂速度和求解精度上均有不同程度的提升,表明非線性控制參數策略能提高算法的性能。在函數F3～F4、F8～F9上,GWO2和GWO4因其采取的改進策略而表現出較優的全局搜索能力。對于函數F5、F6,GWO3采取t-分布概率擾動策略提高了算法跳出局部最優的能力。綜合來看,應用各改進策略的算法在性能上均有不同程度的提升,融入各種改進策略的IGWO 算法具有更強的尋優能力和求解能力。

3.3 與其他參考文獻的灰狼優化算法對比

文獻[13]提出了一種基于停滯檢測的雙向搜索灰狼優化算法(DBGWO),文獻[14]對雜交策略進行改進并將其融入GWO算法中,提出一種改進的雜交策略的自適應灰狼優化算法(AGWO),文獻[15]把粒子群算法和灰狼算法相結合,提出一種混合GWO算法(PSO_GWO)。將IGWO 與上述三種算法在維度為30的場景下進行對比,結果如表4所示,其中加粗字體為最優測試結果,“—”表示參考文獻未做該實驗。

表4 與其他學者改進GWO算法的測試結果對比Tab.4 Test results comparison with other scholars' improved GWO algorithm

從表4可以看出,與其他學者提出的改進算法相比,改進后的IGWO在10個基準測試函數(除F6、F9外)上的均值顯然更小。同時,對比基準函數的標準差發現,IGWO 的標準差在除了F5、F6、F7函數外均位列第一,說明其算法收斂穩定性較強。將IGWO 分別與其他三種改進算法進行對比,發現IGWO在70%的測試函數上優于DBGWO,在20%的測試函數上效果相同,僅在10%的測試函數上較差;在30%的測試函數上優于AGWO,在50%的測試函數上效果相同;在67%的測試函數上優于PSO_GWO。

綜上來看,與基本GWO 算法相比,IGWO 算法具有更好的尋優精度及尋優穩定性。與目前改進的GWO 算法相比,IGWO算法的性能更好。

4 結論(Conclusion)

本文提出了一種基于混合擾動的GWO算法,該算法在求解復雜優化問題的全局最優解時,具有更好的搜索精度和收斂速度。通過引入控制參數和慣性權重,有利于平衡算法全局搜索和局部搜索的能力,加入t-分布概率擾動策略和最優灰狼擾動策略,有利于增強算法跳出局部最優的能力。通過對10個基準測試函數進行測試,從平均值和標準差可以看出,IGWO具有更佳的性能。未來的研究工作有兩個部分:一是不斷改進灰狼優化算法,以期獲得性能更好的算法;二是將改進算法應用于實際,如解決具體的工程設計、車間調度等問題。