丁 毓，劉三陽，陳靜靜，白藝光

(西安電子科技大學數(shù)學與統(tǒng)計學院,西安 710126)

0 引言

差分進化算法(Differential Evolution,DE)是一種簡單且有效的啟發(fā)式方法，用于求解連續(xù)空間問題的全局最優(yōu)解。該算法是R.Storn和K.Price[1-2]于1995年，為求Chebyshev多項式而提出的，后來發(fā)現(xiàn)DE也是解決復雜優(yōu)化問題的有效工具。

進化算法在科研和實際問題中的應用十分廣泛，研究人員提出多種不同的進化方法，其中包括群智能進化方法研究與應用[6-8]，隨著對進化算法的研究，進化算法與復雜網絡[9-10]的聯(lián)系逐漸被挖掘，既可用進化算法解決網絡中的問題，也可將網絡作為設計進化算法的工具。如Ashlock[11]等人在1999年提出了采用組合圖來限制雜交對象選擇的遺傳算法；Mabu[12]等人在2007年提出了基于圖的進化算法和基于圖的強化學習算法；Zelinka[13-14]等在2010和2011年提出可視化進化算法的動力學模型；2017年Skanderova等[15]提出利用復雜網絡對進化算法進行動力學分析。

2017年，Benjamin等[16]發(fā)表的文章說明種群結構會影響種群最終的進化結果，受Skanderova[15]啟發(fā)，采用將算法中的種群結構記錄為復雜網絡的方法，用網絡所含信息指導種群進化，提出基于復雜網絡的差分進化算法(Differential Evolution Algorithm Based on Complex Networks，CNDE)。該算法將差分進化算法中的種群對應網絡，給種群中的個體匹配網絡中的節(jié)點，用邊來表示個體之間的關系。利用網絡的信息，得出個體基因組好壞的相關參數(shù)信息。接著，利用目標函數(shù)值和個體基因組信息共同決定個體被選擇為突變算子中目標向量的概率。在計算概率時,為了保證算法的穩(wěn)定性，提升收斂速度，引入收斂因子α。在選擇階段，針對差分進化算法中的交叉與變異機制，提出新的基于排序的選擇模式，從而優(yōu)化子代的種群結構。

1 標準差分進化算法

(1)

其中,指標r1,r2,r3∈{1,2,…,NP}，且r1,r2,r3,t全不相同。尺度因子F是一個正的實常數(shù)，一般F∈[0,2]。

(2)

(3)

2 基于復雜網絡的差分進化算法

根據達爾文進化論：好的基因組更容易被傳播下來。個體能夠多次成功地產生后代，則認為該個體具有較好的基因組。因此種群中目標向量的選擇可以結合種群的基因組信息。而復雜網絡可視化了個體在種群中的關系，提供了個體的基因組信息，為進化算法的研究提供了一個新的視角。

2.1 網絡的構造

圖1 差分進化算法第一代網絡Fig.1 The first generation network of differential evolution algorithm

假設第二代成功進化的個體及其父代記錄如下x4:{x2,x3,x5}，x6:{x2,x3,x4}。根據記錄，更新第二代的網絡，如圖2所示，并更新鄰接矩陣A2:

圖2 差分進化算法第二代網絡Fig.2 The second generation network of differential evolution algorithm

接下來的每一代都用相同的方法更新網絡。當個體數(shù)目足夠多，進化代數(shù)越來越大時，網絡結構也將變得越來越復雜。

2.2 變異策略的改進

1)賦權有向邊能夠獲取從一個節(jié)點到另一個節(jié)點的基因組的傳播信息。

2)節(jié)點的出邊加權和Wt，表示該節(jié)點成功作為父代的次數(shù)，次數(shù)越多表明基因組越好。

隨著每代鄰接矩陣AG建立，每個節(jié)點的出邊加權和便可求出。接著，根據式(4)計算出個體被選擇為目標向量的概率：

(4)

