自適應雙模式差分進化算法

呼忠權，王洪斌，李 碩

（1.燕山大學 河北省工業計算機控制工程重點實驗室，河北 秦皇島066004；2.燕山大學圖書館，河北 秦皇島066004）

0 引 言

近些年，智能優化算法為全局優化問題［1］提供了新的解決途徑。其中，差分進化算法［2］的表現較為突出。

差分進化 （differential evolution，DE）算法［3］的優勢主要表現在算法簡單、高效并且受控參數少，但基本算法［4］同樣具有缺點：早熟收斂［5］、搜索停滯以及對于控制參數［6］的選擇比較敏感等。

因此，為了改善基本DE 的求解能力，在盡量不增加算法復雜性的基礎上，降低算法對控制參數的敏感性，本文提出一種改進算法，并通過數值仿真進行驗證，驗證結果表明，該算法具有較強的尋優能力和魯棒性。

1 標準差分進化算法［1］

DE算法是求解有n 個連續變量全局優化問題的算法。全局優化問題可以轉化為求解如下函數的最小值問題

式中：D——問題空間的維數，用bj，aj分別表示xj的上下限。

DE算法流程如下：

（1）初始化種群

式中：NP 表示種群大小，Xi（0）表示初始種群中第i個個體，xi，j表示第i個個體的第j 個分量，rand（0，1）表示區間（0，1）內均勻分布的隨機數。

（2）變異

生成新個體

式 中：i≠r1≠r2≠r3，i＝1，2，…，NP ，r1，r2，r3均為區間［1，NP］內的隨機整數，F 為縮放因子，g 表示進化代數，Xi（g）表示第g 代種群中第i個個體。

通過變異后，第g 代種群產生一個新的中間種群｛Vi（g＋1），i＝1，2，…，NP｝。

（3）交叉

式中：i＝1，2，…，NP ，j＝1，2，…，D，rand（0，1）表示區間 （0，1）內均勻分布的隨機數，Ui（g＋1）＝［ui，1，ui，1，…，ui，D］表示第g＋1 代新種群中第i個個體，ui，j（g＋1）和vi，j（g＋1）分別表示Ui（g＋1）和Vi（g＋1）中的第j個分量。CR 為交叉概率，jrand為區間 ［1，D］內的隨機整數。這種交叉策略可確保新個體中至少有一個個體發生了變異和交叉操作。

為了保證求解的有效性和準確性，必須判斷交叉后的新個體是否滿足約束條件，滿足條件的保留，不滿足條件的舍棄，并用步驟 （1）的方式來產生新的個體用于替換被舍棄的個體。如式 （6）所示

式中：i＝1，2，…，NP ，j＝1，2，…，D。（4）選擇操作

DE采用貪婪算法來選擇進入下一代種群的個體

式中：i＝1，2，…，NP 。

（5）終止條件

如果最優解到達求解要求或者迭代次數g 超過了最大迭代次數Gm時，則停止求解，否則重復（1）～（4）操作。

2 自適應雙模式差分進化算法

自適應［7－9］雙模式差分進化算法是將兩種變異模式［10］進行結合，每一次變異操作只選用其中的一種變異模式，這樣不但不會增加該算法的復雜性，而且還會對該算法的性能有所改善。由于DE算法運行參數少，所以每個參數的選取都會影響DE 算法的求解。為了求得全局最優解，參數選擇［11］至關重要。因此，變異因子F 和交叉概率CR 采用自適應的方式進行調節，以此來平衡局部搜索與全局搜索。

2.1 變異操作中的基向量和差分向量

根 據Rainer Storn 和Kenneth Price于1995 年 提 出 的DE算法，基本進化模式有10種［12］，詳見表1。

表1 差分進化模式種類

這10種進化模式采用下面的通式表示

式中：DE——差分進化算法，x——種群中的待變異個體，y——差異向量的個數，z——交叉的模式。在應用中交叉模式一般選用二項交叉，有利于加快算法的收斂速度。

由圖1所示的二維新個體的產生過程可以看出，待變異個體的選取會直接影響算法的收斂速度和全局尋優能力。若待變異個體為隨機選取，則利于算法的全局尋優［12］，但是收斂速度慢；若待變異個體為當前種群中最優個體，則利于算法的快速收斂，但全局尋優能力差。為了解決收斂速度與全局尋優能力間的矛盾，在種群變異的過程中，將DE／rand／1／bin和DE／best／2／bin這兩種變異模式進行結合使用，具體實現流程如圖2所示。

實現方法如下所示

圖1 二維新個體的產生過程

