一种随机变异策略的改进DE算法

刘龙龙

差分进化算法存在进化后期收敛变慢，易陷入局部最优等情况，本文从差分进化算法的变异算子，变异策略等方面改进，提出一种新的改进差分进化算法（IRDE）。利用4个基准函数对IRDE算法进行检验，检验结果表明，本文提出的改进方式能够有效的提升DE算法的收敛速度和全局寻优能力。

差分进化算法（DE，Differential Evolution）是在1995年被Stron等人提出的一种智能寻优算法，该算法的主要思想是在解空间中以随机初始化的方式产生第一代个体，并通过变异、交叉、选择等策略在解空间中寻找适应度最好的个体作为最优个体输出。该算法具有鲁棒性较强，简单易实现等特点，因此受到了相关研究人员的关注。由于DE算法种群中个体的差异程度会影响算法进化效率，而在算法运行后期，种群间个体的相似程度较高、差异性较小，导致算法的进化效率变低、收敛能力下降。针对该不足之处，当前最为常见的改进方式主要有两类：一种是对算法本身的公式或参数进行改进；第二类是将两种算法结合，形成更具优势的新算法。

文献中作者将现有策略DE/rand/1与DE/best/1组合形成一种多变异策略的改进DE算法，并利用4个Benchmark函数对改进算法进行测试，测试结果表明该改进方法取得了较好的效果。文献中作者对算法后期的易陷入局部最优的情况进行分析，在对种群的多样度理论进行研究的基础上，提出一种可以改善种群多样性的改进差分进化算法。文献中作者分别引入变异策略、缩放因子以及交叉参数的候选集，通过运行过程中的历史信息来自适应的选择变异策略、缩放因子以及交叉参数进行组合，提出了一种新的改进差分进化算法（SMDE），并采用10个测试函数对其进行测试。文献中作者将PSO算法中的社会学习机制与差分进化算法相结合，通过随机变异操作来增加种群的多样性，保证算法的全局寻优能力，并利用最优个体信息指引种群进化方向，经过测试表明，改进算法具有较好的优化效果。文献中作者将模拟退火算法中的模型退火操作引入到DE算法中，通过模型退火算子的突变搜索能力增加算法的种群多样性，增强算法的全局寻优能力。

本文主要采用第一类改进方式，在标准DE算法的基础上，对其变异算子，变异策略等进行改进，提出一种新型的改进差分进化算法（IRDE）。

1标准DE算法

标准差分进化算法通过种群间的差异性进行进化，具有结构简单、容易实现、受控参数少等优点，其主要步骤包括以下几项：

1） 初始化. 此阶段为算法的起始阶段，在该步骤中，需要确定算法参数以及种群初始化的方式。标准DE算法中的种群初始化方式如下所示：

其中， 为第一代种群， 为种群中个体元素的取值下界， 为元素的取值上界， 为种群规模， 为每个个体的长度（即个体中元素的数量）。

2） 变异. 在该步骤中，DE算法随机从父代种群中选取三个个体进行变异操作，选择其中的一个作为待变异个体，利用剩余两个个体进行差分操作，并将其差分结果与变异算子相乘后与待变异个体相加，产生变异后的新个体，变异策略如式（2）所示，之后对该新个体中元素的取值进行筛选，防止出现超出给定范围的元素，其筛选方式如（3）式所示。

其中， 表示变异产生的中间个体， 为第 代的第 个父代个体， 且互异， 为第 个变异个体的第 个元素， 为变异算子，其在标准算法中为常数。

3） 交叉. 交叉操作有利于增加算法的种群多样性，在该步骤中，将按照一定的规则，从变异产生的个体与父代个体中选择元素组成新个体，交叉策略所遵循的规则如下：

其中， 为经交叉操作后产生的新个体， 为交叉算子，标准算法中 为常数， 为 间的整数。

