基于復(fù)雜網(wǎng)絡(luò)的差分進(jìn)化算法研究

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

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

0 引言

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

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

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

1 標(biāo)準(zhǔn)差分進(jìn)化算法

(1)

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

(2)

(3)

2 基于復(fù)雜網(wǎng)絡(luò)的差分進(jìn)化算法

根據(jù)達(dá)爾文進(jìn)化論：好的基因組更容易被傳播下來。個體能夠多次成功地產(chǎn)生后代，則認(rèn)為該個體具有較好的基因組。因此種群中目標(biāo)向量的選擇可以結(jié)合種群的基因組信息。而復(fù)雜網(wǎng)絡(luò)可視化了個體在種群中的關(guān)系，提供了個體的基因組信息，為進(jìn)化算法的研究提供了一個新的視角。

2.1 網(wǎng)絡(luò)的構(gòu)造

圖1 差分進(jìn)化算法第一代網(wǎng)絡(luò)Fig.1 The first generation network of differential evolution algorithm

假設(shè)第二代成功進(jìn)化的個體及其父代記錄如下x4:{x2,x3,x5}，x6:{x2,x3,x4}。根據(jù)記錄，更新第二代的網(wǎng)絡(luò)，如圖2所示，并更新鄰接矩陣A2:

圖2 差分進(jìn)化算法第二代網(wǎng)絡(luò)Fig.2 The second generation network of differential evolution algorithm

接下來的每一代都用相同的方法更新網(wǎng)絡(luò)。當(dāng)個體數(shù)目足夠多，進(jìn)化代數(shù)越來越大時，網(wǎng)絡(luò)結(jié)構(gòu)也將變得越來越復(fù)雜。

2.2 變異策略的改進(jìn)

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

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

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

(4)

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

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

(5)

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

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

2.3 選擇策略的改進(jìn)

如果使用標(biāo)準(zhǔn)差分進(jìn)化算法的選擇算子則第G+1代個體選擇如下：

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

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

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

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

Step 1：初始化，設(shè)定相關(guān)符號說明如下表1所示：

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

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

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

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

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

Step 5：根據(jù)式(2)生成試驗(yàn)向量，并計(jì)算試驗(yàn)向量的目標(biāo)函數(shù)值。

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

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

Step 9：判斷是否滿足終止條件，若不滿足轉(zhuǎn)Step3。

4 實(shí)驗(yàn)仿真與分析

為了測試基于復(fù)雜網(wǎng)絡(luò)的差分進(jìn)化算法(CNDE)的性能，用21個標(biāo)準(zhǔn)測試函數(shù)[17]進(jìn)行測試，算法由matlab軟件實(shí)現(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算法進(jìn)行對比，兩個算法分別獨(dú)立運(yùn)行50次，測試結(jié)果如表4所示。其中best表示50次獨(dú)立運(yùn)行的最好值；worst表示50次獨(dú)立運(yùn)行的最差值；Mean表示平均值，反映了算法的求解精確度；S.D表示標(biāo)準(zhǔn)差，反映了算法的穩(wěn)定性。

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

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

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

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

表5 與其他主流差分進(jìn)化算法結(jié)果對比Tab.5 Compared with other mainstream differential evolution algorithms

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

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

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

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

5 結(jié)語

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

進(jìn)一步的研究可嘗試將這種方法推廣到其它進(jìn)化算法上。另外對于網(wǎng)絡(luò)連邊上權(quán)值的選取可以考慮通過適應(yīng)度值來確定。除此之外，還可以研究上述所構(gòu)建出的網(wǎng)絡(luò)性質(zhì)如小世界性、無標(biāo)度性或者不同算法之間所構(gòu)造的網(wǎng)絡(luò)的相似性、相關(guān)性等。