夏莘媛，劉伯穎，李洋，李玲玲

（1.河北工業(yè)大學(xué)電子信息工程學(xué)院，天津 300401；2.河北工業(yè)大學(xué)計算機與軟件學(xué)院，天津 300401；3.河北工業(yè)大學(xué)電氣工程學(xué)院，天津 300401）

一種改進(jìn)的差分進(jìn)化算法及其應(yīng)用

夏莘媛1，劉伯穎2，李洋3，李玲玲3

（1.河北工業(yè)大學(xué)電子信息工程學(xué)院，天津 300401；2.河北工業(yè)大學(xué)計算機與軟件學(xué)院，天津 300401；3.河北工業(yè)大學(xué)電氣工程學(xué)院，天津 300401）

多目標(biāo)優(yōu)化問題（MOP）存在范圍廣且人工求解難度大，通過差分進(jìn)化算法（DE）解決MOP問題具有重要意義．由于常用DE算法性能有限、收斂速度、計算精度和優(yōu)化能力相互制約，通過改善變異因子、進(jìn)化機制以及與粒子群算法融合等措施，研究一類基于粒子群優(yōu)化和DE的混合算法（PSODE），經(jīng)典優(yōu)化函數(shù)的仿真實驗和對比分析，結(jié)果表明在高維復(fù)雜尋優(yōu)問題中可以求得高精度解．在實際數(shù)字濾波器優(yōu)化設(shè)計中，表明其改進(jìn)算法在計算精度和運行速度上均能取得滿意的應(yīng)用效果．

差分進(jìn)化算法；多目標(biāo)優(yōu)化；數(shù)字濾波器設(shè)計

0 前言

在許多情況下，實際優(yōu)化問題為多個相互影響與限制的目標(biāo)所構(gòu)成，因此需要尋求一個融合多個因素的最優(yōu)解．這種涉及多個目標(biāo)并求出問題的最優(yōu)解，即為多目標(biāo)優(yōu)化問題（multi-objectiveoptimization problem，MOP）1．人們通常將MOP問題變?yōu)閱文繕?biāo)優(yōu)化問題，然后再進(jìn)行求解2．這樣，實際轉(zhuǎn)化成一個高維優(yōu)化問題．由于MOP問題往往因其方程復(fù)雜且目標(biāo)彼此制約，問題的解也常常不是唯一的，在解空間中任意一點都可視為一個解．為此需要從海量解中尋找最優(yōu)解，這是常用求解方法難以實現(xiàn)的．

差分進(jìn)化算法（DifferentialEvolution，DE）是由Storn等[3-4]于1995年提出的，該算法是受自然界優(yōu)勝劣汰的進(jìn)化機制啟發(fā)的一種全局尋優(yōu)算法，主要通過模擬自然界生物進(jìn)化機制，包括變異、交叉和選擇等基本操作．常用DE算法適合求解各種最優(yōu)化問題且具有較好的計算精度和收斂性能，并在解決多目標(biāo)優(yōu)化問題上得到廣泛關(guān)注，現(xiàn)在優(yōu)化領(lǐng)域已成為一個研究熱點，比如AbbassHA等人56提出了Pareto前沿DE算法，BabuBV等7利用罰函數(shù)及權(quán)值系數(shù)方法改進(jìn)了DE算法，文獻(xiàn)[8]設(shè)計一種雙群體DE算法求解約束多目標(biāo)優(yōu)化問題，文獻(xiàn)[9]采用自適應(yīng)DE算法求解多約束優(yōu)化問題等，均取得較為理想的應(yīng)用效果．

為進(jìn)一步提高常用DE算法的性能，本文通過改善變異因子、進(jìn)化機制及與粒子群優(yōu)化（PSO）算法融合等措施，研究改進(jìn)的DE算法并進(jìn)行對比分析，在實際濾波器的優(yōu)化設(shè)計中以期取得滿意的應(yīng)用效果．

1 差分進(jìn)化算法及其改進(jìn)

1.1 差分進(jìn)化（DE）算法描述