式(4)表明，具有較高出邊加權和的個體，在突變算子中被選為目標向量的可能性高。特別地，在式(4)中對每個個體的選擇概率都加α，這里α稱作收斂因子，其作用一是為了保證算法的穩(wěn)定性，便于控制收斂速度，二是為了消除選擇概率為零的情況，避免降低目標向量的多樣性。α通常取值為1，可根據不同的函數(shù)類型調整α的大小，一般情況下，對連續(xù)的單峰函數(shù)，將α取較小值，加速收斂；對于不可分的多峰函數(shù)，將α取較大值，增加種群的多樣性。通過實驗，發(fā)現(xiàn)α的取值對算法的穩(wěn)定性有較大的影響，且不同的函數(shù)對α的要求也不同。本文收斂因子α的取值是通過實驗測試選取，日后可研究對不同類型的函數(shù)自適應設置α的取值。

式(4)只考慮了基因組好的個體在突變算子中被選擇作為目標向量的可能性較高。但是，除此之外本文還應考慮目標函數(shù)值好的個體，因為目標函數(shù)值好，不一定成功進化的次數(shù)多。因此更新個體被選為目標向量的概率為

(5)

其中，pbest表示目標函數(shù)值最好的個體在突變算子中被選為目標向量的概率。

推薦理由:本書是華爾街投資大神、對沖基金公司橋水創(chuàng)始人瑞·達利歐的人生經驗之作，是他白手起家40多年以來的生活和工作原則。書中提到了21條高原則、139條中原則、365條分原則，多角度、立體闡述了生活、工作、管理原則。在中國金融圈、投資界和管理層都極具影響力，在中國大陸銷量達一百萬冊，適合多層次、多領域的讀者閱讀。

2.3 選擇策略的改進

如果使用標準差分進化算法的選擇算子則第G+1代個體選擇如下：

而如果使用基于目標函數(shù)值排序的選擇策略，那么第G+1代個體選擇如下：

由假設條件可知f(x1)≥f(x2)≥f(x3)≥f(x4)≥f(x5)≥f(x6)，且滿足條件f(u4)

3 算法實現(xiàn)流程

基于復雜網絡的差分進化算法的基本思路是：首先隨機初始化種群、網絡，對于第一代個體，其變異算子采用標準差分進化算法的方法。對于第二代及以后個體則利用網絡的性質計算基因組好壞參數(shù)。在變異階段依概率選取目標向量，概率由個體的目標函數(shù)值大小基因組信息計算得出。選擇階段采用基于目標函數(shù)值排序的策略。其具體實現(xiàn)步驟如下：

Step 1：初始化，設定相關符號說明如下表1所示：

表1 算法符號說明Tab.1 Algorithm symbol description

此外，用Tab表示個體成功進化標記，初始化Tab=zeros(1,NP)，如果第t個個體成功進化，記Tab的第t個分量為1，否則記為0。

Step 2：在可行域中隨機生成NP個D維個體，計算對應目標函數(shù)值。

Step 3：對Tab進行更新，Tab=zeros(1,NP)；對目標函數(shù)值從大到小排序；對目標函數(shù)值最小的個體，根據式5)計算概率。

Step 4：變異操作，如果∑Wt=0則按標準差分進化算法執(zhí)行變異算子，否則根據計算出來的概率依概率選擇目標向量。并將個體對應的父代記錄在集合S中。

Step 5：根據式(2)生成試驗向量，并計算試驗向量的目標函數(shù)值。

Step 7：求出Tab等于1的個數(shù)k，將這k個試驗向量替換目標函數(shù)值最大的k個目標向量。

Step 8：根據S矩陣計算鄰接矩陣A，由式(4)和(5)利用目標函數(shù)值大小和基因組信息計算每個節(jié)點的選擇概率pt。

Step 9：判斷是否滿足終止條件，若不滿足轉Step3。

4 實驗仿真與分析

