魏鋒濤, 張洋洋, 黎俊宇, 史云鵬

(西安理工大學(xué)機械與精密儀器工程學(xué)院, 陜西 西安 710048)

0 引 言

正弦余弦算法(sine cosine algorithm,SCA)是由Mirjalili等人于2016年提出的一種基于種群的優(yōu)化算法。該算法結(jié)構(gòu)簡單,易于實現(xiàn),其隨機參數(shù)很好地平衡了算法的探索與開發(fā)能力,在裝備制造[1]、非線性優(yōu)化問題[2-4]、節(jié)點部署[5-6]、圖像處理[7]、預(yù)測模型[8-9]、分類識別[10]等方面獲得了廣泛的應(yīng)用。但該算法存在易陷入局部最優(yōu)、求解精度不高、收斂速度較慢等問題,許多學(xué)者對其進行了改進研究。Shubham等[11]提出了一種用于全局優(yōu)化問題的改進SCA(簡稱為MSCA),使用反向?qū)W習(xí)生成初始種群,并在搜索方程中加入自適應(yīng)成分,利用個體最優(yōu)值更新位置,從而使算法從局部最優(yōu)跳出,并探索所有有潛力的搜索空間。Usharani等[12]提出了一種具有指數(shù)遞減轉(zhuǎn)換參數(shù)和控制萊維變異的改進算法(簡稱為ISCA),可在迭代過程中更有效地探索解空間。Long等[13]提出了一種求解高維全局優(yōu)化問題的改進SCA(簡稱為HSCA),位置更新方程引入慣性權(quán)重,提出一種新的基于高斯函數(shù)的非線性轉(zhuǎn)換參數(shù)遞減策略,加快了算法的收斂速度,平衡了SCA的開發(fā)和探索。Singh等[14]提出了一種灰狼算法與SCA混合的新算法(簡稱為GWOSCA)。在開發(fā)階段灰狼優(yōu)化器尋找所有有可能的空間,在探索階段用SCA尋求更高的精度,從而提高算法的收斂精度。Rizk等[15]提出了一種基于SCA和多正交搜索策略(multi-orthogonal search strategy, MOSS)混合的新算法(簡稱為MOSCA),綜合了SCA和MOSS的優(yōu)點,在SCA階段啟動搜索過程以增強探索能力,在MOSS階段增強算法開發(fā)能力,從而平衡算法的探索和開發(fā)過程,提高收斂精度和速度。Shubham等[16]提出了一種用于全局優(yōu)化的SCA(簡稱為GSCA),引入非線性轉(zhuǎn)換來代替線性轉(zhuǎn)換,并引入精英解,修正了原始的搜索策略,從而避免在搜索過程中陷入局部最優(yōu)的情況,更好地平衡了算法的探索與開發(fā)能力。

以上文獻均從不同方面對SCA進行了改進研究,增強了SCA的性能,但如何更好地提高收斂精度和收斂速度,平衡全局搜索能力與局部開發(fā)能力仍需要進一步研究。鑒于此,本文提出一種基于動態(tài)分級策略的SCA(improved SCA based on dynamic classification strategy,DSCA)。首先,在初始化種群階段,通過拉丁超立方種群初始化策略來初始化種群,可以避免漏掉部分有價值的搜索空間,以提高初始種群的多樣性以及在搜索空間分布的合理性。其次,通過動態(tài)分級策略將種群分為好、中、差3個等級,對不同等級應(yīng)用不同策略,對適應(yīng)度值好的種群通過精英引導(dǎo)加快收斂速度。然后，對適應(yīng)度值差的種群通過破壞策略進行擾動,以提高算法的收斂精度,避免陷入局部最優(yōu)。最后,引入反向?qū)W習(xí)方法,設(shè)計動態(tài)反向?qū)W習(xí)全局搜索策略,以提高算法的收斂速度。通過對標準測試函數(shù)進行實驗仿真,并與粒子群優(yōu)化(particle swarm optimization,PSO)算法、回溯搜索優(yōu)化算法(backtracking search optimization algorithm,BSA)、文獻[11]的MSCA、文獻[12]的ISCA、文獻[16]的GSCA幾種改進SCA進行比較,以驗證本文提出改進算法的有效性。

1 SCA

