分布模型和關(guān)聯(lián)模型的自適應(yīng)差分進化算法

周美玲，張勝敏，李 征

（1.開封大學(xué) 軟件學(xué)院，河南 開封475000；2.河南大學(xué) 計算機與信息工程學(xué)院，河南 開封475001）

0 引 言

差分進化算法的性能主要由縮放因子和交叉率兩個控制參數(shù)決定［1－4］。其中縮放因子用于調(diào)整搜索步長，交叉率則控制新個體相較于父代個體變化的強度［5，6］。傳統(tǒng)的差分進化算法依據(jù)問題本身的特性和調(diào)試經(jīng)驗來取值，但這種方法的效果有限，不適于復(fù)雜優(yōu)化問題［7－10］。為了使得參數(shù)取值更好適應(yīng)算法的性能，一些學(xué)者提出了各自的參數(shù)自適應(yīng)差分進化算法，其中最具代表性的算法有Brest等［11］設(shè)計的動態(tài)調(diào)整參數(shù)的jDE算法，以及Qin等［12］提出的自適應(yīng)調(diào)整參數(shù)和變異算子的SaDE 算法。雖然這些參數(shù)自適應(yīng)差分進化算法的種群中每一個新個體使用的縮放因子是動態(tài)變化的，但對于個體中的每一維則是不變的，由于各維變量的尋優(yōu)程度以及它們之間的關(guān)聯(lián)性往往不同，賦予其同等的搜索尺度顯然是不合適的；且已有算法中縮放因子和交叉率的變化總是獨立進行的，而差分進化的公式表明交叉率決定著新個體的哪些維變量受縮放因子的影響，因此二者必然是非獨立的。為此，提出了一種基于雙模型的自適應(yīng)差分進化算法 （double－model－based self－adaptive differential evolution，DMSaDE），分布模型是在自適應(yīng)差分進化算法SaDE 的基礎(chǔ)上，對每一維變量采用不同的縮放因子進行統(tǒng)計，對構(gòu)成的縮放因子矩陣進行主成分分析，在主元空間下進行估計和采樣；關(guān)聯(lián)模型是將交叉率劃分為不同的取值區(qū)間，不同的縮放因子向量對應(yīng)于不同的交叉率區(qū)間，認為交叉率和縮放因子之間的關(guān)系是非線性的，并通過學(xué)習(xí)機制和核支持矢量機建立。

1 相關(guān)描述

自適應(yīng)差分進化算法SaDE［12］對進化過程中參數(shù)取值和變異算子的選擇均進行了自適應(yīng)的調(diào)整。其相比于jDE算法［11］，所采用的參數(shù)取值規(guī)則對經(jīng)驗知識依賴更小，并且調(diào)整過程具有一定的學(xué)習(xí)能力。為此，采用和SaDE 算法類似的策略，在其基礎(chǔ)上來應(yīng)用所提出的兩個模型。

對于一個最小化優(yōu)化問題f（x），x＝ （x1，x2，…，xn），n為變量維數(shù)，x∈可行域S，SaDE 采用DE／rand／1、DE／rand－to－best／2、DE／rand／2 和DE／current－to－rand／1 這4種候選變異算子，它們具有不同的全局探索能力和局部搜索能力，SaDE在初始階段賦予它們同等的選中概率用于某一新個體的生成，然后一定代數(shù)LP內(nèi)不斷的進行統(tǒng)計，例如當(dāng)前為第t代，則統(tǒng)計t－1，t－2，…，t－LP代。統(tǒng)計內(nèi)容為各個策略所生成新個體優(yōu)于父代個體的數(shù)量以及差于父代個體的數(shù)量，再根據(jù)二者的比例調(diào)整各個變異算子的概率，如式 （1）所示

該算法假設(shè)合適的交叉率參數(shù)CR 和縮放因子F 取值均分別服從某一高斯分布模型，但二者模型的構(gòu)建方法有所不同。SaDE在周期LP內(nèi)采用與變異算子相同的標(biāo)準處理交叉率參數(shù)CR，即對于每一個變異算子記錄各自生成更優(yōu)個體時的CR 取值。然后計算各自的CR 序列的中間值，以該中間值作為高斯分布模型的均值，再賦予設(shè)定的方差取值。而對于縮放因子F，SaDE則只建立了一個針對所有變異算子的高斯分布模型，并且均值和方差的取值均是依據(jù)經(jīng)驗設(shè)定的。在這兩個高斯分布模型的基礎(chǔ)上，每個個體所需的參數(shù)取值均通過模型采用來完成。

2 雙模型自適應(yīng)差分進化算法的設(shè)計

