基于混合策略的差分進化算法

梁 靜，周欽亞，瞿博陽，宋 慧

(1.鄭州大學 電氣工程學院，河南 鄭州450001;2.中原工學院電子信息學院，河南鄭州450007)

0 引言

最優化是人們在實際生活中經常遇到的問題，它們可以通過數學方法抽象成函數求最優解問題.隨著實際工程中的問題從線性到非線性的轉變，出現復雜性增加，極值增多以及建模困難等問題，智能優化算法已經逐漸成為相關學科的一個主要研究目標和研究方向.因此，大量國內外學者對智能優化算法進行了研究改進.

在文獻［1］中作者通過對個體進行分工來提高算法的性能.文獻［2］采用隨機向量和最優向量作為基準向量，它們的權值分別為和，通過改變大小來提高算法的性能.文獻［3］使用種群中心作為基準向量并在種群中心產生變異個體.文獻［4］把種群分為三個子種群，每個子種群采用不同的策略并且在不同的時期分配不等的個體.Qin等［5］采用4種變異策略，同時對不同策略采用不同的交叉因子CR，并且CR通過一個自適應機制進行調整.文獻［6］按照個體適應度的差異將個體分成不同的子種群，并針對不同的個體適應度值采用不同的變異因子，保證在加快算法收斂速度的同時能夠跳出局部最優點.在文獻［7］中Brest等人給出了自適應控制參數的差分進化算法，在算法迭代過程中引入4個在0和1之間均勻分布的隨機數，由它們控制變異因子和交叉因子的產生.

筆者提出了一種混合策略差分進化算法，該算法通過種群中個體的適應度大小將種群分為3個大小不同的子種群，而每個子種群的大小根據當前總種群的收斂情況而定.為了提高算法的通用性和穩定性，每個子種群使用不同的變異策略以及不同的控制參數，對適應度好的子種群使用有利于局部搜索的策略和參數，對適應度不好的子種群使用有利于全局搜索的策略和參數.

1 標準差分進化算法及其分析

差分進化算法也是智能優化算法中的一種，由Storn和Price于1997年提出［8］，該算法最初的目的是為了解決切比雪夫多項式問題.算法采用實數編碼方式，利用種群中個體間的差分向量對個體進行方向擾動，實現個體變異，再通過交叉和選擇操作以達到對個體的函數值進行優化的目的.差分進化算法同遺傳算法一樣包括變異、交叉以及選擇操作，但相比于遺傳算法，DE算法的選擇操作采用一對一的淘汰機制來更新種群.從本質上說，DE算法是一種基于實數編碼的具有保優思想的貪婪遺傳算法.

智能優化算法主要解決的是傳統優化算法不能解決的非線性優化問題.非線性最小化優化問題描述如下:

算法首先在所求問題的可行解空間中隨機產生初始種群P(G)={x1(G)，x2(G)，…，xNP(G)}，G=0，NP 為種群大小.

對第G代中的每一個個體xi進行變異操作，得到與其相對應的變異個體vi，即

式中:r1，r2，r3∈{1，2，…，NP} 是3個互異的整數且不同于i，F是變異因子，為固定實數，取值范圍一般是［0，2］.

對每個個體和與其對應的變異個體實施交叉操作，生成實驗個體Ui(G)，即

式中:rand表示［0，1］之間的隨機數;CR是交叉概率，取值范圍是［0，1］;jrand表示{1，2，…，D} 中的隨機整數.

對超出搜索范圍的實驗個體Ui(G)做如下處理

將實驗向量Ui(G)與目標向量xi(G)的目標函數值進行比較，選擇較優的個體進入下一代，選擇操作如下

目前針對差分進化算法的變異操作提出了十余種不同的變異策略.每種策略具有不同的作用，有些策略全局搜索能力比較強;有些策略局部搜索能力比較強，收斂速度比較快，收斂精度比較高;有些策略可以很好的協調種群的全局搜索能力和局部搜索能力.同樣差分進化算法的控制參數對于算法的優化結果也有著很大的影響.DE算法主要參數包括種群的大小NP，變異因子F，交叉概率CR.如果種群NP太小會使搜索的范圍受到限制，導致搜索不到全局最優解，而種群太大會產生大量無效搜索.當F較大時，種群具有較好的多樣性，反之，如果F較小，種群將會在當前個體很小范圍內進行搜索，可以增加種群的收斂速度.較大的CR使得產生的實驗個體與目標個體之間存在較大差別，對于保持種群的多樣性和全局搜索是有利的，較小的CR則有利于種群的局部搜索和收斂速度.