為了測試基于復雜網絡的差分進化算法(CNDE)的性能，用21個標準測試函數(shù)[17]進行測試，算法由matlab軟件實現(xiàn)。表2給出了測試函數(shù)的名稱、維數(shù)、搜索空間和理論最優(yōu)值。其中：f1～f13為高維問題，f1～f7為單峰函數(shù)，f8～f13為多峰函數(shù)，f14～f21為低維函數(shù)。

表2 測試函數(shù)的名稱、維數(shù)、搜索空間和最優(yōu)值Tab.2 The name, dimension, search space, and optimal value of the test functions

續(xù)表2

函數(shù)名稱維數(shù)搜索空間最優(yōu)值函數(shù)名稱維數(shù)搜索空間最優(yōu)值f6Step30[-100,100]0f17Branin2[-5,10],[0,15]0.398f7Quartic30[-1.28,1.28]0f18Goldstein2[-2,2]3f8Schwefel 2.2630[-500,500]-12 569.5f19Shekel 14[0,10]-10.153 2f9Rastrigin30[-0.512,5.12]0f20Shekel 24[0,10]-10.402 9f10Ackley30[-32,32]0f21Shekel 34[0,10]-10.534 0f11Griewank30[-600,600]0

在本文測試中，各參數(shù)取值如下：種群規(guī)模NP=100；尺度因子F=0.6；雜交概率CR=0.9；對于不同函數(shù)，收斂因子α和最大迭代次數(shù)G的取值見表3。

表3 部分參數(shù)取值表Tab.3 Parameter value table

因本文是受啟于lenka skanderova在2017年[13]提出的enhanced DE算法，故將本文算法與enhanced DE算法進行對比，兩個算法分別獨立運行50次，測試結果如表4所示。其中best表示50次獨立運行的最好值；worst表示50次獨立運行的最差值；Mean表示平均值，反映了算法的求解精確度；S.D表示標準差，反映了算法的穩(wěn)定性。

表4 Enhanced DE與CNDE對21個函數(shù)的測試結果比較Tab.4 Enhanced DE compared with CNDE test results for 21 functions

續(xù)表4

函數(shù)算法BestWorstMeanS.Df10Enhanced DE2.920×10-063.872×10-048.573×10-051.930×10-04CNDE8.033×10-113.096×10-074.938×10-086.203×10-08f11Enhanced DE7.772×10-152.396×10-021.074×10-033.520×10-03CNDE01.478×10-022.563×10-044.340×10-03f12Enhanced DE1.879×10-112.388×10-061.366×10-084.351×10-09CNDE1.826×10-162.115×10-102.532×10-125.108×10-11f13Enhanced DE1.347×10-108.932×10-021.327×10-022.498×10-02CNDE3.549×10-212.972×10-141.495×10-155.686×10-15f14Enhanced DE0.998 003 82.982 105 11.057 566 42.459CNDE0.998 003 80.998 003 80.998 003 83.155×10-15f15Enhanced DE3.839×10-042.336×10-033.074×10-045.159×10-04CNDE1.006×10-051.233×10-041.582×10-054.995×10-04f16Enhanced DE-1.031 6-1.031 6-1.031 65.275×10-03CNDE-1.031 6-1.031 6-1.031 64.586×10-16f17Enhanced DE0.3980.3980.3982.413×10-03CNDE0.3980.3980.3985.832×10-16f18Enhanced DE3332.902×10-15CNDE3331.636×10-15f19Enhanced DE-10.153 2-1.268 3-9.902 72.806CNDE-10.153 2-10.153 2-10.153 24.502×10-08f20Enhanced DE-10.402 9-2.375 0-9.875 22.032CNDE-10.402 9-10.402 9-10.402 97.870×10-09f21Enhanced DE-10.536 4-2.146 5-9.575 02.157CNDE-10.536 4-10.536 4-10.536 46.961×10-09