SCA基本思想是利用正余弦函數(shù)的震蕩特性逐步收斂于最優(yōu)解,向外波動進行全局探索,向最優(yōu)解波動進行局部開發(fā)。SCA將優(yōu)化過程分為兩個階段:探索階段與開發(fā)階段。通過搜索和開發(fā)階段不斷逼近全局最優(yōu)解。SCA兩個階段的位置更新方程為

(1)

(2)

(3)

式中,t是當(dāng)前迭代次數(shù);T是最大迭代次數(shù);a是常量,通常取a=2。

由式(1)和式(2)可知,SCA主要包括4個參數(shù):r1、r2、r3和r4。其中,r1決定粒子下次移動的方向,控制算法從全局搜索到局部開發(fā)的轉(zhuǎn)換;r2決定粒子的移動距離;r3增強或減弱移動方向產(chǎn)生的影響;r4使式(1)和式(2)在更新位置時隨機切換。

該算法的具體求解步驟如下。

步驟 1初始化種群,初始化參數(shù)r1、r2、r3和r4,并計算適應(yīng)度函數(shù)值。

步驟 2更新參數(shù)r1、r2、r3和r4,根據(jù)式(1)或式(2)獲取新的位置。

步驟 3計算適應(yīng)度值,更新最優(yōu)方案。

步驟 4終止條件判斷,若滿足,則輸出最優(yōu)解,否則返回步驟2。

2 DSCA

SCA在迭代過程中容易陷入局部最優(yōu),初始化種群采用隨機生成方案,其隨機性導(dǎo)致種群多樣性差,在迭代過程中,位置更新公式的隨機性導(dǎo)致對高維函數(shù)的求解精度不足,收斂速度較慢。針對以上存在問題,本文利用拉丁超立方初始種群策略、動態(tài)分級策略以及全局搜索策略對SCA進行改進。首先,為提高種群的多樣性,利用拉丁超立方抽樣的思想,設(shè)計了拉丁超立方初始種群策略,生成優(yōu)質(zhì)初始種群。其次,通過動態(tài)分級策略將種群按適應(yīng)度值高低分為3個部分,對適應(yīng)度值高的位置應(yīng)用破壞算子進行擾動，同時對適應(yīng)度值低的位置利用精英引導(dǎo)方式進行更新位置,以提高算法的收斂精度,增強跳出局部最優(yōu)的能力。最后,利用反向?qū)W習(xí)方法,采用動態(tài)反向?qū)W習(xí)全局搜索策略,提高算法的收斂速度。

2.1 拉丁超立方種群初始化策略

初始種群的好壞會影響收斂速度和精度。SCA的初始種群是隨機產(chǎn)生的,無法保證種群的多樣性以及在搜索空間分布的合理性,故DSCA通過引入拉丁超立方抽樣法[17-22]生成更加分布均勻的初始點。

拉丁超立方抽樣法是McKay等人提出來的一種多維分層抽樣技術(shù),可以高效地在變量的分布區(qū)間抽樣,其本質(zhì)就是將區(qū)間[0,1]等分成N個等間距不重疊的子區(qū)間,對每個子區(qū)間分別進行獨立的等概率抽樣從而保證抽樣點均勻地分布在整個分布區(qū)間。隨機抽樣是在區(qū)間[0,1]服從均勻分布,在抽樣數(shù)不多的情況下,隨機分布不能很好地將樣本分散到整個區(qū)間。與隨機抽樣不同,拉丁超立方抽樣保證變量覆蓋在整個分布空間。拉丁超立方抽樣和隨機抽樣分布對比如圖1所示,圖中表示隨機抽樣和拉丁超立方抽樣在區(qū)間[0,1]各抽取10個點,可以清楚看到,拉丁超立方抽樣對于少量樣本的情況下可以散布到整個空間。

圖1 抽樣分布對比圖Fig.1 Comparison chart of sampling distribution

初始種群是在D維空間中生成種群規(guī)模為N的種群,故結(jié)合拉丁超立方抽樣法可得到DSCA中種群初始化策略,具體步驟如下。

步驟 1首先,確定種群維數(shù)D和種群規(guī)模N。

步驟 2確定變量x的區(qū)間為[ub,lb],其中ub和lb分別是變量的下界和上界。

步驟 3將變量x的區(qū)間[ub,lb]劃分為N個相等的子區(qū)間。

步驟 4在每一維里各個子區(qū)間中隨機抽取一個點。

步驟 5將抽取的每一維的點組合形成初始種群。

2.2 動態(tài)分級策略