自然界中，每種生物的種群都一直經(jīng)歷著優(yōu)勝劣汰、適者生存的自然選擇．DE算法正是受這種進(jìn)化模式的啟發(fā)而誕生，其基本進(jìn)化操作有：變異、交叉和選擇；其控制參數(shù)有：交叉因子、縮放因子、種群規(guī)模及最大進(jìn)化代數(shù)．

DE算法的具體關(guān)鍵環(huán)節(jié)如下：

1）粒子初始化：產(chǎn)生N個D維的粒子組成種群，記單個個體為χi,Gi=1,2,,N，其中i為個體的標(biāo)號，G為進(jìn)化代數(shù)．依照式(1)進(jìn)行粒子初始化．

6）重復(fù)進(jìn)化：保留每代得到的最優(yōu)解，在給定的進(jìn)化代數(shù)Gn內(nèi)選出最佳解，并輸出結(jié)果．

1.2 DE算法的改進(jìn)

DE算法具有許多優(yōu)點，但也存在一些不足，比如因固定的變異因子F導(dǎo)致的收斂速度與計算精度相互制約，容易出現(xiàn)早熟現(xiàn)象等．為了改善DE算法性能，本文將做進(jìn)一步改進(jìn)．

1.2.1 基于隨機變異因子的DE算法（RDE）

在常用DE算法中，由于變異因子始終為固定值，因此在提高收斂速度時會降低計算精度．為此設(shè)定變異因子F=rand，即不斷地用[0,1]中的隨機數(shù)作為變異因子．這種改進(jìn)算法記為隨機變異因子DE算法（RDE）．

1.2.2 收斂變異因子差分進(jìn)化算法（CDE）

由于固定變異因子F在取值較大時可以使DE算法收斂速度提高，在取值較小時可以提高種群個體逼近最優(yōu)解的精度，因此可以設(shè)定一個收斂因子

這里，F(xiàn)1為新的變異因子，Gn為最大進(jìn)化代數(shù)，G為進(jìn)化代數(shù)．隨著G的增加，收斂因子成對數(shù)形式在1至0的范圍內(nèi)減小，這樣變異因子在最初以較大的值使DE算法收斂、逃離局部極值點，在后期受收斂因子影響而不斷減小，使種群個體逐步逼近最優(yōu)解．這樣在一定程度上可同時提高收斂速度與計算精度．

1.2.3 基于PSO的DE混合算法（PSODE）

粒子群優(yōu)化（PSO）算法的具體過程是：先隨機生成一個由N個粒子構(gòu)成的種群，每個單獨粒子代表著優(yōu)化函數(shù)的一組解，粒子在D維的空間內(nèi)尋優(yōu)，然后每一次迭代中，利用適應(yīng)度函數(shù)fitness對每一個粒子進(jìn)行評價．通過更新每個粒子的速度與位置，實現(xiàn)對最優(yōu)解的尋優(yōu)．

其中：w為慣性權(quán)重；c1與c2是加速因子，一般均取2．r1與r2為[0,1]中的隨機數(shù)．

本文通過結(jié)合PSO與DE算法，得到混合算法（PSODE）．首先，PSO與DE兩種算法各自在尋優(yōu)空間內(nèi)生成獨立的種群，進(jìn)行相應(yīng)算法的尋優(yōu)，然后利用fitness比較兩種算法每一代種群的適應(yīng)度，選取適應(yīng)度高的粒子進(jìn)行兩種算法之間的交叉，這樣可以提高算法的收斂速度，同時還可以減少早熟現(xiàn)象的發(fā)生．

當(dāng)PSO算法采用固定慣性因子w時，與DE算法中采用固定變異因子F一樣，會出現(xiàn)收斂速度與計算精度相沖突的情況．因此，可以通過式(10)更新．

其中：wmin與wmaχ分別為w的下限與上限；k為控制因子；G與Gn同DE算法一樣分別為進(jìn)化代數(shù)與最大進(jìn)化代數(shù)．

當(dāng)PSODE快速收斂后,若停留在某一最優(yōu)值上不再變化，即fitnessχiG=fitnessχiG1==fitnessχiGGp,這樣仍會產(chǎn)生早熟現(xiàn)象．此時可以重新產(chǎn)生粒子，即生成一個臨時向量：