為了使算法的收斂速度更快，但又不至于使算法收斂到局部極小值，將rand（0，1）與進行比較，而不與a進行比較。從圖3中可以看出，這種比較方式可以使rand的值以較大的概率落在曲線的下方，使進化模式DE／best／2／bin被選到的可能性增大，使收斂速度加快。這樣算法就在全局搜索和收斂速度之間進行了平衡。

2.2 自適應變異縮放因子F 和自適應交叉概率CR

自適應參數［13］（F 和CR）會在一定程度上平衡收斂速度和全局搜索之間的關系，改善算法的求解能力。隨著F的變大，全局尋優能力變強，但收斂速度變慢；隨著CR的增大，算法收斂速度加快，但是算法穩定性和成功率變差，早熟收斂［14，15］情況越明顯。因此，為了防止早熟收斂的發生，同時又能保證較快的收斂速度，采取自適應機制對F 和CR 進行賦值。

圖2 算法流程

圖3 函數對比曲線

F 和CR 是根據種群進化代數的變化來自適應調整的。如下式所示

式中：Fmax、Fmin——F的上下限，CRmax、CRmin——CR 的上下限。

此外，由于DE算法對控制參數的選取非常敏感，F 和CR 的選取可以按照這個經驗范圍來選取

式中：P表示函數峰值的個數。

3 仿真及分析

通過對8 個典型Benchmark 函數進行數值仿真，將ADDE算法與兩種基本DE 算法 （采用DE／rand／1／bin 和DE／best／2／bin兩種變異模式）、PSO－w、CLPSO 和DMSDELS算法進行比較。文中將基于DE／rand／1／bin 和DE／best／2／bin模式的DE 算法分別記為DE1 和DE2。在DE1和DE2中，F＝0.5，CR＝0.5。PSO－w、CLPSO 和DMSDELS的參數設置來自于文獻 ［7］。

在表2 中，函數的最大迭代次數也分別給出。將ADDE與其它幾種進行算法性能比較，得到數值求解結果（表中字體加黑的部分表示最優結果和算法），見表2。表中PSO－w、CLPSO 和DMSDELS的求解數據來自文獻 ［7］。

Benchmark函數見表3。

對于單峰函數的求解，ADDE 和DMSDELS算法收斂的精度高，求得的最優解更加接近理論最優解。此外，ADDE比DMSDELS的搜索精度更高，實際值更加接近理論最小值，但對于函數f3（x），ADDE 和DMSDELS都沒有DE2求解的效果好，主要是由于DE2算法比其它3種算法的收斂速度都要快很多，而且函數是單峰函數，不存在局部極小點，因而能夠求解到最優值。

表2 算法性能比較

對于多峰函數f5（x）來說，只有ADDE 求得全局最優解，而對于f6（x）來說，雖然6種方法都不能求得全局最優解，但是ADDE的求解精度更高。

對于低維函數f7（x）和f8（x）來說，6種算法都能求得最優解，但ADDE的求解精度高于其它算法。

通過對上面8個函數的求解結果可以看出，改進算法結合了DE1和DE2的優點，使算法不論是對于低維函數還是高維單峰函數和高維多峰函數，最優解基本不會陷入局部極小點，而且求解精度高。

為了更加清晰的了解6種算法對高維函數的求解能力，分別對函數f5（x）和f6（x）進行了最優解收斂曲線的繪制。為了盡量消除算法的隨機性，分別對兩個函數進行20次求解，取其平均值。圖4所示為平均值隨迭代次數的變化曲線，其中圖 （a）、圖 （b）分別對應函數f5（x）和f6（x）的求解曲線。

圖4 算法的收斂曲線

從圖4 可以看出，對于高維多峰函數的求解，ADDE比其它算法的收斂速度都要快。

綜上所述，對于函數f3（x），雖然ADDE 比DE2求解精度稍差一些，但從對8個函數的求解來看，ADDE 結合了DE1和DE2的優點，使算法在收斂速度與尋優能力之間能夠做到很好的平衡。此外，ADDE 在求解高維多峰函數表現出來的性能更優，全局尋優能力更強，收斂速度更快，求解精度更高。

表3 Benchmark函數

4 結束語

將兩種變異模式結合使用的自適應差分進化算法用于高維多峰函數的優化，并通過對典型Benchmark函數進行測試。測試結果表明，改進算法有效的實現了全局搜索，并且改進了原有算法的收斂速度和收斂精度，顯示了算法的有效性和魯棒性。為實際工程應用提供了有力的理論依據。雖然差分進化算法缺少成型的分析和論證方法，但其自身的并行計算和強魯棒性等優點，相信隨著研究的深入，差分進化算法定將成為解決復雜多維問題的優秀算法。