由表4中的數(shù)據可知，CNDE算法在大多數(shù)測試函數(shù)中表現(xiàn)優(yōu)異。就單峰函數(shù)來講，函數(shù)f1、f2和f3精度提高了近一倍，f4和f5也極大地提高了其精度，函數(shù)f6可以達到最優(yōu)值0，噪聲函數(shù)f7的結果與Enhanced DE算法結果相近。就多峰函數(shù)f8-f13來講，函數(shù)精度基本都有提升或至少能夠等于Enhanced DE算法結果。就低維函數(shù)f14-f21來講，除函數(shù)f15外基本所有函數(shù)都能達到最優(yōu)值，且穩(wěn)定性較好。

為了更為直觀地對比算法的收斂速度，以函數(shù)f1為例，繪制出用CNDE算法和Enhanced DE算法所求得的函數(shù)收斂圖像，如圖3所示。

圖3 函數(shù)收斂圖像Fig.3 Convergence curves

另外，將本文算法與其它主流差分進化算法：DE/rand/1/bin、jDE、CODE、Enhanced DE進行對比。DE/rand/1/bin為標準差分進化算法，較其他進化算法原理簡單，受控參數(shù)少，具有記憶個體最優(yōu)解和種群內信息共享的特點；jDE為自適應參數(shù)差分進化算法，其具有參數(shù)自適應的特點，而非根據經驗取值；CODE為組合差分進化算法，該方法使用3個試向量生成策略和三個控制參數(shù)設置，隨機地組合它們來生成試驗向量，具有較好的收斂性；Enhanced DE則是最新的在動力學的基礎上研究差分進化算法，本文也是在此基礎上提出的改進。每個算法對21個測試函數(shù)分別獨立運行50次，結果均值如表5所示。

表5 與其他主流差分進化算法結果對比Tab.5 Compared with other mainstream differential evolution algorithms

表5中可以看出，CNDE算法相對標準DE算法表現(xiàn)十分優(yōu)秀，但對比于其他主流差分進化算法卻沒有十分突出。其實可以考慮將本文所述方法應用到其他主流差分進化算法中。以jDE為例，在保留其原有步驟的基礎上，改變變異算子，以本文所述方法構建網絡，計算概率，選擇目標向量，并執(zhí)行基于目標函數(shù)值排序的選擇策略。進而提出基于復雜網絡的自適應參數(shù)差分進化算法(CN-jDE)。其中參數(shù)設計為τ1=τ2=0.1，F(xiàn)l=0.1，F(xiàn)u=0.9，其余參數(shù)保持不變。在此分別挑選兩個單峰，多峰，低維函數(shù)進行測試，結果如表6所示。

由表6中數(shù)據可以看出，CN-jDE算法在穩(wěn)定性和求解精度上較jDE算法均表現(xiàn)優(yōu)異。為更直觀地對比算法的收斂速度，以函數(shù)為例，繪制出利用算法CN-jDE和算法jDE所求得的函數(shù)收斂圖像，如圖4所示。

表6 jDE與CN-jDE測試結果比較均值(方差)Tab.6 jDE and CN-jDE test results are compared

圖4 函數(shù)收斂圖像Fig.4 Convergence curves

5 結語

基于網絡研究差分進化算法為進化算法的改進提供了新的思路。本文在網絡的基礎上分析了差分進化算法。該方法將種群中的個體映射成網絡中的節(jié)點，個體之間的基因信息傳播則用網絡中的連邊表示，這使得基因的傳播方向可視化。基因組好的個體以及目標函數(shù)值優(yōu)的個體會有較高的傳播概率。雖然對21個標準測試函數(shù)的仿真結果表明，對于大部分函數(shù)，該方法在收斂速度和計算精度上有一定的提高。但是在測試中，我們發(fā)現(xiàn)α的取值對算法的穩(wěn)定性影響較大，且不同的函數(shù)對α的要求也不同。后續(xù)需要在α的取值方面做深入的研究。

進一步的研究可嘗試將這種方法推廣到其它進化算法上。另外對于網絡連邊上權值的選取可以考慮通過適應度值來確定。除此之外，還可以研究上述所構建出的網絡性質如小世界性、無標度性或者不同算法之間所構造的網絡的相似性、相關性等。