基于隔代映射算子的差分進化算法

符純明　姜　潮　陳光宋　吉　磊

1.湖南大學汽車車身先進設計制造國家重點實驗室，長沙，4100822.南京理工大學，南京，210094

基于隔代映射算子的差分進化算法

符純明1姜潮1陳光宋2吉磊2

1.湖南大學汽車車身先進設計制造國家重點實驗室，長沙，4100822.南京理工大學，南京，210094

摘要：提出一種基于隔代映射算子的差分進化算法以求解優化問題，該方法在保證解的精度的同時具有較快的收斂速度。在經典的差分進化算法基礎上，采用反向學習策略產生初始種群，并采用兩種差分變異策略產生變異個體，以增加種群的多樣性；利用隔代映射算子產生三個新個體替換當前進化種群中最差的三個個體，以實現精英策略提升算法的收斂性；為了保持種群的多樣性和避免獲得局部解，利用探測算子策略產生新個體加入進化種群。采用11個單峰、多峰測試函數和兩個工程實例驗證了該方法的有效性。

關鍵詞：差分進化算法; 隔代映射算子; 反向學習; 探測算子

0引言

在實際工程問題中，經常遇到一類較為復雜的優化問題，其目標函數不連續或不可導，導致傳統基于梯度的優化方法難以有效求解。而基于種群的進化算法不需要目標函數的梯度信息，只需采用適應度函數即可對復雜目標函數進行優化求解，為求解該類問題提供了一種有效的途徑。差分進化(differential evolution，DE)算法是進化算法(evolutionary algorithms，EAs)中一種簡單有效的隨機搜索算法，最早由Storn等[1]于1995年提出，并用于求解切比雪夫多項式擬合問題。因DE操作簡單，控制參數少，具有較強的全局優化性和魯棒性，故被廣泛應用于機械優化設計、機器人控制、車間節能調度等領域[2-4]。

DE算法的性能主要取決于試驗向量產生策略(交叉和變異算子)和控制參數(種群大小、縮放因子、交叉概率)。在改進試驗向量產生策略和控制參數方面，國內外學者進行了一系列研究和探索。如Fan等[5]提出了一種三角變異算子用于加速DE算法收斂性能，并同時引入一參數控制三角變異算子的使用頻率以保持種群的多樣性。Zhang等[6]利用當前群體中最好解和較好解的信息產生變異個體加入進化種群，并將已淘汰的個體儲存于一外部種群中參與隨后的進化，其縮放因子和交叉概率分別通過標準正態分布和柯西分布產生。但該方法需要較大的儲存空間保存淘汰的個體。Das等[7]提出了一種新型的局部搜索模型，采用目標向量鄰域中的最優解產生變異個體，該方法動態地利用臨近個體產生更優良個體。Wang等[8]針對當前DE交叉算子普遍存在的缺陷，提出了一種正交交叉策略，有效地提升了DE算法搜索性能。Ronkkonen等[9]采用大量測試函數分析了初始種群大小和縮放因子對傳統的DE算法性能的影響。

通常，DE算法求解優化問題時，對控制參數較為敏感，找到一組合理的控制參數通常需要反復調試，因此，國內外學者發展了適應性和自適應性策略調節其控制參數[10-11]。適應性策略是指搜索過程中不斷利用反饋信息來調節參數，而自適應性策略是指將控制參數編碼于個體參與進化過程。Zhu等[10]提出了一種動態調整種群大小的策略，可有效地篩除進化種群中冗余個體從而減少計算量。Brest等[11]提出了一種新型自適應算法，將縮放因子和交叉概率進行編碼并參與進化，有利于增加種群的多樣性。Wang等[12]建立了試驗向量產生策略知識庫和控制參數設置知識庫，并提出組合差分進化(composite DE,CoDE)算法來求解優化問題，有效地利用多組策略和參數產生不同的變異個體，保證了該算法求解不同問題時具有優良的性能。車林仙等[13]提出了一種自適應逃逸差分進化算法，并用于求解并聯機器人主驅動機構位置的優化問題。楊曉明等[14]利用改進的差分進化算法優化設計了盤式制動器。王前等[15]提出了一種自適應差分進化方法，并將其應用于輪胎模型的參數辨識中。

