一种自适应多策略差分进化算法及其应用

徐斌，陶莉莉，程武山



一种自适应多策略差分进化算法及其应用

徐斌1，陶莉莉2，程武山1

（1上海工程技术大学机械工程学院，上海201620；2上海第二工业大学工学部，上海 201209）

针对差分进化算法由于固定参数设置而易早熟或陷入局部最优的问题，提出了一种自适应多策略差分进化算法（SMDE）。该方法以基本差分进化为框架，首先引入一个变异策略候选集合，一个缩放因子候选集合和一个交叉参数候选集合，然后在搜索过程中，以过去的搜索信息为基础，自适应地为下一时刻进化群体中的每个个体从候选集合中选择一组合适的变异策略和控制参数，以便在不同的进化时刻设置合适的变异策略和控制参数。对10个常用的标准测试函数进行优化计算，并与其他算法的结果进行了比较，实验结果表明，SMDE具有较好的搜索精度和更快的收敛速度。将SMDE用于化工过程动态系统不确定参数估计问题，实验结果表明该算法能较好地处理实际工程优化问题。

差分进化算法；自适应；多策略；动态系统；参数估计

引 言

差分进化算法（differential evolution，DE）是由Storn等[1]提出的新型启发式搜索算法，具有结构简单、可调参数少、鲁棒性强等特点，在求解各类复杂数值优化问题以及实际工程优化问题方面取得了满意的效果。但是，Pan等[2]认为，DE的搜索性能很大程度上取决于其子代生产策略（变异策略和交叉策略）以及对应的控制参数（种群规模，缩放因子和交叉参数CR），所以在使用DE求解问题时，首先需要选择合适的进化策略，然后确定对应的控制参数，才能使得算法效果较优[3]。因此，如何为DE设置有效的进化策略以及对应的控制参数，在提高算法收敛速度和求解精度的同时，防止陷入局部最优解，已经成为当前DE研究领域的热点。

在差分进化算法参数配置方面，研究者们总结了一系列有效的设置经验[4]，其中最为直接和有效的方案就是设计一种自适应调整方案，如Liu等[5]根据模糊原理，提出关于参数和CR的模糊适应性推理规则。Brest等[6]将控制参数编码到个体染色体中，然后根据搜索过程的反馈信息，自适应地调整参数和CR，提出了jDE算法。Zhang等[7]根据子代与父代之间的竞争情况、历史进化记录以及统计学习规则提出自动调整和CR的JADE方法。Mallipeddi等[8]将变异策略和控制参数看成整体，提出一种集成学习方法。除了研究和CR之外，研究者们对种群规模也感兴趣。Teo[9]使用绝对和相对的编码方法，提出了能自动调整、和CR的DESAP算法。Zhu等[10]根据搜索状态，提出能自动调整进化种群的APTS策略。杨卫东等[11]提出根据种群平均适应度方差非线性改变交叉概率因子的方法，在种群多样性不同时分别采用不同的调整策略。

最近，研究者们对DE进化策略的自适应调整产生了兴趣。因为这类策略能够在不同的进化时刻采用不同的个体重组策略。Qin等[12]根据先前的成功搜索经验自适应地调整当前的子代个体生成策略及其对应的参数和CR，提出了SaDE算法。Wang等[13]提出了结合几种有效的子代产生策略和合适的进化参数来提高DE性能的思想。Gong等[14]提出一种能自动为个体选择合适的变异策略的策略选择机制，并将其结合到JADE算法中，效果明显。向万里等[15]设计交叉概率控制参数库、变异尺度参数库及差分变异策略库，并采用不同的机制产生对应的参数值。Wu等[16]将进化种群分为indicator种群和reward种群两种类型，并采用3种不同的变异策略和类似JADE中自适应参数调整策略。为了提高计算效率，Gong等[17]将多策略模型和代理模型相结合，提出一种基于较为实用的多算子进化算法模型，在求解复杂单目标问题方面具有优势。

结合控制参数和进化策略自适应调整这两方面的优势，本文提出一种自适应多策略差分进化算法（self-adaptive differential evolution algorithm with multiple strategies，SMDE）。本方法以经典DE算法为框架，为了充分利用进化群体在迭代过程中的有用信息，增强算法搜索能力，引入一个变异策略集合、一个缩放因子集合以及一个交叉参数集合。然后在迭代计算过程中，根据过去的搜索信息，动态自适应地为种群中每个个体从这3个集合中选择合适的变异策略以及控制参数和CR，在保证搜索效率的同时提高搜索精度，防止陷入局部最优。