2 算法描述

根據已有的研究成果提出一種混合策略的差分進化算法.該算法的基本思想是根據適應度將種群分為3個大小不同的子種群:優種群、劣種群以及一般種群.其中適應度較好的個體組成優種群，該種群負責局部搜索，提高算法的收斂速度和精度;適應度較差的個體組成劣種群，該種群的作用就是進行全局搜索，使算法跳出局部最優，避免算法早熟;其余的個體組成一般種群，該種群的作用就是平衡算法的全局搜索能力和局部搜索能力.

3個子種群的大小將會根據總種群是否陷入局部最優來設定.當種群陷入到局部最優時，需要增大劣種群以便加強全局搜索能力從而跳出局部最優.種群是否陷入局部最優根據粒子的適應度標準差和粒子間距離標準差來判斷.因為在正常情況下粒子隨著算法的進行將會逐漸收斂到一起，它們的適應度標準差以及它們之間的距離標準差都會越來越小.反之，如果在某些時刻粒子的適應度標準差很小而距離的標準差很大則可以說明粒子已經陷入局部最優，這是由于一些函數在最優值附近存在大量對稱的局部最優所造成的.算法同時還采用變化的控制參數，這樣算法能夠有效的進行局部搜索和全局搜索.

優種群的作用是進行局部搜索，因此選取DE/best/2/bin作為該子種群的變異策略，該模式以當前種群最好的個體為基準個體，再加上2個隨機擾動向量，在當前最好個體的周圍進行搜索，具有很好的局部搜索能力;劣種群的作用是進行全局搜索，所以該種群的變異策略選取DE/current-rand/2/bin，該策略以自身為基準個體，加上2個隨機擾動，具有很強的全局搜索能力;一般種群選取DE/current-best/2/bin作為變異策略，以自身為基準個體，通過向當前種群最優個體進行學習，能夠有效的平衡差分進化算法的全局搜索能力和局部搜索能力.3個變異策略如下所示:

優種群V=Xbest+F(Xr1-Xr2+Xr3-Xr4);

劣種群V=Xi+F(Xr1-Xi+Xr2-Xi);

一般種群V=Xi+F(Xbest-Xi+Xr1-Xr2).

優種群的變異因子F取為0.5，既不影響該子種群的收斂，又降低了該子種群陷入到局部最優的概率，CR 取為0.1［4］.劣種群的 F 在1［4］和0.7之間隨機選擇，CR采用0.9［4］，使該種群在保持種群多樣性的同時還可以進行局部搜索.一般種群作為平衡優種群和劣種群的中間種群，其控制參數應該選取范圍應該在優種群和劣種群中間，因此，F在0.5、0.7、1之間隨機選擇，CR取為0.7，其中F隨機選擇的規則是:在每次選擇操作進行后，如果子代的適應度劣于父代的適應度，那么F在各自的取值范圍內隨機選取一個值作為下次迭代的值.

3 算法仿真分析

為驗證筆者所提出的混合策略差分進化算法的有效性，下面通過4個典型的標準函數:schaffer(f1)、rosenbrock(f2)、rastrigin(f3)和griewank(f4) 進行仿真實驗.其中，函數f1的最優值是1，在距離理論最優值大約3.14的范圍內存在無限多的局部最優點.函數f2的最優值附近存在一個大峽谷，算法很容易陷入里面.f3和f4均是多峰值函數，在它們的搜索范圍內存在大量局部最優點.后面3個函數最優值都是0，4個測試函數的表達式如下:

將本算法記為 HSDE，并與標準遺傳算法(SGA)［9］、采用DE/rand/1/bin策略的DE算法［9］、采用 DE/rand-best/1/bin 策略的DE［9］、采用DE/best/1/bin策略的 DE算法［10］、動態調整子種群個體的 DE算法(NPDE)［10］、雙種群偽并行DE算法(DSPPDE)［9］和動態多種群并行 DE算法(DMPDE)［4］進行比較.

