以優(yōu)秀個體為導向的多策略差分進化算法

陳穎潔，劉三陽，張哲辰

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

差分進化算法（differential evolution，DE）是在1995年由Storn和Price為求解切比雪夫多項式而提出的一種群智能算法[1-2]。該算法的原理簡單，受控參數(shù)少，實施隨機、并行、直接的全局搜索，易于理解和實現(xiàn)[1-2]。差分進化算法在求解問題的過程中沒有利用問題的相關特征信息，而是利用不同個體之間的差分信息來指導整個種群進化，進而實現(xiàn)對最優(yōu)值的搜索，且其魯棒性較好[3]。自差分進化提出以來，許多改進方法已被提出。除此，也有借助網(wǎng)絡中的信息來指導差分進化中種群的進化[4-6]。近年來群智能進化算法以及應用也得到了廣泛研究[7-13]。

一些實驗結果表明差分算法中變異操作對DE算法的收斂性能影響最大[14-18]。針對處于不同狀態(tài)的個體選取合適的變異策略和參數(shù)的問題，國內外許多學者對其進行了研究并提出了一些改進算法。Brest等[14]提出了jDE算法，其為種群中的每個個體設置了控制參數(shù)，并在進化過程中以一定的規(guī)則來實現(xiàn)對其自動的調整，雖然實現(xiàn)了參數(shù)的自適應，但其對不同狀態(tài)的個體所需的變異策略沒有進行分析考慮。Qin等[15]提出了一種自適應差分進化算法（SaDE），在進化過程中，個體的參數(shù)和所需的變異策略是通過學習自身歷史的經(jīng)驗來實現(xiàn)其自動調整，在一定程度上提高了收斂速度，但是其對種群中適應度值差的個體沒有進行獨立的分析。Zhu等[16]提出了一種自適應的多種群差分進化算法，該方法對控制參數(shù)采用自適應的機制，但是對種群中差的個體采用DE/best/2策略，該策略雖然能提高收斂速度，但是會使整個種群陷入局部狀態(tài)的概率增大。Liu等[17]提出了一種基于歷史和啟發(fā)式信息的自適應差分進化算法，該方法對種群中較差個體采用DE/rand/1策略，該策略能探索一些有潛力的解，但是當子種群較分散時，會影響整個種群的尋優(yōu)進程。孫燦等[18]提出了一種融合鄰域搜索的多策略差分進化算法，該方法利用優(yōu)秀個體的優(yōu)勢，在優(yōu)秀個體的鄰域進行探索，降低了種群陷入局部最優(yōu)狀態(tài)的概率，但是針對種群中差的個體其變異策略采取DE/rand/1策略，并且其控制參數(shù)是定值，對于不同的優(yōu)化問題，其求解效果和尋優(yōu)進程都會受到影響。

以上文獻主要是針對優(yōu)秀種群和適應度較好的種群提出的改進。但是，正如一些動物的尾巴對于整個身體的平衡性是十分重要的，同樣在進化過程中，差的種群對于維持整個種群的平衡也十分重要。如果只是針對較好個體進行改進，而忽略差的個體，則會導致整個種群在進化過程中失去平衡，進而影響種群的收斂速度和精度。所以，針對這一缺陷，本文提出了一種基于優(yōu)秀個體的多策略自適應差分進化算法（BEMA-DE）。首先，根據(jù)適應度值的排序將種群等分為三個子種群，對每個子種群使用不同的變異策略和控制參數(shù)因子，從而使不同種群具有不同的搜索能力，來實現(xiàn)搜索能力的互補，進而有利于平衡整個種群的全局搜索與局部搜索能力。其次，為了提高收斂速度，針對適應度差的子種群，提出了一種新的變異策略，一方面通過引入學習因子以此來增強其向優(yōu)秀個體的學習能力，另一方面，為了平衡收斂速度、精度和易陷入局部最優(yōu)的狀態(tài)，引入了平衡因子。并且對其控制參數(shù)采取自適應的機制，以此來降低種群陷入停滯狀態(tài)的概率，保持算法的穩(wěn)定性。

1 以優(yōu)秀個體為導向的多策略自適應差分進化算法

1.1 初始化種群

在維數(shù)為D的空間中按式（1）隨機生成規(guī)模大小為NP初始種群。

