基于兩階段變異交叉策略的差分進化算法

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

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

1 概述

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

本文將兩階段變異交叉策略引入到差分進化算法中，提出了一種改進的差分進化算法。該算法采用反向混沌搜索產生初始個體種群，進而根據種群適應值將個體種群分為好個體子種群和壞個體子種群，兩階段變異交叉操作依次對不同的子種群采取不同的差分策略，借助種群內個體的知識學習能力，使種群內全局搜索尋優信息和局部搜索尋優信息協同在種群間穩定擴散，以達到平衡搜索開發能力和加快收斂的目的，從而提高算法的收斂速度、穩健性和通用性。

2 差分進化算法

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

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

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

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

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

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

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

其中，f(x)是適應值函數。

(5)收斂判斷，當算法運行達到預定進化代數Gmax或目標函數值VTR 小于某一閾值，即達到設定的精度時，結束整個算法的運行，否則將對種群進一步執行變異、交叉和選擇操作。

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

差分進化算法流程如圖1 所示。

圖1 差分進化算法流程

3 兩階段變異交叉策略

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

3.1 第一階段

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

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

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

3.2 第二階段

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

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

4 基于兩階段變異交叉策略的差分進化

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

由于算法在進化初期缺少先驗知識，即只能在可行域中隨機產生初始種群，而尋優時間往往又與初始種群的質量有關，即個體到全局最優值的距離密切。因此，針對算法存在進化初期收斂速度慢的不足，利用反向學習方法［12］和混沌搜索［13］有機結合產生初始種群。首先利用混沌序列的隨機性、遍歷性和初值敏感性來提高初始隨機數的質量。現在大多數都采用Logistis 映射來產生混沌序列，可以用下式描述:

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

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

Step 2產生種群P 對應的反向種群OP，其個體其中，

Step 3合并種群P 和OP，按照適應值的大小進行排序，從中選取規模為NP 的較優個體組成算法的初始種群。

4.2 融合兩階段變異交叉策略的差分進化算法

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

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

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

為平衡全局搜索尋優能力和收斂速度之間的矛盾。在2 個階段，種群均獨立進化若干代(一般是5 代)，有利于全局和局部搜索尋優信息在種群間的穩定傳播。第一階段，2 個子種群第一次獨立并行進化完成后，重新融合成一個新的種群，根據適應值大小再次將新種群分為較好和較差2 個子種群，并持續進化5 代，綜合提高了種群全局和局部尋優的搜索能力。第二階段在第一階段種群進化發展的基礎上，相應增加了較好子種群的個數，持續加強較好子種群的全局搜索尋優能力，同時一定程度上維持了種群的局部搜索尋優能力，進一步加強全局和局部搜索尋優信息協同在種群內的均衡擴散。

4.3 算法的實現過程

算法的實現過程如下:

Step 1種群初始化。按照反向混沌搜索方法初始化種群，產生規模為NP 的初始種群。

Step 2將種群按適應值分為較好子種群M1 和較差子種群M2。

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

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

Step 5重新產生較好子種群和較差子種群，并跳到Step3，持續進行5 代，重新開始子種群的并行搜索。

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

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

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

Step 9重新產生較好子種群和較差子種群，并跳到Step7，持續進行5 代，重新開始子種群的并行搜索。

Step 10合并2 個子種群，并且按照適應值排序。若當前迭代次數小于最大迭代次數，則轉Step2，否則轉Step10。

Step 11結束尋優，輸出結果。

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

圖2 兩階段變異交叉差分進化算法流程

5 函數優化中的應用仿真與結果分析

5.1 函數仿真

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

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

表1 選取的測試函數

5.2 函數的實驗結果分析

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

表2 運行30 次30 維函數的優化結果

圖3 Rosenbrock 函數收斂曲線

圖4 Schaffer 函數收斂曲線

圖5 Step 函數收斂曲線

圖6 Schaffer 函數收斂曲線

圖7 Step 函數收斂曲線

6 結束語

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

［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 的多目標混合進化算法［J］.運籌與管理，2010，19(6):46-50.

［3］姜立強，強 洪.帶基向量種群的改進差分進化算法［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］.小型微型計算機系統，2012，33(1):115-120.

［9］楊添柔.連續域優化問題的差分進化算法研究［D］.武漢:華中師范大學，2013.

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

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

［12］汪慎文，丁立新，謝承旺，等.應用精英反向學習策略的混合差分進化算法［J］.武漢大學學報:理學版，2013，59(2):111-116.

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