差分进化算法的改进研究

蒋兵兵

（湖南铁路科技职业技术学院 湖南 株洲 412007）

0 引言

作为基于群体差异进行随机搜索的算法，差分进化算法的应用无需进行编码和解码，在受控参数较少的情况下获得了较强鲁棒性，在全局寻优方面的性能良好，目前在电力调度、多目标路径规划等多个领域应用广泛。但在实际应用过程中，差分进化算法同样存在过早收敛等问题，需要通过算法改进获得更高收敛精度。现阶段，改进差分进化算法的方法较多，还应掌握不同方法优势，以便结合实际需求合理进行算法改进和应用。

1 差分进化算法概述

1.1 算法原理

根据算法原理可知，对个体进行初始化操作，从种群中随机选择互异个体进行差分、缩放，与第3 个随机个体生成变异个体。而利用父代个体和变异个体进行交叉操作，可以获得试验个体，完成适应度值比较，选择较优个体继续迭代，直至达到终止准则[1]。从本质上来讲，就是对生物体的“优胜略汰”进化过程进行模拟，通过自适应自组织解决问题。将种群当成是操作对象实施并行优化，在迭代次数达到最大或找到最优解后可以停止寻优。

1.2 算法流程

标准的差分进化算法可以划分为种群初始化和进化迭代两个阶段，前者需在可行域内通过均匀分布等概率获得初始空间解向量，后者包含变异、交叉、选择等操作，在达到进化条件时将进行寻优，直至算法结束，见图1。该种算法具有记忆功能，经典变异操作包含DE/rand/1、DE/best/1 等。从算法步骤来看，假设种群中含NP 个个体，每个代表一个问题解，各解为D 维向量，个体表达为Xi，0={xi，1，0，xi，2，0，L，xi，D，0}，满足i=1，2，L，NP。

初始种群则为xi，j，0=xj，low+rand（0，1）·（xj，highxj，low），其中rand（0，1）服从均匀分布，在0 到1 之间随机取值，xj，high 和xj，low 分别指的是变量分量的上下限。在变异操作中，各目标向量将生成对应变异向量，引入新算子参与优解变异操作，能够适应种群动态变化过程。采用不同变异策略，将得到不同的变异公式。如采用DE/rand/1，能够得到：

式中，ui，jG+1、vi，jG+1和xi，jG+1分别指的是第i个试验向量、变异向量和目标向量的G+1 代j分量，j=1，L，D。CR 为交叉概率，Jrand 为根据维数j生成的随机数，能够改善算法多样性，确保至少一维分量来自变异个体，达到进化目的。利用C R 确定试验向量中的变异向量个数，取值在0 ～1 范围内。将变异向量和目标向量交叉获得的试验向量UiG，需限制产生个体向量范围，确保在规定上下限范围内。利用选择算子完成目标和试验向量选择，能够保存适应度好的个体，作为解向量继续迭代。

2 差分进化算法的改进方法

2.1 控制参数调整

该算法需要对多峰复杂函数进行求解，容易因参数设置不当导致种群多样性下降，因早熟而无法找到全局最优解。从算法控制参数来看，除了涉及缩放因子F，还包含种群规模NP 和交叉概率CR。在F 数值过大时，能够完成潜力解挖掘，反之则能为全局最优解的查找提供便利。而N 数值小能够加快算法收敛，出现早熟或停滞情况，反之可以提高种群多样性，但容易因计算量过大出现收敛慢的问题。而CR 过大，将引发多个个体变化，提高种群多样性，有助于寻解，数值过小则能保留更多个体信息。从早期研究来看，倾向于在较小数值范围内取值，如使F 在（0.5，1）范围内取值，使CR 在（0.9，1）范围内取值等，缺少算法执行过程中的信息反馈，导致相同参数在解决不同问题时取得的效果不同[2]。采取动态调整策略，在各代种群中根据个体目标函数完成参数自适应调节，能够取得更好的算法改进效果。如采用FADE 算法，通过模糊逻辑控制器和知识系统完成不一致参数实时调整，能够完成各代F 和CR 值调节。对前期进化优质解找寻经验进行借鉴，可以采用SaDE 算法进行F 和CR 值调整，设定为统一服从高斯分布，F 的服从均值为0.5，标准差为0.3，CR 服从均值为0.5，标准差为0.1，每25 代需要完成一次成功CR 值的更新。在NP 数值调整方面，可以采用DESAP 算法，随机生成（10×n）种群后，n 为参数变量个数，能够得到初始化的NPi为round（10+randn(0，1)），将缩放因子设定为1 后进化至预先指定种群大小，能够确定下代新种群大小。