1 基本DE算法

rand/1

best/1

current-to-best/1

rand/2

best/1

其中，1、2、3、4、5是区间[1]内与不等的随机整数，且满足两两互不相等。缩放因子是一个正常数，通常被限定在区间[0 1]之内。变异之后得到的新个体与父代个体进行交叉操作，交叉操作过程为

2 改进差分进化算法

本文提出的SMDE算法的一个重要特点是以过去成功的经验为基础，引入一个变异策略集合、一个缩放因子集合以及一个交叉参数集合。然后在迭代计算过程中，根据搜索信息自适应地从集合中选择参数参与计算。

2.1 变异策略自适应调整策略

随着DE的不断发展，研究者们提出了许多不同类型的变异策略，但是，至今仍然没有一种理论上的变异策略选择方案，因此，在DE中采用多变异策略得到许多研究者们的青睐[12-15]。为了平衡SMDE算法在不同阶段的探索和开发能力，选择rand/1、rand/2、current-to-best/1和best/2这4种不同类型的变异策略构成一个变异策略候选集合（SS）。在进化过程中，为种群中每个个体从集合SS中动态选择合适的变异策略，其自适应调整方式为

2.2 控制参数自适应调整策略

在确定变异策略之后，需要确定一组合适的控制参数和CR。SMDE参数控制策略基本思想就是以这些经验区间为基础，在区间中选择一些具有代表性的离散值构成候选参数集合，然后在不同的进化时刻，从参数集合中选择合适的值参与计算。

对于参数，在区间[0.4 1.2]中，以0.1为步长选择9个值构成候选集合FS，然后在进化过程中，根据搜索信息为种群中每个个体动态选择合适的值，其自适应调整方式为

对于参数CR，在区间[0.0 1.0]中，以0.2为步长选择6个值构成CR候选集合CRS，然后在进化过程中，根据搜索信息为种群中每个个体动态选择合适的CR值，其自适应调整方式为

从上面的参数调整策略可以看出，该调整策略类似于jDE算法的调整策略[7]，但是，它们是不一样的。首先，在SMDE中有变异策略的调整方案，而jDE中没有；其次，SMDE从有限集合中选择潜在参数，而jDE从给定的连续区间中随机生成控制参数。

2.3 算法基本流程

结合基本DE算法的框架以及上述介绍的变异策略和控制参数自适应调整策略，提出自适应多策略差分进化算法（SMDE），具体实现过程如下。

（1）算法初始化。设定种群规模为，算法停止条件max_nfes，变异策略候选集合SS，缩放因子候选集合FS，交叉参数候选集合CRS。

（2）种群初始化。设初始迭代步数=0，在搜索范围内随机初始化初始种群，，并为种群中每个个体从3个候选集合中分别随机选择一个变异策略S，F和CR。

（4）按照式（7）执行选择操作。

（5）根据式（8）～式（10）调整和更新每个个体下一进化时刻对应的变异策略，和。

（6）判断算法是否满足终止条件。若满足，则算法结束，输出当前最优值为最终结果；若不满足，令，并转至步骤（3）。

3 实验设置与分析

3.1 SMDE算法性能测试

为了验证SMDE算法的有效性，选择10个常用的基准测试函数进行实验仿真[18]。这10个测试函数中，有单峰函数，也有多峰函数，有的函数最优值附近有大量局部极小值，因此具有代表性。为了方便对实验结果进行通知，选择最小误差、取得固定误差值所需要的函数评价次数、成功率以及收敛曲线图4个常用的技术指标进行结果分析[14]。

为了方便进行结果比较和分析，选择两种具有代表性的自适应差分进化算法（jDE[6]和SaDE[12]）进行比较。对于SMDE，取种群规模，对于jDE与SaDE，其参数分别选择对应文献建议值，算法停止条件为函数评价次数max_nfes3×105次。3种算法独立运行25次后，统计误差平均值与标准方差，其统计结果见表1。