一系列改進的DE算法被應用，獲得了較好的效果，但求解某些優化問題時這些算法存在收斂速度慢且易于陷入局部最優的缺陷。為此，本文將連續兩代中的最優個體用于構造搜索方向以便快速有效地獲得更優個體，提出一種基于隔代映射算子的差分進化(intergeneration projection DE，IPDE)算法，相比現有方法，該方法在獲得全局最優解的同時具有較快的收斂速度。

1差分進化算法

通常的優化問題可定義為

(1)

式中，f(x)為目標函數；xk、xkL和xkU分別為設計變量、設計變量的下界和上界；n為設計變量的個數。

DE算法[1]的基本思想是：對當前種群中的個體進行變異和交叉操作產生新個體，然后采用貪婪準則在兩個種群中選出較優個體組成下一代進化種群，不斷迭代直至滿足收斂條件，其流程如圖1所示。

圖1　DE算法流程圖

首先，DE算法在可行域空間隨機產生N個個體組成初始種群[1]：

(2)

i=1,2,…,N；j=1,2,…,n

(3)

(4)

DE/rand/1策略收斂慢但具有較強的全局搜索能力，利于保持種群的多樣性。DE/best/1策略則具有較快的收斂速度，但容易陷入局部最優。

再次，采用二項式交叉算子產生試驗向量ui，其中

(5)

式中，Cr為交叉概率；prj為第j維向量在[0,1]中隨機產生的一實數。

最后，在目標向量和試驗向量中選擇較優個體保留至第t+1代：

(6)

上述操作不斷迭代直至滿足收斂條件。

2IPDE算法及構造

傳統DE算法求解某些較為復雜優化問題時，其后期收斂效率低或易于陷入局部最優。為克服以上缺點，本文提出的IPDE算法采用反向學習策略[16]產生初始種群，并利用進化種群中連續兩代的最優個體來構造搜索方向，以便快速有效地獲得更優個體，即隔代映射策略。同時為了保持種群的多樣性，每隔T代由當前種群中的最優個體和最差個體產生兩個新個體，擇優選擇一個個體進入下一代進化種群。為此，IPDE算法求解優化問題時，在保證解的精度的同時并具有快速收斂的特點。

2.1隔代映射策略

基于種群的進化算法中，其核心之一是如何快速有效地產生優良個體，從而加速算法收斂性能。本文引入一種隔代映射策略[17]，以快速收斂到局部最優解，從而加速算法收斂性能。如圖2所示，隔代映射策略采用連續兩代種群中的最優個體來構造搜索方向，從而在兩代最優個體的搜索方向上產生三個新個體。因新個體在連續兩代的最優個體的方向上產生，有助于快速生成接近局部最優解的個體。

圖2　隔代映射策略示意圖(2變量)

(7)

2.2算法構造

本文提出的IPDE算法同時結合反向學習[16]和隔代映射策略的優點求解優化問題，在保證精度的同時具有快速收斂的特點，其迭代過程如下：

(1)在搜索空間隨機產生N個個體，并利用反向學習策略產生N個個體便于均勻分布于搜索空間，最后在2N個個體中根據目標函數值選出較優的N個個體構成初始種群。

(2)隨機執行DE/best/1或DE/rand/1差分變異策略產生變異個體。首先，隨機產生一個[0, 1]之間的數，當該隨機數小于0.5時，執行DE/rand/1策略，否則執行DE/best/1策略；其次，采用二項式交叉策略生成N個試驗向量個體；最后，在試驗向量和目標向量中選出N個個體進入下一代。

(3)當代數t>1時執行隔代映射算子策略[17]產生三個新個體，替換進化種群中最差的三個個體。

(4)判斷當前進化代數t是否為參數T的整數倍，如果是則執行探測算子策略產生兩個體，擇優選擇一個個體加入下一代種群，以增加進化種群的多樣性，否則不執行。

(5)判斷目標函數調用次數是否大于最大目標函數調用次數，是則輸出當前最優解，否則轉到步驟(2)。

其算法流程如圖3所示。