為了解決SCA存在的收斂精度較低且收斂速度較慢的問題,本文采用動態(tài)分級策略根據(jù)適應(yīng)度值對種群進行排序,將種群動態(tài)地分為3個部分,對適應(yīng)度值小的部分,種群處于較好的位置,通過精英引導(dǎo)加快收斂速度;對適應(yīng)度值處于中間的部分,按照SCA位置更新公式進行迭代;對適應(yīng)度值大的部分,種群處于較差的位置,通過破壞算子進行擾動,以增加其種群多樣性,提高收斂精度,避免陷入局部最優(yōu)。具體分級為

(4)

式中,Xi, j是所有種群,Xi,a,Xi,b和Xi,c分別是按照適應(yīng)度值排序后得到的較差、中等和較好種群;m和n分別是動態(tài)分級的邊界:

具體分級思路如圖2所示。

圖2 動態(tài)分級策略示意圖Fig.2 Schematic diagram of dynamic classification strategy

2.2.1 破壞擾動算子

為了提高SCA的收斂精度和種群的多樣性,并避免陷入局部最優(yōu),引入一種破壞擾動算子,其思想源自天體物理學(xué)中“當(dāng)總質(zhì)量為m′的大量受重力束縛的粒子群過于接近大型物體M時,該粒子群往往會被撕開”[23]。為了實現(xiàn)破壞擾動,將算法中的最優(yōu)種群作為大型物體M,在大型物體的引力作用下,其他種群會被破壞和散射,以提高種群多樣性以及收斂精度。

為了防止算法復(fù)雜性的過分增加,只有在滿足

(5)

(6)

式中,C0是初始閾值。破壞算子為

(7)

對適應(yīng)度值差的部分的種群Xi,a,通過破壞算子進行擾動,通過

(8)

對滿足破壞條件的粒子進行擾動。式(8)中包含兩部分,第一部分來自原來的種群信息,第二部分是包含破壞算子的部分,并且是隨著時間減小的函數(shù),算法早期可以受到破壞,探索更廣闊的區(qū)域,避免陷入局部最優(yōu);在后期可以更快收斂,因此主要靠種群本身的信息,通過破壞算子的擾動,從而提高算法收斂精度。

2.2.2 精英引導(dǎo)方式

SCA通常利用式(1)和式(2)更新種群,存在收斂速度慢等問題,DSCA對適應(yīng)度值好的部分種群Xi,c利用精英引導(dǎo)方式進行位置更新,從而加快算法收斂速度,在位置更新公式里引入個體極值,通過精英引導(dǎo)加快收斂速度。首先更新參數(shù)r1、r2、r3和r4,通過控制參數(shù)pi在精英引導(dǎo)方式和原種群更新方式之間轉(zhuǎn)換，在迭代前期,需要較大的pi值使粒子向最優(yōu)方向進行;到了迭代后期,則不需要精英引導(dǎo)種群,而采用原來的種群更新方式更新種群。因此，通常取pi=0.4-0.4t/T。具體更新策略為

(9)

2.3 全局搜索策略

通過全局搜索策略進行更新,將經(jīng)動態(tài)分級策略擾動的種群合并,對整個種群應(yīng)用全局搜索策略更新,具體構(gòu)造如下：

(10)

(11)

將動態(tài)反向?qū)W習(xí)數(shù)引入到搜索策略中,既可以在迭代后期局部的上下限進行跳動以增強跳出局部最優(yōu)的能力,又可以加快收斂速度,根據(jù)控制參數(shù)pr在全局搜索策略和動態(tài)分級策略之間轉(zhuǎn)換,全局策略為

(12)

2.4 DSCA的基本流程

DSCA基本流程如圖3所示。

圖3 DSCA流程圖Fig.3 DSCA flow chart

3 數(shù)值仿真分析

為了DSCA的性能,選取PSO、BSA、SCA及文獻[11]的MSCA、文獻[12]的ISCA、文獻[16]的GSCA 3種改進算法與DSCA進行對比,選取15個標準測試函數(shù)[28-32]分別在低維D=50和D=100，以及高維D=500進行仿真實驗,比較不同算法的性能,測試函數(shù)信息如表1所示。實驗設(shè)備為一般PC機,運行內(nèi)存為8 GB,基于Matlab 2019 a獲取優(yōu)化結(jié)果。實驗參數(shù)設(shè)置如下:種群規(guī)模N=30,最大迭代次數(shù)設(shè)置為5 000,其余對比算法參數(shù)均按照原文獻設(shè)置。

