基于隨機鄰域策略和廣義反向學習的自適應差分進化算法

吳文海, 郭曉峰, 周思羽, 高 麗

(海軍航空大學青島校區航空儀電控制工程與指揮系, 山東 青島 266041)

0 引 言

差分進化(differential evolution, DE)算法是由Storn等[1]提出的一種基于“貪婪競爭”機制的智能算法,以結構簡單、性能優越、魯棒性強、易于實現等特點,吸引大量學者進行研究[2],被廣泛應用于各領域優化問題[3-5]。標準DE算法采用單一的變異策略和固定控制參數(變異因子F、交叉因子CR、種群數量NP),無法隨進化過程動態調整,導致算法在處理高維、多峰優化問題時容易陷入局部最優,造成算法早熟。因此,如何恰當地平衡DE算法全局探索和局部開發能力,合理地對DE算法控制參數進行整定,成為制約DE算法尋優性能的關鍵問題[6]。

Das等[7]對近幾年DE的研究進行了回顧,主要從同時考慮策略選擇以及變異因子F和交叉因子CR的自適應性、僅考慮變異因子F和交叉因子CR的自適應性、僅考慮種群數量NP的自適應性等3方面系統性地總結和梳理了DE最新發展情況。

在變異策略研究方面,基于鄰域的變異策略被廣泛采用以平衡全局探索和局部開發能力,通過限制個體間相互作用范圍,有效地調整算法搜索能力,減少搜索重疊[8]。Das等[9]提出了一種基于環形拓撲鄰域的DE算法,將標準變異策略和基于局部鄰域改進的變異策略結合,通過權重系數ω∈(0,1)調整兩者比例,動態平衡全局搜索和局部搜索能力。Cai等[10]將自適應選擇機制引入基于鄰域的DE算法中,使其能夠自適應地從含有3種方向信息的備選池中生成變異策略。Cai等[11]提出一種基于指數鄰域的DE算法,引入二級鄰域排序算子,通過評價鄰域內個體適應值獲得潛在搜索方向,引導變異策略。Liao等[12]提出一種基于細胞拓撲鄰域的DE算法,將鄰域方向信息加入到變異操作中,根據適應值將鄰域中個體分為優、劣兩組,從兩組中分別隨機選取一個個體來構造差向量。Pham等[13]引入最近鄰域比較機制,通過搜索總體中最近的個體來預先判斷解決方案是否值得評價,從而避免不必要的評價。

在參數整定技術研究方面,由于不同優化問題的特點各不相同,僅憑經驗無法確定最合適的控制參數,傳統固定控制參數的尋優方法效率低下,嚴重制約DE算法的性能,而隨進化過程動態更新控制參數的自適應技術展現出巨大的優勢。AI-Dabbagh等[14]將自適應參數整定技術劃分為:基于確定性機制、基于漸進控制、基于進程學習3類。Draa等[15]提出了2種改進正弦函數公式,周期性地控制F和CR的增減,提高了算法的靈活性。Venkatakrishnan等[16]采用基于適應值的自適應技術,根據每代進化中最大、最小適應值的比值更新變異因子F,以提高算法在進化初期的多樣性,加強算法在進化后期的搜索能力。Zhang等[17]提出了一種基于高斯-柯西分布的DE算法,通過N(0.5,0.15)的高斯分布和C(0.5,0.3)的柯西分布為每一個體生成變異因子F和交叉因子CR,若子代在選擇操作中存活,則保留原參數,否則重新生成。Stanovov等[18]采用C(MF,0.1)的柯西分布和N(MCR,0.1)的高斯分布為每一個體生成變異因子F和交叉因子CR,通過權重萊默均值更新MF和MCR。Lu等[19]提出一種基于對個體差異和種群多樣性的定量分析的自適應參數整定方法,當個體差異ω≥0且種群多樣性指標σ小于預設值時,根據更新方程重新計算變異因子F和交叉因子CR。

在上述基于鄰域的變異策略研究中,個體的鄰域在進化過程中保持不變,鄰域內個體數量固定,由于靜態鄰域拓撲信息交換速度較慢,從而限制了算法的搜索能力,減緩算法的收斂速度,甚至容易使算法陷入局部最優,導致算法早熟。針對該問題,本文提出一種基于隨機鄰域策略和廣義反向學習(generalized opposition-based learning, GOBL)的自適應差分進化(簡稱為GOBL-RNADE)算法實現對單目標優化問題進行求解。每一代進化過程中,GOBL-RNADE算法為每一個體生成隨機鄰域,鄰域中的個體數量隨進化過程動態更新,鄰域中最優個體作為基向量執行“DE/neighbor/1”操作;根據文獻[18],建立歷史存檔存儲進化過程中“精英”個體信息,通過存檔中數據動態更新控制參數;引入GOBL機制執行種群初始化和種群“代跳”操作,提高算法尋得最優解幾率,避免算法陷入局部最優。