當種群生成之后，根據(jù)其適應度值的排序將其等分為三個種群，記為X1、X2、X3。

1.2 變異操作

1.2.1 優(yōu)秀個體的選取

對于不同的算法，優(yōu)秀種群與優(yōu)秀個體的判定方式與選取方式也不盡相同。文獻[17]中優(yōu)秀種群是取種群的前10%，優(yōu)秀個體則采取隨機選取的機制，在前10%個體中隨機選取一個個體作為優(yōu)秀個體，該方法具有一定的隨機性，能夠在一定程度上避免種群陷入最優(yōu)狀態(tài)，但是優(yōu)秀種群的數(shù)量與算法自身性能有很大關系，文中沒有對其進行實驗分析。文獻[18]中將個體的k鄰域作為優(yōu)秀群體，再從其中選取適應度值最好的個體作為優(yōu)秀個體，鄰域操作能夠更好地探索周圍有潛力的解，但是將適應度值最好的解作為優(yōu)秀個體則會使種群陷入局部最優(yōu)的概率增大。文獻[19]中對于優(yōu)秀群體的選擇是取排序后種群的前50%，并在其中任意選取一個個體作為優(yōu)秀個體，這種選取方式能使種群保持良好的多樣性，但是該方法的優(yōu)秀群體過大，會使選取較好的優(yōu)秀解的概率降低。文獻[20]中則是用自適應的機制來選取優(yōu)秀群體，然后在優(yōu)秀群體中隨機選擇一個個體作為優(yōu)秀個體，該方法能夠實現(xiàn)優(yōu)秀個體自適應的選取，但是在每一次迭代過程中，相關參數(shù)都會進行更新，其計算量會增大。為了減小計算量并避免種群陷入局部最優(yōu)狀態(tài)，本文對于優(yōu)秀個體的選取參照文獻[17]中所提的方法，同時為了探究不同優(yōu)秀種群數(shù)量對本文所提算法的影響，本文將優(yōu)秀種群數(shù)量分別設置為排序后種群的前5%、10%與15%，將函數(shù)f1~f16在不同維數(shù)下30次獨立運行結果的均值列于表1和表2。由表1和表2可以看出當優(yōu)秀種群數(shù)量選取10%時，本文所提在大部分函數(shù)上能取得較好結果。

表1 函數(shù)在不同優(yōu)秀種群數(shù)量時的取值(NP=60,D=30)Table 1 Value of function for different excellent populations when NP=60,D=30

表2 函數(shù)在不同優(yōu)秀種群數(shù)量時的取值(NP=90,D=60)Table 2 Value of function for different excellent populations when NP=90,D=60

1.2.2 學習因子和平衡因子

為了增加適應度值差的個體向優(yōu)秀個體的學習能力，引入學習因子LF1、LF2。對個體Xi而言：

其中，Xpbest是在優(yōu)秀種群中隨機選取的個體。f(Xpbest)是該個體的適應度值。式（2）和（3）中的參數(shù)如下：

其中，Gm是最大迭代次數(shù)，t是當前迭代次數(shù)。隨著進化的推進，由式（5）可以看出WP的值是在逐漸增大。f(Xmax)為個體Xi的適應度函數(shù)值，f(Xmin)和f(Xmax)表示種群在當前代數(shù)t中個體適應度值的最大值和最小值。

由式（4）、（6）和（7）可知，BF、IS1、IS2、(1-BF)可看作是關于個體Xi的單調函數(shù)，即當個體適應度值越大時，其BF、IS1的值越大，IS2與(1-BF)的值越小，當個體適應度值越小時，其BF、IS1的值越小，IS2與(1-BF)的值越大。以函數(shù)f16為例，為了更加直觀地觀察BF的變化趨勢，繪制其最后一次迭代過程中的曲線圖，如圖1所示。

圖1 種群X3中BF值變化曲線Fig.1 Change curve of BF value in population X3