其中：χL與χU同DE算法中的一樣為變量的下限與上限；Gp為最大停留的代數(shù)．

若tempvector的fitness高于現(xiàn)有粒子的fitness，則用tempvector替換最優(yōu)粒子；反之，現(xiàn)有粒子不變．

PSODE算法實現(xiàn)過程如下：

Step1設(shè)置初始參數(shù)：種群數(shù)N，最大進(jìn)化代數(shù)Gn，慣性權(quán)重的最大值w max和最小值w m in，加速因子c1與c2，控制因子k，變異因子F，交叉因子CR；

Step2初始化PSO算法和DE算法種群：PSOpopulation，DEpopulation；

Step3更新PSOpopulation中粒子的速度和位置；對DEpopulation中粒子進(jìn)行變異、交叉、選擇操作；

Step4通過fitness函數(shù)選出PSOpopulation中的最優(yōu)粒子PSObest和DEpopulation中的最優(yōu)粒子DEbest；

Step5對比選出PSObest與DEbest中最優(yōu)個體，替換次優(yōu)個體；

Step6判斷粒子是否停留某點，若停留，產(chǎn)生新粒子；否則繼續(xù)下一步；

Step7若沒達(dá)到最大進(jìn)化代數(shù)，轉(zhuǎn)Step3繼續(xù)尋優(yōu)；若達(dá)到，則輸出最優(yōu)解，完成尋優(yōu)計算．

1.3 仿真實驗與對比分析

為驗證改進(jìn)算法的尋優(yōu)性能，采用表1所示的4個經(jīng)典的國際標(biāo)準(zhǔn)測試函數(shù)進(jìn)行尋優(yōu)實驗與對比分析．

表1 國際標(biāo)準(zhǔn)測試函數(shù)Tab.1 Internationalstandard testing functions

表1中的測試函數(shù)均可視為由多目標(biāo)函數(shù)轉(zhuǎn)化而成，其中Sphere函數(shù)為一簡單的單峰函數(shù)，通過此函數(shù)可以看出不同算法的收斂快慢．Rosenbrock函數(shù)也是單峰函數(shù)，但其全局最優(yōu)值不易獲得，容易出現(xiàn)早熟現(xiàn)象，通過Rosenbrock函數(shù)可以測試算法的計算精度和尋優(yōu)能力．Rastrigin函數(shù)在維數(shù)較少的情況下可以看作非線性的多峰函數(shù)，存在多個局部極值，因此較難實現(xiàn)尋優(yōu)；Griewank函數(shù)擁有許多局部最優(yōu)值，若算法的全局搜索能力與逃離局部最優(yōu)值的能力弱，則難以尋得最優(yōu)值；這兩個函數(shù)可以考察算法全局尋優(yōu)能力．

分別將4個標(biāo)準(zhǔn)測試函數(shù)作為適應(yīng)度函數(shù)fitness來求解其最小值，4種算法（DE、RDE、CDE、PSODE）中的相關(guān)參數(shù)設(shè)置為：wmax=0.9，wmin=0.4，c1=c2=2，CR=0.8，F(xiàn)=0.6，k=3，Gp=20代，種群大小設(shè)定為100組，最大進(jìn)化代數(shù)Gn=3 000次，優(yōu)化函數(shù)設(shè)定為10維．收斂曲線如圖1～圖4所示，適應(yīng)度函數(shù)fitness的計算結(jié)果如表2所示，其中統(tǒng)計了10次測試結(jié)果，Best為最好優(yōu)化值，Worst為最差優(yōu)化值，Mean為平均值．

圖1 幾種算法對Sphere函數(shù)的尋優(yōu)收斂曲線Fig.1 Convergence curves for Sphere function

圖2 幾種算法對Rosenbrock函數(shù)的尋優(yōu)收斂曲線Fig.2 Convergence curves forRosenbrock function

圖4 幾種算法對Griewank函數(shù)的尋優(yōu)收斂曲線Fig.4 Convergence curves forGriewank function