設(shè)計的差分進化算法DMSaDE 采用DE／rand／1、DE／rand－to－best／1、DE／best／1這3種變異算子，如式 （2）～式 （4）所示，以及二元交叉算子，如式 （5）所示

其中，xi為父代個體，xb為當(dāng)前所得最優(yōu)個體，xr1、xr2、xr3為互不相同且不同于xi和xb，從當(dāng)前種群中隨機選擇的3個個體，j0為隨機選中的一維變量，用以保證子代個體不同于父代個體。

2.1 縮放因子分布模型的設(shè)計

DMSaDE與SaDE相比，將縮放因子也納入了自學(xué)習(xí)調(diào)整的范疇，并且針對不同變異算子建立了獨立的基于分布模型的學(xué)習(xí)策略。縮放因子分布模型的具體操作步驟如下：

（1）初始狀態(tài)下每一個體的每一維獨立的在區(qū)間［0.1，0.95］內(nèi)隨機生成縮放因子，構(gòu)成縮放因子向量，若生成的新個體優(yōu)于父代個體則記錄該向量。在LP代后第k個變異算子可以得到nk個縮放因子向量，i＝1，2，…，nk，用這些向量構(gòu)成一個n×nk維的矩陣Mk；

（2）計算矩陣Mk每一行的均值，得到均值向量，然后按照式 （6）計算協(xié)方差矩陣Ck

（3）求取Ck的特征值以及特征向量，，…，，并使得特征值≥≥…≥，再按照貢獻率大于85%的準則確定主元數(shù)量為p，即對應(yīng)前p 個特征值；

（4）將矩陣Mk中各個縮放因子向量按照式 （7）投影到前p 個主元方向上，并據(jù)此計算所有向量在各個主元上的上邊界和下邊界

（5）按照式 （8）確定一個n維超立方體Hk，即為對進化起促進作用的縮放因子向量所在的分布空間，再按照式（9）計算原始向量與投影向量之間的殘差Ek，該殘差用于修正噪聲環(huán)境下分布空間Hk的誤差。此后每隔g 代，利用最近的LP 代結(jié)果構(gòu)建矩陣Mk，并計算分布空間Hk和殘差Ek

其中，α為上下界的修正因子，設(shè)置為0.05。

當(dāng)變量維數(shù)n 過高時，若每一維均獨立考慮則所得矩陣過于龐大而難以計算。故在每次計算時，將n 維變量隨機的劃分為等長度的c 類，每一類對應(yīng)一個縮放因子元素，即得到c×nk維的矩陣Mk。這樣Fk的第i 個元素 （i＝1，2，…，c）即用于第i類中所有維變量使用。基于上述分布模型，新個體所用縮放因子的產(chǎn)生方法為：設(shè)當(dāng)前選中的是第k個變異算子，在分布空間Hk所限定范圍內(nèi)通過均勻隨機采樣得到向量Yk，再將殘差Ek設(shè)定為零均值高斯分布的方差向量，即gauss（0，Ek），并用其產(chǎn)生誤差ek，按照式 （10）即得到最終的縮放因子向量

其中，rj為0.1和0.95之間的一個隨機數(shù)。

2.2 關(guān)聯(lián)模型的設(shè)計

縮放因子通過影響搜索方向和搜索步長最終產(chǎn)生一個臨時變異個體，但最終的子代個體則是利用交叉率控制變異個體的保留程度而獲得的。可見子代個體的質(zhì)量是在兩方面參數(shù)的復(fù)雜作用下決定的，并且兩參數(shù)之間存在著復(fù)雜的聯(lián)系。關(guān)聯(lián)性模型認為這一聯(lián)系是非線性的，并采用核支持矢量機進行描述，更適于處理小樣本問題，還能避免維數(shù)爆炸的問題［13］。此處采用的核函數(shù)為高斯核函數(shù)，如式 （11）所示

關(guān)聯(lián)模型的具體操作步驟如下：

（1）與分布模型相同，在初始的LP代內(nèi)，交叉率CR在 ［0，1）范圍內(nèi)隨機取值，在關(guān)聯(lián)模型建立起來后則以縮放因子向量為輸入，用模型來預(yù)測交叉率，關(guān)聯(lián)模型每隔g 代更新一次；

（2）記錄子代個體優(yōu)于父代個體時對應(yīng)的縮放因子向量和交叉率，每個變異算子分開記錄，這樣LP代后得到縮放因子矩陣Mk和交叉率向量CRk；

（3）將交叉率的取值范圍 ［0，1）劃分為l個等長區(qū)間，再將不同區(qū)間的交叉率依次標(biāo)記為1，2，…，l，由此向量CRk轉(zhuǎn)換為標(biāo)記向量Lk；

