差分进化算法(DE)的详述

用户7506105

发布于 2021-08-09 15:58:08

3.6K0

发布于 2021-08-09 15:58:08

文章被收录于专栏：碎片学习录

之前对一篇和本文类似的生物进化优化算法——遗传算法做了一些解释，本文所述的差分进化算法和遗传算法本身有相通的地方当然也有较多的差异。差分进化算法也是基于群体智能理论的优化算法，它是通过群体内个体间的合作与竞争而产生的智能优化算法，字面意思即可看出它有别于遗传算法的自由组合自然选择，它更侧重的是个体与个体和个体与自身间的关系，包括合作与竞争。

思想

其实是尽可能的较好的穷举，本质上是依靠贪婪算法，其通过自变量差分及概率选择扩大自变量搜索空间，通过适应度值大小进行简单粗暴的选择。

在具体解释该算法前，先把和遗传算法相通但又不完全相同的一些概念做一些解释，差分进化算法也和遗产算法一样，也有变异，交叉，选择几个过程，下面分别解释。

一些概念

变异

遗传算法这里是在编码映射后的基因串长的位点突变

先得到种群中的两个成员向量(自变量可行解)的加权差向量(公式见后，差分体现在这)，然后用得到的加权差向量与第三个成员向量相加即产生新的参数向量，因为变异在生物学中就是多样性的来源，所以这里的变异是为了试出更多的可行解

交叉

也有别于遗传算法，遗传算法是进行多个个体基因串间的重组

这里是在种群中先找到变异向量，然后与另外预先确定的目标向量按照一定的规则(见后)进行混合，所以交叉一定在变异操作的后面

选择

有别于遗传算法需要进行的轮盘选择

这里的选择是如果当前试验向量的代价函数比目标向量的代价函数低，则试验向量就在下一代中代替目标向量，比较简单粗暴，不像遗传算法需要计算累计概率判断每个基因染色体个体是否会在下一轮中被复制

适应度函数

即为要优化的目标函数，本文是取目标函数的最小化

步骤

1、初始化

种群个体表示为自变量维数为D的

X_{i,G}

实数值参数向量,其中i表示当前代数的个体序号，

的范围为

[1,NP]

，NP为种群规模总数即个体总数，G表示进化代数，在算法过程中NP保持不变

确定每个自变量维度j的上下限，即

[X_j^{(L)},X_j^{(U)}]

需要初始化第0代的种群个体，假定每个种群个体

的每个自变量参数j的值都服从上下限之间的均匀分布，即

X_{ij,0} = rand[0,1] * (X_j^{(U)} - X_j^{(L)}) + X_j^{(L)}

其中i=1,2,...,NP;j=1,2,...,D

如果可以预先得到问题的初始解，则初始种群也可以通过对初步解加入正态分布随机偏差来产生，这样就可以提高重建效果

2、变异

对于当前的个体

X_{i,G}

在进入下一代时需要从种群中随机选择三个互不相同的个体进行变异，三个变量相互合作得到新变量

所以种群规模必须

NP>=4

变异公式为

v_{i,G+1} = X_{r1,G} + F*(X_{r2,G} - X_{r3,G})

v_{i,G+1}

为当前为第

个的个体在进入变异成下一代后的个体，

为缩放因子，一般取值范围为

[0,2]

，用于控制差向量值的放大

3、交叉

设在

G_0

代的个体i在发生变异后变异成为了

u_{i,G_0+1}

,则此时的交叉操作体现在

u_{ij, G_0+1} = \begin{cases} v_{ij, G_0+1}, 当randb(j)<=CR或j=rnbr(i) \\ X_{ij, G_0}，当randb(j)>CR且j!=rnbr(i) \end{cases}

其中

randb(j)

为[0,1]随机数序列中的第j个估计值，rnbr(i)为表示第i个个体产生的在

[1,D]

范围上的随机数，CR为交叉概率

需要注意的是交叉操作是针对每个维度的自变量参数进行的操作，它要么依随概率变成变异后的下一代变量对应自变量位置的值，要么是保留当前代变量对应的自变量位置的值，由此产生的组合多样性。

4、边界的处理

因为变异和交叉最终会导致新个体的产生，所以难免新个体不满足约束，所以需要进行边界处理，一般有两种处理方式，假设在上面两个过程中的新变量的其中第j个参数

u_{ij,G+1}

不在

[X_j^{(L)},X_j^{(U)}]

之间:

一种方式是忽略该参数直接用公式

u_{ij,G+1} = rand[0,1] * (X_j^{(U)} - X_j^{(L)}) + X_j^{(L)}

即在上下限之间取随机数来代替不在范围内的值

第二种方式采用边界吸收处理，即

u_{ij, G+1} = \begin{cases} X_j^{(L)}, 当u_{ij, G+1}< X_j^{(L)} \\ X_j^{(U)}, 当u_{ij, G+1}>X_j^{(U)} \end{cases}

5、选择

依照的是贪婪算法，即每次选取当前状态下最优的解

将新变量

u_{i,G+1}

和之前的

X_{ij, G}

代入目标函数，如果前者小于后者，则用

u_{i,G+1}

代替

X_{ij, G}

，否则依然选择

X_{ij, G}

为新一代个体，所以这里就是产生的新变量和原来变量之间的竞争

注意这里的比较只是同一个个体i的目标函数之间的比较，而不是和种群中所有个体比较

值得强调的是当前的种群中的所有成员必须都分别当作目标向量

X_{i, G}

进行一次这样的操作，以便在下一代中出现相同个数竞争者(即种群规模一直不变)。在进化过程中对每一代的最佳参数向量都进行评价，以记录最小化过程。

因为该算法是利用随机偏差扰动产生新个体的方式，所以可以获得一个收敛性非常好的结果，引导搜索过程向全局最优解逼近

特点

自己和同代其他人相互合作，和不同时期的自己相互竞争，有被内涵到

易于实现，因为算法只涉及向量的加减运算，采用的又是随机概率值进行搜索，并且控制的参数比较少，只有缩放因子、交叉概率和种群规模三个参数，而这三个参数又都是具有实际指导性意义的
算法性能好，具有较好的可靠性、高效性和鲁棒性，是一种高效的并行搜索算法(每次都是随机选取，交叉变异又都是针对第i个自变量本身)，适用于求解一些利用常规的数学规划方法很难求解甚至无法求解的复杂优化问题，且对于非线性和不可求导的连续问题(即不存在对目标函数的限定)，其求解效率比其他进化方法好
自适应性好(自适应的含义是根据不同环境自动进行参数的调整的特性)，参数可以是固定常数，也可以具有变异步长和搜索方向随时变化的能力

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-07-08，如有侵权请联系 cloudcommunity@tencent.com 删除

机器学习