表1 測試函數(shù)

3.1 復(fù)雜度分析

算法的時間復(fù)雜度是算法性能重要的衡量標準,主要取決于算法的結(jié)構(gòu),故所提出的DSCA的復(fù)雜度取決于解決方案的種群規(guī)模N,決策變量的維數(shù)D和最大迭代次數(shù)Maxiter。因此,根據(jù)大O表示法可以給出相同參數(shù)設(shè)置情況下SCA的時間復(fù)雜度為

O(SCA)=O(N·D·Maxiter)

(13)

根據(jù)DSCA流程圖得到的算法時間復(fù)雜度包括:拉丁超立方初始化的時間復(fù)雜度O(N·D),計算初始極值的時間復(fù)雜度O(N·D),動態(tài)分級策略的時間復(fù)雜度O(N·D·Maxiter),全局搜索策略的時間復(fù)雜度O(N·D·Maxiter),更新全局極值的時間復(fù)雜度O(N·D·Maxiter)。因此，通過以上分析可知,DSCA的時間復(fù)雜度為

O(DSCA)=O(N·D·Maxiter)

(14)

對每個測試函數(shù)分別獨立運行30次,取函數(shù)運行時間的平均數(shù)進行統(tǒng)計分析,獲得運行時間統(tǒng)計圖如圖4所示。

圖4 運行時間統(tǒng)計圖Fig.4 Running time statistics chart

由圖4可看出,SCA與DSCA的運行時間相差不大,可見DSCA算法沒有增加計算負擔(dān)。

3.2 收斂性分析

3.2.1 算法在低維函數(shù)下收斂性分析

為比較算法在低維函數(shù)下收斂性能,對每個測試函數(shù)分別獨立運行30次,實驗結(jié)果取最優(yōu)值(Best),平均值(Mean)和方差(Std)進行比較。算法在函數(shù)50維測試結(jié)果的比較如表2所示。由表2可知,在單峰測試函數(shù)中,DSCA的收斂精度均優(yōu)于其他比較算法,尤其是對于函數(shù)f3,DSCA可以達到理論最優(yōu)值。對于函數(shù)f4和f7,DSCA與文獻對比算法結(jié)果值相近,但DSCA的方差小,穩(wěn)定性能好。從表2可以看出,DSCA在多峰測試函數(shù)中也能得到高精度的解,尤其是對于函數(shù)f8、f10和f12,DSCA均達到了理論最優(yōu)值;函數(shù)f11和f13雖沒有達到理論最優(yōu),但收斂精度達到了E-200數(shù)量級,相較于其他比較算法跳出局部最優(yōu)值的能力較好。在方差的對比中,所有函數(shù)中DSCA的方差均為最小,因此在穩(wěn)定性方面,DSCA的魯棒性較好。

表2 不同算法測試結(jié)果比較(D=50)

續(xù)表2

為了更為直觀地比較7種算法的收斂性能,實驗選取了測試函數(shù)的適應(yīng)度值迭代收斂曲線來比較算法的收斂性能,鑒于篇幅限制,僅選擇列出單峰測試函數(shù)f4，f6，f7,多峰測試函數(shù)f8，f9，f14,將各函數(shù)維數(shù)設(shè)置為D=100,求解函數(shù)的收斂曲線如圖5所示。

對于單峰測試函數(shù)f4，f6，f7,由于函數(shù)簡單,因此比較容易達到最優(yōu)值。從50維變到100維時,由圖5(a)～圖5(c)可以看出,DSCA和對比算法均達到了特定精度,收斂精度上差異不大,但相比于其他比較算法,DSCA達到特定精度所需的迭代次數(shù)最少,在迭代早期就可以找到與其他比較算法相同精度的值。對于多峰測試函數(shù)f8、f9和f14,函數(shù)較復(fù)雜,從圖5(d)～圖5(f)可以看出,DSCA在函數(shù)f8上依然能收斂到最優(yōu),對于函數(shù)f9和f14,DSCA相較于其他比較算法,收斂精度明顯提高,表明了DSCA跳出局部最優(yōu)的能力強,收斂性能好。

圖5 DSCA不同測試函數(shù)優(yōu)化收斂曲線比較(D=100)Fig.5 Comparison of optimization convergence curves of different DSCA test functions (D=100)

3.2.2 算法在高維函數(shù)下收斂性分析