（5）在預(yù)測階段，對于一個屬于第k 個變異算子的縮放因子向量，依次用l個分類器進行分類，當(dāng)在第m 個分類器上決策函數(shù)輸出為1時，即判定交叉率取值屬于第m個區(qū)間，在此區(qū)間內(nèi)隨機生成一個值作為預(yù)測所得的交叉率；

（6）預(yù)測中可能存在所有分類器結(jié)果顯示輸入向量不屬于任何一類的情況，此時若某些區(qū)間尚無訓(xùn)練樣本，則優(yōu)先在這些區(qū)間隨機生成CR，否則在 ［0，1）內(nèi)隨機生成。

2.3 算法流程描述

基于上述兩模型的改進，DMSaDE 的算法的具體流程如下：

（1）在t＝0代，先將問題的解可行域歸一化，然后隨機生成種群A，其中每個個體的每一維在 ［0，1］之間隨機生成，求取每個個體的目標(biāo)函數(shù)值，并存儲當(dāng)前最優(yōu)結(jié)果f（x＊）；

（2）當(dāng)t＜LP 時，等概率選取變異算子，隨機生成所需的縮放因子向量和交叉率；

（3）當(dāng)t＝LP ＋i＊g 時，i＝0，1，2，…，采用SaDE算法中的策略更新變異算子的選擇概率，用前述方法建立或更新分布模型和關(guān)聯(lián)模型，并用所得分布空間Hk和殘差Ek求取縮放因子向量，以及用核支持矢量機預(yù)測交叉率；

（4）當(dāng)t＞LP且t≠LP＋i＊g 時，采用SaDE算法中的策略更新變異算子的選擇概率，并用當(dāng)前的分布模型和關(guān)聯(lián)模型來生成差分進化所需的參數(shù)；

（5）在每一代中，根據(jù)當(dāng)前獲取的參數(shù)取值和變異算子生成新的個體，若新個體優(yōu)于父代個體，則存儲相應(yīng)的參數(shù)取值，記錄被使用的變異算子；

（6）將每代中新生成的個體集合記為B，混合集合A和B，將所有個體的目標(biāo)函數(shù)值升序排列，選取前A 個個體組成下一代種群，用排序在第一個的個體更新當(dāng)前最優(yōu)結(jié)果f（x＊）；

（7）當(dāng)最大函數(shù)調(diào)用次數(shù)時，則去執(zhí)行步驟 （2）～步驟 （6），否者輸出f（x＊）。

3 性能驗證與分析

為了驗證提出的算法性能，使用了2008 年CEC 大尺度全局優(yōu)化問題競賽［14］上采用的4 個函數(shù)Shifted Schwefel’s Problem 2.21、Shifted Rosenbrock’s Function、Shifted Rastrigin’s Function、Shifted Griewank’s Function，以及提出SaDE 算法的文獻 ［12］所采用的Shifted Schwefel’s Problem 1.2with noise和Shifted noncontinuous Rastrigin’s function 共計6個標(biāo)準目標(biāo)函數(shù) （對應(yīng)標(biāo)記Fun1～Fun6）進行測試，它們的變量維數(shù)均有兩種情況，分別為30和100維。依據(jù)文獻 ［14］中的標(biāo)準，算法在每個目標(biāo)函數(shù)上均獨立運行25次，算法的停止條件為達到最大函數(shù)調(diào)用次數(shù)，30和100維的調(diào)用次數(shù)分別為1.5×105和5×105。DMSaDE 的相關(guān)參數(shù)設(shè)置為：種群A 為100，參數(shù)LP為50，代數(shù)間隔g 為20，變量維數(shù)劃分數(shù)量c在30維時為30，100維時為25，交叉率的區(qū)間數(shù)目l為10，高斯核函數(shù)的方差σ為1。

3.1 算法對比測試

對所提算法DMSaDE 和SaDE 算法進行了對比測試，結(jié)果如表1和表2。其中SaDE 的相關(guān)參數(shù)按照文獻 ［12］所述進行設(shè)置。為了更好的說明測試結(jié)果，統(tǒng)計了兩項指標(biāo)，分別為25次測試所得最優(yōu)值的均值和t檢驗。其中t檢驗的結(jié)果為 “＋”表示DMSaDE 所得結(jié)果優(yōu)于SaDE 的置信區(qū)間為95%，而 “－”則表示二者所得結(jié)果來至于同一個分布，在統(tǒng)計上無差異。

表1 DMSaDE和SaDE在30維時的測試結(jié)果

