基于動態分級策略的改進正余弦算法

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

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

0 引 言

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

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

1 SCA

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

(1)

(2)

(3)

式中,t是當前迭代次數;T是最大迭代次數;a是常量,通常取a=2。

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

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

步驟 1初始化種群,初始化參數r1、r2、r3和r4,并計算適應度函數值。

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

步驟 3計算適應度值,更新最優方案。

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

2 DSCA

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

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

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

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

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

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

步驟 1首先,確定種群維數D和種群規模N。

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

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

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

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

2.2 動態分級策略

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

(4)

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

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

圖2 動態分級策略示意圖Fig.2 Schematic diagram of dynamic classification strategy

2.2.1 破壞擾動算子

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

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

(5)

(6)

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

(7)

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

(8)

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

2.2.2 精英引導方式

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

(9)

2.3 全局搜索策略

通過全局搜索策略進行更新,將經動態分級策略擾動的種群合并,對整個種群應用全局搜索策略更新,具體構造如下：

(10)

(11)

將動態反向學習數引入到搜索策略中,既可以在迭代后期局部的上下限進行跳動以增強跳出局部最優的能力,又可以加快收斂速度,根據控制參數pr在全局搜索策略和動態分級策略之間轉換,全局策略為

(12)

2.4 DSCA的基本流程

DSCA基本流程如圖3所示。

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

3 數值仿真分析

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

表1 測試函數

3.1 復雜度分析

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

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

(13)

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

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

(14)

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

圖4 運行時間統計圖Fig.4 Running time statistics chart

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

3.2 收斂性分析

3.2.1 算法在低維函數下收斂性分析

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

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

續表2

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

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

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

3.2.2 算法在高維函數下收斂性分析

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

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

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

3.3 穩定性分析

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

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

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

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

4 結 論

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