1 GOBL-RNADE算法

1.1 標準DE算法

DE是一種基于“貪婪競爭”以實現種群進化的智能算法,主要包括變異、交叉和選擇等操作。

(1) DE/rand/1:

(1)

(2) DE/best/1:

(2)

(3)

式中:下標j表示個體第j維;jrand為控制參數;交叉因子CR∈(0,1)。

(4)

1.2 隨機鄰域變異策略

本文提出一種基于隨機鄰域的變異策略“DE/neighbor/1”,在每一代進化過程中,算法為每一個個體從當前種群中隨機選擇N個個體組成鄰域,鄰域中的最優個體作為基向量,從鄰域內剩余個體中隨機挑選2個個體組成差分向量,“DE/neighbor/1”具體可表示為

(5)

式中:Xnbest為鄰域內最優個體;Xr1,Xr2為從鄰域內剩余個體中隨機挑選的個體。

(6)

通過自適應策略,種群中較優個體的鄰域中含有較少的鄰域個體,從而引導算法趨于探索能力,而較差的鄰域中含有較多的鄰域個體,從而引導算法趨于開發能力。“DE/neighbor/1”充分利用種群中“隨機”信息和鄰域內“最優”信息,合理地平衡了算法全局探索和局部開發能力,加速了信息交換速度,增加了種群多樣性,在避免算法陷入局部最優的同時,提高算法尋優速度,而且該策略并未引進其他參數,并未增加算法復雜度。

1.3 自適應參數策略

(7)

(8)

(10)

式中:meanWL(·)為權重萊默均值,可表示為

(11)

(12)

本文采用權重萊默均值對MF,k和MCR,k進行更新,不同于傳統的更新策略,本文所采用方法對“精英”存檔值賦予不同的權重,權重根據父代個體和實驗個體的差異進行計算,充分考慮了“精英”信息對MF,k和MCR,k的影響,提高“精英”信息對參數更新的作用。本策略充分利用“精英”信息保證控制參數最優性,同時采用柯西分布和正態分布提高隨機性,保證種群多樣性。

1.4 GBOL策略

GBOL[21]的定義如下:

(13)

(14)

本文應用GOBL執行種群初始化及代跳操作[23]。GOBL種群初始化如算法1所示。

算法1 GOBL種群初始化隨機初始化種群P0={X01,X02,…,X0NP};for i=1 to NP do for j=1 to D do X⌒0i,j=k(aj+bj)-X0i,j; if X⌒0i,jbj then X⌒0i,j=rand (aj,bj); end if end for end for廣義反向學習種群GOP0={X⌒01,X⌒02,…,X⌒0NP};從{P0,GOP0}中選擇NP個最優個體作為初始化種群P0

GOBL種群“代跳”操作如算法2所示。其中Jr為預設代跳率。

算法2 GOBL種群“代跳”if rand(0,1)max(XGj) then X⌒Gi,j=rand (min(XGj),max(XGj)); end if end for end forend if廣義反向學習種群GOPG={XG1,XG2,…,XGNP};從{PG,GOPG}中選擇NP個最優個體作為新種群PG

1.5 GOBL-RNADE收斂性分析

引理1設解空間S,Ψ:Ω×S→S是DE生成的隨機壓縮算子,則Ψ存在唯一的隨機不動點,從而DE漸進收斂[24]。

由引理1可知DE漸進收斂,GOBL-RNADE是基于DE的基礎上改進了隨機鄰域變異策略和GOBL策略,根據DE漸進收斂性可證隨機鄰域變異策略和GOBL策略所產生的個體也漸進收斂到一個最優解。

定理1DE漸進收斂,則GOBL-RNADE也漸進收斂。

(15)

(16)

同時,搜索空間的邊界滿足:

(17)

(18)

證畢

1.6 GOBL-RNADE復雜度分析

1.7 GOBL-RNADE流程框架

GOBL-RNADE的偽代碼如算法3所示。