表2 DMSaDE和SaDE在100維時的測試結(jié)果

表中的結(jié)果可知，DMSaDE 在整體性能上優(yōu)于SaDE，其在30維時有3 個目標(biāo)函數(shù)所得最優(yōu)值均值是顯著小于SaDE的 （即t檢驗結(jié)果為 “＋”），而在100維時達到了5個。且在其余的目標(biāo)函數(shù)上二者也是在統(tǒng)計上無差異的，處于同一優(yōu)化水平，未出現(xiàn)SaDE 結(jié)果顯著優(yōu)于DMSaDE的情況，故提出的兩個模型顯著提高了原有SaDE 算法的性能。

3.2 算法自身分析

分布模型和關(guān)聯(lián)模型是DMSaDE 的主要改進內(nèi)容。在分布模型中，縮放因子向量是在主元空間下進行分布估計的，而變量維數(shù)也被劃分為c類。在關(guān)聯(lián)模型中，非線性映射采用了高斯核函數(shù)的支持矢量機，而交叉率輸出也被劃分為了l個區(qū)間。為分析模型中上述步驟對算法性能的影響，設(shè)計了一系列對比算法。對比算法Algorithm1將分布模型中的主元空間映射步驟取消，直接求取各維上縮放因子的均值和方差，再建立多維高斯分布模型。當(dāng)變量為100 維時，DMSaDE 和Algorithm1 在函數(shù)Fun1、Fun2、Fun5上的測試結(jié)果見表3。

表3 主元空間映射對算法性能的影響

從表3可知，DMSaDE 的性能更佳，說明直接建立分布模型的Algorithm1受變量維之間耦合的影響，并不能有效揭示高質(zhì)量縮放因子的分布情況。

對比算法Algorithm2和Algorithm3則分別采用多項式核的支持矢量機和線性支持矢量機來表述縮放因子與交叉率之間的關(guān)聯(lián)性。同樣對100維變量下的函數(shù)Fun1、Fun2和Fun5進行測試，結(jié)果見表4。

表4 支持矢量機對算法性能的影響

測試結(jié)果顯示，采用核函數(shù)的支持矢量機的測試結(jié)果明顯好于線性支持矢量機的測試結(jié)果，而高斯核的測試結(jié)果又略優(yōu)于多項式核的結(jié)果，證實了縮放因子與交叉率之間的關(guān)系是非線性的。

對于兩個劃分類數(shù)c和區(qū)間數(shù)l，以100維的函數(shù)Fun3為測試對象，取類數(shù)c為2、5、10、20和50，取區(qū)間數(shù)l為2、5、10、15和20。類數(shù)c和區(qū)間數(shù)l 的盒圖測試結(jié)果分別如圖1和圖2所示。

從圖1可以看出，當(dāng)類數(shù)c過小時，各維之間的縮放因子并未得到有效的區(qū)分，從而導(dǎo)致算法的性能較差；從圖2中可知，對于區(qū)間數(shù)l，其取值過小時，交叉率近似于在整個范圍內(nèi)均勻隨機選取，即不同縮放因子對應(yīng)的交叉率取值是隨機的，交叉率和縮放因子之間并未建立正真的聯(lián)系；當(dāng)l的取值過大時，區(qū)間被劃分的過于細小，縮放因子所映射的類數(shù)過多，使得支持矢量機的準確性和泛化能力有所下降。

圖1 類數(shù)c對算法性能影響的測試結(jié)果

圖2 區(qū)間數(shù)l對算法性能影響的測試結(jié)果

4 結(jié)束語

設(shè)計的兩個模型進一步提高自適應(yīng)差分進化算法的性能。其中提出的縮放因子分布模型將各維的縮放因子取值獨立考慮，反映了變量中各維之間的差異性；提出的交叉率關(guān)聯(lián)模型相比于已有算法，不再獨立的進行調(diào)整，而是建立了縮放因子向量與交叉率之間的非線性關(guān)系。6 組標(biāo)準函數(shù)的測試結(jié)果表明了提出算法的改進是有效的，在多數(shù)函數(shù)上獲得了更好的結(jié)果，而其余函數(shù)的測試結(jié)果也保持在了同等水平上；基于主成分分析技術(shù)的主元空間建模是分布模型的重要環(huán)節(jié)，而核函數(shù)下的支持矢量機能更好反映參數(shù)之間的復(fù)雜關(guān)系。

［1］Brest J，Boskovic B，Zumer V.An improved self－adaptive differential evolution algorithm in single objective constrained realparameter optimization ［C］／／IEEE Congress on Evolutionary Computation.Piscataway，NJ：IEEE Press，2010：1－8.