［1］楊啟文，蔡亮，薛云燦.差分進化算法綜述 ［J］.模式識別與人工智能，2008，21 （4）：506－516 （in Chinese）. ［YANG Qiwen，CAI Liang，XUE Yuncan.A survey of differential evolution algorithms［J］.PR ＆Al，2008，21 （4）：506－516.］

［2］WANG Xu，ZHAO Shuguang.Differential evolution algorithm for high dimensional optimization problem ［J］.Journal of Computer Applications，2014，34 （1）：179－181 （in Chinese）. ［王旭，趙曙光.解決高維優化問題的差分進化算法［J］.計算機應用，2014，34 （1）：179－181.］

［3］YANG Yanxia.A hybrid differential evolution algorithm based on simulated annealing operation ［J］.CAAI Transactions on Intelligent Systems，2014，9 （1）：1－6 （in Chinese）. ［楊 艷霞.一種基于模擬退火操作的混合差分進化算法 ［J］.智能系統學報，2014，9 （1）：1－6.］

［4］LIU Ruochen，JIAO Licheng，MA Yajuan.A differential multi－objective optimization algorithm ［J］.PR ＆ Al，2011，24 （6）：748－755 （in Chinese）. ［劉若辰，焦李成，馬亞娟.一種差分多目標優化算法 ［J］.模式識別與人工智能，2011，24 （6）：748－755.］

［5］YAO Feng，YANG Weidong，ZHANG Ming，et al.Improved space－adaptive－based differential evolution algorithm ［J］.Control Theory ＆Applications，2010，27 （1）：32－38（in Chinese）.［姚峰，楊衛東，張明，等.改進自適應變空間差分進化算法 ［J］.控制理論與應用，2010，27 （1）：32－38.］

［6］Daniela Zaharie.Influence of crossover on the behavior of differential evolution algorithms ［J］.Applied Soft Computing，2009，9 （3）：1126－1138.

［7］ZHANG Xuexia，CHEN Weirong，DAI Chaohua.Dynamic multi－group self－adaptive evolution algorithm with local search for function optimization ［J］.ACTA Electronica Sinica，2010，38 （8）：1825－1830 （in Chinese）. ［張雪霞，陳維榮，戴朝華.帶局部搜索的動態多群體自適應差分進化算法及函數優化 ［J］.電子學報，2010，38 （8）：1825－1830.］

［8］Pan Quan－Ke，Suganthan PN，Wang Ling，et al.A differential evolution algorithm with self－adapting strategy and control parameters［J］.Computers ＆Operations Research，2011，38（1）：394－408.

［9］TUO Shouheng.Self－adaptive ant colony differential evolution algorithm ［J］.Computer Engineering and Design，2012，33（7）：2804－2808 （in Chinese）.［拓守恒.自適應蟻群差分進化算法 ［J］.計算機工程與設計，2012，33 （7）：2804－2808.］

［10］ZHANG Chunmei，CHEN Jie，XIN Bin.Distributed differential evolution algorithm with adaptive parameters ［J］.Control and Decision，2014，29 （3）：1－6 （in Chinese）.［張春美，陳杰，辛斌.參數適應性分布差分進化算法 ［J］.控制與決策，2014，29 （3）：1－6.］

［11］Daniela Zaharie.Influence of crossover on the behavior of differential evolution algorithms ［J］.Applied Soft Computing，2009，9 （3）：1126－1138.

［12］XU Xiaojian，HUANG Xiaoping，QIAN Deling.Adaptive accelerating differential evolution ［J］.Complex Systems and Comlexity Science，2008，5 （1）：87－92 （in Chinese）. ［許小健，黃小平，錢德玲.自適應加速差分進化算法 ［J］.復雜系統與復雜性科學，2008，5 （1）：87－92.］

［13］Ali MM.Differential evolution with preferential crossover［J］.European Journal of Operational Research，2007，181（3）：1137－1147.

［14］ZHAO Guangquan，PENG Xiyuan，SUN Ning.A modified differential evolution algorithm with local enhanced operator［J］.ACTA Electronica Sinica，2007，35 （5）：849－853 （in Chinese）.［趙光權，彭喜元，孫寧.帶局部增強算子的微分進化改進算法 ［J］.電子學報，2007，35 （5）：849－853.］

［15］HE Yichao，WANG Xizhao，LIU Kunqi，et al.Convergent analysis and algorithmic improvement of differential evolution［J］.Journal of Software，2010，21 （5）：875－885 （in Chinese）.［賀毅朝，王熙照，劉坤起，等.差分演化的收斂性分析與算法改進 ［J］.軟件學報，2010，21 （5）：875－885.］