由以上低維實驗結(jié)果對比分析可知,DSCA在低維測試函數(shù)上無論在收斂精度還是收斂速度方面均得到了較好的效果。但是算法在高維函數(shù)下,收斂性往往會受到影響,為了分析算法在高維情況下的收斂性能,同樣選擇單峰測試函數(shù)f4，f6，f7和多峰測試函數(shù)f8，f9，f14進行比較。將函數(shù)維數(shù)設(shè)置為D=500,迭代次數(shù)及其他參數(shù)均不變,求解函數(shù)的收斂曲線如圖6所示。對于單峰測試函數(shù)f4，f6，f7,從圖6(a)～圖6(c)可以看出,由于維數(shù)的增加,導(dǎo)致其他比較算法達不到特定精度,而DSCA有較高的收斂精度,并且DSCA達到最優(yōu)值的迭代次數(shù)最少,說明收斂速度較快。對于多峰測試函數(shù)f8、f9和f14,從圖6(d)～圖6(f)可以看出,函數(shù)f8與100維時情況類似,DSCA在函數(shù)f8上依然能收斂到最優(yōu),對于函數(shù)f9和f14,收斂精度都有明顯差距,表明了DSCA在高維函數(shù)中跳出局部最優(yōu)的能力強,收斂性能好。由此可見,DSCA在高維函數(shù)下收斂性能仍比其他6種算法具有優(yōu)勢。

圖6 高維函數(shù)下DSCA收斂曲線比較(D=500)Fig.6 Comparison of DSCA convergence curves under high-dimensional functions (D=500)

綜上所述,DSCA在高維與低維的狀態(tài)下收斂性能均優(yōu)于其他比較算法,在某些函數(shù)上雖然收斂精度差距不明顯,但收斂速度遠高于其他比較算法,整體收斂性能達到最優(yōu)。

3.3 穩(wěn)定性分析

通過上述收斂性分析,可知DSCA具有較好的收斂性能,雖然算法在搜索空間內(nèi)收斂精度和速度越高越好,但算法的穩(wěn)定性也是算法性能的重要指標之一,穩(wěn)定性太差不利于算法的整體性能。因此,研究算法在搜索空間內(nèi)的穩(wěn)定性是十分必要的。為了分析算法在穩(wěn)定性方面的性能,對算法進行方差分析,同樣選取單峰測試函數(shù)f4，f6，f7和多峰測試函數(shù)f8，f9，f14在函數(shù)維數(shù)D=100的情況下運行30次的求解結(jié)果,其方差分析如圖7所示。

從測試函數(shù)的角度來看,方差越小表明算法的穩(wěn)定性越好;從工程應(yīng)用的角度來看,方差越小尋優(yōu)結(jié)果就越集中,尋優(yōu)系統(tǒng)的穩(wěn)定性就越好。對于單峰測試函數(shù)f4，f6，f7,從圖7(a)～圖7(c)可看出,SCA、PSO和BSA在100維函數(shù)下的穩(wěn)定性較差,這是由于原算法沒有經(jīng)過改善,雖然對于50維函數(shù)具有較好的穩(wěn)定性,但當(dāng)維數(shù)達到100及以上后,穩(wěn)定性變差。對于多峰測試函數(shù)f8，f9，f14,從圖7(e)和圖7(f)可看出,除DSCA之外,其他算法均有較大波動,表明了DSCA具有很強的穩(wěn)定性。

圖7 函數(shù)方差圖(D=100)Fig.7 Variance graph of different function(D=100)

因此,在DSCA可以達到收斂精度較高的情況下,穩(wěn)定性也比其他6種比較算法更具有優(yōu)勢。

4 結(jié) 論

本文提出的DSCA采用了拉丁超立方初始化、動態(tài)分級以及精英引導(dǎo)等策略對標準SCA進行改進，以解決SCA存在的易陷入局部最優(yōu)、求解精度不高和收斂速度較慢等問題。通過對15個標準測試函數(shù)進行實驗仿真，表明DSCA改善了SCA存在的缺陷，在收斂性方面，無論是在低維函數(shù)或是高維函數(shù)，DSCA相比于PSO、BSA及其他改進的SCA均具有更好的收斂精度和收斂速度，在穩(wěn)定性方面，DSCA相比于其他對比算法也有更好的表現(xiàn)。下一步的工作將針對多目標SCA的改進及工程應(yīng)用進行研究。