［2］SHEN Jiajie，JIANG Hong，WANG Su.Improved binary differential evolution algorithm based on velocity probability and adaptive speed value ［J］.Computer Engineering and Design，2014，35 （4）：1395－1401 （in Chinese）. ［沈佳杰，江紅，王肅.基于速度概率和自適應(yīng)速度值的差分進化算法 ［J］.計算機工程與設(shè)計，2014，35 （4）：1395－1401.］

［3］SUN Chengfu，ZHANG Yahong，CHEN Jianhong，et al.Improved differential evolution based on Gaussian disturbance and immune search strategy ［J］.Journal of Nanjing University（Nat Sci Ed），2013，49 （2）：202－209 （in Chinese）. ［孫 成富，張亞紅，陳劍洪，等.基于高斯擾動和免疫搜索策略的改進差分進化算法 ［J］.南京大學(xué)學(xué)報 （自然科學(xué)版），2013，49 （2）：202－209.］

［4］WANG Congjiao，WANG Xihuai，XIAO Jianmei.Improved differential evolution algorithm based on dynamic adaptive strategies［J］.Computer Science，2013，40 （11）：265－270 （in Chinese）.［王叢佼，王錫淮，肖健梅.基于動態(tài)自適應(yīng)策略的改進差分進化算法［J］.計算機科學(xué)，2013，40（11）：265－270.］

［5］Das S，Suganthan PN.Differential evolution：A survey of the state－of－the－art［J］.IEEE Transactions on Evolutionary Computation，2011，15 （1）：4－31.

［6］ZHANG Guijun， HE Yangjun，GUO Haifeng，et al.Differential evolution algorithm for multimodal optimization based on abstract convex underestimation ［J］.Journal of Software，2013，24 （6）：1177－1195 （in Chinese）. ［張貴軍，何洋軍，郭海鋒，等.基于廣義凸下界估計的多模態(tài)差分進化算法 ［J］.軟件學(xué)報，2013，24 （6）：1177－1195.］

［7］JIANG Liqiang，QIANG Hongfu，LIU Guangbin.Modified differential evolution for dynamic optimization problems ［J］.Mini－micro Systems，2013，34 （12）：2837－2840 （in Chinese）.［姜立強，強洪夫，劉光斌.求解動態(tài)優(yōu)化問題的改進差分進化算法［J］.小型微型計算機系統(tǒng)，2013，34 （12）：2837－2840.］

［8］ MENG Hongyun，ZHANG Xiaohua，LIU Sanyang. A differential evolution based on double populaitons for constrained multi－objective optimization problem ［J］.Chinese Journal of Computers，2008，31 （2）：228－235 （in Chinese）. ［孟紅云，張小華，劉三陽.用于約束多目標(biāo)優(yōu)化問題的雙群體差分進化算法 ［J］.計算機學(xué)報，2008，31 （2）：228－235.］

［9］Basak A，Das S，Tan KC.Multimodal optimization using a biobjective differential evolution algorithm enhanced with mean distance－based selection ［J］.IEEE Transactions on Evolutionary Computation，2013，17 （5）：666－685.

［10］ZENG Yurong，WANG Lin，DUN Caixia.Simple and effective hybrid differential evolution algorithm for solving traveling salesman problem ［J］.Application Research of Computers，2012，29 （12）：4455－4458 （in Chinese）. ［曾宇容，王林，頓彩霞.一種簡單有效的求解TSP 的混合差分進化算法［J］.計算機應(yīng)用研究，2012，29 （12）：4455－4458.］

［11］Brest J，Greiner S，Boskovic B，et al.Self－adapting control parameters in differential evolution：A comparative study on numerical benchmark problems ［J］.IEEE Transactions on Evolutionary Computation，2006，10 （6）：646－657.

［12］Qin A，Huang V，Suganthan P.Differential evolution algorithm with strategy adaptation for global numerical optimization ［J］.IEEE Transactions on Evolutionary Computation，2009，13 （2）：398－417.

［13］ZHOU Dexin，SONG Mingyu，ZHAN Xianglin.Research of aircraft units testability based on improved extended dependency model［J］.Computer Measurement and Control，2012，20 （12）：3176－3178 （in Chinese）. ［周德新，宋明瑜，詹湘琳.基于改進擴展關(guān)聯(lián)模型的飛機組件測試性研究 ［J］.計算機測量與控制，2012，20 （12）：3176－3178.］

［14］Tang K，Yao X，Suganthan PN，et al.Benchmark functions for the CEC，2008special session and competition on large scale global optimization ［R］.Nature Inspired Computation and Applications Laboratory，USTC，China，2007.