一種自適應多策略差分進化算法及其應用

徐斌，陶莉莉，程武山

?

一種自適應多策略差分進化算法及其應用

徐斌1，陶莉莉2，程武山1

（1上海工程技術大學機械工程學院，上海201620；2上海第二工業大學工學部，上海 201209）

針對差分進化算法由于固定參數設置而易早熟或陷入局部最優的問題，提出了一種自適應多策略差分進化算法（SMDE）。該方法以基本差分進化為框架，首先引入一個變異策略候選集合，一個縮放因子候選集合和一個交叉參數候選集合，然后在搜索過程中，以過去的搜索信息為基礎，自適應地為下一時刻進化群體中的每個個體從候選集合中選擇一組合適的變異策略和控制參數，以便在不同的進化時刻設置合適的變異策略和控制參數。對10個常用的標準測試函數進行優化計算，并與其他算法的結果進行了比較，實驗結果表明，SMDE具有較好的搜索精度和更快的收斂速度。將SMDE用于化工過程動態系統不確定參數估計問題，實驗結果表明該算法能較好地處理實際工程優化問題。

差分進化算法；自適應；多策略；動態系統；參數估計

引 言

差分進化算法（differential evolution，DE）是由Storn等[1]提出的新型啟發式搜索算法，具有結構簡單、可調參數少、魯棒性強等特點，在求解各類復雜數值優化問題以及實際工程優化問題方面取得了滿意的效果。但是，Pan等[2]認為，DE的搜索性能很大程度上取決于其子代生產策略（變異策略和交叉策略）以及對應的控制參數（種群規模，縮放因子和交叉參數CR），所以在使用DE求解問題時，首先需要選擇合適的進化策略，然后確定對應的控制參數，才能使得算法效果較優[3]。因此，如何為DE設置有效的進化策略以及對應的控制參數，在提高算法收斂速度和求解精度的同時，防止陷入局部最優解，已經成為當前DE研究領域的熱點。

在差分進化算法參數配置方面，研究者們總結了一系列有效的設置經驗[4]，其中最為直接和有效的方案就是設計一種自適應調整方案，如Liu等[5]根據模糊原理，提出關于參數和CR的模糊適應性推理規則。Brest等[6]將控制參數編碼到個體染色體中，然后根據搜索過程的反饋信息，自適應地調整參數和CR，提出了jDE算法。Zhang等[7]根據子代與父代之間的競爭情況、歷史進化記錄以及統計學習規則提出自動調整和CR的JADE方法。Mallipeddi等[8]將變異策略和控制參數看成整體，提出一種集成學習方法。除了研究和CR之外，研究者們對種群規模也感興趣。Teo[9]使用絕對和相對的編碼方法，提出了能自動調整、和CR的DESAP算法。Zhu等[10]根據搜索狀態，提出能自動調整進化種群的APTS策略。楊衛東等[11]提出根據種群平均適應度方差非線性改變交叉概率因子的方法，在種群多樣性不同時分別采用不同的調整策略。

最近，研究者們對DE進化策略的自適應調整產生了興趣。因為這類策略能夠在不同的進化時刻采用不同的個體重組策略。Qin等[12]根據先前的成功搜索經驗自適應地調整當前的子代個體生成策略及其對應的參數和CR，提出了SaDE算法。Wang等[13]提出了結合幾種有效的子代產生策略和合適的進化參數來提高DE性能的思想。Gong等[14]提出一種能自動為個體選擇合適的變異策略的策略選擇機制，并將其結合到JADE算法中，效果明顯。向萬里等[15]設計交叉概率控制參數庫、變異尺度參數庫及差分變異策略庫，并采用不同的機制產生對應的參數值。Wu等[16]將進化種群分為indicator種群和reward種群兩種類型，并采用3種不同的變異策略和類似JADE中自適應參數調整策略。為了提高計算效率，Gong等[17]將多策略模型和代理模型相結合，提出一種基于較為實用的多算子進化算法模型，在求解復雜單目標問題方面具有優勢。

結合控制參數和進化策略自適應調整這兩方面的優勢，本文提出一種自適應多策略差分進化算法（self-adaptive differential evolution algorithm with multiple strategies，SMDE）。本方法以經典DE算法為框架，為了充分利用進化群體在迭代過程中的有用信息，增強算法搜索能力，引入一個變異策略集合、一個縮放因子集合以及一個交叉參數集合。然后在迭代計算過程中，根據過去的搜索信息，動態自適應地為種群中每個個體從這3個集合中選擇合適的變異策略以及控制參數和CR，在保證搜索效率的同時提高搜索精度，防止陷入局部最優。

