張大斌，江 華，徐柳怡，張文生

(1.華中師范大學(xué)信息管理學(xué)院，武漢 430079;2.中國科學(xué)院自動化研究所，北京 100190)

1 概述

差分進(jìn)化(Differential Evolution，DE)算法是由Rainer Stoorn 和Kenneth Price［1］在1995 年共同提出的，它是一種簡單、快速、基于全局的并行直接搜索優(yōu)化算法。其原理簡單、魯棒性強(qiáng)、受控參數(shù)少、易于實(shí)現(xiàn)。由于差分進(jìn)化算法對函數(shù)的可導(dǎo)性甚至連續(xù)性要求較低，近年來被廣泛地應(yīng)用于解決復(fù)雜的、離散的、非線性的優(yōu)化問題，且具有良好的效果。DE 與傳統(tǒng)的遺傳算法(GA)不同，它采用實(shí)數(shù)編碼、基于簡單變異交叉操作和一對一的貪婪競爭生存策略，同時保有獨(dú)特的記憶能力進(jìn)行動態(tài)搜索，并可以不斷調(diào)整其搜索策略，最后使種群個體趨于一致。標(biāo)準(zhǔn)的DE 算法在低維度函數(shù)尋優(yōu)問題上能夠使種群收斂于全局最優(yōu)解，并且尋優(yōu)速度快、求解質(zhì)量高。但是在求解高維度、多峰值這些復(fù)雜函數(shù)問題過程中，很容易出現(xiàn)早熟現(xiàn)象，即算法經(jīng)過多次迭代之后，個體間的差異變小，種群多樣性降低并陷入局部收斂;后期收斂速度較慢并且缺乏穩(wěn)健性。此外，在差分進(jìn)化模式和參數(shù)取值上缺乏普遍的指導(dǎo)原則。為了提高差分進(jìn)化算法搜索和開發(fā)能力及算法的收斂速度，許多學(xué)者對標(biāo)準(zhǔn)的DE 算法進(jìn)行了一些研究和改進(jìn)。如文獻(xiàn)［2］提出一種基于DE 算法和NSGA-Ⅱ的多目標(biāo)混合進(jìn)化算法，確保最優(yōu)解不會丟失并保證解的多樣性。文獻(xiàn)［3］提出一種帶基向量種群的改進(jìn)差分進(jìn)化算法，通過縮小基向量選擇范圍減少迭代次數(shù)。文獻(xiàn)［4］在DE 算法中引入搜索空間擴(kuò)展機(jī)制，有效增強(qiáng)了算法的全局收斂能力，該算法在解決線性系統(tǒng)最優(yōu)近似問題時有一定的優(yōu)勢;文獻(xiàn)［5］提出一種基于適應(yīng)性步長的局部搜索策略來確定合適的縮放比例因子F，從而加速算法全局搜索的進(jìn)程;文獻(xiàn)［6-8］采用反向?qū)W習(xí)方法初始化種群和實(shí)現(xiàn)個體跳變以加快算法的收斂速度。

本文將兩階段變異交叉策略引入到差分進(jìn)化算法中，提出了一種改進(jìn)的差分進(jìn)化算法。該算法采用反向混沌搜索產(chǎn)生初始個體種群，進(jìn)而根據(jù)種群適應(yīng)值將個體種群分為好個體子種群和壞個體子種群，兩階段變異交叉操作依次對不同的子種群采取不同的差分策略，借助種群內(nèi)個體的知識學(xué)習(xí)能力，使種群內(nèi)全局搜索尋優(yōu)信息和局部搜索尋優(yōu)信息協(xié)同在種群間穩(wěn)定擴(kuò)散，以達(dá)到平衡搜索開發(fā)能力和加快收斂的目的，從而提高算法的收斂速度、穩(wěn)健性和通用性。

2 差分進(jìn)化算法