从表1可以看出，对于问题sph、ros和wht问题，SMDE结果优于jDE和SaDE，对于问题ack和sal，SMDE表现较弱，对于其他问题，3种算法都能取得较好的优化结果。

表2给出了优化过程中最小误差值小于10-8时，25次独立运行所需要的平均目标函数评价次数以及成功率。从表格中可以看出，对于大多数问题，如问题sph、ack、ras、pn1以及pn1等，虽然3种算法都能在最大迭代次数范围内让误差值达到10-8，但是，SMDE所需要的函数评价次数更少，收敛速度更快。

表1 各算法运行25次统计结果

表2 成功率与平均迭代次数统计结果

为了更加直观地展示算法求解过程，图1给出了10个测试函数收敛曲线。从图1可以看出，对于问题sph、ros、grw和wht，SMDE算法表现较好，对于问题ras和sch，SMDE差于jDE，但收敛速度好于SaDE，而对于其他问题，3种算法收敛性能相当。

图1 函数目标函数收敛曲线

从上面的结果分析可知，SMDE算法相比jDE和SaDE具有优势，是一种有效的求解全局数值优化问题的方法。

3.2 参数自适应策略分析

为了分析SMDE算法中参数自适应策略的有效性，选择ros和wht这两个代表性函数，对其参数自适应搜索过程进行具体分析。

图2给出了在求解ros函数过程中，最优结果为平均值对应的那次运行过程变异策略、缩放因子以及交叉参数概率变化曲线。从图可以看出，在求解该函数时，变异策略current-to-best/1，缩放因子0.4以及交叉参数1.0使用概率较高，使用这种组合求解效率较高。

图3给出了在求解wht函数过程中，变异策略、缩放因子以及交叉参数概率变化曲线。从图3可以看出，在进化前期，变异策略rand/1占优势，但是到后期，current-to-best/1策略占优势。对于缩放因子，进化前期多个参数使用概率相差不大，但是到了后期，参数0.4使用较多。对于交叉参数，进化前期参数0.0使用概率较大，但是后期参数1.0使用较多。

图2 函数Fros求解过程参数概率变化曲线

图3 函数Fwht求解过程参数概率变化曲线

从上面的结果分析可知，本文提出的参数自适应策略是一种参数调整方案，使用该方案可以使算法能够在不同的进化时刻，根据前期搜索信息，选择最为合适的进化策略及其对应的控制参数。

3.3 动态系统参数辨识及结果分析

通过求解10个基准函数，证明了SMDE的优化性能，为了进一步验证其在处理工程优化问题时的有效性，将其用于甲醇转化为烃类物质的反应模型不确定参数最优估计。甲醇转化为各不同烃类的反应模型表示形式为[19-20]

式中，A为氧化剂，B为甲醇，C为烃类物质，P为链烷烃、芳香族化合物以及其他产品。假定上述所有反应均为绝热条件下的一阶反应，碳烯浓度为常数，总的反应模型表示为

式中，1、2、3为A、C和P的浓度；是待辨识的模型参数。为了求解拟合模型，表3给出了实际生产过程产物A、C和P的17组浓度测量值。

表3 不同时刻y的测量值

在系统模型结构已知情况下，根据实际生产过程观测数据，取系统误差平方和为优化目标函数

表4给出了过程产物A、C和P模型输出值与观测值之间的误差值（模型输出值-测量值）。从表4中数值可以看出，大多数时刻浓度误差值都比较小，最小可达1.19×10-4，最大值为3.98×10-2。图4给出了系统模型输出数值与观测值拟合结果。表5给出了rSQP[20]，CPEMR[21]，PNSGA[19]，APSO[22]和SMDE 5种算法求解该动态模型的结果。从结果可以看出，SMDE算法得到的目标函数值较好，虽然对于某些成分值，如相对于APSO算法，A和P产物误差值较大，但是C物质误差值较低，总体目标函数值较好。可以看出，本文提出的SMDE算法是一种有效求解动态系统参数估计问题的方法。

表4 3种产物不同时刻误差值

图4 拟合结果与观测值比较

表5 5种算法的实验结果比较

4 结 论

提出一种新的基于多进化策略的自适应差分进化算法并用于求解化工过程动态模型参数辨识问题，结论如下。

（1）本文引入变异策略、缩放因子和交叉参数的候选集合，算法能针对不同的优化问题在不同的求解阶段，根据过去的搜索信息从候选集合中选择有效的变异策略及其对应的控制参数。