圖3　IPDE算法流程

在步驟(1)中，反向學習策略使初始種群能更好地分布于搜索空間，便于提高算法的全局優化性能。步驟(2)采用隨機策略較好地避免了單獨采用DE/rand/1策略收斂速度慢的缺點，同時也避免了單獨采用DE/best/1策略收斂速度較快可能導致局部收斂的缺陷。在步驟(3)中，采用隔代映射算子較好地利用了當前代和上一代種群中的最優個體信息，有利于快速有效地指導進化種群產生較優個體。

3測試函數及工程應用

3.1測試函數及參數設置

測試函數采用2005年IEEE進化計算大會公布的測試函數中的部分測試函數[19]：單峰函數F1～F5和多峰函數F6、F8～F12。在11個測試函數中，設計變量n為30。IPDE算法的參數設置為：N取70，F取0.8，Cr取0.9，執行探測算子的代數T取20，隔代映射算子中參數γ=s=λ=0.6。為了便于對比各算法的魯棒性，IPDE算法對每個測試函數獨立運算25次，統計其函數誤差值(f(x′)-f(x*))的平均值和標準差，其中x*為測試函數已知的最優解。當算法最大函數評價次數達到300 000次后，算法迭代結束并輸出最優解x′。

3.2算法性能比較

3.2.1與兩種改進的DE算法比較

基于差分進化模式的SaDE(DEwithstrategyadaptation)算法[20]和EPSDE(ensembleofmutationstrategiesandcontrolparameterswithDE)算法[21]求解優化問題時，具有較優異的綜合性能。SaDE算法[20]利用先前搜索過程中積累的經驗，以自適應的方式同時選擇試驗向量產生策略和控制參數。EPSDE算法[21]則采用三種試驗向量產生策略和一組參數的隨機組合產生變異個體。為此，將IPDE算法與SaDE算法和EPSDE算法進行比較，其中，SaDE算法和EPSDE算法求解測試函數的仿真實驗統計數據分別通過參考文獻[20-21]獲得，具體統計結果如表1所示。表1中，“-”，“+”和“≈”分別表示相應算法統計性能差于、優于和相似于IPDE。m和s分別表示25次獨立運行的函數誤差值的平均值和標準差。

表1　IPDE與SaDE、EPSDE、CLPSO和GL-25在11個測試函數上的統計結果

(a)F1收斂曲線

(b)F2收斂曲線

(c)F3收斂曲線

(d)F4收斂曲線圖4　F1、F2、F3和F4收斂曲線

從表1中得出，IPDE算法相比于SaDE算法和EPSDE算法在整體上具有較優異的全局優化性能。具體地，IPDE算法分別在5個和6個測試函數上性能優于SaDE算法和EPSDE算法，在3個測試函數上性能相似于SaDE算法和EPSDE算法，分別在3個和2個函數上劣于SaDE算法和EPSDE算法。IPDE算法、SaDE算法和EPSDE算法求解11個測試函數收斂曲線如圖4～圖6所示。由圖4～圖6可以看出，IPDE算法在整體上一致收斂到全局最優解，其收斂性能在函數F2～F8、F10和F11上顯著優于SaDE算法，在F2～F4、F8、F11和F12上顯著優于EPSDE算法。3.2.2與兩種非DE模式的進化算法比較

為進一步驗證該算法的有效性，采用非差分進化模式的CLPSO(comprehensive learning particle swarm optimizer)算法[22]和GL-25(global and local real-coded genetic algorithms)算法[23]進行對比分析。CLPSO算法[22]以粒子群算法為基礎，其核心為一個粒子采用其他所有粒子的最好信息更新其速度。GL-25算法[23]是一類基于混合實數編碼的遺傳算法。兩種算法求解測試函數的仿真結果統計于表1。從表1中得出，IPDE算法在整體上顯著優于CLPSO算法和GL-25算法。就11個測試函數的統計特性而言，IPDE算法分別在8個和10個測試函數上優于CLPSO算法和GL-25算法。與IPDE算法相比，CLPSO算法僅在2個測試函數(F1和F9)上占優，而GL-25算法在11個測試函數上均不能占優。

(a)F5收斂曲線