假設當前迭代次數(shù)為t，則LF1與LF2也可看作是關于個體Xi的單調函數(shù)，此時，當個體適應度值越大時，LF2的值越大，當個體適應度值越小時，LF1的值越大。對于種群X3中的個體Xi，當其適應度值越大時，其向優(yōu)秀個體學習的能力就需越強，故用學習因子LF2來增強其向優(yōu)秀個體的學習能力，但是為避免其收斂過快，陷入局部最優(yōu)狀態(tài)，引入呈遞減趨勢的平衡因子(1-BF)來對其進行平衡。當其適應度值越小時，需要降低其向優(yōu)秀個體的學習能力，故用學習因子LF1來增強對自己的學習能力，但是因種群X3中個體適應度值相對其他兩個種群而言較差，為了避免對個體自身學習能力過大，故用呈遞減趨勢的平衡因子BF來對自身進行平衡。隨著進化過程的推進，即t逐漸增加時，應該適當?shù)丶涌旆N群的收斂速度，此時WP與1-WP可分別看作是1-IS2與IS2的權重，故此時向優(yōu)秀個體學習的能力應該增強，進而能夠起到加速收斂的目的。以函數(shù)f16為例，圖2能夠更加直觀地觀測出平衡因子BF在進化中對學習因子LF1、LF2的影響及變化趨勢。

圖2 BF值對學習因子的影響曲線圖Fig.2 Graph of BF value influence on learning factor

1.2.3 控制參數(shù)的選取

DE算法中，有兩個控制參數(shù)，尺度因子F和交叉概率CR?？刂茀?shù)的引進有助于了解種群和個體的信息，對于選取不同變異策略的種群來說，控制參數(shù)的選取也極為重要，而參數(shù)調整的目的也在于平衡種群的探索能力和開采能力[8]。F取值越大，種群多樣性下降緩慢，增加了從局部極值點逃脫的可能性[8]。F越小，開采能力越好，但是容易陷入局部最優(yōu)狀態(tài)。CR的值越小，試驗向量中變異向量所占的比例較小，有利于維持種群的多樣性，CR值越大，有利于局部搜索和加速收斂[8]。對于種群X1中的個體來說，其參數(shù)值參照原文獻。對于種群X2中的個體，設置其尺度因子F=0.6，交叉概率CR=0.9，在本文中能夠取得較好的實驗效果。

對于種群X3中的個體來講，同時考慮了進化代數(shù)與種群中不同個體之間的差異，在此基礎上對其參數(shù)采取自適應的機制。假設當前迭代次數(shù)為t，對X3中適應度值較大的個體而言，需要增大其尺度因子的值，減少交叉概率的值來維持種群的多樣性來避免種群陷入停滯的狀態(tài)。反之，對于適應度值較小的個體來講，需要減小其尺度因子的值，增大交叉概率的值。隨著進化過程的推進，即t逐漸增加時，為了平衡算法的全局搜索能力與局部搜索能力，此時F和CR的值隨著迭代次數(shù)的增加應該逐漸增加。所以對種群X3中的每個個體來說，設置其控制參數(shù)如下：

為了更加直觀地觀察種群X3中控制參數(shù)的變化。以函數(shù)f15為例，繪制其在最后一次迭代的F和CR的取值變化圖，如圖3所示。

圖3 種群X3中不同個體的F和CR取值Fig.3 Values of F and CR for different individuals in population X3

圖4給出了對于函數(shù)f15在進化過程中適應度值不同的個體，即IS1和IS2取不同值時，F(xiàn)和CR隨著種群進化的變化曲線圖。由圖4可以看出，當t是定值時，IS1值越小，其CR的值就越大，此時有利于增強局部搜索能力；IS2值越小，其F值就越大，此時有利于增強勘探能力。隨著t的增大，F(xiàn)和CR的值也在不斷地增大，對于種群X3來說，有利于平衡其全局搜索能力與局部搜索能力。

圖4 進化過程中不同狀態(tài)個體的F和CR取值Fig.4 Values of F and CR of individuals in different states during evolution

1.2.4 變異策略的選取

隨著DE算法的不斷完善，已經(jīng)有很多的變異策略被提出來。常見的變異策略如下：

其中，r1、r2、r3、r4是在[1,NP]中隨機選取的不同整數(shù)且和個體X的指標i不同。

針對不同的種群選取不同的策略對整個種群所起的作用是不一樣的。而針對要解決的問題，使用的變異策略也是不一樣的。在本文中，為了提高種群的收斂速度并且增加種群的探索能力，不使種群陷入停滯的狀態(tài)，同時也能夠維持整個種群的平衡狀態(tài)，對于種群X1中的個體而言，為了增強其局部搜索能力，在利用當前優(yōu)秀個體的優(yōu)勢之下，探索其周圍更好的解選擇MSDE-DE算法中的策略[18]：

