高媛，姜志俠，劉宇寧

（1.長春理工大學 數(shù)學與統(tǒng)計學院，長春 130022；2.中電金信軟件有限公司，北京 100192）

差分進化算法（Differential Evolution，DE）是由Storn等人在1995年為解決Chebyshev多項式問題所提出的，現(xiàn)在已經(jīng)成為解決復雜優(yōu)化問題的常用方法［1-2］。DE算法是一種結(jié)構(gòu)簡單、魯棒性強的全局搜索算法，在物流調(diào)度［3］、運動目標檢測［4］、成本控制［5］、數(shù)據(jù)挖掘［6］等許多領(lǐng)域得到了廣泛的應用。

差分進化算法主要由變異、交叉、選擇和邊界條件處理幾步組成。經(jīng)過幾十年的發(fā)展，眾多基于標準DE算法的改進算法被提出。Brest J［7］為每個個體設置了可以自動調(diào)整的控制參數(shù)，提出了jDE算法。Qin等人［8］運用個體之間的迭代經(jīng)驗來自適應調(diào)整參數(shù)和變異策略，提出了自適應差分進化算法（SaDE），提高了算法的收斂速度。為了完善差分進化算法在解決高維優(yōu)化問題時存在的缺陷，張錦華等人［9］結(jié)合了DE-rand-1和DE-best-1的優(yōu)點，并將其加權(quán)組合，提出了WMDDE算法。陳穎潔等人［10］提出了一種以優(yōu)秀個體為導向的多策略差分算法，該算法將種群等分為三個子種群，根據(jù)每個部分不同的特點，采取了不同的變異策略。

本文首先將種群按照適應度值從小到大排列，并將其按一定比例分為三個子種群，針對每個子種群不同的搜索能力構(gòu)建不同的變異策略，設置不同的控制參數(shù)。針對第一個適應度值較好的子種群，使用DE-best-2變異策略，提高種群收斂速度和搜索能力。針對第二個適應度值中等的子種群提出了一種基于優(yōu)秀個體的DE-rand-1 to DE-best-1變異策略，這有利于平衡種群的全局搜索和局部搜索能力。針對第三個適應度值較差的子種群提出了一種引入學習參數(shù)和均衡參數(shù)的組合變異策略，以此降低種群陷入停滯狀態(tài)的概率，保持算法的穩(wěn)定性。

1 標準DE算法

DE算法作為一種進化類算法，結(jié)構(gòu)中包含了變異、交叉、選擇三種進化操作。設DE算法的第t代種群由NP個維數(shù)為D的實數(shù)值參數(shù)向量組成，第i個個體表示為：xi(t)(i=1,2,…,NP)。

1.1 變異操作

標準DE算法采用差分策略產(chǎn)生變異向量。對于每個目標向量xi(t)(i=1,2,…,NP)，常用的變異策略如下：

1.2 交叉操作

交叉操作的目的在于提高種群的多樣性。標準DE算法的交叉操作如下：

其中，j=1,2,…,D；jrand為[1 ,2,…,D]之間的隨機數(shù)，來確保交叉?zhèn)€體至少有一個分量會與目標個體不同；CR稱為交叉算子，取值一般為[0 ,1]內(nèi)的實數(shù)。

1.3 選擇操作

選擇操作在目標個體及交叉?zhèn)€體之間進行，通過優(yōu)勝劣汰的競爭法則，選取其中更加適應環(huán)境的個體進入子代繼續(xù)繁衍，使種群向最優(yōu)解的方向進化。其迭代公式如下：

2 多子群多策略DE算法

下面提出一種多子群多策略DE算法，記為“改進DE”算法。

2.1 初始化種群

根據(jù)問題需要，確定種群個數(shù)NP及個體維數(shù)D，按下式隨機生成的初始種群(t=0)：

其中，xmax(t)，xmin(t)表示取值區(qū)間的最大值和最小值；rand(0 ,1)是在區(qū)間[0 ,1]上的隨機數(shù)。

設計“改進DE”算法的關(guān)鍵問題是如何劃分種群、選擇變異策略和設置參數(shù)?！案倪MDE”算法針對每個子種群不同的搜索能力構(gòu)建不同的變異策略、設置不同的控制參數(shù)，使得各子種群具備不同的搜索能力，體現(xiàn)不同的作用，保持整個種群的搜索和開采能力。本文根據(jù)適應度值從小到大的排序?qū)⒎N群分為三個子種群，選取前10%個體作為第一個子種群即優(yōu)秀種群，第二、第三個子種群根據(jù)經(jīng)驗分別選擇40%和50%。

