一種改進的差分進化算法及其應用

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

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

一種改進的差分進化算法及其應用

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

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

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

差分進化算法；多目標優(yōu)化；數字濾波器設計

0 前言

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

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

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

1 差分進化算法及其改進

1.1 差分進化（DE）算法描述

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

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

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

6）重復進化：保留每代得到的最優(yōu)解，在給定的進化代數Gn內選出最佳解，并輸出結果．

1.2 DE算法的改進

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

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

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

1.2.2 收斂變異因子差分進化算法（CDE）

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

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

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

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

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

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

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

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

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

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

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

PSODE算法實現過程如下：

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

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

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

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

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

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

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

1.3 仿真實驗與對比分析

為驗證改進算法的尋優(yōu)性能，采用表1所示的4個經典的國際標準測試函數進行尋優(yōu)實驗與對比分析．

表1 國際標準測試函數Tab.1 Internationalstandard testing functions

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

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

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

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

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

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

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

2 實際應用

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

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

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

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

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

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

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

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

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

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

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)化設計效果對比Tab.3 Comparison on filteroptimization design effect

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

3 結論

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

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

[2]馬小姝，李宇龍，嚴浪．傳統(tǒng)多目標優(yōu)化方法和多目標遺傳算法的比較綜述[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]孟紅云，張小華，劉三陽．用于約束多目標優(yōu)化問題的雙群體差分進化算法[J]．計算機學報，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．

[責任編輯 代俊秋]

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

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

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