選擇策略DE/best/2；

其中，r1、r2、r3都是隨機選取的數(shù)，且滿足r1+r2+r3=1,lbesti是個體Xi在半徑為k的鄰域內的適應度值最小的個體。Xa和Xb是在個體Xi的k鄰域內隨機選擇的個體。

對于種群X2中的個體來說，其主要作用是探索一些有潛力的解，進而增強種群的全局搜索能力。所以在利用當前優(yōu)秀解的前提下，為了產(chǎn)生更加均勻的解，選取文獻[21]中的策略：

在變異策略中，基向量相當于局部搜索的中心。種群的多樣性在很大程度上是由局部搜索中心來決定的，所以基向量的選取十分重要[8]。種群X3來講，其適應度值較差，所以需要增強其像優(yōu)秀個體的學習能力，故對其基向量的選取如下式：

其中：

這里randCauchy是指以miui(t)為均值，0.1為方差的柯西分布形成的個體，其目的是探索周圍鄰域存在的有潛力的解。對于變異策略中差分向量采取隨機選取的機制，從而在基向量的基礎上向周圍尋優(yōu)。綜上，對于變異策略的選取如下式：

其中，r1、r2是在種群的前20個個體中隨機選取的兩個個體。在種群X3中，對于適應度值越差的個體，當其向優(yōu)秀個體的學習因子過大時，此時基向量會側重以優(yōu)秀個體為中心，變異向量個體則側重在優(yōu)秀個體與差分向量的組合基礎上產(chǎn)生，易使整個種群陷入局部最優(yōu)狀態(tài)，故此時引入平衡因子來放緩其向優(yōu)秀個體的學習速度，在一定程度上避免其陷入局部最優(yōu)狀態(tài)。當其向優(yōu)秀個體的學習因子較小時，此時基向量側重以個體自身為中心，變異向量個體側重在個體自身與差分向量的組合基礎上產(chǎn)生，有利于維持種群的多樣性。

通過對不同的種群使用不同的變異策略和控制參數(shù)，使得不同的變異策略和參數(shù)在進化過程中所發(fā)揮的作用不同，進而實現(xiàn)各個種群之間搜索能力的互補，最終達到平衡全局搜索能力和局部搜索能力的作用。

1.3 交叉操作

對于經(jīng)過變異操作的種群中的每個個體Vi,j，按照下式產(chǎn)生試驗向量個體：

其中，i=1,2,…,NP,j=1,2,…,D,rand(j)∈[0,1]為第j維分量對應的隨機數(shù)。k=1,2,…,D用來保證產(chǎn)生的試驗個體中至少有一個分量來自變異個體。

1.4 選擇操作

傳統(tǒng)DE算法中使用的是貪婪選擇機制。在選擇操作根據(jù)試驗個體Ui,j和目標個體Xi,j的適應度函數(shù)值。按照式（20）產(chǎn)生進入下一代的個體。

本文為了增加優(yōu)秀個體進入下一代的概率，選擇使用基于目標排序的選擇策略[5]。

2 BMEA-DE算法偽代碼

BMEA-DE算法偽代碼如下：

1.隨機初始化種群，設置種群規(guī)模NP以及維數(shù)D。

2.設置當前迭代次數(shù)t，最大迭代次數(shù)Gm。

3.Whilet≤Gmdo：

4.根據(jù)適應度的值將種群分為3個子種群X1,X2,X3。

5.fori=1:NP/3 do：

6.對種群X1中的個體，使用策略（14）。對于種群X2中的個體，使用變異策略式（15）產(chǎn)生變異向量個體，再根據(jù)式（19）產(chǎn)生試驗向量個體。對于種群X3中的個體，使用策略（18）產(chǎn)生變異向量個體，根據(jù)式（19）產(chǎn)生試驗向量個體。

7.對于種群X1,X2中的個體選擇貪婪選擇機制，種群X3的個體則根據(jù)基于目標的排序選擇機制[5]選取合適的個體進入下一代。

8.將三個子種群合并為一個種群并根據(jù)其適應度值再次將其等分為3個子種群。

9.t=t+1。

10.end while

3 數(shù)值仿真

3.1 測試函數(shù)