差分進(jìn)化算法(DE)和傳統(tǒng)的遺傳算法(GA)相似，通過交叉、變異和選擇3 種策略對候選種群進(jìn)行反復(fù)的迭代，最終趨于全局最優(yōu)解。但與其他進(jìn)化算法不同的是，DE 是借助種群個體間不同粒子間的加權(quán)差異向量來對另一個體進(jìn)行擾動實(shí)現(xiàn)變異操作，以產(chǎn)生新差異向量，種群中的每個個體都要進(jìn)行干擾。接下來對父代個體和生成的變異個體按照一定的交叉概率進(jìn)行交叉操作生成中間個體;最后采用貪婪淘汰策略在父代個體和中間個體之間進(jìn)行適應(yīng)度一對一比較選擇操作，選擇具有更佳適應(yīng)度的個體作為下一代迭代種群?；静罘诌M(jìn)化算法的主要操作如下［9］:

(1)種群初始化，定義參數(shù)向量個體:

式(1)表示的是第g 次迭代的第i 個個體，隨機(jī)產(chǎn)生的種群規(guī)模為NP，每個個體均有D 個分量。在可行域內(nèi)依據(jù)式(2)隨機(jī)產(chǎn)生初始種群:

其中，xmax，j，xmin，j分別是xi個體中第j 個分量的上下限;randi，j(0，1)為［0，1］區(qū)間的一個隨機(jī)數(shù)。

(2)變異操作，對種群中的每個目標(biāo)向量xgi，隨機(jī)尋找除自身外3 個不同的個體r1，r2，r3(此時需滿足NP≥4)，根據(jù)式(3)，將其中2 個個體的向量差經(jīng)縮放后加到另一個體上，得到變異后的個體

其中，F(xiàn)(通常取0.5)是縮放比例因子，起控制差異變量縮放幅度的作用。

其中，r∈(0，1)為向量第j 個分量對應(yīng)的均勻分布的隨機(jī)數(shù);rd為［1，D］中第i 個向量對應(yīng)的隨機(jī)整數(shù);它的作用是確保中間向量和目標(biāo)向量的差異性。CR∈［0，1］(一般取0.5)是交叉概率，它是另外一個控制參數(shù)，指定變異向量的繼承水平。

其中，f(x)是適應(yīng)值函數(shù)。

(5)收斂判斷，當(dāng)算法運(yùn)行達(dá)到預(yù)定進(jìn)化代數(shù)Gmax或目標(biāo)函數(shù)值VTR 小于某一閾值，即達(dá)到設(shè)定的精度時，結(jié)束整個算法的運(yùn)行，否則將對種群進(jìn)一步執(zhí)行變異、交叉和選擇操作。

此外，還有多種差分策略，習(xí)慣上將差分策略統(tǒng)一標(biāo)記為DE/x/y/z，其中，x 限定當(dāng)前被變異的向量是隨機(jī)的或最佳的;y 表示變異過程采用的差分向量個數(shù);z 表示交叉程序的操作方法，上面敘述的交叉操作就是bin。其他差分進(jìn)化算法DE/best/1/bin 和DE/best/2/bin 策略的變異操作分別如下:

差分進(jìn)化算法流程如圖1 所示。

圖1 差分進(jìn)化算法流程

3 兩階段變異交叉策略

大多數(shù)研究人員專注于選擇合適的控制參數(shù)值，并取得了不錯的成就［10-11］。本文提出了一個新的方向，以改善DE 全局和局部搜索尋優(yōu)能力。首先，種群根據(jù)適應(yīng)值大小排列。然后，它們分為較好子種群、較差子種群。最后，種群進(jìn)行變異、交叉和選擇操作進(jìn)入下一代。本文提出2 個變異交叉階段子種群數(shù)量具有差異性的變異策略，較好子種群的數(shù)量隨著階段的發(fā)展逐級增加，持續(xù)穩(wěn)定加強(qiáng)較好子種群的全局搜索尋優(yōu)能力的學(xué)習(xí)，并同時提高較差子種群的局部搜索尋優(yōu)能力的學(xué)習(xí)，使全局和局部搜索尋優(yōu)信息協(xié)同在種群間持續(xù)穩(wěn)定擴(kuò)散，從而不斷增加種群尋優(yōu)質(zhì)量。

3.1 第一階段

根據(jù)種群的適應(yīng)值大小，將種群分為較好子種群(better)M1 和較差子種群(worse)M2。

變異操作，對于較好子種群，選取3 個不同粒子，一個是較差子種群的最優(yōu)粒子另外2 個不同粒子來自較好子種群，分別為具體公式DE/wbest/1 如下:

變異操作，對于較差子種群，選取3 個不同粒子，一個是種群最優(yōu)粒子，另外2 個不同粒子來自較差子種群，分別為具體公式如下:

3.2 第二階段

變異操作，對于較好子種群，選取3 個不同粒子，一個是較差子種群的最優(yōu)粒子，另外2 個不同粒子來自較好子種群，分別為具體公式DE/wbest/1 如下:

變異操作，對于較差子種群，選取3 個不同粒子，一個是種群最優(yōu)粒子另外2 個不同粒子來自較差子種群，分別為具體公式如下:

4 基于兩階段變異交叉策略的差分進(jìn)化

4.1 反向混沌搜索的種群初始化

由于算法在進(jìn)化初期缺少先驗(yàn)知識，即只能在可行域中隨機(jī)產(chǎn)生初始種群，而尋優(yōu)時間往往又與初始種群的質(zhì)量有關(guān)，即個體到全局最優(yōu)值的距離密切。因此，針對算法存在進(jìn)化初期收斂速度慢的不足，利用反向?qū)W習(xí)方法［12］和混沌搜索［13］有機(jī)結(jié)合產(chǎn)生初始種群。首先利用混沌序列的隨機(jī)性、遍歷性和初值敏感性來提高初始隨機(jī)數(shù)的質(zhì)量?，F(xiàn)在大多數(shù)都采用Logistis 映射來產(chǎn)生混沌序列，可以用下式描述:

其中，xi表示混沌序列變量在第i 次迭代時的值;v是控制變量常數(shù)。當(dāng)v 取值范圍為［3.56，4.0］，xi就是一個混沌變量。這時系統(tǒng)處于完全混沌狀態(tài)，序列可以無重復(fù)。然后借助反向?qū)W習(xí)方法，為每個混沌序列產(chǎn)生的個體生成相應(yīng)的反向個體，接著合并上述步驟產(chǎn)生的2 個種群，并對所有個體按適應(yīng)值大小排序，最后選擇其中相應(yīng)規(guī)模的較優(yōu)個體組成初始種群，以提高算法的收斂速度。反向混沌搜索過程如下:

Step 1混沌搜索產(chǎn)生規(guī)模為NP 的種群P，其個體為xi=(xi1，xi2…，xiD)，i=1，2，…，N，且每個分量xij∈［aj，bi］，j=1，2，…，D。

Step 2產(chǎn)生種群P 對應(yīng)的反向種群OP，其個體其中，

Step 3合并種群P 和OP，按照適應(yīng)值的大小進(jìn)行排序，從中選取規(guī)模為NP 的較優(yōu)個體組成算法的初始種群。

4.2 融合兩階段變異交叉策略的差分進(jìn)化算法

融合兩階段變異交叉策略的差分進(jìn)化算法(TMCDE)，采取兩階段子種群并行變異交叉進(jìn)化策略。初始種群根據(jù)適應(yīng)值分為較好和較差2 個子種群。較好子種群全局搜索尋優(yōu)能力相對不足，較差子種群局部搜索尋優(yōu)能力相對不足。因此，在種群進(jìn)化尋優(yōu)階段，對較好和較差2 個子種群分別采取不同的變異交叉策略，使種群全局和局部搜索尋優(yōu)能力并行發(fā)展。

第一階段:較好子種群規(guī)模M1，較差子種群規(guī)模M2。較好子種群變異策略采用式(8)，可知，變異個體由較差子種群個體和較好子種群中2 個互不相同的隨機(jī)個體組成，增強(qiáng)較好子種群的多樣性。較差子種群變異策略采用式(9)，可知，變異個體由個體和較差子種群中2 個互不相同的隨機(jī)個體組成，提高了較差子種群的局部搜索尋優(yōu)能力、搜索精度和收斂速度。但在一定程度上會加大算法收斂速度過快，容易陷入局部最優(yōu)點(diǎn)的可能性。較好子種群M1 采取交叉1 策略，目的是保持當(dāng)前最優(yōu)個體的引導(dǎo)作用的同時，相應(yīng)增加種群的多樣性。較差子種群M2 采取交叉2 策略，目的是提高較差子種群的尋優(yōu)質(zhì)量。第一階段的目的是為了縮小種群內(nèi)個體的差異性，使種群相對更加集中。