2.2 第一個子種群X1（優(yōu)秀種群）

針對第一個子種群X1（優(yōu)秀種群），考慮到個體適應度值較好，為了提高種群的收斂速度并且增加種群的搜索能力，不使種群陷入停滯的狀態(tài)，同時也能夠維持整個種群的平衡狀態(tài)，采用了開采能力較強的DE-best-2變異策略：

其中，xbest為種群當前的最優(yōu)個體；xr1(t)，xr2(t)，xr3(t)，xr4(t)為子種群X1中隨機選取的四個不同個體。該策略具有較強的局部尋優(yōu)能力，可以在子種群X1中選擇更接近最優(yōu)解的解。在第一個子種群中F設為0.9可增加差分向量的擾動程度，有利于增強算法的搜索能力，CR設為0.1，是因為第一個子群X1本身就為優(yōu)秀種群?？紤]到交叉算子CR可以控制種群中試驗個體的多樣性，較大的CR值使得試驗個體更多地繼承變異個體的性質(zhì)，這樣可以使種群增強搜索能力；相反，變異算子CR值越小，試驗向量改變越小，有助于種群保持多樣性。

2.3 第二個子種群X2

DE-best-1因包含全局最優(yōu)個體，局部尋優(yōu)能力突出，適合求解單峰類型的問題；而DE-rand-1包含的個體均為隨機選擇，使得該策略的全局搜索能力突出，適合求解多峰類型的問題。因此對于適應度值中等的子種群X2來說，參考文獻［10］引入學習參數(shù)μ(xi(t))構(gòu)造一種新的加權(quán)變異策略，用來平衡子種群X2的全局搜索能力和局部開發(fā)能力。

學習參數(shù)定義如下：

其中，t是當前迭代次數(shù)；f(xi(t))為個體xi(t)的適應度函數(shù)值；f(x(t))min和f(x(t))max表示種群在當前代數(shù)t中個體適應度值的最大值和最小值。μ(xi(t))為單調(diào)遞增函數(shù)，隨著適應度函數(shù)值f(xi(t))的增大而增大。設種群規(guī)模NP=100，維數(shù)D=50，F(xiàn)=0.6，CR=0.9，以函數(shù)f1為例，其中f1的表達式為：

圖1更加直觀地展示出函數(shù)f1的學習參數(shù)μ(xi(t))在第一次迭代中的變化曲線。

圖1 種群X2中 μ(x i(t))的變化曲線

定義引入學習參數(shù)的加權(quán)變異策略DE-rand-1 to DE-best-1：

其中，xr1，xr2，xr3，xr4，xr5為X2中隨機選取的不同個體；μ(xi(t))為單調(diào)遞增函數(shù)，隨著適應度函數(shù)值f(xi(t))的增大而增大。

可知構(gòu)造的變異策略在前期，主要進行全局搜索，隨著μ(xi(t))的遞增，后期主要以在xbest附近進行局部開發(fā)，其中rand(0 ,1)用來隨機調(diào)整算法的進化方向，引導個體朝著最優(yōu)值靠近，從而提高種群多樣性，避免DE算法停滯和過早收斂的情況。

2.4 第三個子種群X3

在變異策略中，種群的多樣性在很大程度上與所選取的搜索中心有關(guān)，也就是圍繞著哪個個體進行差分進化，稱這個個體為基向量。設當前迭代次數(shù)為t，對個體xi(t)參考文獻［10］定義均衡參數(shù)EP(xi(t))和系數(shù)at：

其中，xx1,best是在優(yōu)秀種群中隨機選取的個體，Tmax是最大迭代次數(shù)，隨著進化的推進，由式（6）可以看出系數(shù)at的值是在逐漸增大。

μ(xi(t))，EP(xi(t))，1-EP(xi(t))為f(xi(t))的單調(diào)函數(shù)，即當個體適應度值越大時，μ(xi(t))和EP(xi(t))的值越大，而相應1-EP(xi(t))的值越小。

對于子種群X3中的個體xi(t)，當其適應度值越大時，其向優(yōu)秀種群中個體的學習能力就需越強，因此用學習參數(shù)μ(xi(t))來增強其向優(yōu)秀個體的學習能力，引入呈遞減趨勢的均衡參數(shù)1-EP(xi(t))是為避免其收斂過快，陷入局部最優(yōu)的狀態(tài)。而1-μ(xi(t))的作用則是當其適應度值越小時，子種群X3中個體越需要降低其向優(yōu)秀種群中個體的學習能力。為了避免子種群X3中個體因適應度值較差而向優(yōu)秀種群學習能力過大的情況，引入呈遞減趨勢的均衡參數(shù)EP(xi(t))來對其自身進行平衡。

