获取更多资讯，赶快关注公众号(名称：智能制造与智能调度，公众号：deeprlscheduler)吧！

1、思想

DE是由Rainer Storn 和 Kenneth Price于1995年提出的一种比较经典的进化算法，是一种新型并行直接搜索算法，每一代G中都利用NP个参数向量（个体）作为种群，在优化过程中NP是保持不变的。如果没有掌握一些系统的先验知识，通常初始种群是随机选择的，一般来说，除非另有说明，否则将对所有随机决策假定一个均匀的概率分布，在得到初步解后，通常通过在名义解 x ‾ nom  , 0 \underline{x}_{\text {nom }, 0} x​nom ,0​上加上正太分布的随机偏差来生成初始种群。DE背后的关键思想是一种生成试验参数向量的新方案，其将两个种群个体的差向量加权后再与第三个成员相加，然后就得到了新的参数向量。如果得到的向量的目标函数值低于（最小化问题）种群中的个体，则用新生成的向量替换与之比较的向量。此外，还对每一代G中的最优参数向量 X ‾ best  , G \underline{\mathrm{X}}_{\text {best }, \mathrm{G}} X​best ,G​进行评估，以追踪最小化进程。

从种群中提取距离和方向信息，产生随机偏差结果，该自适应方案具有良好的收敛性能。下面介绍两种最具潜力的DE变体。

2、方案DE1

变异

第一种DE变体的工作原理如下：对于每一个 x ‾ i , G , i = 0 , 1 , 2 , … , N P − 1 \underline{x}_{i, G}, i=0,1,2, \ldots, N P-1 x​i,G​,i=0,1,2,…,NP−1，根据下式生成试验向量：
v ‾ = x ‾ r 1 , G + F ⋅ ( x ‾ r 2 , G − x ‾ r 3 , G ) (1) \underline{\mathrm{v}}=\underline{\mathrm{x}}_{\mathrm{r}_{1}, \mathrm{G}}+\mathrm{F} \cdot\left(\underline{\mathrm{x}}_{\mathrm{r}_{2}, \mathrm{G}}-\underline{\mathrm{x}}_{\mathrm{r}_{3}, \mathrm{G}}\right)\tag {1} v​=x​r1​,G​+F⋅(x​r2​,G​−x​r3​,G​)(1)

其中 r 1 , r 2 , r 3 ∈ [ 0 , N P − 1 ] \mathrm{r}_{1}, \mathrm{r}_{2}, \mathrm{r}_{3} \in[0, \mathrm{NP}-1] r1​,r2​,r3​∈[0,NP−1]，均为整数且互不相同， F > 0 F>0 F>0。这一步相当于变异操作。

r 1 , r 2 , r 3 \mathrm{r}_{1}, \mathrm{r}_{2}, \mathrm{r}_{3} r1​,r2​,r3​为从 [ 0 , N P − 1 ] [0,NP-1] [0,NP−1]中随机选择的整数，之所以是 N P − 1 NP-1 NP−1，是因为这里所以是从0开始的，所以最后一个个体的索引是 N P − 1 NP-1 NP−1, F F F为实值常数因子，控制差分变化 ( x ‾ r 2 , G − x ‾ r 3 , G ) \left(\underline{\mathbf{x}}_{\mathbf{r}_{2}, \mathbf{G}}-\underline{\mathbf{x}}_{\mathbf{r}_{3}, \mathbf{G}}\right) (x​r2​,G​−x​r3​,G​)的放大率。图1以一个二维示例说明了不同向量再DE1中的作用。

图1 按照DE1生成v的过程

交叉

为了增加参数向量的多样性，构造如下向量：

u ‾ = ( u 1 , u 2 , … , u D ) T (2) \underline{\mathrm{u}}=\left(\mathrm{u}_{1}, \mathrm{u}_{2}, \ldots, \mathrm{u}_{\mathrm{D}}\right)^{\mathrm{T}}\tag{2} u​=(u1​,u2​,…,uD​)T(2)