算法3 GOBL-RNADE偽代碼 設置k=1,MF和MCR中所有元素為0.5;執行GOBL種群初始化;while 終止條件未達到 do 重置SF=?,SCR=?; for i=1 to NP do 根據式(7)和式(8)生成FGi和CRGi; 根據式(6)計算鄰域個體數量NGi; 為第i個體隨機選擇NGi個鄰域個體,選擇最優個體為Xnbest; 根據式(5)執行“DE/neighbor/1”生成變異個體VGi; 根據式(3)執行交叉操作生成實驗個體UGi; if f(UGi)H; end if 執行GOBL種群“代跳”;end while

GOBL-RNADE的基本流程如圖1所示。

圖1 GOBL-RNADE流程圖Fig.1 Process of GOBL-RNADE

2 數值實驗與分析

為了驗證GOBL-RNADE的尋優性能,選取27個標準測試函數進行實驗,如表1所示。其中f1～f7為單峰函數,f8～f13為多峰函數[26],f14～f18為偏移單峰函數,f19～f27為偏移多峰函數[27]。實驗中所有算法對每一測試函數獨立運行30遍,最大函數評價次數設置為10 000×D,采用置信度為5%的威爾科克森秩和檢驗評估GOBL-RNADE與其他算法之間顯著性差異,威爾科克森秩和檢驗是一種非參數檢驗,在不依賴總體分布形式的條件下,判斷實驗數據所在總體的分布位置是否存在顯著性差異。其中,“+/≈/-”分別表示GOBL-RNADE優于/近似/劣于所對比算法。

表1 標準測試函數

2.1 GOBL-RNADE與標準DE比較分析

根據前文所述,N取較大值時,“DE/neighbor/1”趨向于“DE/best/1”策略;N取較小值時,“DE/neighbor/1”趨向于“DE/rand/1”策略,因此本節選取“DE/best/1”和“DE/rand/1”2種經典DE作為比較對象,驗證GOBL-RNADE性能。實驗分別在D=30和D=50的情況下進行比較,根據文獻[28],設置標準DE的控制參數為:種群數量N=100,變異因子F=0.5,交叉因子CR=0.9。實驗結果(平均值±標準差)如表2和表3所示,其中黑體表示最優值。從實驗結果中可以看出,GOBL-RNADE在D=30和D=50的情況下均取得最好尋優效果,尋優精度高,穩定性強。當D=30時,GOBL-RNADE在27個測試函數中獲得21個最優值,分別有21個測試函數優于DE/rand/1,22個測試函數優于DE/best/1,僅有2個測試函數劣于對比算法。當D=50時,GOBL-RNADE在27個測試函數中同樣獲得21個最優值,分別有18個測試函數優于DE/rand/1,25個測試函數優于DE/best/1,分別僅在5個和1個函數測試中劣于對比算法,說明GOBL-RNADE在高維變量情況下仍能保持較好的尋優性能。

表2 GOBL-RNADE與標準DE實驗結果(D=30)

表3 GOBL-RNADE與標準DE實驗結果(D=50)

續表3

2.2 GOBL-RNADE與經典DE比較分析

將GOBL-RNADE與JADE[29]、SaDE[30]、MGSDE[31]以及DADDE[32]進行對比。

各算法參數設置與原文獻一致,取D=30。各算法實驗結果(平均值±標準差)如表4和表5所示,其中黑體表示最優值。

表4 GOBL-RNADE與經典DE實驗結果(1)

續表4

表5 GOBL-RNADE與經典DE實驗結果(2)

根據實驗結果可知,GOBL-RNADE在測試中尋優效果最好,27個測試函數中有18個函數獲得最優值。根據威爾科克森秩和檢驗評估結果表明,GOBL-RNADE分別在16個、17個、22個、21個測試函數中優于JADE、SaDE、MGSDE以及DADDE;在4個、7個、5個、4個測試函數中獲得與4種算法近似的結果;僅在7個、3個、0個、2個測試函數中差于JADE、SaDE、MGSDE以及DADDE。相較于其余4種算法,GOBL-RNADE有更好的尋優精度及尋優穩定性。