（2）将SMDE算法用于求解复杂标准测试函数，结果表明，与代表性自适应差分进化算法相比，SMDE算法能有效提高算法搜索速度和解精度，防止陷入局部最优值。

（3）将SMDE算法应用于甲醇反应动态模型不确定参数估计，结果表明，SMDE算法在求解化工过程动态模型系统参数估计问题具有较高的求解精度和较好的应用前景。

（4）本文SMDE算法未对交叉策略进行深入研究，都是采用最基本的二项交叉算子，未来研究工作将关注交叉策略的自适应调整策略，进一步增强算法的鲁棒性。

符 号 说 明

A——氧化剂 B——甲醇 C——烃类物质 CR——交叉参数 CRS——交叉参数候选集合 F——缩放因子 FS——缩放因子候选集合 max_nfes——算法最大迭代次数 N——种群规模 n——优化问题维度 P——链烷烃、芳香族化合物以及其他产品 rand[0,1]——[0,1]之间的随机数 randi(·)——随机整数选择函数 S——变异策略 SS——变异策略候选集合 u——交叉后个体 v——变异后个体 x——种群个体 y1——氧化剂浓度 y2——烃类物质浓度 y3——链烷烃、芳香族化合物以及其他产品浓度 θ——待辨识模型参数

[1] STORN R, PRICE K. Differential evolution—a simple and efficient heuristic for global optimization over continuous spaces [J]. Journal of Global Optimization, 1997, 11 (4): 341-359.

[2] PAN Q K, SUGANTHAN P N, WANG L,. A differential evolution algorithm with self-adapting strategy and control parameters [J]. ComputersOperations Research, 2011, 38 (1): 394-408.

[3] QIAN F, XU B, QI R,. Self-adaptive differential evolution algorithm with α-constrained domination principle for constrained multi-objective optimization[J] Soft Computing, 2012, 16 (8): 1353-1372.

[4] 刘波, 王凌, 金以慧. 差分进化算法研究进展 [J]. 控制与决策, 2007, 22 (7): 721-729. LIU B, WANG L, JIN Y H. Advances in differential evolution [J]. Control and Decision, 2007, 22 (7): 721-729.

[5] LIU J, LAMPINEN J. A fuzzy adaptive differential evolution algorithm [J]. Soft Computing, 2005, 9 (6): 448-462.

[6] BREST J, GREINE S, BOSKOVIC B,. Self-adapting control parameters in differential evolution: a comparative study on numerical benchmark problems [J]. IEEE Transactions on Evolutionary Computation, 2006, 10 (6): 646-657.

[7] ZHANG J, SANDERSON A C. JADE: adaptive differential evolution with optional external archive [J]. IEEE Transactions on Evolutionary Computation, 2009, 9 (6): 945-958.

[8] MALLIPEDDI R, SUGANTHAN P N, PAN Q K,. Differential evolution algorithm with ensemble of parameters and mutation strategies [J]. Applied Soft Computing, 2011, 11 (2): 1679-1696.

[9] TEO J. Exploring dynamic self-adaptive populations in differential evolution [J]. Soft Computing, 2006, 10 (8): 673-686.

[10] ZHU W, TANG Y, FANG J A,. Adaptive population tuning scheme for differential evolution [J]. Information Sciences, 2013, 223 (1): 164-191.

[11] 杨卫东, 姚峰, 张明. 基于自适应交叉概率因子的差分进化算法及其应用 [J]. 信息与控制, 2010, 39 (2): 187-193. YANG W D, YAO F, ZHANG M. Differential evolution algorithm based on adaptive crossover probability factor and its application [J]. Information and Control, 2010, 39 (2): 187-193.

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

[13] WANG Y, CAI Z, ZHANG Q. Differential evolution with composite trial vector generation strategies and control parameters [J]. IEEE Transactions on Evolutionary Computation, 2011, 15 (1): 55-66.

[14] GONG W Y, CAI Z H, LING C X,. Enhanced differential evolution with adaptive strategies for numerical optimization [J]. IEEE Transactions on Systems, Man, and Cybernetics—Part B: Cybernetics, 2011, 41 (2): 397-413.