u j = { v j  for  j = ⟨ n ⟩ D , ⟨ n + 1 ⟩ D , … , ⟨ n + L − 1 ⟩ D ( x ‾ i , G ) j  otherwise  (3) u_{j}=\left\{\begin{array}{ll} v_{j} & \text { for } \quad j=\langle n\rangle_{D},\langle n+1\rangle_{D}, \ldots,\langle n+L-1\rangle_{D} \\ \left(\underline{x}_{i, G}\right)_{j} & \text { otherwise } \end{array}\right.\tag{3} uj​={vj​(x​i,G​)j​​ for j=⟨n⟩D​,⟨n+1⟩D​,…,⟨n+L−1⟩D​ otherwise ​(3)

其中尖括号 ⟨ ⟩ D \langle\rangle_{D} ⟨⟩D​表示模为 D D D的模函数。

式(3)说明 u ‾ \underline{\mathrm{u}} u​中某一向量元素序列等于 v ‾ \underline{\mathrm{v}} v​中的元素，而 u ‾ \underline{\mathrm{u}} u​中的其他元素使用 x ‾ i , G \underline{x}_{i, G} x​i,G​中的原始值。为这种变异选择一组参数的过程类似于进化理论中交叉。图2解释了这一点，其中D=7，n=2,L=3。D为问题维度，起始索引 n n n式从 [ 0 , D − 1 ] [0,D-1] [0,D−1]内随机选择的整数， L L L以交叉概率 C r Cr Cr从 [ 0 , D − 1 ] [0,D-1] [0,D−1]内随机选择, L L L按以下方式确定， C r Cr Cr作用同 F F F，用于控制DE。对于每一个试验向量，都要随机生成新的 n n n和 L L L。
L = 0 ; D O { L = L + 1 ; }  WHILE  ( ( r a n d ( 0 , 1 ) ≤ C r ) A N D ( L ≤ D ) ) \begin{aligned} L &=0 ; \mathrm{DO} \\ &\{\\ L &=L+1 ; \\ &\} \text { WHILE }((r a n d(0,1) \leq C r) \mathrm{AND}(L \leq D)) \end{aligned} LL​=0;DO{=L+1;} WHILE ((rand(0,1)≤Cr)AND(L≤D))​

图2 交叉过程

所以从每个元素的角度就看，则可以得到以下公式：

u j , i , G = { v j , i , G  if  ( rand i , j [ 0 , 1 ] ≤ Cr or  j = j rand ) x j , i , G  otherwise  (4) u_{j, i, G}=\left\{\begin{array}{ll} v_{j, i, G} & \text { if }\left(\text {rand}_{i, j}[0,1] \leq \text {Cr or } j=j_{\text {rand}}\right) \\ x_{j, i, G} & \text { otherwise } \end{array}\right.\tag{4} uj,i,G​={vj,i,G​xj,i,G​​ if (randi,j​[0,1]≤Cr or j=jrand​) otherwise ​(4)
其中 rand i , j [ 0 , 1 ] \text {rand}_{i, j}[0,1] randi,j​[0,1]为均匀分布随机数，该值需要在第 i i i个参数向量的每个维度上都重新调用， j rand ∈ [ 1 , 2 , . . . , D ] j_{\text {rand}}\in [1,2,...,D] jrand​∈[1,2,...,D]为随机选择的索引，以保证 u u u中至少有一个元素取自 v v v，对于每一代中的米格向量，只需要实例化此值一次。

选择

为了保证种群大小不变，这一步叫做“选择”，以确定试验向量或目标向量是否存活到下一代，即
x ‾ i , G + 1 = u ‾  if  f ( u ‾ ) ≤ f ( x ‾ i , G ) = x ‾ i , G  if  f ( u ‾ ) > f ( x ‾ i , G ) (5) \begin{aligned} \underline{\mathrm{x}}_{i, G+1}&=\underline{\mathrm{u}} & \text { if } f\left(\underline{\mathrm{u}}\right) \leq f\left(\underline{\mathrm{x}}_{i, G}\right) \\ & =\underline{\mathrm{x}}_{i, G} & \text { if } f\left(\underline{\mathrm{u}}\right)>f\left(\underline{\mathrm{x}}_{i, G}\right) \end{aligned}\tag{5} x​i,G+1​​=u​=x​i,G​​ if f(u​)≤f(x​i,G​) if f(u​)>f(x​i,G​)​(5)

其中 f ( ) f() f()为待最小化的目标函数，因此新的试验向量产生了相等或更小的目标函数，则替换掉对应的目标向量，否则就保留目标向量至下一代。

算法伪代码

图3 算法伪代码

3、方案DE2

DE2和DE1思想基本一致，只不过在变异时稍有不同：

v ‾ = x ‾ i , G + λ ⋅ ( x ‾ best  , G − x ‾ i , G ) + F ⋅ ( x ‾ r 2 , G − x ‾ r 3 , G ) (6) \underline{\mathrm{v}}=\underline{\mathrm{x}}_{\mathrm{i}, \mathrm{G}}+\lambda \cdot\left(\underline{\mathrm{x}}_{\text {best }, \mathrm{G}}-\underline{\mathrm{x}}_{\mathrm{i}, \mathrm{G}}\right)+\mathrm{F} \cdot\left(\underline{\mathrm{x}}_{\mathrm{r}_{2}, \mathrm{G}}-\underline{\mathrm{x}}_{\mathrm{r}_{3}, \mathrm{G}}\right)\tag{6} v​=x​i,G​+λ⋅(x​best ,G​−x​i,G​)+F⋅(x​r2​,G​−x​r3​,G​)(6)
(6)中引入了一个额外的控制参数 λ \lambda λ，其思想是提供一种通过结合当前最优向量 x ‾ best  \underline{\mathrm{x}}_{\text {best }} x​best ​的方式，来增强该方案的贪婪性。图4说明了DE2的向量生成过程。

图4 DE2生成v的过程

4、 源代码

关注公众号后，回复“差分进化”或“DE”获取Matlab源码和Java源码链接。