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

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

0 引言

最優(yōu)化是人們在實際生活中經(jīng)常遇到的問題，它們可以通過數(shù)學(xué)方法抽象成函數(shù)求最優(yōu)解問題.隨著實際工程中的問題從線性到非線性的轉(zhuǎn)變，出現(xiàn)復(fù)雜性增加，極值增多以及建模困難等問題，智能優(yōu)化算法已經(jīng)逐漸成為相關(guān)學(xué)科的一個主要研究目標(biāo)和研究方向.因此，大量國內(nèi)外學(xué)者對智能優(yōu)化算法進(jìn)行了研究改進(jìn).

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

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

1 標(biāo)準(zhǔn)差分進(jìn)化算法及其分析

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

智能優(yōu)化算法主要解決的是傳統(tǒng)優(yōu)化算法不能解決的非線性優(yōu)化問題.非線性最小化優(yōu)化問題描述如下:

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

對第G代中的每一個個體xi進(jìn)行變異操作，得到與其相對應(yīng)的變異個體vi，即

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

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

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

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

將實驗向量Ui(G)與目標(biāo)向量xi(G)的目標(biāo)函數(shù)值進(jìn)行比較，選擇較優(yōu)的個體進(jìn)入下一代，選擇操作如下

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

2 算法描述

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

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

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

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

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

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

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

3 算法仿真分析

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

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

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

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

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

4 結(jié)論

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

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

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

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

［4］龍文.一種改進(jìn)的動態(tài)多種群并行差分進(jìn)化算法［J］.計算機應(yīng)用研究，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］盧峰，高立群.基于多種群的自適應(yīng)差分進(jìn)化算法［J］.東北大學(xué)學(xué)報:自然科學(xué)版，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ìn)化算法研究及應(yīng)用［J］.控制理論與應(yīng)用，2007，24(3):453-458.

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