2.2 操作算子改进

在算法操作中，包含变异、交叉和选择算子。选择算子仅根据适应度值确定，相对简单，因此算子改进研究主要针对变异算法和交叉算子。在变异算子改进方面，目前提出的策略包含DE/current-to-rand/1、三角变异策略、DE/rand/1/either-or 等多种。采用不同算子，能够通过取长补短适应种群进化。如在JADE 算法中，可以采用DE/current-to-pbest/1 策略，得到vi，G=xi，G+Fi（xbest，G-xi，G）+Fi（xr1，G-xr2，G），可知指的是种群目前寻到的最优个体，Fi则为个体j 的缩放因子，除了来自外部较差个体存档A和种群P 的并集，其余个体均来自种群P。此外，也可以将个别解协方差矩阵特征向量当成是算子进行交叉操作，具有旋转不变性特征。运用该算子进行算法改进，能够使供体个体得到修改，然后投影至替代坐标系特征向量上，适用于变化小的交叉策略[3]。

2.3 种群结构优化

通过优化种群结构方式进行算法改进，能够对算法收敛性能产生影响。如使用环形网络拓扑实施并行运算，能够提高算法收敛速度。而采用分布式算法或自适应算法，能够优化算法性能。如采用平均熵初始化策略完成种群拆分，利用不同变异策略加强种群信息交流，能够完成种群差分运算。利用自适应值大小完成多种群分类，实施不同进化策略可以完成全局优化。采用反向的差分进化算法，需要进行反向搜索，能够使种群的多样性得到改善，达到跳出局部最优的目的。此外，利用岛屿模型进行并行分布运算，将种群划分为多个独立亚种群，然后完成不同控制参数分配，可以得到固定世代间隔。使不同种群相互迁移，能够确保亚种群始终体现良好多样性，有助于算法改良。

2.4 混合算法分析

各种智能算法是基于不同现象和行为产生的，适用于不同场景。考虑到采用单一算法存在较大局限性，可以通过将不同算法结合实现原有算法改进。如在解决电力系统参数配置问题时，将DE 算法和粒子群算法融合，能够加强种群开发和探索。利用标准测试函数进行算法验证，能够保证算法稳定性。MDE-WOA 算法同样为混合算法，可以在差分进化运算中嵌入寿命机制，通过增强算法搜索能力解决局部最优问题，形成的算法不仅具有较强鲁棒性，也能获得较高准确性。在解决车辆路径规划问题时，将DE算法与蜂群算法结合，在迭代中引入进化算子，改善蜂群进化速度慢的问题，能够使形成的算法获得较强鲁棒性，并能实现全局收敛，保证算法的有效性[4]。针对组合优化问题，可以将DE 算法和量子算法结合在一起，增强算法鲁棒性，提高数据运算效率。现阶段，能够与差分进化算法结合的人工智能算法有较多，需要结合实际应用需求选择，确保算法混合能够解决收敛、寻优等问题，取得理想的算法应用效果。

3 差分进化算法的改进实践

3.1 约束优化问题

约束优化问题在生活中较为常见，但求解算法较少，面临搜索空间复杂、约束条件难处理等困难。在解决约束优化问题时，可知包含等式、不等式和边界等不同约束条件，得到：

式中，f(x)为目标函数，x=（x1，x2，...xn），取值范围D 为n 维度决策空间，gj(x)和hj(x)分别为不等式和等式约束，p、q 分别为约束个数，ui和li为xi的上下界。根据x 到j 个约束的距离，可知x 到可行域间距离为约束违反程度G(x)：

式中，Gj(x)指的是x 到j 约束距离，δ 为正容忍因子，取值为0.000 1。

3.2 基于GOBL 的算法

