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

符纯明　姜　潮　陈光宋　吉　磊

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年生。南京理工大学机械工程学院博士研究生。