基于混合擾動的非線性灰狼優(yōu)化算法

李征南,秦江濤

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

0 引言(Introduction)

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

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

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

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

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

1.1 包圍獵物

灰狼包圍獵物的數(shù)學(xué)模型如下所示:

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

1.2 狩獵

在狩獵階段,灰狼ω會根據(jù)其他三只領(lǐng)導(dǎo)狼的位置更新其位置,其數(shù)學(xué)模型如下所示:

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

1.3 攻擊獵物

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

2 改進(jìn)的灰狼優(yōu)化算法(Improved Grey Wolf Optimization algorithm)

2.1 非線性控制參數(shù)和余弦變換的權(quán)值因子

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

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

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

圖2 控制參數(shù)對比Fig.2 Comparison of control parameter

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

2.2 t-分布概率擾動

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

其中,Γ是Gamma函數(shù)。

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

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

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

2.3 最優(yōu)位置擾動策略

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

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

2.4 算法流程

改進(jìn)灰狼優(yōu)化算法的偽代碼如下:

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

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

表1 基準(zhǔn)測試函數(shù)Tab.1 Benchmark function

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

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

表2 各優(yōu)化算法在30維下的尋優(yōu)對比基準(zhǔn)測試函數(shù)Tab.2 Comparison of optimization results of each optimization algorithm in 30 dimensions

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

3.2 與不同改進(jìn)策略的對比

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

表3 各改進(jìn)GWO算法尋優(yōu)結(jié)果對比Tab.3 Comparison of optimization results of each improved GWO algorithm

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

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

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

3.3 與其他參考文獻(xiàn)的灰狼優(yōu)化算法對比

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

表4 與其他學(xué)者改進(jìn)GWO算法的測試結(jié)果對比Tab.4 Test results comparison with other scholars' improved GWO algorithm

從表4可以看出,與其他學(xué)者提出的改進(jìn)算法相比,改進(jìn)后的IGWO在10個基準(zhǔn)測試函數(shù)(除F6、F9外)上的均值顯然更小。同時,對比基準(zhǔn)函數(shù)的標(biāo)準(zhǔn)差發(fā)現(xiàn),IGWO 的標(biāo)準(zhǔn)差在除了F5、F6、F7函數(shù)外均位列第一,說明其算法收斂穩(wěn)定性較強(qiáng)。將IGWO 分別與其他三種改進(jìn)算法進(jìn)行對比,發(fā)現(xiàn)IGWO在70%的測試函數(shù)上優(yōu)于DBGWO,在20%的測試函數(shù)上效果相同,僅在10%的測試函數(shù)上較差;在30%的測試函數(shù)上優(yōu)于AGWO,在50%的測試函數(shù)上效果相同;在67%的測試函數(shù)上優(yōu)于PSO_GWO。

綜上來看,與基本GWO 算法相比,IGWO 算法具有更好的尋優(yōu)精度及尋優(yōu)穩(wěn)定性。與目前改進(jìn)的GWO 算法相比,IGWO算法的性能更好。

4 結(jié)論(Conclusion)

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