在差分进化算法改进方面，采用自适应约束方式过于强调判断个体是否达到约束条件，导致种群中不可行个体数量过多，容易出现寻解精度不高问题。采用反向学习策略（GOBL）进行种群结构优化，利用反向种群约束种群搜索空间，能够根据反向解信息加快运算[5]。根据可行率采取不同变异策略，实现算子自适应设计，能够提高种群多样性。将变异前后的种群混合，排序后完成不同个体选择，可以获得新种群。应用该算法，可知n 维空间中xi存在对应反向解，得到：

式中，k 在0 到1 范围内取值，xi在j 维取值在aj和bj之间，超出这一区域需要采用rand 函数随机生成xi，j数值。根据反向解缩小搜索空间，可以在初始化种群P 和新种群P1中选取数量为Np的个体。在处理无法满足条件的个体时，应利用自适应权衡模型ATM 将种群划分为可行、不可行、半可行3 种状态，将目标函数转换为：

式中，σ 指的是可行率，xbest 和xworst 则为最好和最差个体，Z1和Z2分别为满足和不满足约束条件的个体序号。通过完成目标函数值和违约值的标准化处理，能够得到个体适应值：

式中，ffanal(xi)指的是最终适应值，fnor(xi)和Gnor(xi)分别为目标函数值和违约值的标准化值，在可行时说明可以满足全部约束条件，可以利用目标函数值代表。按照传统差分进化算法，需要将父代向量中个体和新种群个体逐个比较，选择适应值更优的个体，可能出现两个适应值均较差个体相互比较，导致留下的个体适应值较大，影响收敛速度的同时，出现局部最优问题。为改进这一情况，需要完成父代种群和新种群合并，完成适应值排序，然后进行个体优选。

3.3 改进算法步骤

按照算法改进方法，需要先根据适应值完成个体排序，然后计算选择概率：

式中，Ri为个体排序值，N 为种群个体数量，λ 取值将影响参与变异个体，决定最优解搜索范围，体现个体支配关系。在λ 取值为2 的情况下，个体选择概率差值较大，支配关系更加显著。而λ 取值为0.5，支配关系相对模糊。因此将λ 取值为2，能够在进化初期使不可行个体达到约束，获得更多个体，依靠适应值大的个体加快搜索。在种群可行时，则能降低稍差个体选择概率，减少参与变异的个体，容易陷入局部最优问题，因此应使λ 取值为0.5。在采取变异策略时，比较不同策略可知，想要提高种群多样性需要进行自适应变异，得到：

式中，各x 变量为t 代不同个体，vi，t为变异后试验向量，xgbest为适应值最优个体。缩放因子F 在0 到2 之间取值，可知早期进化时个体较少，可行率较小，应选择DE/best/2 策略，利用最优个体资源对其他变异个体进行引领，达到快速收敛效果。在进化后期可行个体增加，可行率也有所增大，应选择DE/rand/2 策略改善种群多样性。考虑到控制参数F 和CR 将给算法寻优带来影响，需要采用自适应算子，得到：

式中，Gen 指的是最大迭代次数，t 为当前迭代次数，F0则为常数，在0 到1 范围内取值。在F0数值较小时，算法收敛慢，但过大将出现寻优能力下降问题，通过反复测试最终取值0.5。在早期进化过程中，多数个体适应值不佳，应增加F 数值以获得更大搜索范围，提升种群多样性。而经过多次迭代后，可以逐渐使F 趋近于F0，尽可能保留优秀个体，增加最优解查找概率。

3.4 算法测试分析

为确定算法改进效果，需要在问题处理时与标准DE算法和常见RMDE 算法进行比较。在算法种群规模NP 达到100 时，将各算法迭代次数设定为1 500 代，利用g02、g03 和g06 函数分别执行不同算法，然后对3 种算法的平均值等指标进行比较。如表1 所示，最终验证改进算法可以获得更好的寻优精度。

表1 测试结果

4 结论

对差分进化算法进行改进，可以采取调整控制参数、优化种群结构等多种方法。实际在改进方法运用过程中，需要结合实际需解决的问题选择适合的改进方法，如在解决约束优化问题时需同时采取调整控制参数、改进操作算子等措施，确保能够加强优秀个体资源利用，达到提高算法精度的目标。