1 基本DE算法

rand/1

best/1

current-to-best/1

rand/2

best/1

其中，1、2、3、4、5是區間[1]內與不等的隨機整數，且滿足兩兩互不相等。縮放因子是一個正常數，通常被限定在區間[0 1]之內。變異之后得到的新個體與父代個體進行交叉操作，交叉操作過程為

2 改進差分進化算法

本文提出的SMDE算法的一個重要特點是以過去成功的經驗為基礎，引入一個變異策略集合、一個縮放因子集合以及一個交叉參數集合。然后在迭代計算過程中，根據搜索信息自適應地從集合中選擇參數參與計算。

2.1 變異策略自適應調整策略

隨著DE的不斷發展，研究者們提出了許多不同類型的變異策略，但是，至今仍然沒有一種理論上的變異策略選擇方案，因此，在DE中采用多變異策略得到許多研究者們的青睞[12-15]。為了平衡SMDE算法在不同階段的探索和開發能力，選擇rand/1、rand/2、current-to-best/1和best/2這4種不同類型的變異策略構成一個變異策略候選集合（SS）。在進化過程中，為種群中每個個體從集合SS中動態選擇合適的變異策略，其自適應調整方式為

2.2 控制參數自適應調整策略

在確定變異策略之后，需要確定一組合適的控制參數和CR。SMDE參數控制策略基本思想就是以這些經驗區間為基礎，在區間中選擇一些具有代表性的離散值構成候選參數集合，然后在不同的進化時刻，從參數集合中選擇合適的值參與計算。

對于參數，在區間[0.4 1.2]中，以0.1為步長選擇9個值構成候選集合FS，然后在進化過程中，根據搜索信息為種群中每個個體動態選擇合適的值，其自適應調整方式為

對于參數CR，在區間[0.0 1.0]中，以0.2為步長選擇6個值構成CR候選集合CRS，然后在進化過程中，根據搜索信息為種群中每個個體動態選擇合適的CR值，其自適應調整方式為

從上面的參數調整策略可以看出，該調整策略類似于jDE算法的調整策略[7]，但是，它們是不一樣的。首先，在SMDE中有變異策略的調整方案，而jDE中沒有；其次，SMDE從有限集合中選擇潛在參數，而jDE從給定的連續區間中隨機生成控制參數。

2.3 算法基本流程

結合基本DE算法的框架以及上述介紹的變異策略和控制參數自適應調整策略，提出自適應多策略差分進化算法（SMDE），具體實現過程如下。

（1）算法初始化。設定種群規模為，算法停止條件max_nfes，變異策略候選集合SS，縮放因子候選集合FS，交叉參數候選集合CRS。

（2）種群初始化。設初始迭代步數=0，在搜索范圍內隨機初始化初始種群，，并為種群中每個個體從3個候選集合中分別隨機選擇一個變異策略S，F和CR。

（4）按照式（7）執行選擇操作。

（5）根據式（8）～式（10）調整和更新每個個體下一進化時刻對應的變異策略，和。

（6）判斷算法是否滿足終止條件。若滿足，則算法結束，輸出當前最優值為最終結果；若不滿足，令，并轉至步驟（3）。

3 實驗設置與分析

3.1 SMDE算法性能測試

為了驗證SMDE算法的有效性，選擇10個常用的基準測試函數進行實驗仿真[18]。這10個測試函數中，有單峰函數，也有多峰函數，有的函數最優值附近有大量局部極小值，因此具有代表性。為了方便對實驗結果進行通知，選擇最小誤差、取得固定誤差值所需要的函數評價次數、成功率以及收斂曲線圖4個常用的技術指標進行結果分析[14]。

為了方便進行結果比較和分析，選擇兩種具有代表性的自適應差分進化算法（jDE[6]和SaDE[12]）進行比較。對于SMDE，取種群規模，對于jDE與SaDE，其參數分別選擇對應文獻建議值，算法停止條件為函數評價次數max_nfes3×105次。3種算法獨立運行25次后，統計誤差平均值與標準方差，其統計結果見表1。