仍以函數(shù)f1為例，圖2更加直觀地展示出第三個子種群在第一次迭代中均衡參數(shù)EP(xi(t))隨著個體的變化而上升的變化曲線。

圖2 種群X3中EP(x i(t))的變化曲線

選取以下變異策略：

其中，xbest是當前迭代的全局最優(yōu)值；xr1(t)，xr2(t)，xr3(t)是在子種群X3中隨機選取的三個個體。這里randnormal是指以ui(t)為均值，0.1為方差的正態(tài)分布形成的個體。randnormal的目的為探索周圍鄰域存在的有潛力解，相比于文獻［10］中的柯西分布，考慮到正態(tài)分布比柯西分布在峰值附近的取值概率更大，接近最優(yōu)值的概率更多，因此引入正態(tài)分布保證了以較大的概率生成均值的控制參數(shù)值，同時不丟失隨機性，保證了種群的多樣性。實驗結(jié)果表明正態(tài)分布在變異策略中可以起到較好的效果。對于變異策略中差分向量采取隨機的機制，從而在基向量的基礎上向周圍尋優(yōu)。對于適應度越差的子種群X3中的個體，為了避免整個種群陷入局部最優(yōu)狀態(tài)從而引入均衡參數(shù)，其目的在于當它向優(yōu)秀的個體學習的學習參數(shù)較大時，減緩向優(yōu)秀的個體學習的速度。當它向優(yōu)秀個體學習參數(shù)較小時，變異向量個體側(cè)重在個體自身與差分向量的組合基礎上產(chǎn)生，因此CR取0.9有利于維持種群的多樣性。

2.5 算法流程

通過對不同的子種群使用不同的變異策略和控制參數(shù)的選取，使得不同的變異策略和參數(shù)在種群的進化過程中所發(fā)揮的作用不同，使得各個種群之間的搜索能力能夠互補，最終達到平衡全局搜索能力和局部搜索能力的作用。算法流程如圖3所示。

圖3 算法流程圖

3 數(shù)值實驗

針對提出的“改進DE”算法，選取8個經(jīng)典的測試函數(shù)對算法的性能進行測試，函數(shù)全局最優(yōu)值均為0。8個測試函數(shù)表達式如表1所示。

表1 測試函數(shù)

用以上提到的常見的四種差分變異策略DE-best-1、DE-rand-1、DE-best-2、DE-current-tobest-2與“改進DE”算法計算8個測試函數(shù)的最優(yōu)值，為了考察算法的綜合性能，設置種群規(guī)模NP=100，維數(shù)D=50，所有算法最大迭代次數(shù)均為1 000次。結(jié)果對比如表2所示。

表2 測試函數(shù)最優(yōu)值結(jié)果對比NP=100，D=50，Tmax=1000

五種算法對8個函數(shù)進行測試的適應度值的迭代曲線如圖4所示，從圖中可以看出本文所提出的“改進DE”算法在迭代過程中所展示的良好的性能，迭代曲線下降速度較快，并且尋優(yōu)精度較高，相比于其他算法總體上尋優(yōu)能力強，收斂速度快。

圖4 測試函數(shù)迭代曲線

4 結(jié)論

本文在標準DE算法的基礎上，將種群按適應度值從小到大排列并按一定比例分為三個子種群，針對不同子種群采用了不同的變異策略，進而使不同的變異策略在不同子種群進化過程中發(fā)揮不同的作用。

第一個子種群采用標準DE算法中DE-best-2變異策略，該策略具有較強的局部尋優(yōu)能力。針對第二個適應度值中等的子種群引入學習參數(shù)，結(jié)合DE-rand-1和DE-best-1變異策略的各自優(yōu)點，提出了一種新的變異策略DE-rand-1 to DE-best-1，該變異策略通過學習參數(shù)在全局搜索和局部搜索之間建立一種平衡。針對第三個適應度值較差的子種群提出了一種引入學習參數(shù)和均衡參數(shù)的組合變異策略，使其能夠更加平衡的向優(yōu)秀種群中的個體進行學習，以此降低種群陷入停滯狀態(tài)的概率，保持算法的穩(wěn)定性并達到更優(yōu)的狀態(tài)。通過8個測試函數(shù)的實驗結(jié)果可得出，“改進DE”算法在大多數(shù)函數(shù)上的尋優(yōu)能力和收斂速度上都有了一定的提升，并具有較強的穩(wěn)定性。