表2 幾種算法的測試效果Tab.2 Testing resultswith fouralgorithms

從圖1～圖4和表2中發(fā)現(xiàn)，DE算法具有較快的收斂速度，在求解低難度優(yōu)化問題時具有較高的計算精度；RDE加快了算法的收斂速度，但更適用低精度的優(yōu)化求解；CDE算法表現(xiàn)穩(wěn)定，收斂速度不快，但是可以求解出高精度的最優(yōu)解；PSODE算法在收斂速度上比CDE快，但不及DE和RDE，然而在高難度的尋優(yōu)問題中可以求得高精度解，特別是在計算后期，與DE算法相比，避免計算停滯的能力明顯提高，即克服了早熟現(xiàn)象的發(fā)生．因此PSODE算法是具有實用價值的．

2 實際應(yīng)用

在紅外搜索系統(tǒng)的應(yīng)用中，常用鐘形波來代替理論上的脈沖信號，因此信號處理器應(yīng)該產(chǎn)生一個與鐘形波相匹配的濾波器，這在實際中是很難實現(xiàn)的．鐘形波的函數(shù)表達(dá)式如下

其中：是波形的半寬度；E是鐘形波的高度．經(jīng)過傅氏變換后的幅頻響應(yīng)為

若想獲得與此匹配的濾波器，可以選擇與之對應(yīng)的低通濾波器進(jìn)行優(yōu)化設(shè)計．其中匹配濾波器可以通過式(14)數(shù)字級聯(lián)方式實現(xiàn)．

其中：A是增益因子；N為級聯(lián)的級數(shù)．在第k級，和均為要優(yōu)化的參數(shù)，可見其濾波器設(shè)計即為一個高維優(yōu)化問題．具體實現(xiàn)方式如圖5所示．

設(shè)定選擇兩級級聯(lián)形式的匹配濾波器，其計算方程可以寫為

其中：X是濾波器的輸入；Y1和Y2分別是第1級和第2級的輸出；W1和W2為加法器的輸出．

圖5 數(shù)字級聯(lián)濾波器示意圖Fig.5 Digital filter in cascade form

在兩級級聯(lián)的濾波器中，頻率響應(yīng)函數(shù)為

其中=A,a1,b1,c1,d1,a2,b2,c2,d2為一組目標(biāo)，通過將匹配濾波器頻率響應(yīng)函數(shù)與鐘形波的頻率響應(yīng)函數(shù)對比作為fitness適應(yīng)度函數(shù)

其中：M為離散點個數(shù)，則可轉(zhuǎn)化為一個9維的最小值優(yōu)化問題，參數(shù)設(shè)置為：wmax=0.9，wmin=0.4，c1=c2=2，CR=0.8，F(xiàn)=0.6，k=3，Gp=20代，種群大小設(shè)定為100組，最大進(jìn)化代數(shù)Gn=3000次，=0.15，M=1 000．分別通過DE算法和PSODE算法進(jìn)行5次尋優(yōu)得到fitness函數(shù)的計算結(jié)果如表3所示，PSODE算法所得濾波器參數(shù)為

A=0.3531588，a1=1.091 5979，b1=0.747245 2，c1=0.572 1020，d1=0.231006 3，a2=2.5489479，b2=1.861 446 3，c2=0.876 254 1，d2=0.205 392 8．

表3 濾波器優(yōu)化設(shè)計效果對比Tab.3 Comparison on filteroptimization design effect

由表3可知，PSODE算法具有很高的計算精度，逃離局部最優(yōu)值的能力強，減少了早熟現(xiàn)象的發(fā)生，因此其尋優(yōu)計算的穩(wěn)定性更高．

3 結(jié)論