從表1可以看出，對于問題sph、ros和wht問題，SMDE結果優于jDE和SaDE，對于問題ack和sal，SMDE表現較弱，對于其他問題，3種算法都能取得較好的優化結果。

表2給出了優化過程中最小誤差值小于10-8時，25次獨立運行所需要的平均目標函數評價次數以及成功率。從表格中可以看出，對于大多數問題，如問題sph、ack、ras、pn1以及pn1等，雖然3種算法都能在最大迭代次數范圍內讓誤差值達到10-8，但是，SMDE所需要的函數評價次數更少，收斂速度更快。

表1 各算法運行25次統計結果

表2 成功率與平均迭代次數統計結果

為了更加直觀地展示算法求解過程，圖1給出了10個測試函數收斂曲線。從圖1可以看出，對于問題sph、ros、grw和wht，SMDE算法表現較好，對于問題ras和sch，SMDE差于jDE，但收斂速度好于SaDE，而對于其他問題，3種算法收斂性能相當。

圖1 函數目標函數收斂曲線

從上面的結果分析可知，SMDE算法相比jDE和SaDE具有優勢，是一種有效的求解全局數值優化問題的方法。

3.2 參數自適應策略分析

為了分析SMDE算法中參數自適應策略的有效性，選擇ros和wht這兩個代表性函數，對其參數自適應搜索過程進行具體分析。

圖2給出了在求解ros函數過程中，最優結果為平均值對應的那次運行過程變異策略、縮放因子以及交叉參數概率變化曲線。從圖可以看出，在求解該函數時，變異策略current-to-best/1，縮放因子0.4以及交叉參數1.0使用概率較高，使用這種組合求解效率較高。

圖3給出了在求解wht函數過程中，變異策略、縮放因子以及交叉參數概率變化曲線。從圖3可以看出，在進化前期，變異策略rand/1占優勢，但是到后期，current-to-best/1策略占優勢。對于縮放因子，進化前期多個參數使用概率相差不大，但是到了后期，參數0.4使用較多。對于交叉參數，進化前期參數0.0使用概率較大，但是后期參數1.0使用較多。

圖2 函數Fros求解過程參數概率變化曲線

圖3 函數Fwht求解過程參數概率變化曲線

從上面的結果分析可知，本文提出的參數自適應策略是一種參數調整方案，使用該方案可以使算法能夠在不同的進化時刻，根據前期搜索信息，選擇最為合適的進化策略及其對應的控制參數。

3.3 動態系統參數辨識及結果分析

通過求解10個基準函數，證明了SMDE的優化性能，為了進一步驗證其在處理工程優化問題時的有效性，將其用于甲醇轉化為烴類物質的反應模型不確定參數最優估計。甲醇轉化為各不同烴類的反應模型表示形式為[19-20]

式中，A為氧化劑，B為甲醇，C為烴類物質，P為鏈烷烴、芳香族化合物以及其他產品。假定上述所有反應均為絕熱條件下的一階反應，碳烯濃度為常數，總的反應模型表示為

式中，1、2、3為A、C和P的濃度；是待辨識的模型參數。為了求解擬合模型，表3給出了實際生產過程產物A、C和P的17組濃度測量值。

表3 不同時刻y的測量值

在系統模型結構已知情況下，根據實際生產過程觀測數據，取系統誤差平方和為優化目標函數

表4給出了過程產物A、C和P模型輸出值與觀測值之間的誤差值（模型輸出值-測量值）。從表4中數值可以看出，大多數時刻濃度誤差值都比較小，最小可達1.19×10-4，最大值為3.98×10-2。圖4給出了系統模型輸出數值與觀測值擬合結果。表5給出了rSQP[20]，CPEMR[21]，PNSGA[19]，APSO[22]和SMDE 5種算法求解該動態模型的結果。從結果可以看出，SMDE算法得到的目標函數值較好，雖然對于某些成分值，如相對于APSO算法，A和P產物誤差值較大，但是C物質誤差值較低，總體目標函數值較好。可以看出，本文提出的SMDE算法是一種有效求解動態系統參數估計問題的方法。

表4 3種產物不同時刻誤差值

圖4 擬合結果與觀測值比較

表5 5種算法的實驗結果比較

4 結 論

提出一種新的基于多進化策略的自適應差分進化算法并用于求解化工過程動態模型參數辨識問題，結論如下。

