多子群多策略差分進化算法

高媛，姜志俠，劉宇寧

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

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

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

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

1 標準DE算法

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

1.1 變異操作

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

1.2 交叉操作

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

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

1.3 選擇操作

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

2 多子群多策略DE算法

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

2.1 初始化種群

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

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

設計“改進DE”算法的關鍵問題是如何劃分種群、選擇變異策略和設置參數。“改進DE”算法針對每個子種群不同的搜索能力構建不同的變異策略、設置不同的控制參數，使得各子種群具備不同的搜索能力，體現不同的作用，保持整個種群的搜索和開采能力。本文根據適應度值從小到大的排序將種群分為三個子種群，選取前10%個體作為第一個子種群即優秀種群，第二、第三個子種群根據經驗分別選擇40%和50%。

2.2 第一個子種群X1（優秀種群）

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

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

2.3 第二個子種群X2

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

學習參數定義如下：

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

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

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

定義引入學習參數的加權變異策略DE-rand-1 to DE-best-1：

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

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

2.4 第三個子種群X3

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

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

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

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

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

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

選取以下變異策略：

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

2.5 算法流程

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

圖3 算法流程圖

3 數值實驗

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

表1 測試函數

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

表2 測試函數最優值結果對比NP=100，D=50，Tmax=1000

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

圖4 測試函數迭代曲線

4 結論

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

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