第二階段:較好子種群規(guī)模M3(M3 ＞M1)，較差子種群規(guī)模M4。較好子種群變異策略采用式(10)，可知，變異個體由較差子種群個體和較好子種群中2 個互不相同的隨機(jī)個體組成，較第一階段進(jìn)一步提高了種群的多樣性和全局搜索能力。較差子種群采用式(11)，可知，變異個體由個體和較差子種群中2 個互不相同的隨機(jī)個體組成，較第一階段繼續(xù)提高種群的局部搜索能力、搜索精度和收斂速度。種群的交叉策略同第一階段一樣。第二階段的目的是在增加對較好子種群個體進(jìn)行擾動的同時，能促使種群向新產(chǎn)生的最優(yōu)個體靠攏，從而起到邊擾動種群，邊聚集種群的作用，進(jìn)而不斷提升種群尋優(yōu)的質(zhì)量。

為平衡全局搜索尋優(yōu)能力和收斂速度之間的矛盾。在2 個階段，種群均獨(dú)立進(jìn)化若干代(一般是5 代)，有利于全局和局部搜索尋優(yōu)信息在種群間的穩(wěn)定傳播。第一階段，2 個子種群第一次獨(dú)立并行進(jìn)化完成后，重新融合成一個新的種群，根據(jù)適應(yīng)值大小再次將新種群分為較好和較差2 個子種群，并持續(xù)進(jìn)化5 代，綜合提高了種群全局和局部尋優(yōu)的搜索能力。第二階段在第一階段種群進(jìn)化發(fā)展的基礎(chǔ)上，相應(yīng)增加了較好子種群的個數(shù)，持續(xù)加強(qiáng)較好子種群的全局搜索尋優(yōu)能力，同時一定程度上維持了種群的局部搜索尋優(yōu)能力，進(jìn)一步加強(qiáng)全局和局部搜索尋優(yōu)信息協(xié)同在種群內(nèi)的均衡擴(kuò)散。

4.3 算法的實(shí)現(xiàn)過程

算法的實(shí)現(xiàn)過程如下:

Step 1種群初始化。按照反向混沌搜索方法初始化種群，產(chǎn)生規(guī)模為NP 的初始種群。

Step 2將種群按適應(yīng)值分為較好子種群M1 和較差子種群M2。

Step 3對較好子種群M1 的個體，采用DE/wbest/1/bin 的變異策略和交叉1 策略進(jìn)行差分進(jìn)化。

Step 4對較差子種群的M2 個體，采用DE/best/1/bin 的變異策略和交叉2 策略進(jìn)行差分進(jìn)化。

Step 5重新產(chǎn)生較好子種群和較差子種群，并跳到Step3，持續(xù)進(jìn)行5 代，重新開始子種群的并行搜索。

Step 6合并2 個子種群，并重新產(chǎn)生較好子種群M3 和較差子種群M4。

Step 7對較好子種群M3 的個體，采用DE/wbest/1/bin 的變異策略和交叉1 策略進(jìn)行差分進(jìn)化。

Step 8對較差子種群的M4 個體，采用DE/best/1/bin 的變異策略和交叉2 策略進(jìn)行差分進(jìn)化。

Step 9重新產(chǎn)生較好子種群和較差子種群，并跳到Step7，持續(xù)進(jìn)行5 代，重新開始子種群的并行搜索。

Step 10合并2 個子種群，并且按照適應(yīng)值排序。若當(dāng)前迭代次數(shù)小于最大迭代次數(shù)，則轉(zhuǎn)Step2，否則轉(zhuǎn)Step10。

Step 11結(jié)束尋優(yōu)，輸出結(jié)果。

兩階段變異交叉差分進(jìn)化算法流程如圖2所示。

圖2 兩階段變異交叉差分進(jìn)化算法流程

5 函數(shù)優(yōu)化中的應(yīng)用仿真與結(jié)果分析

5.1 函數(shù)仿真

由于不同差分策略的進(jìn)化算法對多數(shù)單峰低維函數(shù)均有較好尋優(yōu)效果，為測試所提出的TMCDE 算法的性能，主要選取了5 個具有不同特點(diǎn)的函數(shù)作為測試函數(shù)，根據(jù)所選的指標(biāo)對算法的性能進(jìn)行測試，各測試函數(shù)如表1 所示。