（1）本文引入變異策略、縮放因子和交叉參數的候選集合，算法能針對不同的優化問題在不同的求解階段，根據過去的搜索信息從候選集合中選擇有效的變異策略及其對應的控制參數。

（2）將SMDE算法用于求解復雜標準測試函數，結果表明，與代表性自適應差分進化算法相比，SMDE算法能有效提高算法搜索速度和解精度，防止陷入局部最優值。

（3）將SMDE算法應用于甲醇反應動態模型不確定參數估計，結果表明，SMDE算法在求解化工過程動態模型系統參數估計問題具有較高的求解精度和較好的應用前景。

（4）本文SMDE算法未對交叉策略進行深入研究，都是采用最基本的二項交叉算子，未來研究工作將關注交叉策略的自適應調整策略，進一步增強算法的魯棒性。

符 號 說 明

A——氧化劑 B——甲醇 C——烴類物質 CR——交叉參數 CRS——交叉參數候選集合 F——縮放因子 FS——縮放因子候選集合 max_nfes——算法最大迭代次數 N——種群規模 n——優化問題維度 P——鏈烷烴、芳香族化合物以及其他產品 rand[0,1]——[0,1]之間的隨機數 randi(·)——隨機整數選擇函數 S——變異策略 SS——變異策略候選集合 u——交叉后個體 v——變異后個體 x——種群個體 y1——氧化劑濃度 y2——烴類物質濃度 y3——鏈烷烴、芳香族化合物以及其他產品濃度 θ——待辨識模型參數

[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): 341-359.

[2] PAN Q K, SUGANTHAN P N, WANG L,. A differential evolution algorithm with self-adapting strategy and control parameters [J]. ComputersOperations Research, 2011, 38 (1): 394-408.

[3] QIAN F, XU B, QI R,. Self-adaptive differential evolution algorithm with α-constrained domination principle for constrained multi-objective optimization[J] Soft Computing, 2012, 16 (8): 1353-1372.

[4] 劉波, 王凌, 金以慧. 差分進化算法研究進展 [J]. 控制與決策, 2007, 22 (7): 721-729. LIU B, WANG L, JIN Y H. Advances in differential evolution [J]. Control and Decision, 2007, 22 (7): 721-729.

[5] LIU J, LAMPINEN J. A fuzzy adaptive differential evolution algorithm [J]. Soft Computing, 2005, 9 (6): 448-462.

[6] BREST J, GREINE S, BOSKOVIC B,. Self-adapting control parameters in differential evolution: a comparative study on numerical benchmark problems [J]. IEEE Transactions on Evolutionary Computation, 2006, 10 (6): 646-657.

[7] ZHANG J, SANDERSON A C. JADE: adaptive differential evolution with optional external archive [J]. IEEE Transactions on Evolutionary Computation, 2009, 9 (6): 945-958.

[8] MALLIPEDDI R, SUGANTHAN P N, PAN Q K,. Differential evolution algorithm with ensemble of parameters and mutation strategies [J]. Applied Soft Computing, 2011, 11 (2): 1679-1696.

[9] TEO J. Exploring dynamic self-adaptive populations in differential evolution [J]. Soft Computing, 2006, 10 (8): 673-686.

[10] ZHU W, TANG Y, FANG J A,. Adaptive population tuning scheme for differential evolution [J]. Information Sciences, 2013, 223 (1): 164-191.

[11] 楊衛東, 姚峰, 張明. 基于自適應交叉概率因子的差分進化算法及其應用 [J]. 信息與控制, 2010, 39 (2): 187-193. YANG W D, YAO F, ZHANG M. Differential evolution algorithm based on adaptive crossover probability factor and its application [J]. Information and Control, 2010, 39 (2): 187-193.

[12] 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.

[13] WANG Y, CAI Z, ZHANG Q. Differential evolution with composite trial vector generation strategies and control parameters [J]. IEEE Transactions on Evolutionary Computation, 2011, 15 (1): 55-66.

[14] GONG W Y, CAI Z H, LING C X,. Enhanced differential evolution with adaptive strategies for numerical optimization [J]. IEEE Transactions on Systems, Man, and Cybernetics—Part B: Cybernetics, 2011, 41 (2): 397-413.