(b)F6收斂曲線

(c)F8收斂曲線

(d)F9收斂曲線圖5　F5、F6、F8和F9收斂曲線

由上述5種算法求解11個測試函數的仿真結果和收斂曲線得出：相比于對比算法，IPDE算法在獲得最優解的同時具有較好的全局優化和快速收斂性能。

按照13號線停站方案，運行圖鋪畫結果顯示(快車-慢車-慢車-慢車-快車的發車間隔為3 min-3 min-2 min-2 min)，遠期早高峰慢車需在白芒站、羅租站、同觀路站、東周路站和長春北站待避。

3.3工程實例

3.3.1火炮身管結構優化設計

火炮的射擊精度在很大程度上取決于射彈的初始條件，而火炮發射時身管的振動對射彈初始條件有較大的影響，因此，優化設計身管的結構來調節其固有頻率具有重要的意義。本文采用文獻[24]所簡化的身管模型，如圖7所示，其模型主要由6根Timoshenko梁組成，其中m1和m2為簡化的炮口制退器和炮尾的集中質量，圖中兩支撐點為搖架的前后支撐點，L為身管的總長，xi(i=1,2,…,5)表示各個等截面Timoshenko梁的長度。

(a)F10收斂曲線

(b)F11收斂曲線

(c)F12收斂曲線圖6　F10、F11和F12收斂曲線

圖7　簡化的火炮身管模型

身管模型的一階固有頻率的高低可表征其剛度的大小，所以將最大化身管的一階固有頻率ω作為優化目標函數，其設計變量為身管的各軸向長度xk(k=1,2,…,5)，其數學模型表示為

(8)

某汽車車架結構[25]如圖8所示，由2根縱梁和8根橫梁組成，需優化其橫梁的布置使車架在y方向上具有最大剛度。bi(i=1,2,…,8)表示8根橫梁，xi(i=1,2,3,4)表示各橫梁之間的跨距。車架為汽車的基座，大多數關鍵部件如發動機、懸架、油箱和駕駛室等都固定于車架，而這些部件通過連接件對車架產生載荷，通過簡化處理，獲得車架的靜力學模型如圖9所示。圖中Q1、Q2、Q3和Q4分別表示駕駛室、發動機、油箱和載重的等價質量作用于車架的載荷，分別取值為19 600N，39 200N，4410N，343 000N；三角形表示不同方向的固定約束。車架材料的密度為ρ=7.86×103kg/m3，彈性模量E=2.0×108Pa，泊松比ν=0.3。

圖8　某車架簡化模型(mm)

圖9　車架有限元模型及加載

橫梁b1、b6、b7、b8固定，其他橫梁間的跨距需優化。因為車架變形在y向上的最大位移可表征其剛度的大小，故將其作為目標函數，建立如下的優化問題：

(9)

式中，dmax為車架變形后在y向上的最大位移。

建立車架的有限元模型，采用SHELL63單元劃分網格。采用IPDE算法優化，初始種群N為30，收斂準則為連續兩代獲得最大位移誤差小于10-3mm，其他參數設置與求解測試函數的參數設置一致。該算法優化求解獲得的最小最大位移為1.682mm，其對應的最優設計向量為(410mm, 1580mm, 1030mm, 791mm)，降低了原模型的最大位移，使車架結構設計更為合理。工程設計師可根據優化結果結合工程經驗指導實際的工程設計。

4結語

提出了一種基于隔代映射算子的差分進化算法來求解優化問題，在保證解的精度的同時具有較快的收斂速度。11個單峰和多峰測試函數驗證了該算法具有優秀的全局優化與快速收斂性。其統計性能指標表明，IPDE算法相比于SaDE算法和EPSDE算法分別在5個和6個測試函數中優于SaDE算法和EPSDE算法，并分別在8個和11個測試函數上顯著優于非差分模式的CLPSO算法和GL-25算法。最后，算法被應用于兩個實際工程問題的求解，獲得了比優化前更好的設計方案。

參考文獻：

[1]StornR,PriceK.DifferentialEvolution-aSimpleandEfficientHeuristicforGlobalOptimizationoverContinuousSpaces[J].JournalofGlobalOptimization, 1997, 11(4): 341-359.