對算法的改進不僅是要求找到函數的最優值，而且要保證算法的效率.因此，如果需要對幾種算法進行比較，可以有兩種比較方式，比較常見的就是保持種群的大小以及迭代次數一樣，另外一種是保持評價次數一樣，這樣算法可以在搜尋最優值的同時不會降低算法的效率，它們所達到的效果是一樣的.筆者參考文獻［9］中所給的參數，對其中的參數進行一定的修改，其它參數不變.筆者將NP全部設置為原文獻中NP的一半，將它們的迭代次數翻倍，和原文獻的評價次數一樣大.每個函數運行30次，通過平均值和標準差進行比較，平均值可以看出算法的搜索能力，標準差可以看出算法的穩定性，比較結果如表1所示.

從表1中可以看出，標準遺傳算法搜索到的結果距離理論最優值還有很大的距離，尤其是對于第二個函數的優化結果顯示算法的收斂精度和穩定性很差.使用單一策略的標準差分進化算法和標準遺傳算法相比，采用DE/rand/1/bin的DE算法對第三個函數的優化結果跟遺傳算法相差比較大，穩定性也不是太好，采用DE/best/1/bin的DE算法對第三個函數的優化結果略劣于遺傳算法，其余的在收斂精度和穩定性上均有不同程度的提高.3個單一策略相比采用DE/rand-best/1/bin的DE算法的優化結果最好，其余2個分別是全局搜索和局部搜索，從中可以看出算法只有兼顧全局搜索和局部搜索才能有比較好的結果.NPDE、DSPPDE和DMPDE算法相較于前面4個算法，從它們的優化結果可以看到這3個算法在收斂精度和穩定性上都有了很大的提高.筆者提出的HSDE算法通過將種群分為3個大小不等的子種群并且每個種群使用不同的變異策略、變異因子和交叉概率，使種群隨時保持最好的全局搜索能力和局部搜索能力.從結果可以看出算法對函數的優化結果有了很大的提升，除了第二個函數以外，其它3個均可以找到理論最優，而且第二個函數的優化結果相比較于其它的算法也有了很大的提高.

表1 8種算法對4個測試函數的實驗結果Tab.1 Experiment results of four test functions under eight algorithms

4 結論

針對傳統差分進化算法易早熟收斂的現象，提出一種混合策略差分進化算法.該算法利用粒子適應度將種群分為多個子種群，每個種群使用不同的策略，同時根據粒子適應度標準差和粒子距離標準差判定每個種群的大小，同時每個種群還使用不同的變異因子和交叉概率，保證種群在搜索的過程中一直能夠保持最好的全局搜索能力和局部搜索能力.從仿真結果看以看到，筆者的算法具有更強的穩定性、通用性和收斂精度.

［1］姜立強，劉光斌，郭錚.分工差分進化算法［J］.小型微型計算機系統，2009，30(7):1302-1304.

［2］高岳林，劉俊梅.一種帶有隨機變異的動態差分進化算法［J］.計算應用，2009，29(10):2719-1922.

［3］池元成，方杰，蔡國飆.中心變異差分進化算法［J］.系統工程與電子技術，2010，32(5):1105-1108.

［4］龍文.一種改進的動態多種群并行差分進化算法［J］.計算機應用研究，2012，29(7):2429-2431.

［5］QIN A K，HUANG V L，SUGANTHAN P N.Differential evolution algorithm with strategy adaptation for global numerical optimization［J］.IEEE Transactions on Evolutionary Computation.2009，13(2):398-417.

［6］盧峰，高立群.基于多種群的自適應差分進化算法［J］.東北大學學報:自然科學版，2010，31(11):1538-1541.

［7］BREST J，GREINER S，BOSKOVIC B，et al.Self-A-dapting control parameters in differential evolution:a comparative study on numerical benchmark problems［J］.IEEE Transactions on Evolutionary Computation.2006，10(6):646-657.

［8］STORN R，PRICE K.Differential evolution-a simple and efficient adaptive scheme for global optimization over continuous spaces［J］.Journal of Global Optimization.1997，11(4):341-359.

［9］吳亮紅，王耀南，周少武，等.雙群體偽并行差分進化算法研究及應用［J］.控制理論與應用，2007，24(3):453-458.

［10］徐松金，龍文.調整子種群個體的差分進化算法［J］.計算機應用，2011，31(11):3101-3103.