對于單峰函數f1～f7,GOBL-RNADE除函數f7外均尋得最優解0,函數f7GOBL-RNADE僅劣于DADDE,且兩種算法的最優解誤差在同一數量級。單峰函數優化問題中,種群中的“精英”信息能夠高效引導算法尋得最優解,根據“精英”信息,GOBL-RNADE變異策略趨向開發能力,算法參數也根據“精英”信息動態整定,從而使得GOBL-RNADE在處理單峰函數優化問題時具有明顯的優勢;對于多峰函數f8～f13,GOBL-RNADE尋優性能遠優于MGBDE和DADDE,與SaDE尋優性能相當,GOBL-RNADE對于f9～f11均收斂到最優解0,函數f12和f13的最優解誤差也與SaDE在同一量級。多峰函數優化問題中,由于函數存在多個局部最優解,因此如何避免算法陷入局部最優導致算法早熟是關鍵問題,GOBL-RNADE采取GOBL種群“代跳”操作,基于代跳率Jr隨機在某代進化結束后執行GOBL,從而提高了種群的多樣性,避免算法陷入局部最優導致算法早熟,因而GOBL-RNADE在處理多峰函數優化問題時具有一定的優勢;對于偏移單峰函數f14～f18,GOBL-RNADE在f14收斂到最優解,在5個偏移單峰函數測試中獲得4組最優結果,對于函數f17標準測試集在介紹時描述到“如果初始化過程在邊界處填充,則問題將很容易解決”,本文采用GOBL執行種群初始化,根據式(13)可知,在參數k的作用下初始化種群將遠離邊界,因而導致GOBL-RNADE在函數f17測試中結果并不理想;對于偏移多峰函數f19～f27,GOBL-RNADE在9組測試中分別在f21、f24、f25、f26獲得最優結果,f20和f27的最優解誤差與最優算法在同一量級,尋優效果近似,因此整體來說GOBL-RNADE在處理多峰函數優化問題時具有一定的優勢。

進一步比較GOBL-RNADE與各算法在30次仿真實驗中各測試函數的計算用時,其結果如表6所示,可以看出GOBL-RNADE計算用時遠小于其余算法。

表6 GOBL-RNADE與經典DE計算用時

圖2給出GOBL-RNADE,JADE,SaDE,MGSDE以及DADDE在9個代表測試函數中的收斂曲線,其中縱坐標為與全局最優解的誤差值。可看出GOBL-RNADE的收斂曲線明顯快于其余算法,f9和f10在較短時間內收斂到最優解0,說明GOBL-RNADE尋優速度更快。

圖2 GOBL-RNADE與經典DE收斂曲線Fig.2 Convergence curves of GOBL-RNADE and classic DE

為進一步比較GOBL-RNADE與其余4種算法的性能,本文采用弗里德曼檢驗計算平均排序值,弗里德曼檢驗是多個樣本齊一性的統計檢驗,所考查的樣本中的每組都具有一致的樣本數量,各樣本間相應個體存在對應關系。

對k個樣本量為n的樣本進行排序,獲得k個樣本的秩和為

(19)

則檢驗值可表示為

(20)

(21)

則拒絕檢驗的原假設。

5種算法基于27個測試函數的平均排序值如表5所示,黑體為最優值。從表7中可以看出GOBL-RNADE取得最優排序值,且明顯優于其余算法,說明GOBL-RNADE具有更好的尋優性能。

表7 5種DE算法弗里德曼檢驗平均排序值

2.3 GOBL-RNADE各策略分析

如前文所述,GOBL-RNADE包含3種改進策略:隨機鄰域變異策略、基于歷史進化信息自適應參數策略和GOBL策略。為了研究各策略對DE性能的影響,本文將3種改進策略進行不同組合形成6種DE變體,分別表示為ADE僅包含自適應參數策略,RNDE僅包含隨機鄰域變異策略,GOBL-DE僅包含GOBL策略,GOBL-ADE同時包含自適應參數策略和GOBL策略,GOBL-RNDE同時包含隨機鄰域變異策略和GOBL策略和RNADE同時包含隨機鄰域變異策略和自適應參數策略。通過與6種DE變體與GOBL-RNADE進行對比,驗證3種改進策略對DE性能的改進。

實驗中選取DE/rand/1作為ADE、GOBL-ADE和GOBL-ADE的變異策略,RNDE、GOBL-DE和GOBL-RNDE的變異因子F=0.5,交叉因子CR=0.9,取D=30。實驗結果(平均值±標準差)如表8和表9所示,其中黑體表示最優值。

表8 GOBL-RNADE與各策略實驗結果

表9 GOBL-RNADE與各策略實驗結果

從實驗結果可以看出,GOBL-RNADE在21個測試函數中取得最優值,具有最好的尋優性能,尋優精度高,可靠性及魯棒性強。根據威爾科克森秩和檢驗評估結果表明,GOBL-RNADE分別在25個、19個、25個、17個、17個、19個測試函數中優于ADE、RNDE、GOBL-DE、GOBL-ADE、GOBL-RNDE和RNADE。