[2]Mezura-MontesE,CoelloCAC,VelZquez-ReyesJ,etal.MultipleTrialVectorsinDifferentialEvolutionforEngineeringDesign[J].EngineeringOptimization, 2007, 39(5): 567-589.

[3]陳勇, 吳云翔, 王亞良, 等. 訂單不確定下雙資源約束多裝配線魯棒調度[J]. 中國機械工程, 2014, 25(12): 1567-1573.

ChenYong,WuYunxiang,WangYaliang,etal.Multi-assemblyLineRobustSchedulingofDoubleResourceConstrainsunderUncertainOrders[J].JournalofMechanicalEngineering, 2014, 25(12): 1567-1573.

[4]趙燕偉, 張立萍, 張景玲, 等. 加工裝配式流水車間節能調度建模與優化[J]. 中國機械工程, 2014, 25(16): 2196-2203.

ZhaoYanwei,ZhangLiping,ZhangJingling,etal.ModelingandOptimizationofProcess-assembly-typeFlow-shopSchedulingProblemwithEnergySaving[J].JournalofMechanicalEngineering, 2014, 25(16): 2196-2203.

[5]FanHY,LampinenJ.ATrigonometricMutationOperationtoDifferentialEvolution[J].JournalofGlobalOptimization, 2003, 27(1): 105-129.

[6]ZhangJ,SandersonAC.JADE:AdaptiveDifferentialEvolutionwithOptionalExternalArchive[J].IEEETransactionsonEvolutionaryComputation, 2009, 13(5): 945-958.

[7]DasS,AbrahamA,ChakrabortyUK,etal.DifferentialEvolutionUsingaNeighborhood-basedMutationOperator[J].IEEETransactionsonEvolutionaryComputation, 2009, 13(3): 526-553.

[8]WangY,CaiZ,ZhangQ.EnhancingtheSearchAbilityofDifferentialEvolutionthroughOrthogonalCrossover[J].InformationSciences, 2012, 185(1): 153-177.

[9]RonkkonenJ,KukkonenS,PriceKV.Real-parameterOptimizationwithDifferentialEvolution[C]//ProceedingsoftheIEEECongressonEvolutionaryComputation(CEC'2005),Piscataway,NJ:IEEEPress,2005:506-513.

[10]ZhuW,TangY,FangJA,etal.AdaptivePopulationTuningSchemeforDifferentialEvolution[J].InformationSciences, 2013, 223: 164-191.

[11]BrestJ,GreinerS,BoskovicB,etal.Self-adaptingControlParametersinDifferentialEvolution:aComparativeStudyonNumericalBenchmarkProblems[J].IEEETransactionsonEvolutionaryComputation, 2006, 10(6): 646-657.

[12]WangY,CaiZ,ZhangQ.DifferentialEvolutionwithCompositeTrialVectorGenerationStrategiesandControlParameters[J].IEEETransactionsonEvolutionaryComputation, 2011, 15(1): 55-66.

[13]車林仙, 何兵, 程志紅. 6-CRS并聯機器人機構及其位置分析[J]. 中國機械工程, 2010,21(14): 1669-1675.

CheLinxian,HeBing,ChengZhihong.A6-CRSParallelManipulatorandItsPositionalAnalysis[J].JournalofMechanicalEngineering, 2010,21(14): 1669-1675.

[14]楊曉明, 邱清盈, 馮培恩, 等. 盤式制動器的全性能優化設計[J]. 中國機械工程, 2005, 16(7): 630-633.

YangXiaoming,QiuQingying,FengPei’en,etal.OptimalDesignforOverallPerformanceofDiskBrake[J].JournalofMechanicalEngineering,2005, 16(7): 630-633.

[15]王前, 楊志堅, 丁康. 基于新自適應差分進化算法的MagicFormula輪胎模型參數辨識方法[J]. 機械工程學報, 2014, 50(6): 120-128.

WangQian,YangZhijian,DingKang.MethodinIdentifyingtheParametersofMagicFormulaTireModelBasedonNewSelf-adaptiveDifferentialEvolution[J].JournalofMechanicalEngineering, 2014, 50(6): 120-128.