針對本文提出的算法，選取了19個標準測試函數(shù)來對其進行驗證。其中，f1~f7為高維單模態(tài)問題，f8為Noise函數(shù)。f9~f16為高維多模態(tài)函數(shù)。f17~f19是低維函數(shù)，其維數(shù)D=2。表3為各個測試函數(shù)所對應的參數(shù)。

表3 函數(shù)的名稱、搜索范圍和最優(yōu)值Table 3 Name、search space and optimal value of test function

3.2 實驗結果

將文中所提的算法與4種不同的算法進行對比，分別是標準DE、jDE、SADE以及同樣是多策略的MSDE-NS算法[17]，其相關參數(shù)參照原文獻中的值。實驗所用處理器為Intel?CoreTMi5-6500CPU@3.20 GHz 3.19 GHz，所有算法均在Matlab2016a下進行，以迭代次數(shù)Gm=3 000次為停機準則，各算法獨立運行30次，實驗結果如表4。其中mean表示30次獨立運行的最優(yōu)值的均值，反映了算法的求解精度，std表示方差，反映了算法的穩(wěn)定性。

當測試函數(shù)的維數(shù)升高時，函數(shù)的優(yōu)化就會隨之變得更加復雜，為此將種群規(guī)模和維度分別升至NP=90,D=60，得到均值和方差，如表5所示。由表4和表5可以看出，BMEA-DE在大部分函數(shù)上性能表現(xiàn)很好，當維數(shù)增加時其解的精度與其他算法相比仍有優(yōu)勢。

表4 NP=60,D=30時BMEA-DE算法與主流算法的結果對比Table 4 Results of BEMA-DE algorithm compared with mainstream algorithm when NP=60,D=30

表5 NP=90,D=60時BEMA-DE算法與主流算法的結果對比Table 5 Results of BEMA-DE algorithm compared with mainstream algorithm when NP=90,D=60

為了更直觀地觀察不同維數(shù)對算法的影響，選擇單峰函數(shù)f6和多峰函數(shù)f13，將其維數(shù)由20維逐步升至40維，各算法獨自運行30次，取平均值，得到各算法在不同維數(shù)下最優(yōu)值結果的曲線對比圖，如圖5。

由圖5可以看出，BMEA-DE算法對于維數(shù)的增加更具有穩(wěn)定性。

圖5 函數(shù)f6和f13在不同維數(shù)下的最優(yōu)值Fig.5 Optimal values of function f6 and f13 in different dimensions

為了更加直觀地觀察不同算法的收斂速度和精度，將函數(shù)f1、f4、f11、f13、f15的收斂曲線繪制如圖6。收斂曲線是各算法獨立運行30次的平均曲線。

由圖6可以看出BMEA-DE算法具有更快的收斂速度與精度，對于多峰函數(shù)，其部分函數(shù)精度也有所提高。對于多峰函數(shù)f13和f15，相比較的算法在進化后期基本都陷入一種停滯的狀態(tài)，只有BMEA-DE算法還在不斷尋優(yōu)。

圖6 5個函數(shù)在不同算法下的收斂曲線Fig.6 Convergence curves of five functions under different algorithms

表6給出了文中所有算法的Friedman排名，可以看出在不同維數(shù)下BMEA-DE算法的排名都為第一。

表6 BMEA-DE與改進的DE算法的Friedman排名結果Table 6 Friedman ranking results of BMEA-DE and improved DE algorithm

4 結束語

根據(jù)種群個體適應度值的排名，本文針對處于不同狀態(tài)的種群個體使用了不同的變異策略，進而使不同的變異策略在整個種群進化過程中發(fā)揮其各自的作用。并針對適應度值較差的種群提出了一種新的變異策略，使其能夠更加平衡地向優(yōu)秀個體學習，從而達到平衡加速收斂以及避免陷入局部最優(yōu)狀態(tài)的作用。通過對其參

數(shù)使用自適應的機制也能使種群更加多樣性。最后通過19個測試函數(shù)的實驗結果可知，BMEA-DE算法在大部分函數(shù)上尋優(yōu)精度和收斂速度上都有一定的提升。并且通過維數(shù)的分析，可以得出維數(shù)的增加對BMEA-DE算法的尋優(yōu)精度影響較小，算法有較強的穩(wěn)定性。