[15] 向万里, 马寿峰, 安美清. 具有Pbest引导机制的适应性多策略差分进化算法 [J]. 模式识别与人工智能, 2013, 26 (8): 711-721. XIANG W L, MA S F, AN M Q. Adaptive multiple strategy differential evolution algorithm with guiding scheme of Pbest [J]. Pattern Recognition and Artificial Intelligence, 2013, 26 (8): 711-721.

[16] WU G H, MALLIPEDDI R, SUGANTHAN P N,. Differential evolution with multi-population based ensemble of mutation strategies [J]. Information Sciences, 2016, 329 (2): 329-345.

[17] GONG W, ZHOU A, CAI Z. A multioperator search strategy based on cheap surrogate models for evolutionary optimization [J]. IEEE Transactions on Evolutionary Computation, 2015, 19 (5): 746-758.

[18] NOMAN N, IBA H. Accelerating differential evolution using an adaptive local search [J]. IEEE Transactions on Evolutionary Computation, 2008, 12 (1): 107-125.

[19] 商秀芹, 卢建刚, 孙优贤, 等. 一种基于偏好的多目标遗传算法在动态模型参数辨识中的应用 [J].化工学报, 2008, 59 (7): 1620-1624. SHANG X Q, LU J G, SUN Y X,. A preference-based non-dominated sorting genetic algorithm for dynamic model parameters identification [J]. Journal of Chemical Industry and Engineering (China), 2008, 59 (7): 1620-1624.

[20] 江爱朋, 邵之江, 钱积新. 基于简约SQP和混合自动微分的反应参数优化 [J]. 浙江大学学报(工学版), 2004, 38 (12): 1606-1614. JIANG A P, SHAO Z J, QIAN J X. Optimization of reaction parameters based on rSQP and hybrid automatic differentiation algorithm [J]. Journal of Zhejiang University (Engineering Science), 2004, 38 (12): 1606-1614.

[21] MARIA G. An adaptive strategy for solving kinetic model concomitant estimation—reduction problems[J]. The Canadian Journal of Chemical Engineering, 1989, 67(5): 825-832.

[22] 夏立荣, 李润学, 刘启玉, 等. 基于动态层次分析的自适应多目标粒子群优化算法及其应用 [J]. 控制与决策, 2015, 30 (2): 215-222. XIA L R, LI R X, LIU Q Y,. An adaptive multi-objective particle swarm optimization algorithm based on dynamic AHP and its application [J]. Control and Decision, 2015, 30 (2): 215-222.

A self-adaptive differential evolution algorithm with multiple strategies and its application

XU Bin1, TAO Lili2, CHENG Wushan1

(1School of Mechanical Engineering, Shanghai University of Engineering Science, Shanghai 201620, China;2College of Engineering, Shanghai Second Polytechnic University, Shanghai 201209, China)

A self-adaptive differential evolution algorithm with multiple strategies (SMDE) was proposed to overcome premature or localized optimization of differential evolution (DE) as a result of fixed parameter settings. Based on basic framework of classical DE, the first step in SMDE was to create a candidate set of mutation strategy, scale factor () and crossover rate (CR). In the followed searching process, mutation strategy,andCR for each individual variable in next evolutionary generation were determined self-adaptively from the corresponding candidate set according to knowledge learnt from previous searches, so that proper mutation strategies and control parameters could be set at various evolution stages. Compared to other famous DE variants on optimizing 10 routine standard testing problems, SMDE had better search precision and faster convergence rate. Moreover, study on estimation of uncertain parameters in dynamic process systems of chemical engineering showed that SMDE could effectively solve engineering optimization challenges.

differential evolution algorithm; self-adaptive; multiple strategies; dynamic system; parameter estimation

date: 2016-09-09.

XU Bin, xubin@mail.ecust.edu.cn

10.11949/j.issn.0438-1157.20161273

TP 301

A

0438—1157（2016）12—5190—09

上海高校青年教师培养资助计划项目（ZZgcd14002）；上海市科委地方高校能力建设项目（14110501200）。

supported by the Young College Teachers Program of Shanghai Education Committee (ZZgcd14002) and the Local Colleges and Universities Capacity Construction Project of Shanghai Science and Technology Commission (14110501200).

2016-09-09收到初稿，2016-09-16收到修改稿。

联系人及第一作者：徐斌（1984—），男，博士，讲师。