采用單一改進策略的3種算法尋優性能明顯較差,分別僅有1個、1個、2個測試函數優于GOBL-RNADE,僅RNDE在7個測試函數中取得近似結果。采用2種改進策略的DE變體實驗結果要優于采用單一改進策略的DE變體,但仍遠劣于GOBL-RNADE,分別僅有1個、1個、0個測試函數優于GOBL-RNADE。

續表9

為進一步比較各策略對DE性能的改進效果,采用弗里德曼檢驗計算GOBL-RNADE和6種DE變體的平均排序值,結果如表10所示,黑體為最優值。從表10中可看出GOBL-RNADE取得最優排序值,且明顯優于其余算法。

表10 7種DE算法弗里德曼檢驗平均排序值

表11給出了6種DE變體與GOBL-RNADE尋優結果基于校正p值的多重檢驗結果。根據表11結果可知,在α=0.05情況下,6種DE變體尋優結果均與GOBL-RNADE存在顯著性差異,表明GOBL-RNADE性能明顯優于其余6種算法。

表11 基于校正p值的多重檢驗結果(1)

表12為3種改進策略不同情況下基于校正p值的多重檢驗結果,其中1組、2組針對有無隨機鄰域變異策略;3組、4組針對有無自適應參數策略;5組、6組針對有GOBL策略。

對比ADE和RNADE,RNADE獲得8組與GOBL-RNADE相當的測試結果,而ADE僅獲得1組;其次,RNADE在f6、f20、f22均獲得最優結果,其中在f6收斂到最優解0,而ADE僅在f21獲得最優結果;在全部27組測試中,RNADE僅在f3、f15、f16、f21劣于ADE。對比GOBL-DE和GOBL-RNDE,GOBL-RNDE獲得9組與GOBL-RNADE相當的測試結果,1組優于GOBL-RNADE的測試結果,而GOBL-DE僅獲得2組優于GOBL-RNADE的測試結果;其次,GOBL-RNADE在f6、f9、f18均獲得最優結果,其中在f6、f9收斂到最優解0;在全部27組測試中,GOBL-RNAD僅在f7、f16、f21、f24、f27劣于ADE。根據表12結果可知,在α=0.05的情況下,ADE和RNADE、GOBL-DE和GOBL-RND均存在顯著性差異,通過以上對比分析可以得出隨機鄰域變異策略能夠明顯提高DE的尋優性能。

表12 基于校正p值的多重檢驗結果(2)

對比RNDE和RNADE,RNADE在27組測試中有17組測試結果優于RNDE。對比GOBL-DE和GOBL-ADE,GOBL-ADE僅在f7和f27劣于GOBL-DE,其余結果均優于GOBL-DE,根據表12結果可知,在α=0.05情況下,GOBL-DE和GOBL-ADE存在顯著性差異,通過以上對比分析可以得出自適應參數策略對DE尋優精度起到改善作用。

對比RNDE和GOBL-RNDE,GOBL-RNDE在27組測試中有18組測試結果優于RNDE,對比ADE和GOBL-ADE,GOBL-ADE在27組測試中有20組測試結果優于ADE;其次,通過分析圖3可以得出,廣義反向學習策略能夠有效提高種群多樣性,幫助算法及時跳出局部極值,避免算法早熟。基于上述不同策略條件下DE與GOBL-RNADE性能分析可以得出,本文所采用的3種改進策略對算法尋優精度、尋優速度及尋優穩定性等性能具有較好改進。

此外,圖3給出了GOBL-RNADE和其余6種DE變體在9個代表測試函數中的收斂曲線。從圖3中可以看出,GOBL-RNADE的收斂曲線快于其余算法,具有更快的尋優速度。

圖3 GOBL-RNADE與不同策略收斂曲線Fig.3 Convergence curves of GOBL-RNADE and different strategies

3 結 論

本文提出了一種基于隨機鄰域策略和GOBL的自適應差分進化算法,本算法提出一種基于隨機鄰域的變異策略,進化過程中,通過動態更新鄰域信息以平衡算法全局探索和局部開發能力,采用基于歷史存檔的自適應參數策略,充分利用進化過程中的“精英”信息,自適應調節控制參數,提高了算法的尋優精度和速度。引入GOBL策略,提高種群多樣性,避免算法陷入局部最優,導致算法早熟。通過基于27個標準測試函數的3組不同仿真實驗分析表明,GOBL-RNADE具有很好的尋優性能,尋優精度高,收斂速度快,可靠性魯棒性強,明顯優于其他對比算法。