4） 选择. 在该操作中，标准DE算法通过对比父代个体与交叉产生的新个体的适应度大小，选择其中适应度较小的个体进入新种群。选择策略如下所示：

5） 判断是否结束. 计算目标函数值并对比目标函数值与结束条件，若满足，则结束；否则算法继续迭代。

2改进DE算法

文献指出，差分进化算法的收敛速度和寻优能力与算法的种群多样性有着较大的关系。算法中变异算子的取值、变异策略的选取以及交叉算子的取值均会对算法的种群多样性产生一定影响，因此，本文将从变异算子、交叉算子以及变异策略对标准DE算法进行改进。

2.1自适应变异算子.

从式（2）中可以看出， 的取值大小会对进化产生的新个体的生成位置产生影响。若给 赋予一个较大值，会增加算法的搜索范围，有利于寻找全局最优解，若给 赋予一个较小值，则算法会在一个较小的范围内进行寻优操作，有利于算法加速收敛。因此，在算法初期应给 赋予较大值，后期给 赋予一个较小值，基于此思想，提出一种递减型变异算子，该算子前期取值为0.8，并随着进化次数增加而逐渐减小，该算子的表达形式如下所示：

2.2随机变异策略

标准DE算法中，变异策略为固定形式。本文为了增加变异个体的随机性，对变异策略作出改进，通过设置一个随机数 （ ），比较 与变异算子的大小来选择变异策略。由于 具有随机性，因此，在IRDE算法中，变异策略将是随机的。随机变异策略的表达形式如下所示：

其中， 为变异产生的子代个体， 为0～1间的随机数， 为算法的当前最优解， 且互不相同。

2.3自适应交叉算子

交叉操作产生的新个体中的染色体主要来源于父代个体以及变异产生的子代个体。在该操作中， 的取值大小控制着新个体中父代个体染色体所占比例， 越小，更有利于保存父代个体的染色体，可以较好的实现全局寻优；反之，有利于算法加速收敛。基于这一情况，设置 的表达式如下。

其中， 與 分别表示当前迭代次数与最大迭代次数。

由于本文仅在上述三处地方进行了改进，因此，其余操作均参照标准DE算法进行。

2.4改进算法测试

为了检验IRDE算法的效果，采用4个基准函数（见表1）对IRDE算法进行测试。为了更好的体现出IRDE算法的改进效果，将IRDE算法与jDE（现有改进算法）]和标准DE算法进行比较，将三个算法的部分参数设置为： ，标准DE算法中， ，测试结果见表2.

从表2中可以看出，IRDE算法在对4个函数的寻优测试中，除函数Schwefels2.21外，其余函数均可以寻找到最优解，对于Schwefels2.21，IRDE算法也具有较高的收敛精度。相同情况下，在对jDE算法进行测试时，Schwefels2.26与Rastrigins函数存在一定的几率寻优成功，其余函数，jDE算法无法寻找到最优解。标准DE算法在所有测试函数的测试过程中均无法找到最优解。下文给出了4个函数测试效果图。

从表2的测试结果及4个基准函数的测试效果图可以看出，本文算法在收敛速度、收敛精度以及全局收敛能力上均有一定的提升。

3结论

本文主要针对标准差分进化算法存在的收敛速度慢、收敛精度低的不足进行改进，提出了一种拥有自适应变异算子、随机变异策略以及自适应交叉算子的改进差分进化算法（IRDE），并通过与jDE算法和标准DE算法的寻优效果对比，结果表明，IRDE算法实现了收敛速度更快，收敛精度更高以及全局寻优能力更强的目的，这一实验结果证明了本文所提出的改进策略的有效性。

但是也存在一定的不足之处，在本文选取的测试函数中，仍存在一个函数无法寻到最优解，后期还需要继续对算法的全局寻优能力及收敛速度进行研究。且本文算法仅在基准函数上进行了测试，后期还需要考虑到算法的实际应用，例如：将IRDE与SVM组合并应用于实例。

（作者单位：东华理工大学理学院）