在差分進(jìn)化算法中，采用隨機變異因子可以加快算法的收斂速度，很適用于低精度的優(yōu)化求解；采用收斂變異因子雖然收斂速度不快，但表現(xiàn)穩(wěn)定，可以求解出高精度的最優(yōu)解；而采用基于粒子群優(yōu)化算法的混合算法（PSODE）在高難度尋優(yōu)問題中可以求得高精度解，特別是在計算后期可以避免計算停滯等早熟現(xiàn)象，從而提高優(yōu)化效率．?dāng)?shù)字濾波器的設(shè)計為一個高維函數(shù)優(yōu)化問題，采用差分進(jìn)化算法能夠?qū)崿F(xiàn)濾波器的優(yōu)化設(shè)計，特別是采用本文改進(jìn)的混合算法可以取得更為滿意的設(shè)計效果．

[1]肖曉偉，肖迪，林錦國，等．多目標(biāo)優(yōu)化問題的研究概述[J]．計算機應(yīng)用研究，2011，28（3）：805-808．

[2]馬小姝，李宇龍，嚴(yán)浪．傳統(tǒng)多目標(biāo)優(yōu)化方法和多目標(biāo)遺傳算法的比較綜述[J]．電氣傳動自動化，2010，32（3）：48-50．

[3]Storn R，Pricek．Differential evolution-a simple and efficient adaptive scheme for global optimization over continuous spaces[J]．Technical Report，International Computer Science Institute，1995，9（8）：22-25．

[4]Storn R，Pricek．Differentialevolution-a simple and efficientheuristic for globaloptimization over continuous spaces[J]．Journalof Global Optimization，1997，11（4）：341-359．

[5]AbbassH A，Sarker R，New ton C．A Pareto-frontier differentialevolution approach formulti-objectiveoptimization problems[C]//IEEECongress on Evolutionary Computation．Piscataway，2001，971-978．

[6]Abbass HA，SarkerR．Thepareto differentialevolution algorithm[J]．International Journalon Artificial Intelligence Tools，2002，11（4）：531-552．

[7]Babu BV，Jehan M M L．D ifferentialevolution for M ulti-objective optimization[C]//IEEE Congress on Evolutionary Computation．Canberra，2003，2696-2703．

[8]孟紅云，張小華，劉三陽．用于約束多目標(biāo)優(yōu)化問題的雙群體差分進(jìn)化算法[J]．計算機學(xué)報，2008，31（2）：228-235．

[9]Saber M Elsayed，Ruhul A Sarker，Daryl L Essam．A self-adaptive combined strategies algorithm for constrained optim ization using differential evolution[J]．Applied M athematics and Computation，2014，241：267-282．

[責(zé)任編輯 代俊秋]

An improved differentialevolution algorithm and itsapplication

XIA Xin-yuan1，LIU Bo-ying2，LIYang3，LILing-ling3

(1.Schoolof Electronic and Information Engineering,HebeiUniversityofTechnology,Tianjin300401,China;2.SchoolofComputer Scienceand Software,HebeiUniversity ofTechnology,Tianjin 300401,China;3.Schoolof ElectricalEngineering,HebeiUniversity of Technology,Tianjin 300401,China)

Multi-objectiveOptim ization Problem（MOP）isvery common butdifficult to besolved,so ithas im portant significance to solve MOPusing DifferentialEvolution(DE)algorithm.To overcome theshortcom ingsin DEalgorithm, such as the lim ited performance,themutual restriction among convergent rate,com putationalaccuracy and optim ization ability,ahybrid approach to particleswarm optimization(PSO)andDEalgorithm ispresented by improvingmutagenic factor,evolutionism andmixing PSO algorithm.Simulation experimentand comparative analysis on classical testing functionsshow thatthepresented improved approach can get thehigh accuracy solution inhigh dimensionalcomplex optimization problems.In theactualdesign on digital filterby improved approach,theapplication effect can be obtained satisfactory at computationalaccuracy and operation rate.

differentialevolution algorithm;multi-objective optim ization problem;digital filter design

TP18

A

1007-2373(2015)01-0012-07

10.14081/j.cnki.hgdxb.2015.01.003

2014-11-05

國家自然科學(xué)基金（51475136）；河北省引進(jìn)留學(xué)人員基金（C2012003038）；國家大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計劃（201310080017）；河北省大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計劃（201310080073）

夏莘媛（1992-），女（漢族），碩士生．通訊作者：李玲玲（1968-），女（漢族），教授，博士生導(dǎo)師．