[16]RahnamayanS,TizhooshHR,SalamaMM.Opposition-basedDifferentialEvolution[J].IEEETransactionsonEvolutionaryComputation, 2008, 12(1): 64-79.

[17]Xu Y, Li G, Wu Z. A Novel Hybrid Genetic Algorithm Using Local Optimizer Based on Heuristic Pattern Move[J]. Applied Artificial Intelligence, 2001, 15(7): 601-631.

[18]劉桂萍. 基于微型遺傳算法的多目標優化方法及應用研究[D].長沙： 湖南大學, 2007.

[19]Suganthan P N, Hansen N, Liang J J, et al. Problem Definitions and Evaluation Criteria for the CEC 2005 Special Session on Real-parameter Optimization[R]. Singapore:Nanyang Technological University,2005.

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

[21]Mallipeddi R, Suganthan P N, Pan Q K, et al.Differential Evolution Algorithm with Ensemble of Parameters and Mutation Strategies[J]. Applied Soft Computing, 2011, 11(2): 1679-1696.

[22]Liang J J, Qin A K, Suganthan P N, et al. Comprehensive Learning Particle Swarm Optimizer for Global Optimization of Multimodal Functions[J]. IEEE Transactions on Evolutionary Computation, 2006, 10(3): 281-295.

[23]Garcia-Martnez C, Lozano M, Herrera F, et al. Global and Local Real-coded Genetic Algorithms Based on Parent-centric Crossover Operators[J]. European Journal of Operational Research, 2008, 185(3): 1088-1113.

[24]陳光宋, 錢林方, 徐亞棟, 等. 身管橫向固有振動的半解析解法[J]. 兵工學報, 2012, 33(10): 1168-1172.

Chen Guangsong, Qian Linfang, Xu Yadong, et al.Semi-analysis Solution of Nature Frequency of Transverse Vibration of a Barrel[J]. Acta Armamentarii, 2012, 33(10): 1168-1172.

[25]Jiang C, Han X, Lu G Y, et al. Correlation Analysis of Non-probabilistic Convex Model and Corresponding Structural Reliability Technique[J]. Computer Methods in Applied Mechanics and Engineering, 2011, 200(33): 2528-2546.

(編輯王艷麗)

Differential Evolution Algorithm with Intergeneration Projection Operator

Fu Chunming1Jiang Chao1Chen Guangsong2Ji Lei2

1.State Key Laboratory of Advanced Design and Manufacturing for Vehicle Body,Hunan University,Changsha,410082 2.Nanjing University of Science and Technology,Nanjing,210094

Abstract：A DE based on intergeneration projection operator with good optimum and fast convergence performance was proposed to solve optimization problems. The proposed method based on the classical differential evolution mainly included the following characteristics. Firstly, for improving the diversity of population, opposition learning was employed to generate initial population and two different strategies were randomly selected to generate new mutant individuals. Secondly, an intergeneration projection operator was designed to generate three offsprings to substitute for the three worst individuals into the next generation. Thirdly, the exploratory operator was introduced to generate the new individuals into the next generation for keeping the diversity of evolutionary population and avoiding to obtain local solution. Finally, the performances of IPDE algorithm were verified by the eleven single-and multi-modal benchmark tests and two practical engineering problems.

Key words：differential evolution(DE) algorithm; intergeneration projection(IP) operator; opposition learning; explorative operator

收稿日期：2015-07-27

基金項目：國家自然科學基金資助項目(11172096)；教育部全國百篇優秀博士論文資助項目(201235)；湖南省杰出青年基金資助項目(14JJ1016)

中圖分類號：TP18

DOI：10.3969/j.issn.1004-132X.2016.11.019

作者簡介：符純明，男，1987年生。湖南大學機械與運載工程學院博士研究生。主要研究方向為智能算法及多目標優化。姜潮(通信作者)，男，1978年生。湖南大學機械與運載工程學院教授、博士研究生導師。陳光宋，男，1987年生。南京理工大學機械工程學院博士研究生。吉磊，男，1990年生。南京理工大學機械工程學院博士研究生。