為考察TMCDE 算法的性能，選取了DE/rand/1，DE/best/1 及DE/best/2 這些差分策略的進(jìn)化算法作比較，對測試函數(shù)進(jìn)行尋優(yōu)仿真。差分進(jìn)化算法的參數(shù)設(shè)置主要由差分策略和待求解問題決定，其主要涉及縮放因子F 和交叉概率CR 這2 個參數(shù)。為了確保算法尋優(yōu)的可比性，本文統(tǒng)一選取種群規(guī)模NP=100，M1=30，M3=40，{F=0.5，CR=0.9}，此外，TMCDE 算法中2 個階段信息傳遞間隔均為5，對30 維函數(shù)尋優(yōu)，迭代次數(shù)100 次，并獨(dú)立運(yùn)行30次，尋優(yōu)結(jié)果如表2 所示。

表1 選取的測試函數(shù)

5.2 函數(shù)的實(shí)驗(yàn)結(jié)果分析

從表2、圖3 所示的簡單30 維單模態(tài)Sphere 函數(shù)的優(yōu)化結(jié)果可以看出，各個算法的最優(yōu)值、最差值、平均值和標(biāo)準(zhǔn)差結(jié)果顯示，TMCDE 算法在單模態(tài)函數(shù)上具有較好的尋優(yōu)能力，得到的優(yōu)化結(jié)果明顯優(yōu)于其他算法。從收斂曲線可以看出，TMCDE 算法性能最好，能夠持續(xù)、有效地搜索函數(shù)全局最優(yōu)點(diǎn)。前期性能良好、收斂速度快，后期能夠在最優(yōu)極值點(diǎn)附近進(jìn)行細(xì)致搜索。從表2、圖4 中對于30 維多模態(tài)Rantrigin 函數(shù)，可以看出TMCDE 算法和各種差分策略算法都能找到函數(shù)的最優(yōu)點(diǎn)，但是TMCDE 算法表現(xiàn)出了較好的全局收斂性和健壯性，收斂曲線在前期就能夠迅速地接近于最優(yōu)點(diǎn)，而其他差分策略收斂速度較慢，需要較多的迭代次數(shù)才能收斂到極值點(diǎn)附近，另外在圖中DE 算法很容易停滯于局部極值點(diǎn)。從表2、圖5 所示的復(fù)雜單模態(tài)Rosenbrock 函數(shù)優(yōu)化結(jié)果來看，TMCDE 算法能夠?qū)ふ业嚼碚撟顑?yōu)點(diǎn)，并且本文算法自尋優(yōu)早期既有較好的收斂速度，又可以通過相對較少的迭代次數(shù)找到正確的搜索方向，從而保持繼續(xù)下降，能夠快速地找到最優(yōu)極值點(diǎn)，并且DE/rand/1 算法目標(biāo)函數(shù)值均大于0.01。表2、圖6 顯示了30 維Schaffer 函數(shù)的優(yōu)化結(jié)果，雖然后期各算法均陷入了局部極值點(diǎn)，但是TMCDE 算法能保持正確的搜索方向，持續(xù)地尋找全局最優(yōu)點(diǎn)，在搜索后期仍能夠保持較好的種群多樣性，算法性能顯著。表2、圖7 顯示了30 維Step 函數(shù)的優(yōu)化結(jié)果，TMCDE 算法表現(xiàn)出了較好的全局尋優(yōu)能力，收斂曲線在前期就能夠迅速地接近并且達(dá)到最優(yōu)點(diǎn)，而其他DE 算法需要較多迭代次數(shù)才能收斂到極值點(diǎn)附近。綜上所述，本文算法TMCDE 無論在單模態(tài)還是多模態(tài)優(yōu)化問題中均表現(xiàn)出了較好的尋優(yōu)結(jié)果和收斂速度，效果顯著。

表2 運(yùn)行30 次30 維函數(shù)的優(yōu)化結(jié)果

圖3 Rosenbrock 函數(shù)收斂曲線

圖4 Schaffer 函數(shù)收斂曲線

圖5 Step 函數(shù)收斂曲線

