自適應(yīng)雙模式差分進(jìn)化算法

呼忠權(quán)，王洪斌，李 碩

（1.燕山大學(xué) 河北省工業(yè)計(jì)算機(jī)控制工程重點(diǎn)實(shí)驗(yàn)室，河北 秦皇島066004；2.燕山大學(xué)圖書館，河北 秦皇島066004）

0 引 言

近些年，智能優(yōu)化算法為全局優(yōu)化問題［1］提供了新的解決途徑。其中，差分進(jìn)化算法［2］的表現(xiàn)較為突出。

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

因此，為了改善基本DE 的求解能力，在盡量不增加算法復(fù)雜性的基礎(chǔ)上，降低算法對(duì)控制參數(shù)的敏感性，本文提出一種改進(jìn)算法，并通過數(shù)值仿真進(jìn)行驗(yàn)證，驗(yàn)證結(jié)果表明，該算法具有較強(qiáng)的尋優(yōu)能力和魯棒性。

1 標(biāo)準(zhǔn)差分進(jìn)化算法［1］

DE算法是求解有n 個(gè)連續(xù)變量全局優(yōu)化問題的算法。全局優(yōu)化問題可以轉(zhuǎn)化為求解如下函數(shù)的最小值問題

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

DE算法流程如下：

（1）初始化種群

式中：NP 表示種群大小，Xi（0）表示初始種群中第i個(gè)個(gè)體，xi，j表示第i個(gè)個(gè)體的第j 個(gè)分量，rand（0，1）表示區(qū)間（0，1）內(nèi)均勻分布的隨機(jī)數(shù)。

（2）變異

生成新個(gè)體

式 中：i≠r1≠r2≠r3，i＝1，2，…，NP ，r1，r2，r3均為區(qū)間［1，NP］內(nèi)的隨機(jī)整數(shù)，F(xiàn) 為縮放因子，g 表示進(jìn)化代數(shù)，Xi（g）表示第g 代種群中第i個(gè)個(gè)體。

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

（3）交叉

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

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

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

DE采用貪婪算法來選擇進(jìn)入下一代種群的個(gè)體

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

（5）終止條件

如果最優(yōu)解到達(dá)求解要求或者迭代次數(shù)g 超過了最大迭代次數(shù)Gm時(shí)，則停止求解，否則重復(fù)（1）～（4）操作。

2 自適應(yīng)雙模式差分進(jìn)化算法

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

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

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

表1 差分進(jìn)化模式種類

這10種進(jìn)化模式采用下面的通式表示

式中：DE——差分進(jìn)化算法，x——種群中的待變異個(gè)體，y——差異向量的個(gè)數(shù)，z——交叉的模式。在應(yīng)用中交叉模式一般選用二項(xiàng)交叉，有利于加快算法的收斂速度。

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

實(shí)現(xiàn)方法如下所示

圖1 二維新個(gè)體的產(chǎn)生過程

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

2.2 自適應(yīng)變異縮放因子F 和自適應(yīng)交叉概率CR

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

圖2 算法流程

圖3 函數(shù)對(duì)比曲線

F 和CR 是根據(jù)種群進(jìn)化代數(shù)的變化來自適應(yīng)調(diào)整的。如下式所示

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

此外，由于DE算法對(duì)控制參數(shù)的選取非常敏感，F(xiàn) 和CR 的選取可以按照這個(gè)經(jīng)驗(yàn)范圍來選取

式中：P表示函數(shù)峰值的個(gè)數(shù)。

3 仿真及分析

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

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

Benchmark函數(shù)見表3。

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

表2 算法性能比較

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

對(duì)于低維函數(shù)f7（x）和f8（x）來說，6種算法都能求得最優(yōu)解，但ADDE的求解精度高于其它算法。

通過對(duì)上面8個(gè)函數(shù)的求解結(jié)果可以看出，改進(jìn)算法結(jié)合了DE1和DE2的優(yōu)點(diǎn)，使算法不論是對(duì)于低維函數(shù)還是高維單峰函數(shù)和高維多峰函數(shù)，最優(yōu)解基本不會(huì)陷入局部極小點(diǎn)，而且求解精度高。

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

圖4 算法的收斂曲線

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

綜上所述，對(duì)于函數(shù)f3（x），雖然ADDE 比DE2求解精度稍差一些，但從對(duì)8個(gè)函數(shù)的求解來看，ADDE 結(jié)合了DE1和DE2的優(yōu)點(diǎn)，使算法在收斂速度與尋優(yōu)能力之間能夠做到很好的平衡。此外，ADDE 在求解高維多峰函數(shù)表現(xiàn)出來的性能更優(yōu)，全局尋優(yōu)能力更強(qiáng)，收斂速度更快，求解精度更高。

表3 Benchmark函數(shù)

4 結(jié)束語

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

［1］楊啟文，蔡亮，薛云燦.差分進(jìn)化算法綜述 ［J］.模式識(shí)別與人工智能，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）. ［王旭，趙曙光.解決高維優(yōu)化問題的差分進(jìn)化算法［J］.計(jì)算機(jī)應(yīng)用，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ìn)化算法 ［J］.智能系統(tǒng)學(xué)報(bào)，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）. ［劉若辰，焦李成，馬亞娟.一種差分多目標(biāo)優(yōu)化算法 ［J］.模式識(shí)別與人工智能，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）.［姚峰，楊衛(wèi)東，張明，等.改進(jìn)自適應(yīng)變空間差分進(jìn)化算法 ［J］.控制理論與應(yīng)用，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）. ［張雪霞，陳維榮，戴朝華.帶局部搜索的動(dòng)態(tài)多群體自適應(yīng)差分進(jìn)化算法及函數(shù)優(yōu)化 ［J］.電子學(xué)報(bào)，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）.［拓守恒.自適應(yīng)蟻群差分進(jìn)化算法 ［J］.計(jì)算機(jī)工程與設(shè)計(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）.［張春美，陳杰，辛斌.參數(shù)適應(yīng)性分布差分進(jìn)化算法 ［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）. ［許小健，黃小平，錢德玲.自適應(yīng)加速差分進(jìn)化算法 ［J］.復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，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）.［趙光權(quán)，彭喜元，孫寧.帶局部增強(qiáng)算子的微分進(jìn)化改進(jìn)算法 ［J］.電子學(xué)報(bào)，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ìn) ［J］.軟件學(xué)報(bào)，2010，21 （5）：875－885.］