[15] 向萬里, 馬壽峰, 安美清. 具有Pbest引導機制的適應性多策略差分進化算法 [J]. 模式識別與人工智能, 2013, 26 (8): 711-721. XIANG W L, MA S F, AN M Q. Adaptive multiple strategy differential evolution algorithm with guiding scheme of Pbest [J]. Pattern Recognition and Artificial Intelligence, 2013, 26 (8): 711-721.

[16] WU G H, MALLIPEDDI R, SUGANTHAN P N,. Differential evolution with multi-population based ensemble of mutation strategies [J]. Information Sciences, 2016, 329 (2): 329-345.

[17] GONG W, ZHOU A, CAI Z. A multioperator search strategy based on cheap surrogate models for evolutionary optimization [J]. IEEE Transactions on Evolutionary Computation, 2015, 19 (5): 746-758.

[18] NOMAN N, IBA H. Accelerating differential evolution using an adaptive local search [J]. IEEE Transactions on Evolutionary Computation, 2008, 12 (1): 107-125.

[19] 商秀芹, 盧建剛, 孫優賢, 等. 一種基于偏好的多目標遺傳算法在動態模型參數辨識中的應用 [J].化工學報, 2008, 59 (7): 1620-1624. SHANG X Q, LU J G, SUN Y X,. A preference-based non-dominated sorting genetic algorithm for dynamic model parameters identification [J]. Journal of Chemical Industry and Engineering (China), 2008, 59 (7): 1620-1624.

[20] 江愛朋, 邵之江, 錢積新. 基于簡約SQP和混合自動微分的反應參數優化 [J]. 浙江大學學報(工學版), 2004, 38 (12): 1606-1614. JIANG A P, SHAO Z J, QIAN J X. Optimization of reaction parameters based on rSQP and hybrid automatic differentiation algorithm [J]. Journal of Zhejiang University (Engineering Science), 2004, 38 (12): 1606-1614.

[21] MARIA G. An adaptive strategy for solving kinetic model concomitant estimation—reduction problems[J]. The Canadian Journal of Chemical Engineering, 1989, 67(5): 825-832.

[22] 夏立榮, 李潤學, 劉啟玉, 等. 基于動態層次分析的自適應多目標粒子群優化算法及其應用 [J]. 控制與決策, 2015, 30 (2): 215-222. XIA L R, LI R X, LIU Q Y,. An adaptive multi-objective particle swarm optimization algorithm based on dynamic AHP and its application [J]. Control and Decision, 2015, 30 (2): 215-222.

A self-adaptive differential evolution algorithm with multiple strategies and its application

XU Bin1, TAO Lili2, CHENG Wushan1

(1School of Mechanical Engineering, Shanghai University of Engineering Science, Shanghai 201620, China;2College of Engineering, Shanghai Second Polytechnic University, Shanghai 201209, China)

A self-adaptive differential evolution algorithm with multiple strategies (SMDE) was proposed to overcome premature or localized optimization of differential evolution (DE) as a result of fixed parameter settings. Based on basic framework of classical DE, the first step in SMDE was to create a candidate set of mutation strategy, scale factor () and crossover rate (CR). In the followed searching process, mutation strategy,andCR for each individual variable in next evolutionary generation were determined self-adaptively from the corresponding candidate set according to knowledge learnt from previous searches, so that proper mutation strategies and control parameters could be set at various evolution stages. Compared to other famous DE variants on optimizing 10 routine standard testing problems, SMDE had better search precision and faster convergence rate. Moreover, study on estimation of uncertain parameters in dynamic process systems of chemical engineering showed that SMDE could effectively solve engineering optimization challenges.

differential evolution algorithm; self-adaptive; multiple strategies; dynamic system; parameter estimation

date: 2016-09-09.

XU Bin, xubin@mail.ecust.edu.cn

10.11949/j.issn.0438-1157.20161273

TP 301

A

0438—1157（2016）12—5190—09

上海高校青年教師培養資助計劃項目（ZZgcd14002）；上海市科委地方高校能力建設項目（14110501200）。

supported by the Young College Teachers Program of Shanghai Education Committee (ZZgcd14002) and the Local Colleges and Universities Capacity Construction Project of Shanghai Science and Technology Commission (14110501200).

2016-09-09收到初稿，2016-09-16收到修改稿。

聯系人及第一作者：徐斌（1984—），男，博士，講師。