圖6 Schaffer 函數(shù)收斂曲線

圖7 Step 函數(shù)收斂曲線

6 結(jié)束語

本文提出了一種基于兩階段不同變異交叉策略的差分進(jìn)化算法，通過在差分進(jìn)化算法中引入反向混沌搜索初始化種群方法和兩階段不同變異交叉策略，使算法全局快速收斂，并提高了算法收斂精度。函數(shù)仿真表明，TMCDE 算法具有較好的收斂速度、優(yōu)化精度和魯棒性。然而，在引進(jìn)兩階段變異交叉策略的同時也增加了算法參數(shù)的設(shè)置，如M1、M2、M3、M4。本文雖已借助函數(shù)仿真對算法進(jìn)行了分析，但算法的參數(shù)設(shè)置在解決不同的實(shí)際問題時仍存在一定的難度。因此，在接下來的研究中，可以對算法的各個參數(shù)的性能進(jìn)行比較分析，以降低參數(shù)設(shè)置的復(fù)雜度，增加搜索過程的隨機(jī)性，從而提高整個算法的性能。由于差分進(jìn)化算法的通用性強(qiáng)，易與其他算法相結(jié)合，諸如與人工免疫網(wǎng)絡(luò)、灰色預(yù)測預(yù)警等相結(jié)合，進(jìn)行模型參數(shù)優(yōu)化，在提高預(yù)測精度上有較好的效果，能夠更好地解決現(xiàn)實(shí)中的工程管理問題。

［1］Storn R，Price K.Differential Evolution——A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces［J］.Journal of Global Optimization，1997，11(4):58-64.

［2］王 林，陳 璨.一種基于DE 算法和NSGA-II 的多目標(biāo)混合進(jìn)化算法［J］.運(yùn)籌與管理，2010，19(6):46-50.

［3］姜立強(qiáng)，強(qiáng) 洪.帶基向量種群的改進(jìn)差分進(jìn)化算法［J］.計(jì)算機(jī)工程，2012，38(3):9-11.

［4］Cheng S L，Hwang C.Optimal Approximation of Linear Systems by a Differential Evolution Algorithm［J］.IEEE Transactions on Systems，Man，and Cybernetics，2001，31(6):698-707.

［5］Chiou J P，Chang C F，Su C T.Variable Scaling Hybrid Deferential Evolution for Solving Network Reconfiguration of Distribution Systems ［J］.IEEE Transactions on Power Systems，2005，20(2):668-674.

［6］Rahnamayan S，Tizhoosh H R.Opposition-based Differential Evolution ［J］.IEEE Transactions on Evolutionary Computation，2008，12(1):64-69.

［7］Wang Yuanhui，Wang Xiukun，Teng Hongfei.Oppositionbased Cooperative Co-evolutionary Differential Evolution Algorithm with Gaussian Mutation for Simplified Satellite Module Optimization ［J］.Information Technology Journal，2012，11(1):67-75.

［8］劉 罡，李元香，鄭 昊.保存基因的2-Opt 一般反向差分演化算法［J］.小型微型計(jì)算機(jī)系統(tǒng)，2012，33(1):115-120.

［9］楊添柔.連續(xù)域優(yōu)化問題的差分進(jìn)化算法研究［D］.武漢:華中師范大學(xué)，2013.

［10］戈劍武，祁榮賓，錢 鋒，等.一種改進(jìn)的自適應(yīng)差分進(jìn)化算法［J］.華東理工大學(xué)學(xué)報(bào):自然科學(xué)版，2009，35(4):600-605.

［11］王海倫，余世明，鄭秀蓮.自適應(yīng)差分進(jìn)化算法及其在參數(shù)估計(jì)中的應(yīng)用［J］.計(jì)算機(jī)工程，2012，38(5):202-207.

［12］汪慎文，丁立新，謝承旺，等.應(yīng)用精英反向?qū)W習(xí)策略的混合差分進(jìn)化算法［J］.武漢大學(xué)學(xué)報(bào):理學(xué)版，2013，59(2):111-116.

［13］盧有麟，周建中.基于混沌搜索的自適應(yīng)差分進(jìn)化算法［J］.計(jì)算機(jī)工程與應(yīng)用，2008，44(10):31-33.